55 \end{center} |
54 \end{center} |
56 |
55 |
57 \noindent |
56 \noindent |
58 into Chomsky normal form. |
57 into Chomsky normal form. |
59 |
58 |
|
59 \item Consider the following grammar $G$ |
|
60 |
|
61 \begin{center} |
|
62 \begin{tabular}{l} |
|
63 $S \rightarrow \texttt{if0} \cdot E \cdot \texttt{then} \cdot S$\\ |
|
64 $S \rightarrow \texttt{print} \cdot S$\\ |
|
65 $S \rightarrow \texttt{begin} \cdot B\cdot \texttt{end}$\\ |
|
66 $B \rightarrow S\cdot \texttt{;}$\\ |
|
67 $B \rightarrow S\cdot \texttt{;} \cdot B$\\ |
|
68 $E \rightarrow num$ |
|
69 \end{tabular} |
|
70 \end{center} |
|
71 |
|
72 where $S$ is the start symbol and $S$, $E$ and $B$ are |
|
73 non-terminals. |
|
74 |
|
75 Check each rule below and decide whether, when added to $G$, |
|
76 the combined grammar is ambiguous. If yes, give a string that |
|
77 has more than one parse tree. |
|
78 |
|
79 \begin{center} |
|
80 \begin{tabular}{rl} |
|
81 (i) & $S \rightarrow \texttt{if0} \cdot E\cdot \texttt{then} \cdot S\cdot \texttt{else} \cdot S$\\ |
|
82 (ii) & $B \rightarrow B \cdot B$\\ |
|
83 (iii) & $E \rightarrow ( \cdot E \cdot )$\\ |
|
84 (iv) & $E \rightarrow E \cdot + \cdot E$ |
|
85 \end{tabular} |
|
86 \end{center} |
|
87 |
60 |
88 |
61 %\item {\bf (Optional)} The task is to match strings where the letters are in alphabetical order---for example, |
89 %\item {\bf (Optional)} The task is to match strings where the letters are in alphabetical order---for example, |
62 %\texttt{abcfjz} would pass, but \texttt{acb} would not. Whitespace should be ignored---for example |
90 %\texttt{abcfjz} would pass, but \texttt{acb} would not. Whitespace should be ignored---for example |
63 %\texttt{ab c d} should pass. The point is to try to get the regular expression as short as possible! |
91 %\texttt{ab c d} should pass. The point is to try to get the regular expression as short as possible! |
64 %See: |
92 %See: |