56 \begin{center} |
61 \begin{center} |
57 \begin{tabular}{ll} |
62 \begin{tabular}{ll} |
58 $r^+$ & (one or more matches)\\ |
63 $r^+$ & (one or more matches)\\ |
59 $r^?$ & (zero or one match)\\ |
64 $r^?$ & (zero or one match)\\ |
60 $r^{\{n\}}$ & (exactly $n$ matches)\\ |
65 $r^{\{n\}}$ & (exactly $n$ matches)\\ |
61 $r^{\{m, n\}}$ & (at least $m$ and maximal $n$ matches, with the\\ |
66 $r^{\{m.. n\}}$ & (at least $m$ and maximal $n$ matches, with the\\ |
62 & \phantom{(}assumption $m \le n$)\\ |
67 & \phantom{(}assumption $m \le n$)\\ |
63 \end{tabular} |
68 \end{tabular} |
64 \end{center} |
69 \end{center} |
65 |
70 |
66 in terms of the usual basic regular expressions |
71 in terms of the usual basic regular expressions |
67 |
72 |
68 \begin{center} |
73 \begin{center} |
69 $r ::= \ZERO \;|\; \ONE \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$ |
74 $r ::= \ZERO \;|\; \ONE \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$ |
70 \end{center} |
75 \end{center} |
|
76 |
|
77 \solution{ |
|
78 $r^+ \dn r\cdot r^*$\\ |
|
79 $r^? \dn r + 1$\\ |
|
80 $r^{\{0\}} = \ONE$\\ |
|
81 $r^{\{n\}} \dn r\cdot r^{\{n-1\}}$\\ |
|
82 $r^{\{..n\}} \dn (r^?)^{\{n\}}$\\ |
|
83 $r^{\{n..m\}} \dn r^{\{..m-n\}}\cdot r^{\{n\}}$\\ |
|
84 |
|
85 BTW, $r^{\{n..m\}}$ cannot be defined in terms of $r^{\{n..\}} \;\&\; r^{\{..m\}}$ where $\&$ is |
|
86 the intersection operator I introduced this year. For example assume $r=aaa + aaaaaaa$, then |
|
87 $r^{\{4..6\}}$ cannot match 21 a's, but $r^{\{4..\}} \;\&\; r^{\{..6\}}$. |
|
88 } |
|
89 |
71 |
90 |
72 \item Give the regular expressions for lexing a language |
91 \item Give the regular expressions for lexing a language |
73 consisting of identifiers, left-parenthesis \texttt{(}, |
92 consisting of identifiers, left-parenthesis \texttt{(}, |
74 right-parenthesis \texttt{)}, numbers that can be either |
93 right-parenthesis \texttt{)}, numbers that can be either |
75 positive or negative, and the operations \texttt{+}, |
94 positive or negative, and the operations \texttt{+}, |
85 \end{enumerate} |
104 \end{enumerate} |
86 |
105 |
87 In case they can, give the corresponding token sequences. (Hint: |
106 In case they can, give the corresponding token sequences. (Hint: |
88 Observe the maximal munch rule and the priorities of your regular |
107 Observe the maximal munch rule and the priorities of your regular |
89 expressions that make the process of lexing unambiguous.) |
108 expressions that make the process of lexing unambiguous.) |
|
109 |
|
110 \solution{ |
|
111 The first two strings can be lexed. But not the last ($/$ is not part of the language). |
|
112 } |
90 |
113 |
91 \item Suppose the following context-free grammar $G$ |
114 \item Suppose the following context-free grammar $G$ |
92 |
115 |
93 \begin{plstx}[margin=1cm] |
116 \begin{plstx}[margin=1cm] |
94 : \meta{S\/} ::= \meta{A\/}\cdot\meta{S\/}\cdot\meta{B\/} \;\mid\; |
117 : \meta{S\/} ::= \meta{A\/}\cdot\meta{S\/}\cdot\meta{B\/} \;\mid\; |
107 \item[$\bullet$] $ba$ |
130 \item[$\bullet$] $ba$ |
108 \item[$\bullet$] $bb$ |
131 \item[$\bullet$] $bb$ |
109 \item[$\bullet$] $baa$ |
132 \item[$\bullet$] $baa$ |
110 \end{itemize} |
133 \end{itemize} |
111 |
134 |
|
135 \solution{ |
|
136 The first and the last cannot be matched. Maybe it is a good exercise to |
|
137 write down the derivations for the rest. |
|
138 |
|
139 BTW, the language recognised by this grammar is strings consisting of |
|
140 a's and b's where there are equal or more number of b's than a's (including the |
|
141 empty string). |
|
142 } |
|
143 |
112 \item Suppose the following context-free grammar |
144 \item Suppose the following context-free grammar |
113 |
145 |
114 \begin{plstx}[margin=1cm] |
146 \begin{plstx}[margin=1cm] |
115 : \meta{S\/} ::= a\cdot \meta{S\/}\cdot a\;\mid\; |
147 : \meta{S\/} ::= a\cdot \meta{S\/}\cdot a\;\mid\; |
116 b\cdot \meta{S\/}\cdot b\;\mid\; \epsilon\\ |
148 b\cdot \meta{S\/}\cdot b\;\mid\; \epsilon\\ |
117 \end{plstx} |
149 \end{plstx} |
118 |
150 |
119 Describe which language is generated by this grammar. |
151 Describe which language is generated by this grammar. |
120 |
152 |
|
153 \solution{Palindromes with the same number of a's and b's, including |
|
154 the empty string} |
|
155 |
|
156 |
121 \item Remember we have specified identifiers with regular expressions as |
157 \item Remember we have specified identifiers with regular expressions as |
122 strings that start with a letter followed by letters, digits and |
158 strings that start with a letter followed by letters, digits and |
123 underscores. This can also be specified by a grammar rule or rules. |
159 underscores. This can also be specified by a grammar rule or rules. |
124 What would the rule(s) look like for identifiers? |
160 What would the rule(s) look like for identifiers? |
125 |
161 |