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

Need a 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

Need a 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

Need a 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

Need a hint?

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