# HG changeset patch # User Christian Urban # Date 1729080853 -3600 # Node ID d8d8911a3d6f74a963eb316861cf20d7825c68f2 # Parent ce5de01b963272b0e787d9fadbd37bc9d662d9d9 updated diff -r ce5de01b9632 -r d8d8911a3d6f cws/cw01.pdf Binary file cws/cw01.pdf has changed diff -r ce5de01b9632 -r d8d8911a3d6f cws/cw02.pdf Binary file cws/cw02.pdf has changed diff -r ce5de01b9632 -r d8d8911a3d6f cws/cw02.tex --- a/cws/cw02.tex Fri Oct 11 19:13:00 2024 +0100 +++ b/cws/cw02.tex Wed Oct 16 13:14:13 2024 +0100 @@ -13,12 +13,20 @@ WHILE language. 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 need to submit your written answers as pdf---see attached -questionaire. Code send as code. If you use Scala in your code, a +awarded. %You need to submit your written answers as pdf---see attached +% questionaire. Code send as code. +If you use Scala in your code, a good place to start is the file \texttt{lexer.sc} and \texttt{token.sc} uploaded to KEATS. The template file on Github is -called \texttt{cw02.sc}. Your code needs to be uploaded to Github by -the deadline. +called \texttt{cw02.sc}. The example files are in the subdirectory +\texttt{examples}. The main function that will be tested is +called \texttt{tokenise}. The marks will be distributed such that +3 marks are given for the correct \texttt{WHILE\_REGS} regular +expression; 5 marks for the correct \texttt{inj} and \texttt{mkeps} +definitions; and two marks when \texttt{tokenise} produces the correct +results for the example files. + + \subsection*{Disclaimer\alert} @@ -140,9 +148,9 @@ this you need to implement the functions $nullable$ and $der$ (you can use your code from CW~1), as well as $mkeps$ and $inj$. These functions need to be appropriately extended for -the extended regular expressions from Q1. Write down in the -questionaire at the end the -clauses for +the extended regular expressions from Q1. The definitions +you need to create are: + \begin{center} \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} @@ -176,94 +184,99 @@ Also add the record regular expression from the -lectures to your lexer and implement a function, say -\pcode{env}, that returns all assignments from a value (such -that you can extract easily the tokens from a value).\medskip +lectures to your lexer and complete the function +\pcode{env} so that it returns all assignments from a value (this then +allows you to extract easily the tokens from a value in the next +question).\medskip \noindent -Finally give \textbf{all} the tokens for your regular expressions from Q1 and the -string +Finally make that the function \texttt{lexing\_simp} generates +with the regular expression from Q1 for the string \begin{center} \code{"read n;"} \end{center} \noindent -and use your \pcode{env} function to give the token sequence. +the following pairs: + +\begin{center} +\texttt{List((k,read), (w, ), (i,n), (s,;))} +\end{center} + + + \subsection*{Question 3} -Extend your lexer from Q2 to also simplify regular expressions after -each derivation step and rectify the computed values after each -injection. Use this lexer to tokenize six WHILE programs some of which -are given in Figures~\ref{fib} -- \ref{collatz}. You can find these programms also on -Github under the \texttt{cw2} directory. Give the tokens of these -programs where whitespaces and comments are -filtered out. Make sure you can tokenise \textbf{exactly} these -programs.\bigskip +Make sure your lexer from Q2 also simplifies regular expressions after +each derivation step and rectifies the computed values after each +injection. Use this lexer to tokenise the six WHILE programs +in the \texttt{examples} directory. Make sure that the \texttt{tokenise} +function filters out whitespaces and comments.\bigskip -\begin{figure}[h] -\mbox{\lstinputlisting[language=While,xleftmargin=10mm]{../cwtests/cw02/fib.while}} -\caption{Fibonacci program in the WHILE language.\label{fib}} -\end{figure} +% \begin{figure}[h] +% \mbox{\lstinputlisting[language=While,xleftmargin=10mm]{../cwtests/cw02/fib.while}} +% \caption{Fibonacci program in the WHILE language.\label{fib}} +% \end{figure} -\begin{figure}[h] -\mbox{\lstinputlisting[language=While,xleftmargin=10mm]{../cwtests/cw02/loops.while}} -\caption{The three-nested-loops program in the WHILE language. -(Usually used for timing measurements.)\label{loop}} -\end{figure} +% \begin{figure}[h] +% \mbox{\lstinputlisting[language=While,xleftmargin=10mm]{../cwtests/cw02/loops.while}} +% \caption{The three-nested-loops program in the WHILE language. +% (Usually used for timing measurements.)\label{loop}} +% \end{figure} -\begin{figure}[h] -\mbox{\lstinputlisting[language=While,xleftmargin=10mm]{../cwtests/cw02/factors.while}} -\caption{A program that calculates factors for numbers in the WHILE - language.\label{factors}} -\end{figure} +% \begin{figure}[h] +% \mbox{\lstinputlisting[language=While,xleftmargin=10mm]{../cwtests/cw02/factors.while}} +% \caption{A program that calculates factors for numbers in the WHILE +% language.\label{factors}} +% \end{figure} -\begin{figure}[h] -\mbox{\lstinputlisting[language=While,xleftmargin=10mm]{../cwtests/cw02/collatz2.while}} -\caption{A program that calculates the Collatz series for numbers - between 1 and 100.\label{collatz}} -\end{figure} +% \begin{figure}[h] +% \mbox{\lstinputlisting[language=While,xleftmargin=10mm]{../cwtests/cw02/collatz2.while}} +% \caption{A program that calculates the Collatz series for numbers +% between 1 and 100.\label{collatz}} +% \end{figure} -\clearpage -\newpage -\section*{Answers} +% \clearpage +% \newpage +% \section*{Answers} -\mbox{} +% \mbox{} -\noindent -\textbf{Question 2:}\\ (Use mathematical notation, such as $r^+$, rather than code, such as \code{PLUS(r)}) +% \noindent +% \textbf{Question 2:}\\ (Use mathematical notation, such as $r^+$, rather than code, such as \code{PLUS(r)}) -\begin{center} - \def\arraystretch{1.6} -\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} -$mkeps([c_1,c_2,\ldots,c_n])$ & $\dn$ & \uline{\hspace{8cm}}\\ -$mkeps(r^+)$ & $\dn$ & \uline{\hspace{8cm}}\\ -$mkeps(r^?)$ & $\dn$ & \uline{\hspace{8cm}}\\ -$mkeps(r^{\{n\}})$ & $\dn$ & \uline{\hspace{8cm}}\bigskip\\ -$inj\, ([c_1,c_2,\ldots,c_n])\,c\,\ldots$ & $\dn$ & \uline{\hspace{8cm}}\\ -$inj\, (r^+)\,c\,\ldots$ & $\dn$ & \uline{\hspace{8cm}}\\ -$inj\, (r^?)\,c\,\ldots$ & $\dn$ & \uline{\hspace{8cm}}\\ -$inj\, (r^{\{n\}})\,c\,\ldots$ & $\dn$ & \uline{\hspace{8cm}}\\ -\end{tabular} -\end{center}\bigskip +% \begin{center} +% \def\arraystretch{1.6} +% \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} +% $mkeps([c_1,c_2,\ldots,c_n])$ & $\dn$ & \uline{\hspace{8cm}}\\ +% $mkeps(r^+)$ & $\dn$ & \uline{\hspace{8cm}}\\ +% $mkeps(r^?)$ & $\dn$ & \uline{\hspace{8cm}}\\ +% $mkeps(r^{\{n\}})$ & $\dn$ & \uline{\hspace{8cm}}\bigskip\\ +% $inj\, ([c_1,c_2,\ldots,c_n])\,c\,\ldots$ & $\dn$ & \uline{\hspace{8cm}}\\ +% $inj\, (r^+)\,c\,\ldots$ & $\dn$ & \uline{\hspace{8cm}}\\ +% $inj\, (r^?)\,c\,\ldots$ & $\dn$ & \uline{\hspace{8cm}}\\ +% $inj\, (r^{\{n\}})\,c\,\ldots$ & $\dn$ & \uline{\hspace{8cm}}\\ +% \end{tabular} +% \end{center}\bigskip -\noindent -Tokens for \code{"read n;"}\\ +% \noindent +% Tokens for \code{"read n;"}\\ -\noindent -\uline{\hfill}\medskip +% \noindent +% \uline{\hfill}\medskip -\noindent -\uline{\hfill}\medskip +% \noindent +% \uline{\hfill}\medskip -\noindent -\uline{\hfill}\medskip +% \noindent +% \uline{\hfill}\medskip -\noindent -\uline{\hfill}\medskip +% \noindent +% \uline{\hfill}\medskip \end{document} diff -r ce5de01b9632 -r d8d8911a3d6f cws/cw03.pdf Binary file cws/cw03.pdf has changed 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} diff -r ce5de01b9632 -r d8d8911a3d6f cws/cw04.pdf Binary file cws/cw04.pdf has changed diff -r ce5de01b9632 -r d8d8911a3d6f cws/cw05.pdf Binary file cws/cw05.pdf has changed diff -r ce5de01b9632 -r d8d8911a3d6f progs/matcher/cw1.sc --- a/progs/matcher/cw1.sc Fri Oct 11 19:13:00 2024 +0100 +++ b/progs/matcher/cw1.sc Wed Oct 16 13:14:13 2024 +0100 @@ -122,6 +122,7 @@ extension (r: Rexp) { def ~ (s: Rexp) = SEQ(r, s) def % = STAR(r) + def | (s: Rexp) = ALT(r, s) } diff -r ce5de01b9632 -r d8d8911a3d6f style.sty --- a/style.sty Fri Oct 11 19:13:00 2024 +0100 +++ b/style.sty Wed Oct 16 13:14:13 2024 +0100 @@ -91,11 +91,17 @@ % CW deadlines -\def\cwONE{16 October} -\def\cwTWO{10 November} -\def\cwTHREE{27 November} -\def\cwFOUR{14 December} -\def\cwFIVE{12 January} +%\def\cwONE{16 October} +%\def\cwTWO{10 November} +%\def\cwTHREE{27 November} +%\def\cwFOUR{14 December} +%\def\cwFIVE{12 January} + +\def\cwONE{2nd January} +\def\cwTWO{2nd January} +\def\cwTHREE{2nd January} +\def\cwFOUR{2nd January} +\def\cwFIVE{2nd January} %%\def\cwISABELLE{11 December}