Lex, Yacc and the PLUS-TIMES-POWER language
 In this part of the Assignment, you will use the lexical analyser generator lex, initially by itself,
 and then with the parser generator yacc1.
 Some useful references on Lex and Yacc:
 • T. Niemann, Lex & Yacc Tutorial, http://epaperpress.com/lexandyacc/
 • Doug Brown, John Levine, and Tony Mason, lex and yacc (2nd edn.), O’Reilly, 2012.
 • the lex and yacc manpages.
 We will illustrate the use of these programs with a language PLUS-TIMES-POWER based on
 simple arithmetic expressions involving nonnegative integers, using just addition, multiplication and
 powers. Then you will use lex and yacc on some languages related to quantum computing.
 PLUS-TIMES-POWER
 The language PLUS-TIMES-POWER consists of expressions involving addition, multiplication and
 powers of nonnegative integers, without any parentheses (except for those required by the function
 Power). Example expressions include:
 5 +8, 8+5, 3+5∗2, 13+8∗4+Power(2,Power(3,2)), Power(1,3)+Power(5,3)+Power(3,3),
 Power(999,0), 0+99∗0+1, 2014, 10∗14+74+10∗13∗73, 2∗3∗5∗7∗11∗13∗17∗19.
 In these expressions, integers are written in unsigned decimal, with no leading zeros or decimal point
 (so 2014, 86, 10, 7, and 0 are ok, but +2014, −2014, 86.0, A, 007, and 00 are not).
 For lexical analysis, we treat every nonnegative integer as a lexeme for the token NUMBER.
 Lex
 An input file to lex is, by convention, given a name ending in .l. Such a file has three parts:
 • definitions,
 • rules,
 • Ccode.
 These are separated by double-percent, %%. Comments begin with /* and end with */. Any
 comments are ignored when lex is run on the file.
 You will find an input file, plus-times-power.l, among the files for this Assignment. Study
 its structure now, identifying the three sections and noticing that various pieces of code have been
 commented out. Those pieces of code are not needed yet, but some will be needed later.
 Wefocus mainly on the Rules section, in the middle of the file. It consists of a series of statements
 of the form
 pattern
 { action }
 where the pattern is a regular expression and the action consists of instructions, written in C,
 specifying what to do with text that matches the pattern.2 In our file, each pattern represents a set
 of possible lexemes which we wish to identify. These are:
 1actually, Linux includes more modern implementations of these programs called flex and bison.
 2This may seem reminiscent of awk, but note that: the pattern is not delimited by slashes, /.../, as in awk; the
 action code is in C, whereas in awk the actions are specified in awk’s own language, which has similarities with C but
 is not the same; and the action pertains only to the text that matches the pattern, whereas in awk the action pertains
 to the entire line in which the matching text is found.
 
• a decimal representation of a nonnegative integer, represented as described above;– This is taken to be an instance of the token NUMBER (i.e., a lexeme for that token).
 • the specific string Power, which is taken to be an instance of the token POWER.
 • certain specific characters: +, *, (, ), and comma;
 • the newline character;
 • white space, being any sequence of spaces and tabs.
 Note that all matching in lex is case-sensitive.
 Our action is, in most cases, to print a message saying what token and lexeme have been found.
 For white space, we take no action at all. A character that cannot be matched by any pattern yields
 an error message.
 If you run lex on the file plus-times-power.l, then lex generates the C program lex.yy.c.3
 This is the source code for the lexical analyser. You compile it using a C compiler such as cc.
 For this assignment we use flex, a more modern variant of lex. We generate the lexical analyser
 as follows.
 $ flex plus-times-power.l
 $ cc lex.yy.c
 By default, cc puts the executable program in a file called a.out4. This can be executed in
 the usual way, by just entering ./a.out at the command line. If you prefer to give the executable
 program another name, such as plus-times-power-lex, then you can tell this to the compiler using
 the-o option: cc lex.yy.c-o plus-times-power-lex.
 When you run the program, it will initially wait for you to input a line of text to analyse. Do
 so, pressing Return at the end of the line. Then the lexical analyser will print, to standard output,
 messages showing how it has analysed your input. The printing of these messages is done by the
 printf statements from the file plus-times-power.l. Note how it skips over white space, and only
 reports on the lexemes and tokens.
 $ ./a.out
 13+8 * 4 + Power(2,Power
 Token: NUMBER; Lexeme: 13
 Token and Lexeme: +
 Token: NUMBER; Lexeme: 8
 Token and Lexeme: *
 Token: NUMBER; Lexeme: 4
 Token and Lexeme: +
 Token: POWER; Lexeme: Power
 Token and Lexeme: (
 Token: NUMBER; Lexeme: 2
 Token and Lexeme: ,
 Token: POWER; Lexeme: Power
 Token and Lexeme: (
 Token: NUMBER; Lexeme: 3
 Token and Lexeme: ,
 Token: NUMBER; Lexeme: 2
 Token and Lexeme: )
 Token and Lexeme: )
 Token and Lexeme: <newline>
 (3,2
 ))
 Try running this program with some input expressions of your own. You can keep entering new
 expressions on new lines, and enter Control-D to stop when you are finished

Yacc
 We now turn to parsing, using yacc.
 Consider the following grammar for PLUS-TIMES-POWER.
 S −→ E
 E −→ I
 E −→ POWER(E,E)
 E −→ E∗E
 E −→ E+E
 I −→ NUMBER
 In this grammar, the non-terminals are S, E and I. Treat NUMBER and POWER as just single
 tokens, and hence single terminal symbols in this grammar.
 We now generate a parser for this grammar, which will also evaluate the expressions, with +,∗
 interpreted as the usual integer arithmetic operations and Power(...,...) interpreted as raising its
 f
 irst argument to the power of its second argument.
 To generate this parser, you need two files, prob1.l (for lex) and plus-times-power.y (for
 yacc):
 • Change into your problem1 subdirectory and do the following steps in that directory.
 • Copy plus-times-power.l to a new file prob1.l, and then modify prob1.l as follows:– in the Definitions section, uncomment the statement #include "y.tab.h";– in the Rules section, in each action:
 ∗ uncomment the statements of the form
 · yylval.str = ...;
 · yylval.num = ...;
 · return TOKENNAME;
 · return *yytext;
 · yyerror...
 ∗ Comment out the printf statements. These may still be handy if debugging is
 needed, so don’t delete them altogether, but the lexical analyser’s main role now is
 to report the tokens and lexemes to the parser, not to the user.– in the C code section, comment out the function main(), which in this case occupies
 four lines at the end of the file.
 • plus-times-power.y, the input file for yacc, is provided for you. You don’t need to modify
 this yet.
 An input file for yacc is, by convention, given a name ending in .y, and has three parts, very loosely
 analogous to the three parts of a lex file but very different in their details and functionality:
 • Declarations,
 • Rules,
 • Programs.
 These are separated by double-percent, %%. Comments begin with /* and end with */.
 Peruse the provided file plus-times-power.y, identify its main components, and pay particular
 attention to the following, since you will need to modify some of them later.
 9
• in the Declarations section:– lines like
 int printMatrix(Matrix x);
 Matrix identity();
 .
 .
 .
 Register kroneckerProductReg(Register v, Register w);
 which are declarations of functions (but they are defined later, in the Programs section);5– declarations of the tokens to be used:
 %token <num> NUMBER
 %token <str> POWER– some specifications that certain operations are left-associative (which helps determine the
 order in which operations are applied and can help resolve conflicts and ambiguities):
 %left ’+’
 %left ’*’– declarations of the nonterminal symbols to be used (which don’t need to start with an
 upper-case letter):
 %type <iValue> start
 %type <iValue> line
 %type <iValue> expr
 %type <iValue> int– nomination of which nonterminal is the Start symbol:
 %start start
 • in the Rules section, a list of grammar rules in Backus-Naur Form (BNF), except that the
 colon “:” is used instead of →, and there must be a semicolon at the end of each rule. Rules
 with a common left-hand-side may be written in the usual compact form, by listing their
 right-hand-sides separated by vertical bars, and one semicolon at the very end. The terminals
 may be token names, in which case they must be declared in the Declarations section and also
 used in the lex file, or single characters enclosed in forward-quote symbols. Each rule has
 an action, enclosed in braces {...}. A rule for a Start symbol may print output, but most
 other rules will have an action of the form $$ = .... The special variable $$ represents the
 value to be returned for that rule, and in effect specifies how that rule is to be interpreted for
 evaluating the expression. The variables $1, $2, ... refer to the values of the first, second, ...
 symbols in the right-hand side of the rule.
 • in the Programs section, various functions, written in C, that your parsers will be able to use.
 You do not need to modify these functions, and indeed should not try to do so unless you are
 an experienced C programmer and know exactly what you are doing! Most of these functions
 are not used yet; some will only be used later, in Problem 4.
 After constructing the new lex file prob1.l as above, the parser can be generated by:
 $ yacc-d plus-times-power.y
 $ flex prob1.l
 $ cc lex.yy.c y.tab.c-lm
 The executable program, which is now a parser for PLUS-TIMES-POWER, is again named a.out
 by default, and will replace any other program of that name that is sitting in the same directory.
 5These functions for computing with quantum expressions are not needed by plus-times-power.y, but you will
 need them later, when you make a modified version of plus-times-power.y to parse quantum expressions.
 10
$./a.out
 13+8 * 4+Power(2,Power (3,2 ))
 557
 13+8*4+Power(2,Power(3,2))
 557
 Power(1,3)+Power(5,3)+Power(3,3)
 153
 1+2+3+4+5+6+7+8+9+10
 55
 10*9*8*7*6*5*4*3*2*1
 3628800
 Power(999,0)
 1
 Control-D
 Runitwithsomeinputexpressionsofyourown.Youcankeepenteringnewexpressionsonnew
 lines,asabove,andenterControl-Dtostopwhenyouarefinished

Problem 1. [2 marks]
 Construct prob1.l, as described on pp. 9–11, so that it can be used with plus-times-power.y
 to build a parser for PLUS-TIMES-POWER