Context-free grammars in Compiler Design - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a context-free grammar (CFG)?

A context-free grammar is a set of rules used to describe the structure of languages. It consists of terminals, non-terminals, a start symbol, and production rules that replace non-terminals with groups of terminals and non-terminals.

beginner

What are the four main components of a context-free grammar?

The four main components are: 1) A set of terminals (basic symbols), 2) A set of non-terminals (symbols that can be replaced), 3) A start symbol (a special non-terminal where parsing begins), and 4) Production rules (which define how non-terminals can be replaced).

beginner

Explain the role of production rules in a CFG.

Production rules define how non-terminal symbols can be replaced by combinations of terminals and non-terminals. They guide how strings in the language are generated step-by-step.

intermediate

Why are context-free grammars important in compiler design?

CFGs are used to describe the syntax of programming languages clearly and precisely. They help compilers understand and check the structure of code during parsing.

beginner

Give an example of a simple context-free grammar rule.

An example rule: <expr> → <expr> + <term> | <term>. This means an expression can be another expression plus a term, or just a term.

Which component of a CFG represents the symbols that cannot be broken down further?

A Non-terminals

B Terminals

C Start symbol

D Production rules

Terminals are the basic symbols of the language and cannot be replaced further.

What does a production rule in a CFG do?

A Defines how to replace non-terminals with terminals and/or non-terminals

B Defines how to replace terminals with non-terminals

C Defines the start symbol

D Defines the set of terminals

Production rules specify how non-terminals can be replaced by combinations of terminals and non-terminals.

In compiler design, CFGs are mainly used for:

A Describing syntax of programming languages

B Optimizing code

C Executing programs

D Memory management

CFGs describe the syntax rules that programming languages follow, helping compilers parse code.

Which symbol in a CFG indicates where parsing starts?

A Terminal

B Non-terminal

C Production rule

D Start symbol

The start symbol is a special non-terminal symbol where parsing begins.

Which of the following is NOT a component of a context-free grammar?

A Terminals

B Non-terminals

C Lexical analyzer

D Start symbol

A lexical analyzer is a separate part of a compiler, not a component of CFG.

Describe the components of a context-free grammar and their roles.

Think about what each part represents and how they work together to generate language strings.

Explain why context-free grammars are useful in designing programming languages.

Consider how CFGs help compilers understand code structure.

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