equal
deleted
inserted
replaced
1 \documentclass{article} |
1 \documentclass{article} |
2 \usepackage{../style} |
2 \usepackage{../style} |
3 \usepackage{../graphics} |
3 \usepackage{../graphics} |
4 \usepackage{../langs} |
4 \usepackage{../langs} |
|
5 \usepackage{../grammar} |
5 |
6 |
6 \begin{document} |
7 \begin{document} |
7 |
8 |
8 \section*{Homework 9} |
9 \section*{Homework 9} |
9 |
10 |
90 %6 = add i32 %5, %4 |
91 %6 = add i32 %5, %4 |
91 ret i32 %6 |
92 ret i32 %6 |
92 } |
93 } |
93 \end{lstlisting} |
94 \end{lstlisting} |
94 |
95 |
|
96 \item As an optimisation technique, a compiler might want to detect `dead code' and |
|
97 not generate anything for this code. Why does this optimisation technique have the |
|
98 potential of speeding up the run-time of a program? (Hint: On what CPUs are programs |
|
99 run nowadays?) |
|
100 |
|
101 \item In an earlier question, we analysed the advantages of having a lexer-phase |
|
102 before running the parser (having a lexer is definitely a good thing to have). But you |
|
103 might wonder if a lexer can also be implemented by a parser and some simple |
|
104 grammar rules. Consider for example: |
|
105 |
|
106 \begin{plstx}[margin=1cm] |
|
107 : \meta{S\/} ::= (\meta{Kw\/}\mid \meta{Id\/}\mid \meta{Ws\/}) \cdot \meta{S\/} \;\mid\; \epsilon\\ |
|
108 : \meta{Kw\/} ::= \texttt{if} \mid \texttt{then} \mid \ldots\\ |
|
109 : \meta{Id\/} ::= (\texttt{a} \mid\ldots\mid \texttt{z}) \cdot \meta{Id\/} \;\mid\; \epsilon\\ |
|
110 : \meta{Ws\/} ::= \ldots\\ |
|
111 \end{plstx} |
|
112 |
|
113 What is wrong with implementing a lexer in this way? |
|
114 |
95 \item What is the difference between a parse tree and an abstract |
115 \item What is the difference between a parse tree and an abstract |
96 syntax tree? Give some simple examples for each of them. |
116 syntax tree? Give some simple examples for each of them. |
97 |
117 |
98 |
118 |
99 \item Give a description of how the Brzozowski matcher works. |
119 \item Give a description of how the Brzozowski matcher works. |