Context-free grammars in Compiler Design - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define a simple production rule in a context-free grammar.

Compiler Design

S -> [1]

Drag options to blanks, or click blank then click option'

A"aSb"

B"a"

C"ab"

D"b"

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing a string with multiple symbols which is not a single production.

Using non-terminal symbols on the right side without proper notation.

The production rule S -> "a" defines that the start symbol S can be replaced by the terminal symbol a. This is a basic example of a context-free grammar rule.

2fill in blank

medium

Fill both blanks to show a recursive production rule for balanced parentheses.

Compiler Design

P -> [1] P [2] | ""

Drag options to blanks, or click blank then click option'

A"["

B"("

C"{"

D")"

Attempts:

3 left

💡 Hint

Common Mistakes

Using mismatched parentheses symbols.

Forgetting the empty string alternative.

The rule P -> "(" P ")" | "" defines balanced parentheses recursively. The symbol P can be replaced by an opening parenthesis, followed by P, then a closing parenthesis, or by the empty string.

3fill in blank

hard

Fix the error in the production rule for arithmetic expressions.

Compiler Design

E -> E [1] T | T

Drag options to blanks, or click blank then click option'

A"+"

B"-"

C"*"

D"/"

Attempts:

3 left

💡 Hint

Common Mistakes

Using multiplication or division instead of addition.

Using an operator that does not fit the grammar rule.

The production rule E -> E + T | T correctly defines addition in arithmetic expressions. The symbol E can be replaced by E + T or just T. Using + here models addition.

4fill in blank

hard

Fill both blanks to complete the production rule for identifiers starting with a letter followed by letters.

Compiler Design

ID -> [1] | [1] [2]

Drag options to blanks, or click blank then click option'

Aletter

B"digit"

CID

D"number"

Attempts:

3 left

💡 Hint

Common Mistakes

Using digits as the first symbol.

Not using recursion to allow multiple characters.

The rule ID -> letter | letter ID defines an identifier starting with a letter followed by zero or more letters. This recursive definition allows building identifiers of any length.

5fill in blank

hard

Fill all three blanks to define a production rule for a simple if-statement.

Compiler Design

Stmt -> "if" [1] "then" [2] [3]

Drag options to blanks, or click blank then click option'

Acondition

BStmt

C"else"

Dexpression

Attempts:

3 left

💡 Hint

Common Mistakes

Using "expression" instead of "condition".

Omitting the "else" keyword.

The production rule Stmt -> "if" condition "then" Stmt "else" Stmt models a simple if-then-else statement. The condition is checked, then a statement is executed, optionally followed by an else clause.

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