16.1 CONTEXT-FREE GRAMMAR CONVERSION TO NONDETERMINISTIC PUSHDOWN AUTOMATON
Pushdown Automata for LL Parsing
Given a context-free grammar, we create an equivalent nondeterministic pushdown automaton (npda) that models the LL parsing process. We previously saw in Section 7.2 an algorithm for converting any context-free grammar to an npda. In that algorithm, we first had to convert the context-free grammar to Greibach normal form. Here we use a different approach where the context-free grammar is not restricted to any form.
We design the npda in the following way. Given a grammar G = (V, T, S, P), parsing starts with the start symbol and repeatedly replaces a variable by one of its rules. For a rule A → w ∈ P with A ∈ V and w ∈ (V ∪ T)*, the ...
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.
