Quiz 4 Flashcards
What algorithm do you use for bottom up parsing?
Shift Reduce parsing
What does it mean if you can generate a conflict-free parsing table for a grammar G?
It means the grammar is LL(1).
What is a conflict in an LL(1) parsing table?
A conflict occurs when a table entry has more than one choice, meaning the grammar is not LL(1).
What is non-recursive predictive parsing?
It is when a predictive parser runs from a table without using non-recursive predictive parsing
What is bottom-up parsing?
Bottom-up parsing constructs a parse tree for an input string starting from the leaves (terminal symbols) and works up to the root (starting symbol S).
What is shift-reduce parsing?
Shift-reduce parsing uses the shift and reduce strategy to derive the start symbol from an input string and recognizes LR grammars.
What are the four operations of a shift-reduce parser?
Shift, Reduce, Accept, and Error.
What happens during the Shift operation in shift-reduce parsing?
A token is moved from the input to the stack.
What happens during the Reduce operation in shift-reduce parsing?
When a sequence of tokens on the stack matches the RHS of a production, it is replaced with the LHS non-terminal.
What is a handle in shift-reduce parsing?
A handle is a substring that matches the RHS of a production.
What are the benefits of shift-reduce parsing?
It doesn’t require worrying about left recursion, can recognize more grammars, handle some ambiguity, and parse tables can be generated with tooling.
What are the limitations of shift-reduce parsing?
Rules are more complex and harder to understand, must be generated with tooling, memory-intensive due to large tables, and can have conflicts when minimized.
What types of grammars are parsed by LR parsers?
LR grammars.
What strategy do LR parsers use?
Shift-reduce parsing.
What do LR items allow a parser to do?
They allow the parser to know when to shift or reduce.
What are inadequate states in LR parsing?
States with shift/reduce or reduce/reduce conflicts.
What causes inadequate states in LR parsing?
Issues with the grammar or inappropriate table construction methods.
What is the key difference between LR(0) and LR(1) items?
LR(0) items are simpler because they have no lookahead, whereas LR(1) items are more complex because they incorporate lookahead.
What is the key difference between LR(0) and LR(1) items?
LR(0) items are simpler because they have no lookahead, whereas LR(1) items are more complex because they incorporate lookahead.
What are the different LR grammars? (6)
SLR, CLR, LR, LALR, LLR, GLR
