In these exercises, you will

• implement a lexical analyser using lex (Problems 2, 4);

• implement parsers using lex and yacc (Problems 1, 3–6);

• program a Turing machine (Problem 7);

• learn about quaternions, by applying our methods to calculations with them (Problems 3–6);

• practise your skills relating to context-free languages (Problem 8).

Solutions to Problem 7 must be implemented in the simulator Tuatara. We are providing version 2.1 on Moodle under week 8; the file name is tuatara-monash-2 .1 .jar. You must use exactly this version, not some other version downloaded from the internet. Do not unpack this file. It must be run directly using the Java runtime.

How to manage this assignment

• You should start working on this assignment now and spread the work over the time until it is due. Do as much as possible before week 10. There will not be time during your prac class to do the assignment from scratch; there will only be time to get some help and clarification.

• Don’t be deterred by the length of this document!  Much of it is an extended tutorial to get you started with lex and yacc (pp. 7–11) and documentation for functions, written in C, that are provided for you to use (pp. 12–14); some sample outputs also take up a fair bit of space. Although lex and yacc are new to you, the questions about them only require you to modify some existing input files for them rather than write your own input files from scratch.

• The tasks required for the assignment are on pp. 3–6.           For Problem 1–5, read the background material on pp. 7–11.

For Problems 2–6, also read the background material on pp. 12–14.

For Problems 7–8, read the background material on p. 15.

Instructions

Instructions are as for Assignment 1, except that some of the filenames have changed.  To begin working on the assignment, download the workbench asgn2 .zip from Moodle.  Create a new Ed Workspace and upload this file, letting Ed automatically extract it.  Edit the student-id file to contain your name and student ID. Refer to Lab 0 for a reminder on how to do these tasks.

Open a terminal and change into the directory asgn2.  You will find three files already in the directory: plus-times-power .l, plus-times-power .y, and quat .h. You will not modify these files directly; you will make copies of the first two and modify the copies, while quat .h must remain unaltered in the directory where you do this work.

You need to construct new lex files, using plus-times-power .l as a starting point, for Problems 1, 4 & 5, and you’ll need to construct a new yacc file from plus-times-power .y for Problem 5. Your submission must include:

• a lex file prob1 .l which should be obtained by modifying a copy of plus-times-power .l

• a te北t file prob2 .txt which should contain a single line with a regular expression in lex syntax

• a PDF file prob3 .pdf which should contain your solution to Problem 3

• a lex file prob4 .l which should also be obtained by modifying a copy of plus-times-power .l

• a lex file prob5 .l which should be obtained by modifying a copy of prob4 .l

• a yacc file prob5 .y which should be obtained by modifying a copy of plus-times-power .y

• a te北t file prob6 .txt which should contain two lines, being your solution to Problem 6

• a Tuatara Turing machine file prob7 .tm

• a PDF file prob8 .pdf which should contain your solution to Problem 8.

Each of the problem directories under the asgn2 directory contains empty files with the required filenames. These must each be replaced by the files you write, as described above. Before submission, check that each of these empty files is, indeed, replaced by your own file.

To submit your work, download the Ed workspace as a zip file by clicking on “Download All” in the file manager panel. The “Download All” option preserves the directory structure of the zip file, which is required to aid the marking process. You must submit this zip file to Moodle by the deadline given above.

Assignment tasks

For each problem, the files you are submitting must be in the corresponding subdirectory,  i.e. problemx for Problem x.

First, read about “Lex, Yacc and the PLUS-TIMES-POWER language” on pp. 7–11.

Now refer to the document “Quaternions and the language QUAT”, pages 12–14.

Now we use regular expressions (in the lex file, prob4 .l) and a grammar (in the yacc file, prob5 .y) to construct a lexical analyser (Problem 4) and a parser (Problem 5) for QUAT.

Sample output:

$  ./a .out

Rotation(120 .0,2 .0i+2 .0j+2 .0k)^2  *  i  /  Rotation(120 .0,2 .0i+2 .0j+2 .0k)^2

Token:  ROTATION;    Lexeme:  Rotation

Token  and  Lexeme:  (

Token:  NUMBER;    Lexeme:  120 .0

Token  and  Lexeme:  ,

Token:  NUMBER;    Lexeme:  2 .0

Token  and  Lexeme:  i

Token  and  Lexeme:  +

Token:  NUMBER;    Lexeme:  2 .0

Token  and  Lexeme:  j

Token  and  Lexeme:  +

Token:  NUMBER;    Lexeme:  2 .0

Token  and  Lexeme:  k

Token  and  Lexeme:  )

Token  and  Lexeme:  ^

Token:  WHOLENUMBER;    Lexeme:  2

Token  and  Lexeme:  *

Token  and  Lexeme:  i

Token  and  Lexeme:  /

Token:  ROTATION;    Lexeme:  Rotation

Token  and  Lexeme:  (

Token:  NUMBER;    Lexeme:  120 .0

Token  and  Lexeme:  ,

Token:  NUMBER;    Lexeme:  2 .0

Token  and  Lexeme:  i

Token  and  Lexeme:  +

Token:  NUMBER;    Lexeme:  2 .0

Token  and  Lexeme:  j

Token  and  Lexeme:  +

Token:  NUMBER;    Lexeme:  2 .0

Token  and  Lexeme:  k

Token  and  Lexeme:  )

Token  and  Lexeme:  ^

Token:  WHOLENUMBER;    Lexeme:  2

Token  and  Lexeme:  

Control-D