A compiler's front-end performs several steps to establish the validity of its input. An input stream is scanned for tokens as discussed in Chapter 3. Tokens defined using regular sets could be processed by scanners that were constructed automatically from the regular-set specifications. Just as regular sets guide the actions of an automatically constructed scanner, so also can the actions of the parsers described in Chapter 5 and Chapter 6 be guided by a grammar that specifies a programming language's syntax. Modern programming languages often contain a grammar in their specification as a guide to those who teach, study, or use the language. Based on the analysis discussed in this chapter, such grammars can also participate in the automatic construction of syntax-checking parsers. Programming language rules that are not easily expressed by grammars are enforced during the semantic analyses discussed in Chapter 7, Chapter 8, and Chapter 9.
In Chapter 2, we discuss the rudiments of context-free grammars (CFGs) and define a simple language using a CFG. Here, we formalize the definition and notation for CFGs and present algorithms that analyze such grammars in preparation for the parsing techniques covered in Chapter 5 and Chapter 6.