116 b\cdot \meta{S\/}\cdot b\;\mid\; \epsilon\\ |
116 b\cdot \meta{S\/}\cdot b\;\mid\; \epsilon\\ |
117 \end{plstx} |
117 \end{plstx} |
118 |
118 |
119 Describe which language is generated by this grammar. |
119 Describe which language is generated by this grammar. |
120 |
120 |
|
121 \item Remember we have specified identifiers with regular expressions as |
|
122 strings that start with a letter followed by letters, digits and |
|
123 underscores. This can also be specified by a grammar rule or rules. |
|
124 What would the rule(s) look like for identifiers? |
121 |
125 |
|
126 \solution{ |
|
127 \begin{plstx}[margin=1cm] |
|
128 : \meta{Id\/} ::= \meta{Let\/}\cdot \meta{R}\\ |
|
129 : \meta{Let\/} ::= a \;\mid\; \dots \;\mid\; z\\ |
|
130 : \meta{Dig\/} ::= 0 \;\mid\; \dots \;\mid\; 9\\ |
|
131 : \meta{R\/} ::= \meta{Let\/} \cdot \meta{R\/} \;\mid\; |
|
132 \meta{Dig\/} \cdot \meta{R\/} \;\mid\; |
|
133 $\_$ \cdot \meta{R\/} \;\mid\; \epsilon\\ |
|
134 \end{plstx} |
|
135 } |
|
136 |
|
137 \item If we specify keywords, identifiers (see above) and programs |
|
138 by grammar rules, are there any problems you need to be careful |
|
139 about when using a parser for identifying tokens? |
|
140 |
|
141 \solution{Parsers do not have the POSIX rules (e.g.~longest munch |
|
142 rule) built in. I am not aware that any parser does this out of |
|
143 the box and you would need to build in such constraints into the |
|
144 grammar rules or parsing mechanism.} |
122 |
145 |
123 \item {\bf(Optional)} Recall the definitions for $Der$ and $der$ |
146 \item {\bf(Optional)} Recall the definitions for $Der$ and $der$ |
124 from the lectures. Prove by induction on $r$ the |
147 from the lectures. Prove by induction on $r$ the |
125 property that |
148 property that |
126 |
149 |