CHAPTER 6
SIMPLIFICATION OF CONTEXT-FREE GRAMMARS AND NORMAL FORMS
CHAPTER SUMMARY
In Chapter 5, we encountered the important issues of membership and parsing for context-free languages. While brute force parsing is always possible, it is very inefficient and therefore not practical. For actual applications, such as compilers, we need more efficient methods. This is made difficult by the unrestricted form of the right side of a context-free production, so we investigate if we can restrict the right side without reducing the power of the grammar.
The first thing we can do is to show that we need not worry about certain types of productions. In particular, if a context-free grammar has in it productions that have λ on the right, we can find an ...
Get An Introduction to Formal Languages and Automata, 6th 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.
