Context-free grammars in Compiler Design - Mini Project: Build & Apply

Understanding Context-Free Grammars

📖 Scenario: You are learning about how programming languages and simple languages are described using rules called context-free grammars. These grammars help computers understand the structure of sentences or code.

🎯 Goal: Build a simple context-free grammar for a tiny language that describes arithmetic expressions with addition and multiplication.

📋 What You'll Learn

Create a dictionary called grammar with non-terminals as keys and lists of productions as values

Add a start symbol variable called start_symbol with the value 'Expr'

Write a loop to print all productions for each non-terminal in the grammar

Add a final statement that confirms the grammar is ready for use

💡 Why This Matters

🌍 Real World

Context-free grammars are used to define the syntax of programming languages and data formats, helping compilers and interpreters understand code structure.

💼 Career

Understanding grammars is essential for roles in compiler design, language development, and software tools that analyze or transform code.

1

Create the grammar dictionary

Create a dictionary called grammar with these exact entries: 'Expr' maps to ['Expr + Term', 'Term'], 'Term' maps to ['Term * Factor', 'Factor'], and 'Factor' maps to ['( Expr )', 'number'].

Compiler Design

# Create the grammar dictionary with the specified rules
# Your code here

Hint

Use a Python dictionary with keys as non-terminal strings and values as lists of production strings.

2

Add the start symbol

Add a variable called start_symbol and set it to the string 'Expr'.

Compiler Design

grammar = {
    'Expr': ['Expr + Term', 'Term'],
    'Term': ['Term * Factor', 'Factor'],
    'Factor': ['( Expr )', 'number']
}
# Define the start symbol
# Your code here

Hint

The start symbol is the main non-terminal from which parsing begins.

3

Print all productions

Write a for loop using variables non_terminal and productions to iterate over grammar.items(). Inside the loop, write another for loop using production to iterate over productions. For each production, write a line that shows the production in the format: non_terminal -> production.

Compiler Design

grammar = {
    'Expr': ['Expr + Term', 'Term'],
    'Term': ['Term * Factor', 'Factor'],
    'Factor': ['( Expr )', 'number']
}
start_symbol = 'Expr'
# Loop through grammar to display productions
# Your code here

Hint

Use nested loops to access each production for every non-terminal and print them in a readable format.

4

Confirm grammar readiness

Add a final line that sets a variable called grammar_ready to True to indicate the grammar is ready for use.

Compiler Design

grammar = {
    'Expr': ['Expr + Term', 'Term'],
    'Term': ['Term * Factor', 'Factor'],
    'Factor': ['( Expr )', 'number']
}
start_symbol = 'Expr'
for non_terminal, productions in grammar.items():
    for production in productions:
        print(f"{non_terminal} -> {production}")
# Mark the grammar as ready
# Your code here

Hint

This variable can be used later to check if the grammar setup is complete.

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