equal
deleted
inserted
replaced
205 \[ |
205 \[ |
206 \textit{KEYWORD} < \textit{IDENT} < \textit{OP} < \ldots |
206 \textit{KEYWORD} < \textit{IDENT} < \textit{OP} < \ldots |
207 \] |
207 \] |
208 |
208 |
209 \noindent |
209 \noindent |
210 and so on. So even if both regular expressions match in the example above, |
210 So even if both regular expressions match in the example above, |
211 we can give the regular expression for \ref{Page ??} as follows |
211 we give preference to the regular expression for keywords. |
212 |
212 |
213 Let us see how our algorithm for lexing works in detail. The regular |
213 Let us see how our algorithm for lexing works in detail. The regular |
214 expressions and their ranking are shown above. For our algorithm it will |
214 expressions and their ranking are shown above. For our algorithm it will |
215 be helpful to have a look at the function \emph{zeroable} |
215 be helpful to have a look at the function \emph{zeroable} |
216 defined as follows: |
216 defined as follows: |
228 |
228 |
229 \noindent |
229 \noindent |
230 In contrast to the function $nullable(r)$, which test whether a regular expression |
230 In contrast to the function $nullable(r)$, which test whether a regular expression |
231 can match the empty string, the $zeroable$ function identifies whether a regular |
231 can match the empty string, the $zeroable$ function identifies whether a regular |
232 expression cannot match anything at all. The mathematical way of stating this |
232 expression cannot match anything at all. The mathematical way of stating this |
233 is |
233 property is |
234 |
234 |
235 \begin{center} |
235 \begin{center} |
236 $s \in zeroable(s)$ implies $L(r) = \varnothing$ |
236 $zeroable(r)$ if and only if $L(r) = \varnothing$ |
237 \end{center} |
237 \end{center} |
238 |
238 |
239 \noindent |
239 \noindent |
240 Let us fix a set of regular expressions $rs$. |
240 Let us fix a set of regular expressions $rs$. |
241 The crucial idea of the algorithm is to take the input string, say |
241 The crucial idea of the algorithm working with $rs$ and the string, say |
242 |
242 |
243 \begin{center} |
243 \begin{center} |
244 \texttt{\grid{$c_1$}\grid{$c_2$}\grid{$c_3$}\grid{$c_4$}\grid{\ldots}} |
244 \texttt{\grid{$c_1$}\grid{$c_2$}\grid{$c_3$}\grid{$c_4$}\grid{\ldots}} |
245 \end{center} |
245 \end{center} |
246 |
246 |
247 \noindent |
247 \noindent |
248 and build the derivative of all regular expressions in $rs$ with respect |
248 is to build the derivative of all regular expressions in $rs$ with respect |
249 to the first character $c_1$. Then we take the result and continue with $c_2$ |
249 to the first character $c_1$. Then we take the results and continue with |
|
250 building the derivatives with respect to $c_2$ |
250 until we have either exhausted our input string or all of the regular expressions |
251 until we have either exhausted our input string or all of the regular expressions |
251 are ``zeroable''. |
252 are ``zeroable''. |
252 |
253 |
253 \end{document} |
254 \end{document} |
254 |
255 |