Discussion Session 2¶
Grammar¶
- Nonterminal
- Terminal
- Production Rule (Left Hand Side, Right Hand Side)
Parsing¶
Parsing is the procedure of transforming a list of tokens into a tree with tokens as leaves.
Note
This process is also called derivation.
Color | Meaning |
---|---|
Red | Terminal |
Blue | Nonterminal |
Example
The abstract syntax for 1 - 2 - 3 -4
goes as follows:
A good grammar has no ambiguity. Only one tree can be constructed from the token stream.
A good grammar should match human expectation.
Anatomy of LL(k)¶
L: Left-to-right
Examine the input (token stream) left-to-right in one parse.
L: Leftmost-derivation
Create / expand the left most sub-tree first.
Note
R: Rightmost-derivation
k: Lookahead
Inspect the first k tokens before making decision.
Eliminating Left Recursion¶
For productions like this:
It will be turned into
And you can verify that the resulting language is the same.
Warning
This is actually eliminating direct left recursions, and turning them into right recursions. There are methods to eliminate all recursions, direct or indirect, but it is more complicated, and needs some restrictions on the input grammar.
Coding Demo¶
Left-factoring¶
For productions like this:
We turn them into
Example
start ::=exp
// Start exp ::=exp
+term
// Add exp ::=exp
-term
// Minus exp ::=term
// Term term ::= ID // Id term ::= NUM // Num term ::= (exp
) // Group
is turned into
start ::=exp
exp ::=exp
term1
term1 ::= +term
term1 ::= -term
exp ::=term
Do left recursion elimination.
start ::=exp
exp ::=term
exp1
exp1 ::=term1
exp1
exp1 ::= epsilon term1 ::= +term
term1 ::= -term