14 |
14 |
15 \begin{enumerate} |
15 \begin{enumerate} |
16 \item Suppose the following grammar for the WHILE-language: |
16 \item Suppose the following grammar for the WHILE-language: |
17 |
17 |
18 \begin{center} |
18 \begin{center} |
19 \begin{tabular}{l} |
19 \begin{tabular}{lcl} |
20 $S \rightarrow N\cdot P$\\ |
20 $Stmt$ & $\rightarrow$ & $\text{skip}$\\ |
21 $P \rightarrow V\cdot N$\\ |
21 & $|$ & $Id := AExp$\\ |
22 $N \rightarrow N\cdot N$\\ |
22 & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\ |
23 $N \rightarrow A \cdot N$\\ |
23 & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\medskip\\ |
24 $N \rightarrow \texttt{student} \;|\; \texttt{trainer} \;|\; \texttt{team} \;|\; \texttt{trains}$\\ |
24 $Stmt$ & $\rightarrow$ & $Stmt \;\text{;}\; Stmts$\\ |
25 $V \rightarrow \texttt{trains} \;|\; \texttt{team}$\\ |
25 & $|$ & $Stmt$\medskip\\ |
26 $A \rightarrow \texttt{The} \;|\; \texttt{the}$\\ |
26 $Block$ & $\rightarrow$ & $\{ Stmts \}$\\ |
|
27 & $|$ & $Stmt$\medskip\\ |
|
28 $AExp$ & $\rightarrow$ & $AExp + AExp$\\ |
|
29 & $|$ & $AExp * AExp$\\ |
|
30 & $|$ & $( AExp )$\\ |
|
31 & $|$ & $Num$\\ |
|
32 & $|$ & $Id$\medskip\\ |
|
33 $BExp$ & $\rightarrow$ & $AExp = AExp$\\ |
|
34 & $|$ & $AExp \not= AExp$\\ |
|
35 & $|$ & $\text{false}$\\ |
|
36 & $|$ & $\text{true}$\\ |
|
37 |
27 \end{tabular} |
38 \end{tabular} |
28 \end{center} |
39 \end{center} |
29 |
40 |
|
41 Transform this grammar into Chomsky normalform. |
30 |
42 |
31 \item Consider the following grammar |
|
32 |
|
33 \begin{center} |
|
34 \begin{tabular}{l} |
|
35 $S \rightarrow N\cdot P$\\ |
|
36 $P \rightarrow V\cdot N$\\ |
|
37 $N \rightarrow N\cdot N$\\ |
|
38 $N \rightarrow A \cdot N$\\ |
|
39 $N \rightarrow \texttt{student} \;|\; \texttt{trainer} \;|\; \texttt{team} \;|\; \texttt{trains}$\\ |
|
40 $V \rightarrow \texttt{trains} \;|\; \texttt{team}$\\ |
|
41 $A \rightarrow \texttt{The} \;|\; \texttt{the}$\\ |
|
42 \end{tabular} |
|
43 \end{center} |
|
44 |
|
45 where $S$ is the start symbol and $S$, $P$, $N$, $V$ and $A$ are non-terminals. |
|
46 Using the CYK-algorithm, check whether or not the following string can be parsed |
|
47 by the grammar: |
|
48 |
|
49 \begin{center} |
|
50 \texttt{The trainer trains the student team} |
|
51 \end{center} |
|
52 |
|
53 \item {\bf (Optional)} The task is to match strings where the letters are in alphabetical order---for example, |
|
54 \texttt{abcfjz} would pass, but \texttt{acb} would not. Whitespace should be ignored---for example |
|
55 \texttt{ab c d} should pass. The point is to try to get the regular expression as short as possible! |
|
56 See: |
|
57 |
|
58 \begin{center} |
|
59 \url{http://callumacrae.github.com/regex-tuesday/challenge11.html} |
|
60 \end{center} |
|
61 \end{enumerate} |
43 \end{enumerate} |
62 |
44 |
63 \end{document} |
45 \end{document} |
64 |
46 |
65 %%% Local Variables: |
47 %%% Local Variables: |