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.