15 also an interpreter. The parser needs to use parser combinators. You |
15 also an interpreter. The parser needs to use parser combinators. You |
16 can do the implementation in any programming language you like, but |
16 can do the implementation in any programming language you like, but |
17 you need to submit the source code with which you answered the |
17 you need to submit the source code with which you answered the |
18 questions, otherwise a mark of 0\% will be awarded. If you use Scala |
18 questions, otherwise a mark of 0\% will be awarded. If you use Scala |
19 in your code, a good place to start is the file \texttt{comb1.sc} and |
19 in your code, a good place to start is the file \texttt{comb1.sc} and |
20 \texttt{comb2.sc} uploaded to KEATS. Feel free to use the ``hack'' |
20 \texttt{comb2.sc} uploaded to KEATS. Make sure your parser combinators |
|
21 process list of tokens as input, not strings. Feel free to use the ``hack'' |
21 explained during the lectures. This might make your grammar |
22 explained during the lectures. This might make your grammar |
22 simpler. However, make sure you understand the code involved in the |
23 simpler. However, make sure you understand the code involved in the |
23 ``hack'' because if you just do ``mix-and-match'' you will receive |
24 ``hack'' because if you just do ``mix-and-match'' you will receive |
24 strange errors. The main function that will be tested is called |
25 strange errors. The main function that will be tested is called |
25 \texttt{eval} and \texttt{Stmts.parse\_all}. The latter expects a list |
26 \texttt{eval} and \texttt{Stmts.parse\_all}. The latter expects a list |
26 of tokens as input and generates an AST. The former expects an AST and |
27 of tokens as input and generates an AST. The former expects an AST and |
27 ``runs'' the program. The marks will be distributed such that 6 marks |
28 ``runs'' the program. The marks will be distributed such that 6 marks |
28 are given for the correct grammar (and parsers); 4 marks for the correct |
29 are given for the correct grammar (and parsers); 4 marks for the correct |
29 \texttt{eval} function. You should use the lexer from CW2 for the |
30 \texttt{eval} function. You should use the lexer from CW2 for the |
30 parser - you potentially need to make additions for CW2. |
31 parser - you potentially need to make additions for CW3. |
31 |
32 |
32 \subsection*{Disclaimer\alert} |
33 \subsection*{Disclaimer\alert} |
33 |
34 |
34 It should be understood that the work you submit represents your own |
35 It should be understood that the work you submit represents your own |
35 effort. You have not copied from anyone else. An exception is the |
36 effort. You have not copied from anyone else. An exception is the |
36 Scala code I showed during the lectures or uploaded to KEATS, which |
37 Scala code I showed during the lectures or uploaded to KEATS, which |
37 you can both use. You can also use your own code from the CW~1 and |
38 you can both use. You can also use your own code from the CW~1 and |
38 CW~2. But do not |
39 CW~2. |
39 be tempted to ask Github Copilot for help or do any other |
40 %But do not |
40 shenanigans like this! |
41 %be tempted to ask Github Copilot for help or do any other |
41 |
42 %shenanigans like this! |
42 \subsection*{Syntax Error in Template File cw03.sc\alert} |
43 |
43 |
44 %\subsection*{Syntax Error in Template File cw03.sc\alert} |
44 Apologies, there is a small syntax error in the template file where a variable |
45 % |
45 needs to be called \texttt{tks} instead of \texttt{tk}. The code |
46 %Apologies, there is a small syntax error in the template file where a variable |
46 in question is at the end of \texttt{cw03.sc} and should be like |
47 %needs to be called \texttt{tks} instead of \texttt{tk}. The code |
47 this (see lines 5, 6 and 8): |
48 %in question is at the end of \texttt{cw03.sc} and should be like |
48 |
49 %this (see lines 5, 6 and 8): |
49 \begin{lstlisting}[language=Scala,numbers=left] |
50 % |
50 @main |
51 %\begin{lstlisting}[language=Scala,numbers=left] |
51 def test(file: String) = { |
52 %@main |
52 val contents = os.read(os.pwd / "examples" / file) |
53 %def test(file: String) = { |
53 println(s"Lex $file: ") |
54 % val contents = os.read(os.pwd / "examples" / file) |
54 val tks = tokenise(contents) |
55 % println(s"Lex $file: ") |
55 println(tks.mkString(",")) |
56 % val tks = tokenise(contents) |
56 println(s"Parse $file: ") |
57 % println(tks.mkString(",")) |
57 val ast = Stmts.parse_all(tks).head |
58 % println(s"Parse $file: ") |
58 println(ast) |
59 % val ast = Stmts.parse_all(tks).head |
59 println(s"Eval $file: ") |
60 % println(ast) |
60 println(eval(ast)) |
61 % println(s"Eval $file: ") |
61 } |
62 % println(eval(ast)) |
62 \end{lstlisting} |
63 %} |
63 |
64 %\end{lstlisting} |
64 |
65 |
65 |
66 |
66 \subsection*{Question 1} |
67 |
|
68 \subsection*{Task 1} |
67 |
69 |
68 Design a grammar for the WHILE language and give the grammar |
70 Design a grammar for the WHILE language and give the grammar |
69 rules. The main categories of non-terminals should be: |
71 rules. The main categories of non-terminals should be: |
70 |
72 |
71 \begin{itemize} |
73 \begin{itemize} |
123 // logical operations: and, or |
125 // logical operations: and, or |
124 \end{lstlisting} |
126 \end{lstlisting} |
125 \caption{The datatype for abstract syntax trees in Scala.\label{trees}} |
127 \caption{The datatype for abstract syntax trees in Scala.\label{trees}} |
126 \end{figure} |
128 \end{figure} |
127 |
129 |
128 \subsection*{Question 3} |
130 \subsection*{Task 3} |
|
131 |
|
132 In addition to the simple assignments of the form \code{... := ...} |
|
133 from Task 1, parse the assignments of the form |
|
134 |
|
135 \begin{quote} |
|
136 \texttt{... += ...} \;\;and\;\; \texttt{... *= ...} |
|
137 \end{quote} |
|
138 |
|
139 and translate them into simple assignments. For example |
|
140 |
|
141 \begin{quote} |
|
142 \texttt{cnt += 1} |
|
143 \end{quote} |
|
144 |
|
145 should give the assignment \texttt{cnt := cnt + 1}. Similarly |
|
146 for \texttt{*=}. |
|
147 |
|
148 \subsection*{Task 4} |
129 |
149 |
130 Implement an interpreter for the WHILE language you designed |
150 Implement an interpreter for the WHILE language you designed |
131 and parsed in Question 1 and 2. This interpreter should take |
151 and parsed in Tasks 1 and 2. This interpreter should take |
132 as input an AST. However be careful because, programs |
152 as input an AST. However be careful because, programs |
133 contain variables and variable assignments. This means |
153 contain variables and variable assignments. This means |
134 you need to maintain a kind of memory, or environment, |
154 you need to maintain a kind of memory, or environment, |
135 where you can look up a value of a variable and also |
155 where you can look up a value of a variable and also |
136 store a new value if it is assigned. Therefore an |
156 store a new value if it is assigned. Therefore an |
154 according to straightforward rules: for example an |
174 according to straightforward rules: for example an |
155 if-statement will ``run'' the if-branch if the boolean |
175 if-statement will ``run'' the if-branch if the boolean |
156 evaluates to \pcode{true}, otherwise the else-branch. |
176 evaluates to \pcode{true}, otherwise the else-branch. |
157 Loops should be run as long as the boolean is \pcode{true}. |
177 Loops should be run as long as the boolean is \pcode{true}. |
158 Note also that some programs contain a read-statement, |
178 Note also that some programs contain a read-statement, |
159 which means you need to read and integer from the commandline |
179 which means you need to read an integer from the commandline |
160 and store the value in the corresponding variable. |
180 and store the value in the corresponding variable. |
161 Programs you should be able to run are given in the |
181 Programs you should be able to run are given in the |
162 \texttt{examples} directory. The output |
182 \texttt{examples} directory. The output |
163 of the \texttt{primes.while} should look as follows: |
183 of the \texttt{primes.while} should look as follows: |
164 |
184 |