Automata Theory and Formal Languages

4: Context-free grammar

Abstract

This is the right place to introduce the concept of context-free languages and context-free grammars. Context-free grammars play a vital role in the compiler construction process. Implementation of a parser in the compiler construction is achieved by context-free grammars. This chapter gives deep insights on context-free grammars and languages. We introduce formal notations for context-free grammars followed by string derivations. We present two types of derivations, leftmost derivation and rightmost derivation. We also present a method to check the ambiguity of a context-free grammar. The concept of a parse tree plays an important role in ambiguity checking. Further, we describe the CFG simplification methods, ...