An Introduction to Formal Languages and Automata, 7th Edition

© VS148/Shutterstock.

CHAPTER 17LR PARSING

CHAPTER SUMMARY

In Section 15.2 we saw how bottom-up parsers work with respect to derivation trees. Starting with symbols from the string, we build the tree from the bottom to the top, finishing with the start symbol. Turning the tree over shows that the tree has the same structure as the derivation trees for top-down parsers.

This chapter explores LR parsing, an efficient bottom-up parsing method. LR parsing starts with the string, applies the productions in reverse order, and eventually derives the start symbol. Along the way, each production in the derivation has its right-hand side replaced with ...