CS374: Principles of Programming Languages - The Parser (100 Points)

Purpose, Task, and Criteria

Purpose: To see what a parser generator does by building an LR(1) table yourself, to use Flex and Bison on the same calculator, and to add variables to both versions.

Task: Build an LR(1) calculator in Python from a given grammar and lexer. Build the same calculator in Flex and Bison. Then add variable assignment and lookup to both.

Criteria: I grade this on closure and goto that handle lookaheads correctly, tables your code generates with no conflicts, a driver that computes correct answers from those tables, a Flex and Bison calculator with no conflicts, and variables that work in both versions. The rubric below breaks this down in full.

Assignment Goals

The goals of this assignment are:

To implement LR(1) items, FIRST sets, closure, goto, and tables for a given grammar
To drive a shift-reduce parse from those tables, computing a value on each reduction
To write the same calculator in Flex and Bison
To add variable assignment and lookup with a symbol table, in both versions

Background Reading and References

Please refer to the following readings and examples offering templates to help get you started:

The Assignment

In this assignment you build what a parser generator builds, and then you use one. Everything you need is in the starter kit, and nothing depends on any earlier assignment.

Part 1: build an LR(1) calculator in Python: your code computes the parse tables from the grammar, and a small driver runs them.
Part 2: build the same calculator in Flex and Bison, which build those tables for you.
Part 3: add variable assignment and lookup to both versions.

Neither calculator builds a tree. Each one computes its answer as it parses, because a reduction is the moment a piece of the input is complete.

Before You Start

You need Python 3.10 or newer, flex, bison, gcc, and make. On Ubuntu, sudo apt install flex bison gcc make installs the last four. Check them:

python3 --version
flex --version
bison --version
gcc --version

Make a folder named cs374-parser, and copy the python and flexbison folders of the starter kit into it.

Part 1: An LR(1) Calculator in Python

You write: every TODO in python/calculator.py, plus a hand trace in notes.md. You run: the check after each step, from inside python. lexer.py is complete.

Here is the grammar. It is small enough that you can look at every state.

S' -> E
E  -> E + T
E  -> E - T
E  -> T
T  -> T * F
T  -> T / F
T  -> F
F  -> ( E )
F  -> num

Precedence lives in the levels: an E is built from Ts, and a T is built from Fs, so * is reduced before +. The rules are left-recursive, which an LR parser handles without trouble, so 8 - 3 - 2 means (8 - 3) - 2.

An LR parser keeps a stack and repeats one of two moves. It shifts the next token onto the stack, or it reduces the top of the stack to a non-terminal when a right-hand side is complete. The tables tell it which move to make, so most of this part builds those tables.

Step 1.1: Trace a tiny grammar by hand

Trace this grammar on paper first, in notes.md. Every function you write does what you do here.

S' -> E
E  -> E + n
E  -> n

Items, closure, and lookaheads are worked on a smaller grammar in LR(1) items, by hand, and the shift-reduce idea in Bottom-Up in One Picture.

An LR(1) item is a production, a dot showing how much of it the parser has seen, and a lookahead: the token that must come next once the production is complete. [E -> E . + n, $] means “I have seen an E, I expect + n, and after that I expect $.”

The closure rule says that if an item has the dot before a non-terminal B, as in [A -> x . B y, a], the parser may be about to see a B, so it may also be at the start of any B production. Add [B -> . z, b] for every B -> z, where b is any token that can come right after this B: whatever begins y, or a if y is empty.

Do this.

Compute the closure of [S' -> . E, $], one pass at a time. You should finish with five items.

Write one sentence saying why a second pass was needed.

Trace the shift-reduce parse of n + n $ with three columns: the stack, the remaining input, and the action. It takes five moves before accept.

Step 1.2: Items

An item is a tuple (production_index, dot, lookahead). So (1, 1, "+") is [E -> E . + T, +], because PRODUCTIONS[1] is E -> E + T and the dot sits before position 1. Tuples work well here, because a state will be a frozenset of items, and a frozenset can be a dictionary key. That is how you will recognize a state you have already built. Python for Language Work covers tuples and frozensets.

Fill in show_item, so that every later check is something you can read:

def show_item(item):
    """Render (1, 1, "+") as "[E -> E . + T, +]"."""
    # TODO: unpack the tuple, and look up the production's left-hand side and right-hand side.
    # TODO: copy the right-hand side into a new list, and insert "." at the dot position.
    # TODO: return the brackets, the left-hand side, " -> ", the symbols joined by spaces, ", ", and the lookahead.

python3 -c "from calculator import show_item; print(show_item((1, 1, '+'))); print(show_item((8, 1, '*')))"

You should see.

[E -> E . + T, +]
[F -> num ., *]

Step 1.3: FIRST sets

Closure needs to know which tokens can begin a non-terminal, because that is what can come next. To know FIRST(T) you need FIRST(T), since T -> T * F, so you cannot compute these in one sweep. You start with empty sets and sweep until nothing changes. That is a fixed point, and closure uses the same idea (FIRST and FOLLOW Sets shows more):

first = an empty set for each non-terminal
repeat:
    for each production A -> X ... :
        add X to first[A] if X is a terminal, or everything in first[X] if it is not
until a whole sweep changes nothing

No production here is empty, so only the first symbol of a right-hand side matters.

python3 -c "from calculator import first_sets; f = first_sets(); print(sorted(f['F']), sorted(f['E']))"

You should see. ['(', 'num'] ['(', 'num']

Step 1.4: Closure

Write the lookahead piece first. Given an item [A -> x . B y, a], lookaheads(y, a, first) returns the tokens that can follow B:

if y is empty:                  {a}          what follows this production also follows B
if y starts with a terminal t:  {t}
otherwise:                      first[y[0]]

Now closure. One pass is not enough. Adding [E -> . T, $] puts a dot before T, which pulls in new productions. Adding [E -> . E + T, $] then gives E a new lookahead, +, so every E item has to be added again with that lookahead. So it is a fixed point again:

closure(items):
    result = set(items)
    repeat:
        new = empty set
        for each item (p, dot, a) in result:
            if the symbol after the dot is a non-terminal B:
                for each b in lookaheads(what comes after B, a, first):
                    for each production q of B:
                        add (q, 0, b) to new
        if new adds nothing to result: return frozenset(result)
        result = result | new

Compute first_sets() once, because it never changes. Do not add to result inside the loop that walks it, because Python raises a RuntimeError if a set changes size during iteration. That is why the pseudocode collects into new.

python3 -c "from calculator import closure; print(len(closure({(0, 0, '\$')})))"

You should see. 35. This is state 0.

If it fails. A much smaller count, with every lookahead $, means your loop makes a single pass, or lookaheads always returns {a}. If it never finishes, your loop decides something changed even when new added nothing.

Step 1.5: Goto

goto(state, X) answers: “if the parser is in this state and sees X, where does it go?” Every item with the dot before X moves its dot past X, and the lookahead stays the same. Any other item drops out. Then close the result, since the dot may now sit before a non-terminal. If no item can move, the result is an empty frozenset, which means there is no edge.

goto(state, X):
    moved = { (p, dot + 1, a) for each (p, dot, a) in state whose symbol after the dot is X }
    return closure(moved)

Why lookaheads matter. Follow num from two places, the top level and inside parentheses. The production is the same, but the machine keeps two states, because it remembers the context. In the first state below a ) has no action, so an extra ) fails right where the mistake is.

python3 -c "from calculator import *; i0 = closure({(0, 0, '\$')}); print(*sorted(show_item(i) for i in goto(i0, 'num'))); print(*sorted(show_item(i) for i in goto(goto(i0, '('), 'num'))); print(len(goto(i0, '+')))"

You should see. The two states, and then 0, because no item in state 0 has the dot before +.
[F -> num ., $] [F -> num ., *] [F -> num ., +] [F -> num ., -] [F -> num ., /]
[F -> num ., )] [F -> num ., *] [F -> num ., +] [F -> num ., -] [F -> num ., /]
0

Step 1.6: Build the states

The machine’s states are every set of items reachable from state 0. So start from state 0, try goto on every symbol, and treat each new result as a new state to explore. Keep a dictionary from state to number, so that one lookup tells you whether a result is new.

build_states():
    states = [ closure({(0, 0, "$")}) ]
    worklist = [ 0 ]
    while worklist is not empty:
        i = take the FRONT of worklist
        for X in SYMBOLS:
            g = goto(states[i], X)
            if g is empty: skip it
            if g is new: give it the next number, add it to states, and add that number to the BACK of worklist
            transitions[(i, X)] = the number of g
    return states, transitions

Use exactly this worklist order and SYMBOLS, so that everyone gets the same state numbers.

python3 -c "from calculator import *; s, t = build_states(); print(len(s), t[(0, 'E')], t[(0, 'num')], t[(0, '(')])"

You should see. 30 1 4 5

Step 1.7: Build the tables

Read the tables straight off the states. action[i][terminal] is ("s", j) to shift and go to state j, ("r", p) to reduce by production p, or ("acc",) to accept. goto_table[i][nonterminal] is a state number. For every item (p, dot, a) in state i:

If the dot is before a terminal t, then action[i][t] is ("s", transitions[(i, t)]).
If the dot is at the end and p is not 0, then action[i][a] is ("r", p). Only on a: this is what the lookahead is for.
If the dot is at the end and p is 0, then action[i]["$"] is ("acc",).
If a cell already holds a different action, append (i, token, old, new) to conflicts, and leave the cell alone. A table builder that overwrites hides an ambiguous grammar from you.

goto_table comes from every edge in transitions whose symbol is a non-terminal.

python3 -c "from calculator import *; s, t = build_states(); a, g, c = build_tables(s, t); print(c); print(sorted(a[t[(0, '(')]])); print(sorted(a[t[(0, 'num')]].items()))"

You should see. No conflicts. After ( the parser can shift only what starts an expression. After a num it reduces by production 8 on each lookahead:
[]
['(', 'num']
[('$', ('r', 8)), ('*', ('r', 8)), ('+', ('r', 8)), ('-', ('r', 8)), ('/', ('r', 8))]

Step 1.8: Run the table, and compute as you reduce

The driver is short, because the table holds all the knowledge. It keeps a stack of state numbers, which starts as [0], and a stack of values, which starts empty. A value stack is what lets it calculate: a token’s value goes on when it is shifted, and a reduction replaces the values of its right-hand side with one answer.

pos = 0
loop:
    entry = action[top of state stack][type of tokens[pos]]
    no entry:   raise ParseError(the token's type, its col)
    shift j:    push j and the token's value, and move to the next token
    reduce p:   pop len(rhs of p) from both stacks, keeping the popped values in order as v
                push reduce_value(p, v), then push goto_table[new top state][lhs of p]
    accept:     return the top of the value stack

Look up the GOTO from the state the pops exposed, not the state you were in. That state remembers what the parser was doing before this right-hand side began.

reduce_value has productions 1, 3, and 8 done for you. Fill in 2, 4, 5, 6, and 7 the same way. Think about what v holds for each one: for F -> ( E ), v has three values, and the answer is the middle one.

Here is how the values move on 1 + 2 * 3:

shift 1, reduce F -> num, T -> F, E -> T      values: 1
shift +, shift 2, reduce F -> num, T -> F     values: 1 + 2
shift *, shift 3, reduce F -> num             values: 1 + 2 * 3
reduce T -> T * F                             values: 1 + 6
reduce E -> E + T                             values: 7

The * happens first because the table says to shift it while T is on top, and no code in your driver mentions precedence.

python3 calculator.py "1 + 2 * 3"
python3 calculator.py "(1 + 2) * 3"
python3 calculator.py "8 - 3 - 2"
python3 calculator.py "8 / 2 / 2"
python3 calculator.py "1 + ) 2"

You should see. 7, 9, 3, and 2.0. The last command ends in calculator.ParseError: ParseError at col 5: unexpected ).

If it fails.

A KeyError from goto_table: you read the top state before you popped.

A KeyError on action instead of a ParseError: use .get, because an empty cell is how a syntax error shows up.

5 for 8 - 3 - 2 or a string where a number belongs: check the order of v, and check that production 8 is what turns a token’s text into a number.

Part 2: The Same Calculator in Flex and Bison

You write: the three TODOs in flexbison/calc.y. You run: make, then the calculator, from inside flexbison.

You just built what Bison builds. Bison reads a grammar like the one in Part 1 and writes the tables and driver as C, and Flex writes the lexer. You only write the grammar and what to do on each reduction.

Flex and Bison explains these files from zero, and From the Table to Flex and Bison connects them to Part 1. Read calc.l first. Each line is a pattern and the C code to run when it matches. [0-9]+ stores the number in yylval and returns the token NUM. A single-character token returns the character itself.

Now read calc.y. It has three sections, separated by %%: declarations, grammar rules, and C code. Here is the rule that matters:

expr '+' term     { $$ = $1 + $3; }

The braces hold what to do on this reduction, which is your reduce_value. $1 and $3 are the values of the first and third symbols, and $$ is the value of the left-hand side. Bison keeps the value stack for you, and the %union and %type lines tell it that these values are doubles.

Do this.

Replace the three TODO comments in calc.y: subtraction, multiplication and division, and parentheses. Each one is a rule in the form above. Keep term and factor in their levels, so that precedence comes from the grammar, as in Part 1.

Build it. make runs three commands, which you can also run yourself:

bison -d calc.y          # writes calc.tab.c, and calc.tab.h for the scanner
flex calc.l              # writes lex.yy.c
gcc -o calc calc.tab.c lex.yy.c

make
printf '1 + 2 * 3\n(1 + 2) * 3\n8 - 3 - 2\n8 / 2 / 2\n' | ./calc

You should see. No conflict warnings, and then:
7
9
3
2

If it fails. conflicts in the Bison output means a rule is ambiguous, usually because a rule refers to the wrong level, such as expr '*' expr. An undefined reference to a name means that make didn’t rerun a step, so try make clean and then make.

Part 3: Add Variable Assignment and Lookup

Calculator with Variables walks through the idea. A variable needs two things: somewhere to keep its value, and grammar rules that use it. The somewhere is a symbol table, which maps names to values. Both versions use the same two grammar rules: a name in an expression looks up its value, and an assignment stores one.

Assignment goes in its own level, A, above E. If you put id = E directly into E, the grammar has shift/reduce conflicts, because after x = 1 the parser cannot tell whether a + continues the right side. The new level settles it, and the rule refers to itself so that a = b = 2 works.

Step 3.1: Variables in Python

You write: changes to python/calculator.py. You run: the check at the end of this step.

The payoff of Part 1 is here: you change the grammar, and your code rebuilds the tables. lexer.py already returns id and = tokens.

Change the grammar. Production 0 now starts from A, and three productions go on the end, so the numbers you already use do not move:

("S'", ["A"]),               # 0, changed
...
("A",  ["id", "=", "A"]),    # 9, new
("A",  ["E"]),               # 10, new
("F",  ["id"]),              # 11, new

Add "A" to NONTERMINALS. Add "A", "id", and "=" to the end of SYMBOLS.

Add the symbol table, and fill in the three new cases in reduce_value. v holds the values of the right-hand side, and a shifted id token’s value is its name:

VARIABLES = {}   # the symbol table, above reduce_value

# TODO, production 9, A -> id = A: store v[2] under the name v[0], and return v[2].
# TODO, production 10, A -> E: return the value of E.
# TODO, production 11, F -> id: return the name's value from VARIABLES.
#       If the name is missing, raise NameError(f"undefined name {name}").

Your closure, goto, states, and tables do not change at all. Each call to calculate runs one line, and VARIABLES keeps its contents between calls.

python3 -c "from calculator import *; print(len(build_states()[0]), build_tables(*build_states())[2]); [print(calculate(x)) for x in ['x = 3', 'y = x * 2 + 1', 'y', 'x = x + 1', 'x * y', 'a = b = 2', 'a + b']]"
python3 -c "from calculator import *; calculate('z')"

You should see. The new state count, no conflicts, and the answers. The second command ends in NameError: undefined name z.
36 []
3
7
7
4
28
2
4

Step 3.2: Variables in Flex and Bison

You write: changes to flexbison/calc.l and flexbison/calc.y. You run: make, then the check.

C for Flex and Bison covers the linked list, malloc, strdup, and strcmp this step uses, on a different example.

In calc.l, return two new tokens. Add these two lines above the line for single-character tokens, and add #include <string.h> at the top. strdup matters because Flex reuses yytext for the next token, so you have to keep your own copy of the name.

[a-zA-Z_][a-zA-Z0-9_]*  { yylval.name = strdup(yytext); return T_ID; }
"="                     { return T_ASSIGN; }

In the top of calc.y, add #include <string.h> and the symbol table, and fill in its two functions:

typedef struct Binding {
    char *name;
    double value;
    struct Binding *next;
} Binding;

static Binding *table = NULL;

static double lookup(const char *name) {
    /* TODO: walk the list, and return the value of the binding whose name matches.
       Compare names with strcmp, which returns 0 when they are equal. */
    fprintf(stderr, "error: undefined name %s\n", name);
    exit(1);
}

static void set(char *name, double value) {
    /* TODO: if the name is in the list, update its value and return. */
    /* TODO: otherwise, malloc a new Binding, fill it in, and put it at the front of the list. */
}

In the declarations of calc.y, add char *name; to the %union, and declare the tokens:

%token <name> T_ID
%token T_ASSIGN

In the rules of calc.y, a name used in an expression looks up its value, and an assignment stores one:

factor:  ... | T_ID             { $$ = lookup($1); }

Assignment goes in its own level above expr, as in Step 3.1, and line uses that level:

line:    '\n' | assign '\n'     { printf("%g\n", $1); }
assign:  T_ID T_ASSIGN assign   { set($1, $3); $$ = $3; }
       | expr                   { $$ = $1; }

Add assign to the %type <number> line.

make clean && make
printf 'x = 3\ny = x * 2 + 1\ny\nx = x + 1\nx * y\na = b = 2\na + b\nz\n' | ./calc

You should see. No conflict warnings, and then:
3
7
7
4
28
2
4
error: undefined name z

Deliverables

Submit a ZIP of your cs374-parser folder, with the build products removed (make clean in flexbison), containing:

python/calculator.py, with variables added, and notes.md with your hand trace
flexbison/calc.l and flexbison/calc.y, with variables added

Self-Check Before You Submit

Before you added variables, closure({(0, 0, "$")}) had thirty-five items, build_states found thirty states, and build_tables reported no conflicts.
python3 calculator.py "8 - 3 - 2" prints 3, and "1 + ) 2" raises a ParseError at col 5.
make clean && make in flexbison shows no conflict warnings.
Both versions handle a = b = 2, and in both an undefined name reports an error with its name.

Reflection Prompts

Precedence never appears in your Python driver’s code. Where does it live, and how does it get into the answer?
What did Bison do for you that you wrote by hand in Part 1, and what did you still have to write?
When you added variables in Python, which functions did you not have to change, and why?

Submission

In your submission, please include answers to any questions asked on the assignment page, as well as the questions listed below, in your README file.

If you wrote code as part of this assignment, please describe your design, approach, and implementation in a separate document prepared using a word processor or typesetting program such as LaTeX. This document should include specific instructions on how to build and run your code, and a description of each code module or function that you created suitable for re-use by a colleague.

In your README, please include answers to the following questions:

Describe what you did, how you did it, what challenges you encountered, and how you solved them.
Please answer any questions found throughout the narrative of this assignment.
If collaboration with a buddy was permitted, did you work with a buddy on this assignment? If so, who? If not, do you certify that this submission represents your own original work?
Please identify any and all portions of your submission that were not originally written by you (for example, code originally written by your buddy, or anything taken or adapted from a non-classroom resource). It is always OK to use your textbook and instructor notes; however, you are certifying that any portions not designated as coming from an outside person or source are your own original work.
Approximately how many hours it took you to finish this assignment (I will not judge you for this at all...I am simply using it to gauge if the assignments are too easy or hard)?
Your overall impression of the assignment. Did you love it, hate it, or were you neutral? One word answers are fine, but if you have any suggestions for the future let me know.
Using the grading specifications on this page, discuss briefly the grade you would give yourself and why. Discuss each item in the grading specification.
Any other concerns that you have. For instance, if you have a bug that you were unable to solve but you made progress, write that here. The more you articulate the problem the more partial credit you will receive (it is fine to leave this blank).
Please describe any use of outside resources you may have engaged in the completion of this assignment, including the use of generative Artificial Intelligence.

Assignment Rubric

Description	Pre-Emerging (< 50%)	Beginning (50%)	Progressing (85%)	Proficient (100%)
LR(1) Items, FIRST, Closure, and Goto (Goal 1) (25%)	closure and goto are missing or do not run	Items carry no lookaheads, or closure makes a single pass	closure reaches a fixed point, but lookaheads are wrong in some case, or goto does not close its result	The hand trace is complete; FIRST is computed by a fixed point; closure adds each item with the lookaheads that can follow its non-terminal and yields the thirty-five-item start state; and goto advances the dot and closes the result
LR(1) Tables and the Calculating Driver (Goals 1, 2) (25%)	No state construction, table, or driver is produced	States are built, but tables or the driver are missing, or the state count is wrong	The driver runs, but a table cell or a reduction's value is wrong, or a syntax error crashes it without a ParseError	The thirty states are built in the required order; ACTION and GOTO are generated by the code with no conflicts; reduce actions appear only on each item's lookahead; the driver computes correct answers with precedence and left associativity; and a syntax error raises a ParseError with its column
The Flex and Bison Calculator (Goal 3) (25%)	The calculator does not build	It builds, but most operators are missing or compute wrong answers	Most operators work, but one rule is wrong, such as parentheses or subtraction	The calculator builds with the Makefile and no conflict warnings, and it computes correct answers for all four operators and parentheses, with each action computing its value directly
Variable Assignment and Lookup in Both Versions (Goal 4) (25%)	No variables are added	Variables work in only one version, or assignment or lookup is missing	Both versions work, but reassignment or chained assignment is wrong, or an undefined name does not report an error	In both versions, assignment stores and updates a value, lookup finds it, chained assignment works, the grammar has no conflicts, and an undefined name reports an error with its name

Please refer to the Style Guide for code quality examples and guidelines.