diff -r ce5de01b9632 -r d8d8911a3d6f cws/cw03.tex --- a/cws/cw03.tex Fri Oct 11 19:13:00 2024 +0100 +++ b/cws/cw03.tex Wed Oct 16 13:14:13 2024 +0100 @@ -12,12 +12,22 @@ \noindent This coursework is worth 10\% and is due on \cwTHREE{} at 16:00. You are asked to implement a parser for the WHILE language and -also an interpreter. The parser needs to use parser combinators. -You can do the implementation in any programming -language you like, but you need to submit the source code with which -you answered the questions, otherwise a mark of 0\% will be -awarded. You should use the lexer from the previous coursework for the -parser. Please submit your code to Github by the deadline. +also an interpreter. The parser needs to use parser combinators. You +can do the implementation in any programming language you like, but +you need to submit the source code with which you answered the +questions, otherwise a mark of 0\% will be awarded. If you use Scala +in your code, a good place to start is the file \texttt{comb1.sc} and +\texttt{comb2.sc} uploaded to KEATS. Feel free to use the ``hack'' +explained during the lectures. This might make your grammar +simpler. However, make sure you understand the code involved in the +``hack'' because if you just do ``mix-and-match'' you will receive +strange errors. The main function that will be tested is called +\texttt{eval} and \texttt{Stmts.parse\_all}. The latter expects a list +of tokens as input and generates an AST. The former expects an AST and +``runs'' the program. The marks will be distributed such that 6 marks +are given for the correct grammar (and parsers); 4 marks for the correct +\texttt{eval} function. You should use the lexer from CW2 for the +parser - you potentially need to make additions for CW2. \subsection*{Disclaimer\alert} @@ -29,6 +39,29 @@ be tempted to ask Github Copilot for help or do any other shenanigans like this! +\subsection*{Syntax Error in Template File cw03.sc\alert} + +Apologies, there is a small syntax error in the template file where a variable +needs to be called \texttt{tks} instead of \texttt{tk}. The code +in question is at the end of \texttt{cw03.sc} and should be like +this (see lines 5, 6 and 8): + +\begin{lstlisting}[language=Scala,numbers=left] +@main +def test(file: String) = { + val contents = os.read(os.pwd / "examples" / file) + println(s"Lex $file: ") + val tks = tokenise(contents) + println(tks.mkString(",")) + println(s"Parse $file: ") + val ast = Stmts.parse_all(tks).head + println(ast) + println(s"Eval $file: ") + println(eval(ast)) +} +\end{lstlisting} + + \subsection*{Question 1} @@ -54,21 +87,13 @@ \subsection*{Question 2} You should implement a parser for the WHILE language using parser -combinators. Be careful that the parser takes as input a stream, or -list, of \emph{tokens} generated by the tokenizer from the previous +combinators. Be careful that the parser takes as input a list of +\emph{tokens} generated by the tokenizer from the previous coursework. For this you might want to filter out whitespaces and comments. Your parser should be able to handle the WHILE programs in -Figures~\ref{fib} -- \ref{collatz}. In addition give the -parse tree according to your grammar for the statement: - -\begin{lstlisting}[language=While,numbers=none] -if (a < b) then skip else a := a * b + 1 -\end{lstlisting} - -\noindent -The output of the parser is an abstract syntax tree (AST). -A (possibly incomplete) datatype for ASTs of the WHILE language -is shown in Figure~\ref{trees}. +the \texttt{examples} directory. The output of the parser is an +abstract syntax tree (AST). A (possibly incomplete) datatype for ASTs +of the WHILE language is shown in Figure~\ref{trees}. \begin{figure}[p] \begin{lstlisting}[language=Scala] @@ -133,8 +158,8 @@ Note also that some programs contain a read-statement, which means you need to read and integer from the commandline and store the value in the corresponding variable. -Programs you should be able to run are shown in -Figures \ref{fib} -- \ref{collatz}. The output +Programs you should be able to run are given in the +\texttt{examples} directory. The output of the \texttt{primes.while} should look as follows: \begin{figure}[h] @@ -170,79 +195,6 @@ \caption{Sample output for the file \texttt{primes.while}.\label{fib}} \end{figure} -\noindent -Give some time measurements for your interpreter -and the loop program in Figure~\ref{loop}. For example -how long does your interpreter take when \pcode{start} -is initialised with 100, 500 and so on. How far can -you scale this value if you are willing to wait, say -1 Minute? - -\clearpage - -\begin{figure}[h] -\lstinputlisting[language=while,xleftmargin=20mm]{../cwtests/cw03/fib.while} -\caption{Fibonacci program in the WHILE language.\label{fib}} -\end{figure} - -\begin{figure}[h] -\lstinputlisting[language=while,xleftmargin=20mm]{../cwtests/cw03/loops.while} -\caption{The three-nested-loops program in the WHILE language. -Usually used for timing measurements.\label{loop}} -\end{figure} - -\begin{figure}[h] -\lstinputlisting[language=while,xleftmargin=0mm]{../cwtests/cw03/primes.while} -\caption{Prime number program.\label{primes}} -\end{figure} - - -\begin{figure}[p] -\lstinputlisting[language=while,xleftmargin=0mm]{../cwtests/cw03/collatz2.while} -\caption{Collatz series program.\label{collatz}} -\end{figure} - -\clearpage -\newpage -\section*{Answers} - -\mbox{} - -\noindent -\textbf{Name:}\uline{\hfill}\bigskip - - - -\noindent -\textbf{Question 1 (Grammar):}\\ - -\mbox{}\\[9cm] - -\newpage -\noindent -\textbf{Question 2 (Parse Tree):}\\ - -\mbox{}\\[8cm] - - -\noindent -\textbf{Question 3 (Timings):}\\ - -\begin{center} - \def\arraystretch{1.5} - \begin{tabular}{l|l} - n & secs\\ - \hline - 100 & \\ - 500 & \\ - 700 & \\ - 1000 & \\ - \\ - \\ - \\ - \\ - \end{tabular} -\end{center} \end{document}