Simulating Derivations of Context-Free Grammar

Abstract As opposed to automata, grammars are used to generate strings instead of identifying them. The use of regular languages and finite automata is simple and restrictive. Context-Free Grammar or CFG is a formal grammar used to produce all possible combinations of strings in a given formal language. Context-Free Grammar consists of a set of grammar rules which are finite and predetermined. In computer science, a CFG is said to be ambiguous if a given string could be generated by the grammar in more than one way. Syntax of high-level programming languages, Parser programs and compiler design can be described using Context-Free Grammar. This paper presents a method to implement the derivations of Context-Free Grammar using Python. By applying an appropriate production rule to the leftmost non-terminal in each step, a leftmost derivation is obtained. On the contrary, by applying the appropriate production rule to the rightmost non-terminal in each step, a rightmost derivation is obtained.