55 |
55 |
56 (i) Give a grammar that can recognise such boolean expressions |
56 (i) Give a grammar that can recognise such boolean expressions |
57 and (ii) give a sample string involving all rules given in 1.-4.~that |
57 and (ii) give a sample string involving all rules given in 1.-4.~that |
58 can be parsed by this grammar. |
58 can be parsed by this grammar. |
59 |
59 |
60 \item Given the regular expressions |
|
61 |
60 |
62 \begin{center} |
|
63 \begin{tabular}{ll} |
|
64 1) & $(ab + a)\cdot (\ONE + b)$\\ |
|
65 2) & $(aa + a)^*$\\ |
|
66 \end{tabular} |
|
67 \end{center} |
|
68 |
|
69 there are several values for how these regular expressions can |
|
70 recognise the strings (for 1) $ab$ and (for 2) $aaa$. Give in each case |
|
71 \emph{all} the values and indicate which one is the POSIX value. |
|
72 |
|
73 \item Given the regular expression $(a + b)^* \cdot b \cdot (a + b)^*$, |
|
74 which of the following regular expressions are equyivalent |
|
75 |
|
76 \begin{center} |
|
77 \begin{tabular}{ll} |
|
78 1) & $(ab + bb)^* \cdot (a + b)^*$\\ % no |
|
79 2) & $(a + b)^* \cdot (ba + bb + b) \cdot (a + b)^*$\\ % yes |
|
80 3) & $(a + b)^* \cdot (a + b) \cdot (a + b)^*$ % no |
|
81 \end{tabular} |
|
82 \end{center} |
|
83 |
61 |
84 \item Parsing combinators consist of atomic parsers, alternative |
62 \item Parsing combinators consist of atomic parsers, alternative |
85 parsers, sequence parsers and semantic actions. What is the purpose |
63 parsers, sequence parsers and semantic actions. What is the purpose |
86 of (1) atomic parsers and of (2) semantic actions? |
64 of (1) atomic parsers and of (2) semantic actions? |
87 |
65 |
|
66 \item Parser combinators can directly be given a string as |
|
67 input, without the need of a lexer. What are the |
|
68 advantages to first lex a string and then feed a |
|
69 sequence of tokens as input to the parser? |
|
70 |
|
71 |
|
72 |
88 \item \POSTSCRIPT |
73 \item \POSTSCRIPT |
89 \end{enumerate} |
74 \end{enumerate} |
90 |
75 |
91 \end{document} |
76 \end{document} |
92 |
77 |