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.
