17.3 DFA MODELS THE LR PARSING STACK
In LR parsing, in order to choose whether to shift or reduce for the next operation, we need to know when multiple symbols on top of the stack form the right-hand side of a production. However, we do not want to look down into the stack past the top symbol. Instead, for a context-free grammar, we build a dfa to model all the possible combinations of variables and terminals that could be on the stack. For each state in the dfa, we associate a set of items from the grammar with that state to indicate which symbols are on the stack at this point and which symbols are not yet on the stack. Then when we parse a string, we trace the string through the dfa. The final states in the dfa identify when a right-hand ...
Get An Introduction to Formal Languages and Automata, 7th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
