22 |
22 |
23 \begin{document} |
23 \begin{document} |
24 |
24 |
25 \section*{Handout 5 (Grammars \& Parser)} |
25 \section*{Handout 5 (Grammars \& Parser)} |
26 |
26 |
27 While regular expressions are very useful for lexing and for recognising |
27 So far we have focused on regular expressions as well as matching and |
28 many patterns in strings (like email addresses), they have their |
28 lexing algorithms. While regular expressions are very useful for lexing |
29 limitations. For example there is no regular expression that can |
29 and for recognising many patterns in strings (like email addresses), |
30 recognise the language $a^nb^n$ (where you have strings starting with $n$ $a$'s |
30 they have their limitations. For example there is no regular expression |
31 followed by the same amount of $b$'s). Another example for which there |
31 that can recognise the language $a^nb^n$ (where you have strings |
32 exists no regular expression is the language of well-parenthesised |
32 starting with $n$ $a$'s followed by the same amount of $b$'s). Another |
33 expressions. In languages like Lisp, which use parentheses rather |
33 example for which there exists no regular expression is the language of |
34 extensively, it might be of interest to know whether the following two |
34 well-parenthesised expressions. In languages like Lisp, which use |
35 expressions are well-parenthesised or not (the left one is, the right |
35 parentheses rather extensively, it might be of interest to know whether |
36 one is not): |
36 the following two expressions are well-parenthesised or not (the left |
|
37 one is, the right one is not): |
37 |
38 |
38 \begin{center} |
39 \begin{center} |
39 $(((()()))())$ \hspace{10mm} $(((()()))()))$ |
40 $(((()()))())$ \hspace{10mm} $(((()()))()))$ |
40 \end{center} |
41 \end{center} |
41 |
42 |