In these exercises, you will

.  implement a lexical analyser using lex (Problem 3);

.  implement parsers using lex and yacc (Problems 1–6);

. program a Turing machine (Problem 7);

.  learn about some aspects of quantum circuits and quantum registers, by applying our methods to calculations with them (Problems 2–7);

. 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.

.  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–17); some matrices and sample outputs also take up a fair bit of space.  There is an optional three-page introduction to  some  of the basics of quantum computing (pp. 17–19), which is there for those who are interested in knowing more but is not required for this assignment.  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 Problems 1–5, read the background material on pp. 7–11.

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

For Problem 7, read the background material on p. 21.

For Problem 8, read the background material on p. 22.

Instructions

Instructions are mostly as for Assignment 1, except that some of the filenames have changed, and now each Problem has its own directory. 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 quant.h.  You will not modify these files directly;  you will make copies of the first two and modify the copies, while  quant.h must remain unaltered (although it’s ok to have copies of it in other directories).

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

. the file  student-id, edited to contain your name and student ID

.  a lex file prob1.l which should be obtained by modifying a copy of plus-times-power.l .  a PDF file prob2.pdf which should contain your solution to Problem 2

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

.  a yacc file prob4.y which should be obtained by modifying a copy of plus-times-power.y .  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 prob4.y

.  a text file prob6.txt which should contain ten 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.

The original directory structure and file locations must be preserved.  For each problem, the files you are submitting must be in the corresponding subdirectory, i.e. problemx for Problem x.

Each of these problem subdirectories 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

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

Now refer to the document “Quantum circuits, registers and the language QUANT”, pages12–17. In fact, for Problem 2, you can focus just on pages 15–17 and the language QCIRC.

Now we use some very basic regular expressions (in the lex file, prob3.l) and a CFG (in the yacc file, prob4.y) to construct a lexical analyser (Problem 3) and a parser (Problem 4) for QCIRC.

Sample output:

$  ./a.out

CNOT*  (  H  (x)I)

Token:  CNOT;    Lexeme:  CNOT

Token  and  Lexeme:  *

Token  and  Lexeme:  (

Token:  H;    Lexeme:  H

Token:  KRONECKERPROD;    Lexeme:   (x)

Token:  I;    Lexeme:  I

Token  and  Lexeme:  )

Token  and  Lexeme:  

Control-D

When entering your grammar into the Rules section of prob4.y, it is best to leave the existing rules for the nonterminal start unchanged, as this has some extra stuff designed to allow you to enter a series of separate expressions on separate lines.  So, take the Start symbol from your grammar in Problem 2 and represent it by the nonterminal line instead of by start.

The specific modifications you need to do in the Declarations section should be:

. You need a new %token declaration for the tokens  I, H, X, Z, CNOT, TOF, and KRONECKERPROD. These have the same structure as the line for the NUMBER token, except that “num” is replaced by “str” (since each of the above tokens represents a string, being names of matrices, registers or operations, whereas NUMBER  represents a number).

. You should include each of our two matrix operations, * (multiplication) and KRONECKERPROD (the Kronecker product, ⊗), in a %left or %right statement.  Such a statement specifies when an operation is left- or right-associative, i.e., whether you do multiple consecutive operations left-to-right or right-to-left.  Mathematically, for * and ⊗, it doesn’t matter.  So, for these, you can use either %left or %right.  But you should do one of them, because it helps the parser determine an order in which to do the operations and removes some ambiguity.  For operations whose %left or %right statements are on different lines, the operations with higher precedence are those with higher line numbers  (i.e.,  later  in the file).   Ordinary matrix multiplication should have higher precedence than Kronecker product.

. For nonterminal symbols, you can include a %type line that declares its type, i.e., the type of

value that is returned when an expression generated from this nonterminal is evaluated. E.g., %type    start

Here, “qmx” is the type name we are using for quantum matrices.  The various type names can be seen in the %union statement a little earlier in the file. But you do not need to know how that works in order to do this task.

. You should still use start as your Start symbol.  If you use another name instead, you will

need to modify the %start line too.

Sample output:

$  ./a.out

CNOT*  (  H  (x)I)