91 $r^{\{n\}}$ & n-times $r$\\ |
91 $r^{\{n\}}$ & n-times $r$\\ |
92 \end{tabular} |
92 \end{tabular} |
93 \end{center} |
93 \end{center} |
94 |
94 |
95 \noindent |
95 \noindent |
|
96 Try to design regular expressions to be as small as possible. |
96 |
97 |
97 \subsection*{Question 2 (marked with 3\%)} |
98 \subsection*{Question 2 (marked with 3\%)} |
98 |
99 |
99 Implement the Sulzmann \& Lu tokeniser from the lectures. For |
100 Implement the Sulzmann \& Lu tokeniser from the lectures. For |
100 this you need to implement the functions $nullable$ and $der$ |
101 this you need to implement the functions $nullable$ and $der$ |
101 (you can use your code from CW 1), as well as $mkeps$ and |
102 (you can use your code from CW~1), as well as $mkeps$ and |
102 $inj$. These functions need to be appropriately extended for |
103 $inj$. These functions need to be appropriately extended for |
103 the extended regular expressions from Q1. Also add the record |
104 the extended regular expressions from Q1. Write down the |
104 regular expression from the lectures and implement a function, |
105 clauses for |
105 say \pcode{env}, that returns all assignments from a value |
|
106 (such that you can extract easily the tokens from a value). |
|
107 |
106 |
108 The functions $mkeps$ and $inj$ return values. Calculate the |
107 \begin{center} |
109 value for your regular expressions from Q1 and the string |
108 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
|
109 $mkeps([c_1 c_2 \ldots c_n])$ & $\dn$ & $?$\\ |
|
110 $mkeps(r^+)$ & $\dn$ & $?$\\ |
|
111 $mkeps(r^?)$ & $\dn$ & $?$\\ |
|
112 $mkeps(r^{\{n\}})$ & $\dn$ & $?$\medskip\\ |
|
113 $inj\, ([c_1 c_2 \ldots c_n])\,c\,\ldots$ & $\dn$ & $?$\\ |
|
114 $inj\, (r^+)\,c\,\ldots$ & $\dn$ & $?$\\ |
|
115 $inj\, (r^?)\,c\,\ldots$ & $\dn$ & $?$\\ |
|
116 $inj\, (r^{\{n\}})\,c\,\ldots$ & $\dn$ & $?$\\ |
|
117 \end{tabular} |
|
118 \end{center} |
|
119 |
|
120 \noindent where $inj$ takes three arguments: a regular |
|
121 expression, a character and a value. Also add the record |
|
122 regular expression from the lectures to your tokeniser and |
|
123 implement a function, say \pcode{env}, that returns all |
|
124 assignments from a value (such that you can extract easily the |
|
125 tokens from a value).\medskip |
|
126 |
|
127 \noindent |
|
128 Fiannly give the tokens for your regular expressions from Q1 and the |
|
129 string |
110 |
130 |
111 \begin{center} |
131 \begin{center} |
112 \code{"read n;"} |
132 \code{"read n;"} |
113 \end{center} |
133 \end{center} |
114 |
134 |