Context-free grammars in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the Components of a Context-Free Grammar

Which of the following correctly lists the four components that make up a context-free grammar (CFG)?

A A set of terminals, a set of states, a start state, and a transition function

B A set of terminals, a set of non-terminals, a start symbol, and a set of production rules

C A set of terminals, a set of non-terminals, a set of states, and a transition function

D A set of terminals, a start symbol, a set of production rules, and a transition function

💡 Hint

Think about what defines the structure and rules of a language in CFG.

A context-free grammar consists of terminals (basic symbols), non-terminals (syntactic variables), a start symbol (where derivation begins), and production rules (how symbols can be replaced).

📋 Factual

intermediate

Derivation in Context-Free Grammars

What does a derivation in a context-free grammar represent?

A A sequence of production rule applications to generate a string from the start symbol

B A sequence of states visited in a finite automaton

C A set of terminals that cannot be replaced further

D A function mapping terminals to non-terminals

💡 Hint

Consider how strings are formed from the start symbol using rules.

Derivation is the process of applying production rules step-by-step to replace non-terminals and produce a string of terminals starting from the start symbol.

🔍 Analysis

advanced

Identifying Ambiguity in a CFG

Given the grammar with productions:

S → S + S | S * S | ( S ) | a

Which statement is true about this grammar?

A The grammar is ambiguous because it generates strings with unmatched parentheses

B The grammar is unambiguous because it uses only terminals and no non-terminals

C The grammar is unambiguous because each string has a unique parse tree

D The grammar is ambiguous because the string 'a + a * a' has more than one parse tree

💡 Hint

Try to draw parse trees for the string 'a + a * a'.

This grammar is ambiguous because the expression 'a + a * a' can be parsed in multiple ways, reflecting different operator precedence and associativity.

❓ Comparison

advanced

Comparing Context-Free and Regular Grammars

Which of the following statements correctly distinguishes context-free grammars (CFGs) from regular grammars?

A Regular grammars allow production rules with multiple non-terminals on the left side

B Regular grammars can generate all languages that CFGs can generate

C CFGs can generate languages with nested structures, while regular grammars cannot

D CFGs are less powerful than regular grammars in language generation

💡 Hint

Think about the kinds of patterns each grammar type can describe.

CFGs can describe languages with nested or recursive patterns (like balanced parentheses), which regular grammars cannot handle.

❓ Reasoning

expert

Determining the Language Generated by a CFG

Consider the CFG with productions:

S → a S b | ε

What language does this grammar generate?

A All strings with equal numbers of 'a's followed by equal numbers of 'b's

B All strings with any number of 'a's followed by any number of 'b's

C All strings with equal numbers of 'a's and 'b's in any order

D All strings consisting only of 'a's

💡 Hint

Look at how the production adds 'a' and 'b' in pairs recursively.

The grammar generates strings where each 'a' is matched by a corresponding 'b' later, ensuring equal numbers in the correct order.

Practice

1. What is a context-free grammar primarily used for in compiler design?

easy

A. To optimize machine code

B. To execute programs

C. To manage memory allocation

D. To define the syntax rules of programming languages

Solution

1. Step 1: Understand the role of context-free grammar

   Context-free grammars describe the structure and syntax of languages, especially programming languages.

2. Step 2: Relate to compiler design

   Compilers use these grammars to parse and check if code follows language rules.

3. Final Answer:

   To define the syntax rules of programming languages -> Option D

4. Quick Check:

   Context-free grammar = syntax rules [OK]

Hint: Context-free grammar defines language syntax, not execution [OK]

Common Mistakes:

• Confusing grammar with code execution
• Thinking grammar manages memory
• Mixing syntax rules with optimization

2. Which of the following is the correct way to write a production rule in a context-free grammar?

easy

A. S -> aSb | ε

B. S = aSb | ε

C. S := aSb + ε

D. S => aSb & ε

Solution

1. Step 1: Identify standard notation for production rules

   Context-free grammar production rules use '->' to show how a symbol can be replaced.

2. Step 2: Check each option

   S -> aSb | ε uses '->' correctly; others use incorrect symbols like '=', ':=', '=>' or '&'.

3. Final Answer:

   S -> aSb | ε -> Option A

4. Quick Check:

   Production rule uses '->' [OK]

Hint: Look for '->' symbol in production rules [OK]

Common Mistakes:

• Using '=' instead of '->'
• Confusing ':=' with grammar syntax
• Using symbols like '&' or '+' incorrectly

3. Given the grammar with rules:
S -> aSb | ε
What is the language generated by this grammar?

medium

A. All strings with only 'a's

B. All strings with any number of 'a's and 'b's in any order

C. All strings with equal number of 'a's followed by 'b's

D. All strings with only 'b's

Solution

1. Step 1: Analyze the production rule

   The rule S -> aSb | ε means S can be empty or 'a' followed by S followed by 'b'.

2. Step 2: Understand generated strings

   This produces strings with matching 'a's at the start and 'b's at the end, equal in number.

3. Final Answer:

   All strings with equal number of 'a's followed by 'b's -> Option C

4. Quick Check:

   Grammar generates balanced 'a's and 'b's [OK]

Hint: Match 'a' and 'b' pairs from outside in [OK]

Common Mistakes:

• Assuming any order of 'a' and 'b'
• Ignoring the empty string ε
• Thinking only 'a's or only 'b's are generated

4. Identify the error in the following grammar rule:
A -> aA | bB
B -> bB | c
C -> cC | a

medium

A. Terminal symbols are incorrectly capitalized

B. Non-terminal C is never used in any production

C. Production rules use wrong arrow symbol

D. Grammar contains left recursion

Solution

1. Step 1: Check usage of non-terminals

   Non-terminal C is defined but never appears on the right side of any rule, so it is unreachable.

2. Step 2: Verify other options

   Arrows are correct (->), terminals are lowercase (a,b,c), no left recursion (all rules start with terminals).

3. Final Answer:

   Non-terminal C is never used in any production -> Option B

4. Quick Check:

   Unused non-terminal = error [OK]

Hint: Check if all non-terminals appear on right side somewhere [OK]

Common Mistakes:

• Confusing terminals and non-terminals capitalization
• Thinking left recursion is always an error
• Ignoring unreachable rules

5. Consider the grammar:
S -> AB | BC
A -> aA | a
B -> bB | b
C -> cC | c
Which of the following strings can be generated by this grammar?

hard

A. "aabbb"

B. "abcc"

C. "abbc"

D. "acb"

Solution

1. Step 1: Understand the grammar rules

   S can produce AB or BC. A produces one or more 'a's, B produces one or more 'b's, C produces one or more 'c's.

2. Step 2: Check each string

   "abbc" can: S -> AB, A -> a, B -> bB -> bC? No, B cannot produce 'c'. But let's check carefully.
   "abcc" cannot: starts with 'a' so AB, but 'bcc' not all 'b's; BC starts with 'b'.
   "aabbb" cannot: S -> AB, A -> aA -> 'aa', B -> bB -> 'bbb' but string is 'aabbb' which matches.
   "acb" cannot: 'c' misplaced, no matching AB or BC.

3. Final Answer:

   "aabbb" -> Option A

4. Quick Check:

   Check string matches AB or BC pattern [OK]

Hint: Match string parts to A, B, C sequences in order [OK]

Common Mistakes:

• Ignoring that B and C produce only their own letters
• Assuming mixed letters in one non-terminal
• Not checking both AB and BC options