equal
deleted
inserted
replaced
107 negation and back-references. |
107 negation and back-references. |
108 \end{abstract} |
108 \end{abstract} |
109 |
109 |
110 |
110 |
111 \section{Introduction} |
111 \section{Introduction} |
112 test |
|
113 While we believe derivatives of regular expressions, written |
112 While we believe derivatives of regular expressions, written |
114 $r\backslash s$, are a beautiful concept (in terms of ease of |
113 $r\backslash s$, are a beautiful concept (in terms of ease of |
115 implementing them in functional programming languages and in terms of |
114 implementing them in functional programming languages and in terms of |
116 reasoning about them formally), they have one major drawback: every |
115 reasoning about them formally), they have one major drawback: every |
117 derivative step can make regular expressions grow drastically in |
116 derivative step can make regular expressions grow drastically in |
122 the derivative is given as a tree. The reason for the poor runtime of |
121 the derivative is given as a tree. The reason for the poor runtime of |
123 the derivative-based lexing algorithms is that they need to traverse |
122 the derivative-based lexing algorithms is that they need to traverse |
124 such trees over and over again. The solution is to find a complete set |
123 such trees over and over again. The solution is to find a complete set |
125 of simplification rules that keep the sizes of derivatives uniformly |
124 of simplification rules that keep the sizes of derivatives uniformly |
126 small. |
125 small. |
|
126 |
|
127 This has been partially addressed by the function $\blexer_{simp}$, |
|
128 which after the simplification the $(a+aa)^*$ example's 8000 nodes will be |
|
129 reduced to just 6 and stays constant in each derivative step. |
|
130 The part that still needs more work is the correctness proof of this |
|
131 function, namely, |
|
132 \begin{equation}\label{mainthm} |
|
133 \blexers \; r \; s = \blexer \;r\;s |
|
134 \end{equation} |
|
135 |
|
136 \noindent |
|
137 and this is what this report is mainly about. A condensed |
|
138 version of the last report will be provided in the next section |
|
139 to help the reader understand the report, and the attempts |
|
140 on the problem will follow. |
127 |
141 |
128 |
142 |
129 \section{Recapitulation of Concepts From the Last Report} |
143 \section{Recapitulation of Concepts From the Last Report} |
130 |
144 |
131 \subsection*{Regular Expressions and Derivatives} |
145 \subsection*{Regular Expressions and Derivatives} |