17.1 CONTEXT-FREE GRAMMAR CONVERSION TO NPDA
Section 7.2 showed one way to convert a context-free grammar to an npda, in which the grammar was restricted to Greibach normal form. Then Section 16.1 showed another way to convert a context-free grammar to an npda, modeling how LL parsing works. We now see a third way to convert a context-free grammar to an npda, modeling how LR parsing works. In both LL parsing and LR parsing, the context-free grammar is not restricted to any form.
We start with a context-free grammar and design the npda to model how the LR parsing process works. The process starts with an empty stack, shifting symbols from the input string onto the stack until the right-hand side of a production is recognized. The process then ...
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.
