CFG, Derivations, Parse Trees & Ambiguity
Open in the Padhaiko appContext-Free Grammar, Derivations, Parse Trees and Ambiguity
In formal language theory, regular expressions and finite automata can describe many simple patterns, but they fail to capture recursive, nested structures such as balanced parentheses or matching counts (e.g., ). Context-free grammars (CFGs) provide a richer, more powerful generative mechanism capable of describing hierarchical block structure, nested syntax, and arithmetic expressions essential for compiler construction.
3.1 Introduction to Context-Free Grammar (CFG) and Context-Free Language
Consider the regular expression , which denotes all strings over beginning with and ending with . Using production rules with a start non-terminal and an auxiliary non-terminal , we can generate this language via:
To generate the string , we substitute by , regardless of the symbols surrounding . Because production replacements depend solely on the single variable being replaced and not on surrounding contextual symbols, the system is termed context-free.
Context-Free Grammar (CFG)
A Context-Free Grammar is formally defined as a 4-tuple:
where:
- is a finite set of non-terminals (variables).
- is a finite set of terminal symbols, disjoint from ().
- is a finite set of production rules of the form , where and .
- is the distinguished start symbol.
(Note: Some texts denote the total alphabet as and write rules as , treating as non-terminals and as terminals).
Applications of Context-Free Grammars
- Compilers and Parsing: CFGs serve as the mathematical foundation for syntactic analysis in modern compilers (such as GCC, Clang, and javac).
- Programming Language Specification: The syntax of programming languages (blocks, control flow, functions) is formally specified using CFGs.
- Parser Generation: Grammars are directly converted by parser generators (like Yacc, Bison, and ANTLR) into syntax tree builders.
- Document Type Definitions: XML DTDs and schema validators define valid nesting of tags through context-free rules.
3.1.1 Terminologies: Derivations, Languages & Sentential Forms
Derivations, Context-Free Language, and Sentential Forms
Let be a context-free grammar:
- Derivation Step (): If , and , then replacing yields .
- Derivation (): The reflexive, transitive closure of . If , we write .
- Sentential Form: Any string such that . If (contains only terminals), it is called a sentence.
- Context-Free Language (): The set of all terminal strings generated from the start symbol:
Worked Out Examples: Designing CFGs
1
Let where , , and rules are:
Find the context-free language .
Applying the terminal production :
Applying the recursive production once followed by :
Applying repeatedly times followed by :
The language generated by grammar consists of all non-empty strings of matching 's and 's:
2
Let where , , and production rules:
Find the context-free language .
The base production gives:
Each application of prepends two 's before :
The language generated by grammar is:
3
Write a Context-Free Grammar for the language:
The condition means the number of leading 's is greater than or equal to the number of trailing 's. We can decompose this into two phases:
- Matching pairs of and ().
- Surplus leading 's ( where ).
Let generate either a balanced and , an extra leading , or terminate at :
The CFG is with productions:
4
Write a CFG for the language:
A string with equal numbers of 's and 's can be empty (), or start with and end with , or start with and end with , or be the concatenation of two balanced substrings ():
The context-free grammar is with rules:
5
Write Context-Free Grammars for each of the following languages over :
- (odd-length palindromes with center marker )
- (even-length palindromes)
Matching outer symbols symmetrically until reaching the center terminal or :
Matching outer symbols symmetrically until shrinking to the empty string:
Every step adds any combination of two terminal symbols, ending at :
Symmetrically adding pairs of symbols and ending at a single terminal or :
The CFG production sets are:
3.2 Types of Derivations, Parse Trees & Ambiguity
Leftmost and Rightmost Derivations
- Leftmost Derivation (): A derivation in which the leftmost non-terminal variable in the current sentential form is replaced at every single step.
- Rightmost Derivation (): A derivation in which the rightmost non-terminal variable in the current sentential form is replaced at every single step.
Parse Tree (Derivation Tree)
An ordered tree representing the hierarchical syntactic structure of a derivation in grammar :
- The root node is labeled with the start symbol .
- Each interior node is labeled with a non-terminal variable .
- If an interior node has children from left to right, then .
- Leaf nodes are labeled with terminal symbols or the empty string .
- The concatenation of the leaves from left to right forms the yield of the tree.
6
Let be the grammar for balanced parentheses:
Show the leftmost derivation, rightmost derivation, and draw the parse tree for the string:
Expanding the leftmost non-terminal variable at each step:
- S
- ⇒SSS → SS
- ⇒(S)SS → (S)
- ⇒((S))SS → (S)
- ⇒(())SS → ε
- ⇒(())(S)S → (S)
- ⇒(())()S → ε
Expanding the rightmost non-terminal variable at each step:
The hierarchical parse tree for :
The string has identical yield in both leftmost and rightmost derivations, correctly captured by the derivation tree.
7
Let with production rules:
Show the leftmost and rightmost derivations and draw the parse tree for the string .
Expanding variables from left to right:
Expanding variables from right to left:
The derivations yield via , , and .
8
Using the balanced parentheses grammar:
Derive the string and construct its parse tree.
The string is generated by splitting and closing both child clauses using .
9
Capture the arithmetic expression using a Context-Free Grammar and draw its parse tree.
Let where:
Deriving the expression with multiplication at the root level to match the grouping:
The production set generates reflecting parenthesis grouping first, followed by outer multiplication.
3.2.3 Ambiguity in CFG
Ambiguity and Inherent Ambiguity
- Ambiguous Grammar: A context-free grammar is called ambiguous if there exists at least one string that possesses two or more distinct parse trees (or equivalently, two or more distinct leftmost derivations, or two or more distinct rightmost derivations).
- Inherent Ambiguity: A context-free language is said to be inherently ambiguous if every grammar that generates is ambiguous. A classic example is:
10
Demonstrate that the following grammar is ambiguous for the string :
Deriving via groups 's with 's and 's with 's ( and ):
- S
- ⇒ABS → AB
- ⇒aAbBA → aAb
- ⇒aabbBA → ab
- ⇒aabbcBdB → cBd
- ⇒aabbccddB → cd
Deriving via groups outer 's with 's and inner 's with 's ( and ):
- S
- ⇒CS → C
- ⇒aCdC → aCd
- ⇒aaDddC → aDd
- ⇒aabDcddD → bDc
- ⇒aabbccddD → bc
Because there are two distinct leftmost derivations for the string , the grammar produces two distinct parse trees.
Since the terminal string admits two distinct leftmost derivations and parse trees, the grammar is ambiguous.
3.3 Regular Grammars
Regular Grammar
A grammar is called a regular grammar if each production has at most one non-terminal on its right-hand side, placed strictly at the end or beginning:
- Right-Linear Grammar: Every rule has the form or , where and .
- Left-Linear Grammar: Every rule has the form or , where and .
Every regular grammar generates a regular language and can be transformed into an equivalent Finite Automaton.
11
Convert the following right-linear regular grammar into an equivalent Finite Automaton:
Each non-terminal variable corresponds to a state in the automaton:
- is the start state.
- is an intermediate state.
- A new final state is introduced for terminal-only rules:
- (accepting)
- (accepting)
| State | 0 | 1 |
|---|---|---|
| →S | {S} | {A, F} |
| A | {A, F} | {A} |
| *F | ∅ | ∅ |
- Machine-checked
- ✓ accepts 1
- ✓ accepts 01
- ✓ accepts 10
- ✓ accepts 00110
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 11
The resulting NFA has states , start state , and accepting state .
12
Construct the leftmost derivation, rightmost derivation, and parse tree for the string using the grammar where:
Both leftmost and rightmost derivations produce the identical derivation tree.
The string is successfully derived with identical parse tree structure across leftmost and rightmost expansions.
Solutions to Important Examination Questions
13
Construct a context-free grammar for the language:
over . Derive the string and draw its corresponding parse tree. [2082 Baishakh]
The condition with requires strictly more 's than 's. The minimal valid string is . We decompose the grammar into balanced 's and 's generated by , followed by extra trailing 's generated by :
Derivation of ():
The CFG is . String is verified with the parse tree above.
14
Construct a CFG for the language:
Test your grammar to generate and draw its parse tree. [2081 Chaitra]
The language has nested dependencies: outer 's match outer 's, while inner 's match inner 's.
- (matching outer )
- (matching inner )
Generating ():
The grammar generates through nested variable expansion.
15
Construct a CFG for the palindrome language:
Also use the grammar to derive the string and draw its parse tree. [2076 Ashwin]
The language contains all even-length palindromes over . Each step wraps in matching symbols:
The CFG is . Derivation and parse tree for are established.
16
Write a context-free grammar for:
Use leftmost and rightmost derivations to generate and draw its parse tree. [2075 Chaitra]
Production rules: .
Leftmost derivation for :
For this sequence of single-variable expansions, the rightmost derivation proceeds through the exact same sentential forms:
The grammar generates through symmetric pairing with derivation tree shown above.
17
Write a context-free grammar for:
over . Use leftmost and rightmost derivations to generate and draw its parse tree. [2075 Ashwin]
The number of leading 's equals the number of trailing 's (), while intermediate 's () are independent:
Leftmost derivation:
Because only one variable exists at each intermediate stage, the rightmost derivation is identical.
The grammar successfully generates .
18
Write a CFG for all palindromes over and draw parse trees for an even-length and an odd-length palindrome. [2073 Chaitra]
Palindromes can be even-length (terminating in ) or odd-length (terminating in or ):
The CFG generates all palindromes. The even palindrome terminates on , while the odd palindrome terminates on .
19
Construct a CFG for . Generate the string and construct its parse tree. [2073 Shrawan]
For each generated on the left, exactly two 's must be generated on the right:
(or for )
Using :
The grammar generates with the parse tree above.
20
Write a CFG for the regular expression:
[2072 Chaitra]
The expression is a concatenation of three parts:
- : zero or more 's (represented by variable ).
- : a single (represented by variable ).
- : any string over (represented by variable ).
The required context-free grammar is:
Exercise Set: CFG, Derivations and Ambiguity
Exercise Questions: CFG, Derivations & Ambiguity
Formally define a Context-Free Grammar (CFG). [2082 Baishakh, 2080 Baishakh]
Formal 4-Tuple Specification: A Context-Free Grammar (CFG) is formally defined as a 4-tuple:
where:
- is a finite, non-empty set of variables (also called non-terminals or syntactic categories). Each variable defines a sub-language.
- is a finite set of terminal symbols (the alphabet of the generated language), disjoint from ().
- is a finite set of production rules (rewrite rules). Each production has the form:
The left-hand side contains exactly one variable , and the right-hand side is a string of terminals and/or variables (including the empty string ).
- is the distinguished start symbol from which all derivations initiate.
The grammar is called context-free because replacing non-terminal by depends solely on , without regard to surrounding context symbols.
Derivations and Language Generated: Let . If rule , we write:
denoting that directly derives in one step. The reflexive and transitive closure of is denoted by .
The language generated by , denoted , is the set of all terminal strings derived from start symbol :
A language is a Context-Free Language (CFL) if there exists a CFG such that .
Concrete Example and Derivation: Consider grammar with productions:
To generate the string :
- S
- ⇒aSbS → aSb
- ⇒aaSbbS → aSb
- ⇒aabbS → ε
A Context-Free Grammar is a 4-tuple where is a finite set of variables (non-terminals), is a finite set of terminal symbols disjoint from , is a finite set of productions of the form (), and is the start symbol. The language generated is .
What is inherent ambiguity in a context-free grammar? [2079 Bhadra, 2079 Baishakh]
Definition of Inherent Ambiguity: While ambiguity in a specific CFG can often be eliminated by restructuring production rules (such as enforcing operator precedence), some context-free languages possess no unambiguous grammar whatsoever.
A context-free language is called inherently ambiguous if every context-free grammar that generates (i.e. ) is ambiguous. That is, for every CFG for , there exists at least one string that has two or more distinct parse trees (or distinct leftmost derivations).
Canonical Example: : This language is the union of two simpler context-free languages:
- (matching 's and 's)
- (matching 's and 's)
A natural CFG generating is:
Two Distinct Leftmost Derivations for :
The string belongs to both and , yielding two distinct parse trees:
- Derivation 1 (via , grouping 's and 's first):
- Derivation 2 (via , grouping 's and 's first):
Because every CFG generating must generate strings of with multiple parse trees, the language is inherently ambiguous.
A context-free language is inherently ambiguous if every context-free grammar that generates is ambiguous (i.e., every possible grammar for yields at least two distinct parse trees for some string ). An example is , where every string of the form inevitably has two independent derivations.
What is ambiguity in a Context-Free Grammar? [2078 Kartik]
Definition of Grammar Ambiguity: A Context-Free Grammar is called ambiguous if there exists at least one string for which there are:
- Two or more distinct parse trees (derivation trees), or equivalently
- Two or more distinct leftmost derivations, or
- Two or more distinct rightmost derivations.
If every string in has exactly one unique parse tree, the grammar is unambiguous.
Demonstration on Arithmetic Expressions: Consider the standard expression grammar :
For the input string , two distinct leftmost derivations exist:
- Leftmost Derivation 1 (evaluating at root, giving higher precedence):
- E
- ⇒E+EE → E + E
- ⇒id + EE → id
- ⇒id + E * EE → E * E
- ⇒id + id * EE → id
- ⇒id + id * idE → id
- Leftmost Derivation 2 (evaluating at root, giving higher precedence):
- E
- ⇒E*EE → E * E
- ⇒E+E*EE → E + E
- ⇒id + E * EE → id
- ⇒id + id * EE → id
- ⇒id + id * idE → id
Significance and Disambiguation: Ambiguity creates semantic uncertainty in compiler design because different parse trees correspond to different abstract syntax trees (e.g. vs ).
To remove ambiguity, the grammar is stratified into levels that enforce operator precedence and associativity:
In this unambiguous grammar, multiplication binds tighter than addition , and both operators are left-associative, yielding a unique parse tree for every valid expression.
A CFG is ambiguous if there exists at least one terminal string in its language that has two or more distinct parse trees, or equivalently two or more distinct leftmost (or rightmost) derivations. Ambiguity can often be eliminated by structuring production rules to enforce operator precedence and associativity.