Compiler Parsing Lab

by Todd Cooper & Karen Lemone

In this lab you will use yacc (or its newer version) Bison as well as lex (flex) to create a parser for a small subset of Javalet

The yacc (bison) program is in the left box, the related lex (flex) code is in the bottom box and the input program for the generated parser is in the right box.

When you press the button Edit the text and click me, the following will happen:

  1. The yacc/bison code in the left box will be run by bison (yacc)
  2. The lex/flex code will be run by flex (lex)
  3. The C code created by flex will be compiled by cc, the C compiler
  4. The C code created by bison will be compiled by cc, the C compiler, creating an executable parser
  5. The input in the right box is executed by this parser producing a bottom-up parse
    (The parser prints the left hand side of productions just like you will in Project, Part 2)

The results will be displayed on the bottom of the page.
You might have to scroll down in your browser to see them.

Step 1 Looking at the bison/yacc code in the left box, write the BNF in standard form.
Hint: The first production is

lines --> epsilon | lines line

Step 2 It is really hard to see the bottom-up parse from the output, so change the input to contain just the first statement 1 + 1; and press the button again. Now you should be able to create a parse from the output (which is the reverse of a leftmost derivation). Show it as a parse tree.

Step 3 Now, change the yacc/bison grammar in the left box so that it recognizes division. Note that the lex code already recognizes "/", calling the token DIVIDE. (Ask us if you don't see this)
Run an input to show that the division works (if it does! If not, fix your production) and show us your output. Draw the parse tree from the output.

Step 4 In your written BNF, add productions to perform exponentiation, "^". Show it to us before you go on. Now add the bison code for ^ to the left box, enter a statement using ^ in the right box and click on the button. Note that the lex code for "^" is already there with the token called POWER. Show us when it works.

Step 5 Moving to unix/linux:

Yacc/Bison Parsing Program Yacc/Bison Parsing Input
Lex Scanner Program
Edit the text above, and click on the button to see the result.

Valid XHTML 1.0 Strict