LR Parser Flashcards
LR Parser
input is scanned left-to-right and a rightmost derivation is constructed
SLR
simple LR
LALR
look ahead LR
What is the most general grammar?
LR
What is the most specific grammar?
SLR
LR parsers to time and space __________ in the size of input
linear
Which is more powerful, LR or LL?
LR
Which is more natural, LR or LL?
LR
Disadvantages of LR grammar?
harder to write parser, larger table size, more difficult error repair
What does the stack represent in a bottom up parser?
summary of input already seen
shift operation
shif the next input token from the input to the top of the stack
reduce operation
pop N symbols on stack that match a RHS of production and push non-term
What type of derivation is constructed for LR?
reverse rightmost derivation
reduction
each step of building the parse tree (add a new nonterm as parent of subtree)
What actions can an LR parser perform?
shift, reduce, accept, reject
What are symbols pushed onto LR parser’s stack?
states
2 tables of LR parsers:
action table
goto table
action table
indexed by the top-of-stack symbol and current token, tells which action to perform
What is different for different LR parsers?
definition of an item
number of states in underlying state machine
amount of information in a state
item
production with a dot somewhere on the rhs
for an item to the right of a dot
look for productions with a LHS of that symbol, then add to the closure
Closure(I) tells you what?
Goto(I,X) tells you what?
where we might be in the parse
where we might be after parsing X
When is a grammar not in SLR(1)
When there is a conflict in the SLR Action Table
2 types of conflicts for
shift/reduce
reduce/reduce
shift/reduce
it is not possible to determine based on the top-of-stack state symbol and current token to shift or reduce
reduce/reduce
not possible to determine which grammar rule to reduce by
