Sample solution
Both process input tokens left to right and permit k tokens of lookahead when
selecting what rule to apply next.
LL uses left recursion and is typically applied as part of top-down parsing,
while LR uses right recursion and is typically applied as part of bottom-up parsing.
Note: both require the grammar be unambigous, and in terms of power
(the breadth of languages they can recognize) LR(k) = LR(1) > LL(k) > LL(1)
|
Sample solution Recursive descent uses a collection of parsing functions, typically one per core language structure, which are often hand-crafted to check for tokens in fixed expected positions and which call other parsing functions to process substructures. The grammar 'rule choices' are reflected in the logic structure of the parsing algorithm for the relevant program component (non-terminal). The stack-based approach relies on the system stack to store 'in-progress' parses: which tokens/nonterminals are still to be matched against remaining input tokens. It's rule choices determine which tokens/nonterminals are to be added to the stack to reflect the expected form of a current non-terminal. |
Sample solution The action table considers the current top-of-stack configuration (represented as a state) and the upcoming input token, and dictates which rule is to be applied next (shifts or reduces). On a reduce, the goto table considers top-of-stack state and the nonterminal being reduced and identifies what the new top-of-stack configuration should be. Together the two of them allow the stack-driven algorithm to direct the exact sequence of choices to be applied as parsing progresses. |
Sample solution It should accept when the result of a rule leaves nothing in the input and nothing in the stack to be popped into current: indicating we have consumed all input and have also processed everything derived from the original prog non-terminal. |
Grammar
prog: mult;
mult: single mult;
mult: single;
single: square;
single: round;
single: IDENT;
square: LSQ mult RSQ
round: LRD mult RRD
Tokens
IDENT: [a-z]
RRD: "("
LRD: ")"
LSQ: "["
RSQ: "]"
| Algorithm
current = starting nonterminal
stack is initially empty
repeat until done
if current is a token then match against the next input token
if they don't match then reject
otherwise consume the input
otherwise (current is a nonterminal)
pick a rule whose LHS matches current (basing your choice on the next input token)
push the RHS elements of the rule (right-to-left)
pop the top of stack item into current
Input:
[ x ] ( ( y ) [ z ] )
|
Sample solution (with apologies for how long this one turned out!) Current Remaining input Top of stack Rule choices prog [x]((y)[z]) - prog->mult mult [x]((y)[z]) - mult->single mult single [x]((y)[z]) mult single->square square [x]((y)[z]) mult square->LSQ mult RSQ LSQ [x]((y)[z]) mult RSQ mult match/consume mult x]((y)[z]) mult RSQ mult->single single x]((y)[z]) mult RSQ single->IDENT IDENT x]((y)[z]) mult RSQ match/consume RSQ ]((y)[z]) mult match/consume mult ((y)[z]) - mult->single single ((y)[z]) - single->round round ((y)[z]) - round->LRD mult RRD LRD ((y)[z]) RRD mult match/consume mult (y)[z]) RRD mult->single mult single (y)[z]) RRD mult single->round round (y)[z]) RRD mult round->LRD mult RRD LRD (y)[z]) RRD mult RRD mult match/consume mult y)[z]) RRD mult RRD mult->single single y)[z]) RRD mult RRD single->IDENT IDENT y)[z]) RRD mult RRD match/consume RRD )[z]) RRD mult match/consume mult [z]) RRD mult->single single [z]) RRD single->square square [z]) RRD square->LSQ mult RSQ LSQ [z]) RRD RSQ mult match/consume mult z]) RRD RSQ mult->single single z]) RRD RSQ single->IDENT IDENT z]) RRD RSQ match/consume RSQ ]) RRD match/consume RRD ) - match/consume - - - ACCEPT! |