Project 3

Deadline	Tuesday, November 21, 11:59pm
Name on Marmoset	P3
To Submit	Standard Format: `wlp4parse.cc` OR `wlp4parse.rkt` Prescanned Format: `wlp4parse-prescanned.cc` OR `wlp4parse-prescanned.rkt`
Marking Scheme	50 marks for release tests, 50 marks for secret tests

WLP4 Parser

In this project, you will write a parser for the WLP4 programming language. The goal is to take the output of the WLP4 scanner (Project 1B), which is a sequence of tokens, and use the LR(1) parsing algorithm to produce a parse tree for a WLP4 program.

WLP4 Grammar and SLR(1) DFA

To facilitate implementing the algorithm, we provide some files containing components representing an augmented version of the WLP4 context-free grammar, and the SLR(1) DFA corresponding to this grammar.

The CFG is represented by a CFG component, and the SLR(1) DFA is represented by a TRANSITIONS component followed by a REDUCTIONS component.

For C++ Users: wlp4data.h and wlp4data.cc

The files wlp4data.h and wlp4data.cc together provide the following five string constants:

WLP4_CFG is a CFG component for the augmented WLP4 grammar.
WLP4_TRANSITIONS is a TRANSITIONS component for the WLP4 SLR(1) DFA.
WLP4_REDUCTIONS is a REDUCTIONS component for the WLP4 SLR(1) DFA.
WLP4_DFA is a single string consisting of WLP4_TRANSITIONS followed by WLP4_REDUCTIONS.
WLP4_COMBINED is a single string consisting of WLP4_CFG followed by WLP4_DFA.

For Racket Users: wlp4data.rkt

The file wlp4data.rkt provides the following five string constants:

wlp4-cfg is a CFG component for the augmented WLP4 grammar.
wlp4-transitions is a TRANSITIONS component for the WLP4 SLR(1) DFA.
wlp4-reductions is a REDUCTIONS component for the WLP4 SLR(1) DFA.
wlp4-dfa is a single string consisting of wlp4-transitions followed by wlp4-reductions.
wlp4-combined is a single string consisting of wlp4-cfg followed by wlp4-dfa.

Input and Output Requirements

As in Project 2, there are two input formats.

Standard Format: Plain WLP4 source code.
Prescanned Format: The result of running a Standard Format input through wlp4scan.

The parsing algorithm should be performed using scanned input, that is, a sequence of tokens representing the input program.

If using Standard Format, you will need to scan the input yourself using your solution to Project 1B.
If using Prescanned Format, you will need to read in the sequence of tokens from standard input.

Producing The Output (Successful Parse)

You should use the LR(1) parsing algorithm to parse the tokens and build a tree representation of the program.

We provide you with a text representation of the WLP4 context-free grammar. You should read this and store the rules in a data structure.
We provide you with a text representation of a SLR(1) DFA for the WLP4 grammar. You should read this and store the transition and reduction information in data structures.
The WLP4 grammar is augmented, so you should also augment the input sequence by adding a beginning-of-file token to the start, and an end-of-file token to the end.
- The kind and lexeme of the beginning-of-file token should both be BOF.
- The kind and lexeme of the end-of-file token should both be EOF.
After augmenting the input sequence, process the tokens and perform the LR(1) parsing algorithm using the SLR(1) DFA for the WLP4 grammar. You should use the version of the algorithm that uses a tree stack instead of a symbol stack to represent the progress of the derivation, i.e., you should build the parse tree as you read the input. At tree nodes corresponding to nonterminals, you should store the CFG rule used to expand the nonterminal, and at tree nodes corresponding to terminal tokens, you should store the token (both kind and lexeme).
Note that after you read the EOF token, the parse is successful. However, there is one more step. After reading EOF, your tree stack will contain three trees: a tree for the BOF token, a complete parse tree for the non-augmented input, and a tree for the EOF token. You should manually perform one final reduction to produce a single tree with the augmented starting rule start BOF procedures EOF stored at the root, and the three aforementioned trees as the children of the root.

Finally, so Marmoset can verify that your output is correct, you need to print out a representation of the parse tree. You should do this using the following recursive algorithm (a simpler version of the printing algorithm from Question 10):

Print a line representing the root node:
- If the root node of the tree being printed is a nonterminal, print the grammar rule used to expand the nonterminal (the left-hand side, followed by a space, followed by each symbol on the right-hand side with a space between each one).
  Special Case: If the right-hand side of the rule is empty, print the left-hand side, a space, and then the special string .EMPTY.
- If the root node of the tree being printed is a token, print the kind, followed by a space, followed by the lexeme.
For each child of the root node, recursively print the child subtree.

Handling Errors (Unsuccessful Parse)

There is one error case that can occur in the LR(1) parsing algorithm. It occurs when you attempt to shift a terminal token, but there is no transition in the SLR(1) DFA corresponding to the terminal. If this occurs, print an error message containing ERROR to standard error and exit normally (without crashing or leaking memory). It does not matter if you produce partial output before printing ERROR.

There are no other error cases in the LR(1) algorithm, and no other error checking is required for this project. The structure of the DFA means that errors cannot occur during a reduce step, for example. If something unexpected happens in another part of the algorithm, it is likely a mistake in your code, or maybe the test input you're using is somehow incorrectly formatted.

Reference Implementation

If using Prescanned Format input, your program's functionality should be equivalent to the wlp4parse course tool.

If using Standard Format input, your program's functionality should be equivalent to running wlp4scan on the input and passing the result into wlp4parse.

Using the Reference Implementations

The following command lets you view the expected output for a WLP4 program provided in Standard Format.

wlp4scan < program.wlp4 | wlp4parse

The following command lets you view the expected output for a WLP4 program provided in Prescanned Format.

wlp4parse < program.prescanned

If you are using the web tools, the WLP4 web tools page has drop-down boxes that let you select whether the input is Standard Format or Prescanned Format, and set the output to wlp4parse output.

You can use cs241.treeprint with the command line option --wlp4 to format the output in the style of Question 10, which may make it easier to understand the structure of the output. This command line option tells cs241.treeprint to use the WLP4 grammar to process the derivation, and therefore you do not need to include explicit CFG and DERIVATION components in the input, and can just directly provide cs241.treeprint with the output from wlp4parse.

The following command lets you view the parse tree (using the Q10 output format) for a WLP4 program provided in Standard Format.

wlp4scan < program.wlp4 | wlp4parse | cs241.treeprint --wlp4

There is also a checkbox on the web version of cs241.treeprint which has the same effect as this command line option.

Example

Consider the following WLP4 program:

int wain(int a, int b) {
  return 241;
}

We will trace through part of the parsing algorithm for this program to illustrate how your program should process the input. (Even for a program this small, a complete trace would be extremely long.)

Partial Trace of the Parsing Algorithm

Scanning this program produces the following sequence of tokens:

INT int
WAIN wain
LPAREN (
INT int
ID a
COMMA ,
INT int
ID b
RPAREN )
LBRACE {
RETURN return
NUM 241
SEMI ;
RBRACE }

To parse this input, we first augment it with "beginning-of-file" and "end-of-file" tokens:

BOF BOF
INT int
WAIN wain
LPAREN (
INT int
ID a
COMMA ,
INT int
ID b
RPAREN )
LBRACE {
RETURN return
NUM 241
SEMI ;
RBRACE }
EOF EOF

We follow the tree-building version of the LR(1) algorithm, using the SLR(1) DFA for WLP4, which is encoded in the "wlp4data" files linked near at the top of the page.

We begin parsing with an empty tree stack, and a state stack containing state 0, the initial state of the WLP4 DFA.

Next Token State Stack Tree Stack Next Action Explanation

BOF BOF 0 Shift BOF / 45
The .REDUCTIONS component of the SLR(1) DFA contains no entries for state 0, so we shift.
The .TRANSITIONS component of the SLR(1) DFA contains the line 0 BOF 45, corresponding to a transition from state 0 to state 45 on BOF.

INT int 0 45
BOF BOF
Shift INT / 68
The .REDUCTIONS component contains no entries for state 45.
The .TRANSITIONS component contains 45 INT 68.

WAIN wain 0 45 68
BOF BOF · INT int
Shift WAIN / 128
The .REDUCTIONS component contains no entries for state 68.
The .TRANSITIONS component contains 68 INT 128.

LPAREN ( 0 45 68 128
BOF BOF · INT int · WAIN wain
Shift LPAREN / 84
The .REDUCTIONS component contains no entries for state 128.
The .TRANSITIONS component contains 128 LPAREN 84.

INT int 0 45 68 128 84
BOF BOF · INT int · WAIN wain · LPAREN (
Shift INT / 17
The .REDUCTIONS component contains no entries for state 84.
The .TRANSITIONS component contains 84 INT 17.

ID a 0 45 68 128 84 17
BOF BOF · INT int · WAIN wain · LPAREN ( · INT int
Reduce by type INT
The .REDUCTIONS component contains 17 9 ID, which means that in state 17, rule number 9 (which is type INT) has ID in the lookahead tag set. Therefore, we reduce by type INT.
Pop INT from the tree stack and 17 from the state stack. The top of the state stack is now 84.
Create a type tree with child INT and push it to the tree stack. Since the top of the state is 84, and the .TRANSITIONS component contains 84 type 48, push 48 to the state stack.
Since we reduced instead of shifting, we do not consume a token from input.

ID a 0 45 68 128 84 48
type BOF BOF · INT int · WAIN wain · LPAREN ( · ╰─INT int
Shift ID / 101
The .REDUCTIONS component contains no entries for state 48.
The .TRANSITIONS component contains 48 ID 101.

COMMA , 0 45 68 128 84 48 101
type BOF BOF · INT int · WAIN wain · LPAREN ( · ╰─INT int · ID a
Reduce by dcl type ID
The .REDUCTIONS component contains 101 14 COMMA, so we should reduce by rule number 14, which is dcl type ID.
Pop the type and ID trees from the tree stack, and 101 and 48 from the state stack. The top of the state stack is now 84.
Create a dcl tree with children type and ID and push it to the tree stack. The .TRANSITIONS component contains 84 dcl 75, so push 75 to the state stack.
Since we reduced instead of shifting, we do not consume a token from input.

COMMA , 0 45 68 128 84 75
dcl ├─type │ ╰─INT int BOF BOF · INT int · WAIN wain · LPAREN ( · ╰─ID a
...
And so on...

When the parsing algorithm terminates, you will have three trees on your stack (the BOF tree, the tree for the non-augmented input, and the EOF tree) and you can manually perform the final reduction to get the full tree.

Stepping Stones

Step 1: Setup

There are a lot of things that your program will need to represent and work with.

The rules of the WLP4 context-free grammar. You should be able to efficiently look up each rule by its number (where 0 is the first rule, 1 is the second rule, etc.) For each rule, it should be convenient to access the left-hand side and right-hand side of the rule, and to print a representation of the rule.
The SLR(1) DFA. Given a the current state of the DFA, and the next symbol of unread input, you should be able to efficiently check whether the next step is a transition (shift) or reduction (reduce); if it is a transition, you should be able to efficiently get the next state to go to, and if it is a reduction, you should be able to efficiently get the rule number to reduce by.
The input sequence, which is a sequence of tokens. While the WLP4 grammar only describes sequences of token kinds, you need to preserve the lexemes to be able to properly print the tree. You should be able to efficiently examine the first token of unread input, and efficiently consume a token from input.
The stacks used by the LR(1) algorithm. Although a stack traditionally only allows you to examine the top element, it is useful if you can print out the entire stack contents for debugging purposes.
The parse tree. Each node should store either a CFG rule (for nonterminal nodes) or a token (for terminal nodes), as well as a data struture containing (pointers to) child nodes. If you use the same tree structure you used in Question 10, then you can use your tree-printing function for debugging!

Here are suggestions for what data structures to use. You might want to try to come up with your own ideas first, and then compare with these suggestions to see how they differ.

Recommended Data Structures

To represent rules, use a struct/class with a string field for the LHS and a list or vector of strings for the RHS. The CFG can just be a vector of rules. It's not necessary to keep track of other information about the CFG (like the set of nonterminals) for this project.
For the SLR(1) DFA, create as struct/class that contains two maps, for transitions and reductions.
- The transitions map should have <state, symbol> keys and state values.
- The reductions map should have <state, symbol> keys and rule-number values.
For the input sequence, in C++, a double-ended queue (std::deque) is a good choice because queues support efficient removal from the front. Although we recommended having your scanner produce a vector of tokens in Project 1B, you might want to change it to a deque for this project (if you're using your P1B scanner rather than the prescanned format).
Technically, you only need a ordinary single-ended queue, but the C++ std::queue container doesn't allow iterating over the queue, which is inconvenient for debugging.
A vector will also work as long as you do not erase from the front of the input sequence (which is slow). To "consume" tokens from the front of a vector, you should keep an index variable pointing to the "current token" and simply advance the index (rather than actually modifying the vector).
For Racket, you can just use a list, but there's a catch. If you read one token at a time and add it to a list with cons, your input sequence will be in reverse order, i.e., the front of the list will contain the last token in the input. This is no big issue though; just reverse the list after constructing it and you are good to go.
For the stacks used by the LR(1) algorithm, a vector is sufficient in C++ (use push_back to push and pop_back to pop). Note that std::stack might seem like a natural choice, but it doesn't allow iteration, which is inconvenient for debugging. In Racket, a list will work (use cons to push and rest to pop).
For the tree stack in C++, use a vector of pointers to trees to avoid potential efficiency issues caused by copying large trees around when doing reductions.
For the parse tree, you can modify the tree structure you used in Question 10. For C++ users, note that manual memory management might be a little tricky for this project, because if a parsing error occurs mid-parse, you have to make sure to clean up every tree currently on the tree stack before exiting. Smart pointers might be a little easier (although they come with their own annoyances).

Once all your structs and classes are set up, populate them with the information from the starter files and standard input:

Read the WLP4 context-free grammar. Skip the .CFG header line. Each line after that represents one rule. Split the line according to whitespace and store the information in your CFG data structure.
Make sure to properly handle the case of an empty right-hand side. If the RHS is .EMPTY, the right-hand side should be literally empty, that is, it should contain zero elements (rather than one element called .EMPTY). However, when you print out such a rule, you do need to print out .EMPTY after printing the left-hand side.
Read the SLR(1) DFA transitions. Skip the .TRANSITIONS header line, then read the transitions line by line.
Read the SLR(1) DFA reductions. Skip the .REDUCTIONS header line, then read the reductions line by line. Note that the second number on the line is not a state, but rather a number referring to a CFG rule.
Read the input sequence. If you are using the Standard Format, you will need to scan the contents of standard input to produce a sequence of tokens. If you are using the Prescanned Format, read from standard input line by line; each line contains one token.
Augment the input sequence. Add a token BOF BOF (the kind and lexeme are both BOF) to the front of the input. Add a token EOF EOF (the kind and lexeme are both EOF) to the end of the input.
Set up the stack(s) used by the LR(1) algorithm: A tree stack for partial parse trees, and a state stack for keeping track of progress in the DFA. The tree stack should initially be empty, and the state stack should initially contain 0, the initial state of the SLR(1) DFA.

With all of this set up, you can dive right into implementing the LR(1) parsing algorithm if you want. The next stepping stones just describe a more structured approach.

Step 2: Reducing

This is the trickiest part, so let's implement it first. Write a function called reduceTrees that takes a CFG rule as a parameter. The function should reduce the current tree stack by the right hand side of the rule.

In C++, your function should modify the tree stack as a side effect. (This might entail passing the tree stack by reference as a parameter, unless your tree stack is a global variable.)

In Racket, you can decide whether to functionally update the tree stack (i.e., return a new tree stack) or use mutation, depending on what programming style you are more comfortable with.

Create a new tree node storing the CFG rule.
Let len be the length of the right-hand side of the CFG rule.
Copy the last len trees from the tree stack into the new node's children. Make sure to copy them in the right order (the tree corresponding to the leftmost symbol of the CFG rule's right-hand-side should be the first child).
Pop the last len trees from the tree stack.
Push the new node to the tree stack.

Now, write a similar function called reduceStates, which takes a CFG rule as a parameter, but reduces the state stack instead of the tree stack.

Let len be the length of the right-hand side of the CFG rule.
Pop the last len states from the state stack.
Look at the current top of the state stack, and the left-hand side of the CFG rule. Look up the transition in the SLR(1) DFA corresponding to this state and symbol. Push the resulting next state from this transition to the top of the state stack.

It's possible to combine these functions into a single "reduce" function that modifies both stacks, but splitting them up will be useful in later stepping stones.

Step 3: Shifting

This is a lot simpler than reducing. Write a function called shift. Calling it should update each of the following as a side effect:

The input sequence of tokens.
The tree stack.
The state stack.

Specifically, the function should do the following

Create a new tree node corresponding to the first token of unread input, and push this node to the tree stack.
Look at the current top of the state stack. Check if there is a DFA transition from this state, with the symbol being the kind of the first token of unread input.
- If there is no such transition, print an error message containing ERROR to standard error and stop the program.
- If there is a transition to a new state, push that new state to the state stack.
Consume the first token from unread input.

Step 4: Testing

You are ready to implement the main algorithm now, but debugging the main algorithm is difficult because even a small WLP4 program has a fairly complex derivation and parse tree. It might help to first test the reduceTrees function in a simpler context to make sure it is implemented correctly.

The reduceTrees function is a little difficult to test because it requires creating a sequence of trees to test it. Since the reduceTrees function doesn't do error checking though, it doesn't really matter what trees you test it with, i.e., your test input doesn't have to correspond to a valid WLP4 program (or portion of a program). Your tests should focus on making sure that the function pops the correct number of trees and connects up the children correctly.

First, write a helper function tokensToTrees that converts a sequence of tokens to a stack of trees. It should consume the tokens from the input sequence in a loop, and for each token, it should create a single-node tree corresponding to that token and add it to the stack.

Then, create a main function that reads the input sequence of tokens, calls tokensToTrees to convert it to a stack of trees, then calls reduceTrees with some CFG rule. The number of trees in the tree stack should be at least as large as the right-hand side of the CFG rule (otherwise, you will pop too many things and crash).

Print the contents of the tree stack before and after calling reduceTrees and check that the changes make sense. Solving Question 10 might be helpful because you can use your solution to print out more easily readable representations of the tree.

Here is an example. The program is provided with the input "a b c d", which is converted to tokens and then trees. Then, the program reduces the tree stack by rule 0, which is start BOF procedures EOF. There are three things on the right hand side, so the program should pop three items from the tree stack, then push a new tree with these three items as its children, in the correct order.

Before Reduce:
[Element 0]
ID a
[Element 1]
ID b
[Element 2]
ID c
[Element 3]
ID d
After Reduce:
[Element 0]
ID a
[Element 1]
start BOF procedures EOF
├─ID b
├─ID c
╰─ID d

We see that the behaviour makes sense. Before the reduce, there are four single-node trees on the stack. After, there are two trees. The first tree, for the token "a", is unmodified because there were four things on the stack and only three elements on the RHS of the rule. The second tree has three children, corresponding to the three trees on top of the stack, in the correct order (b c d). The root of the tree is the rule that we reduced by.

Note that the above sample output assumes the input has not been augmented at this point (BOF and EOF are not added to the tree stack); if the input was augmented then the children would be ID c, ID d and EOF.

Here is another example. We use the same input and setup, but reduce by rule 11, which is dcls .EMPTY.

Before Reduce:
[Element 0]
ID a
[Element 1]
ID b
[Element 2]
ID c
[Element 3]
ID d
After Reduce:
[Element 0]
ID a
[Element 1]
ID b
[Element 2]
ID c
[Element 3]
ID d
[Element 4]
dcls .EMPTY

The behaviour once again makes sense. The right hand side of the rule is empty, so we pop nothing. We then push a new tree, where the root contains the rule, and the tree has no children (because the RHS is empty).

The reduceStates and shift functions might be easier to test in the context of an actual parse, since they rely on taking transitions that actually exist in the SLR(1) DFA.

Step 5: Parsing

Make sure you've done the necessary setup: the input should be augmented with BOF and EOF, the state stack should contain the initial state 0, and the tree stack should be empty.

If your shift, reduceTrees, and reduceStates functions are all working, the main parsing loop is not that complicated. The difficult part will probably be debugging your code if you made a mistake somewhere. Good luck!

Look up the current top of the state stack, and the kind of the first token in unread input, in the SLR(1) DFA reductions. If a rule is found (meaning you are in a reduce state), call reduceTrees and reduceStates to reduce by the rule.
Repeat the previous step until you are no longer in a reduce state.
Call shift, which will consume a token from input and update the tree stack and state stack. Note that this may also result in an error if there's no transition on the next token.
If all input is consumed (EOF has been shifted) and no error was produced, the parse was successful and the main parsing loop ends. Otherwise, repeat from Step 1.

After the main parsing loop, you should have three trees in your tree stack, corresponding to BOF, the parse tree for the non-augmented input, and EOF. Call reduceTrees one last time with rule 0 (start BOF procedures EOF) to obtain the final tree.

Print out the tree as described higher up on this assignment page (under "Producing The Output") and you have a (hopefully) working parser! Yay!

Next Token	State Stack	Tree Stack	Next Action	Explanation
BOF BOF	0		Shift `BOF` / 45	The `.REDUCTIONS` component of the SLR(1) DFA contains no entries for state 0, so we shift. The `.TRANSITIONS` component of the SLR(1) DFA contains the line `0 BOF 45`, corresponding to a transition from state 0 to state 45 on `BOF`.
INT int	0 45	BOF BOF	Shift `INT` / 68	The `.REDUCTIONS` component contains no entries for state 45. The `.TRANSITIONS` component contains `45 INT 68`.
WAIN wain	0 45 68	BOF BOF · INT int	Shift `WAIN` / 128	The `.REDUCTIONS` component contains no entries for state 68. The `.TRANSITIONS` component contains `68 INT 128`.
LPAREN (	0 45 68 128	BOF BOF · INT int · WAIN wain	Shift `LPAREN` / 84	The `.REDUCTIONS` component contains no entries for state 128. The `.TRANSITIONS` component contains `128 LPAREN 84`.
INT int	0 45 68 128 84	BOF BOF · INT int · WAIN wain · LPAREN (	Shift `INT` / 17	The `.REDUCTIONS` component contains no entries for state 84. The `.TRANSITIONS` component contains `84 INT 17`.
ID a	0 45 68 128 84 17	BOF BOF · INT int · WAIN wain · LPAREN ( · INT int	Reduce by `type INT`	The `.REDUCTIONS` component contains `17 9 ID`, which means that in state 17, rule number 9 (which is `type INT`) has ID in the lookahead tag set. Therefore, we reduce by `type INT`. Pop `INT` from the tree stack and 17 from the state stack. The top of the state stack is now 84. Create a `type` tree with child `INT` and push it to the tree stack. Since the top of the state is 84, and the `.TRANSITIONS` component contains `84 type 48`, push 48 to the state stack. Since we reduced instead of shifting, we do not consume a token from input.
ID a	0 45 68 128 84 48	type BOF BOF · INT int · WAIN wain · LPAREN ( · ╰─INT int	Shift `ID` / 101	The `.REDUCTIONS` component contains no entries for state 48. The `.TRANSITIONS` component contains `48 ID 101`.
COMMA ,	0 45 68 128 84 48 101	type BOF BOF · INT int · WAIN wain · LPAREN ( · ╰─INT int · ID a	Reduce by `dcl type ID`	The `.REDUCTIONS` component contains `101 14 COMMA`, so we should reduce by rule number 14, which is `dcl type ID`. Pop the `type` and `ID` trees from the tree stack, and 101 and 48 from the state stack. The top of the state stack is now 84. Create a `dcl` tree with children `type` and `ID` and push it to the tree stack. The `.TRANSITIONS` component contains `84 dcl 75`, so push 75 to the state stack. Since we reduced instead of shifting, we do not consume a token from input.
COMMA ,	0 45 68 128 84 75	dcl ├─type │ ╰─INT int BOF BOF · INT int · WAIN wain · LPAREN ( · ╰─ID a	...	And so on...