LL(1)
Overview
In this assignment, you reimplement the previous parser project using a table-driven LL(1) implementation. The goal is to replace the previous parser with a table-driven LL(1) version without changing the language definition or the observable behavior of the project.
Your new implementation must produce the same Abstract Syntax Tree (AST) as your earlier projects for all valid inputs. In other words, for any test case used previously, the AST output of this assignment should be structurally identical to that produced before.
Note: for convenience of the recursive descent parser implementation, all binary operators are right associative.
Caveats to building an AST
Grammar Structure vs. Control Structure
In recursive‑descent parsing, the call stack implicitly:
- Enforces precedence
- Ensures correct grouping
- Determines combination order
In a table‑driven parser, these properties must be managed explicitly. Note: Translating grammar rules mechanically often produces incorrect ASTs.
Semantic Actions Must Be Explicit
Because the parser is non‑recursive:
- AST construction must be handled by explicit semantic actions
- Actions should be treated as symbols pushed onto the parse stack
- Actions execute when popped, just like grammar symbols
You may not rely on: - Function return values - Implicit sequencing from recursion
Operator Handling Requires Delayed Construction
For productions such as:
E' -> + T E'You must wait until T is completely parsed before constructing the
+ AST node.
Common mistake: - Creating operator nodes before the right operand exists
Correct approach: - Accumulate the left operand - Parse the right operand - Combine only when both are available
epsilon‑Productions Still Matter Semantically
Although epsilon does not consume input, epsilon‑productions often:
- Signal the end of an operator chain
- Trigger the return of accumulated subtrees
Failure to handle epsilon correctly can result in: - Missing nodes - Duplicated nodes - Partial ASTs
Use a Separate Semantic Stack (Strongly Recommended)
Maintain:
- A parse stack for grammar symbols
- A semantic stack for AST nodes
This separation simplifies reasoning, debugging, and validation.
Common Failure Modes
Watch for:
- AST nodes created too early
- Incorrect child ordering
- Accidental right‑associativity
- Extra nodes for grammar artifacts
- Missing nodes caused by epsilon‑productions
Turning in the Assignment
To submit your assignment, create a zip file of a DIRECTORY named
ll1-handin containing ONLY the files required to build the
project and a README file that includes the left-factored grammar and
the FIRST and FOLLOW sets. Then submit that file to the appropriate
folder on D2L.