Yacc/Bison tool overview in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

📋 Factual

intermediate

What is the primary purpose of Yacc/Bison?

Yacc and Bison are tools used in compiler design. What is their main function?

A To generate lexical analyzers that tokenize input text

B To optimize machine code for faster execution

C To generate parsers that analyze the grammatical structure of input

D To manage memory allocation during program execution

💡 Hint

Think about which part of the compiler deals with grammar rules and structure.

Yacc and Bison generate parsers that analyze the grammatical structure of input based on a defined grammar. Lexical analyzers are generated by tools like Lex.

🧠 Conceptual

intermediate

Which file format does Yacc/Bison typically produce?

After processing a grammar specification, what kind of file does Yacc/Bison generate?

A A C source file containing parser code

B A configuration file for the lexer

C A text file listing tokens only

D An executable binary file ready to run

💡 Hint

Consider what Yacc/Bison outputs that you can compile further.

Yacc/Bison generates a C source file that contains the parser code. This file is then compiled with a C compiler to create an executable.

🔍 Analysis

advanced

What happens if a grammar given to Yacc/Bison is ambiguous?

Consider a grammar with ambiguous rules. How does Yacc/Bison handle this situation?

A It refuses to generate any parser and exits with an error

B It automatically resolves ambiguity by choosing the first rule

C It ignores ambiguity and generates incorrect parsers silently

D It reports shift/reduce or reduce/reduce conflicts during generation

💡 Hint

Think about how parser generators inform users about grammar problems.

Yacc/Bison detects ambiguous grammar by reporting conflicts like shift/reduce or reduce/reduce. It still generates a parser but warns the user to resolve these conflicts.

❓ Comparison

advanced

How does Bison differ from the original Yacc?

Both Yacc and Bison are parser generators. What is a key difference between them?

A Bison is free and open source, while Yacc is proprietary

B Yacc supports more programming languages than Bison

C Bison cannot generate parsers for LALR grammars, unlike Yacc

D Yacc automatically generates lexical analyzers, Bison does not

💡 Hint

Consider licensing and availability differences.

Bison is a free and open-source replacement for Yacc, which was originally proprietary. Bison also adds some features and improvements over Yacc.

❓ Reasoning

expert

What is the role of the %token directive in a Bison grammar file?

In a Bison grammar file, what does the %token directive specify?

A It defines the precedence of operators in the grammar

B It declares the names of tokens that the lexer will provide to the parser

C It specifies the start symbol of the grammar

D It includes external C code into the parser

💡 Hint

Think about how the parser knows what tokens to expect from the lexer.

The %token directive declares token names that the lexer returns. This lets Bison know what tokens it should expect when parsing.

Practice

1. What is the primary purpose of the Yacc/Bison tool in compiler design?

easy

A. To optimize machine code for faster execution

B. To generate graphical user interfaces

C. To convert grammar rules into code that parses language syntax

D. To manage memory allocation during program execution

Solution

1. Step 1: Understand Yacc/Bison role

   Yacc/Bison are tools that take grammar rules and produce code that can parse input based on those rules.

2. Step 2: Compare options with purpose

   Only To convert grammar rules into code that parses language syntax describes converting grammar rules into parsing code, which matches Yacc/Bison's function.

3. Final Answer:

   To convert grammar rules into code that parses language syntax -> Option C

4. Quick Check:

   Yacc/Bison = grammar to parser code [OK]

Hint: Yacc/Bison turn grammar into code that reads language [OK]

Common Mistakes:

• Confusing Yacc/Bison with code optimizers
• Thinking Yacc/Bison create user interfaces
• Assuming Yacc/Bison handle memory management

2. Which of the following is the correct way to define a token in a Yacc/Bison grammar file?

easy

A. %token NUMBER

B. token NUMBER;

C. #define NUMBER

D. var NUMBER;

Solution

1. Step 1: Recall Yacc/Bison token syntax

   Tokens in Yacc/Bison are declared using the %token directive followed by the token name.

2. Step 2: Check each option

   Only %token NUMBER uses the correct %token syntax. Others are invalid in Yacc/Bison files.

3. Final Answer:

   %token NUMBER -> Option A

4. Quick Check:

   Token declaration uses %token [OK]

Hint: Tokens start with %token keyword in Yacc/Bison [OK]

Common Mistakes:

• Using C or other language syntax for tokens
• Omitting the % sign before token
• Confusing token declaration with variable declaration

3. Given the following Yacc/Bison grammar snippet:

%token NUMBER
%%
expr: expr '+' NUMBER { printf("Sum\n"); };

What will happen when parsing the input "3 + 4"?

medium

A. The parser will produce a syntax error

B. The parser will print "Sum" twice

C. The parser will print nothing

D. The parser will print "Sum" once

Solution

1. Step 1: Analyze grammar rule

   The rule expr: expr '+' NUMBER triggers action printing "Sum" when matched.

2. Step 2: Parse input "3 + 4"

   Input matches expr '+' NUMBER once, so action runs once printing "Sum".

3. Final Answer:

   The parser will print "Sum" once -> Option D

4. Quick Check:

   One matching rule triggers one print [OK]

Hint: Each matched rule action runs once per match [OK]

Common Mistakes:

• Assuming multiple prints for single input
• Thinking input causes syntax error
• Ignoring action code in grammar

4. Identify the error in this Yacc/Bison grammar snippet:

%token NUMBER
%%
expr: expr '+' NUMBER { printf("Sum\n"); }
    | NUMBER;

medium

A. Incorrect token declaration syntax

B. Missing semicolon after first rule action

C. Missing %start directive

D. Using printf inside action is invalid

Solution

1. Step 1: Check rule syntax

   Each grammar rule must end with a semicolon. The first rule lacks a semicolon after the action block.

2. Step 2: Verify other parts

   Token declaration is correct, %start is optional if default is used, and printf is allowed in actions.

3. Final Answer:

   Missing semicolon after first rule action -> Option B

4. Quick Check:

   Rules end with semicolon [OK]

Hint: Grammar rules must end with semicolon [OK]

Common Mistakes:

• Forgetting semicolon after action block
• Confusing token syntax errors
• Assuming printf is disallowed in actions

5. You want to extend a Yacc/Bison grammar to parse simple arithmetic expressions with addition and multiplication. Which approach correctly handles operator precedence?

hard

A. Define separate rules for addition and multiplication and declare precedence using %left and %right directives

B. Use only one rule combining '+' and '*' without precedence declarations

C. Declare all tokens as %token without precedence directives

D. Handle precedence in the lexer instead of grammar

Solution

1. Step 1: Understand operator precedence in Yacc/Bison

   Yacc/Bison uses %left, %right, and %nonassoc directives to declare operator precedence and associativity.

2. Step 2: Evaluate options

   Define separate rules for addition and multiplication and declare precedence using %left and %right directives correctly uses separate rules and precedence declarations. Options B and C ignore precedence, causing incorrect parsing. Handle precedence in the lexer instead of grammar is incorrect because lexer does not handle precedence.

3. Final Answer:

   Define separate rules for addition and multiplication and declare precedence using %left and %right directives -> Option A

4. Quick Check:

   Precedence via %left/%right = correct parsing [OK]

Hint: Use %left/%right to set operator precedence in grammar [OK]

Common Mistakes:

• Ignoring precedence causing wrong parse trees
• Trying to handle precedence in lexer
• Declaring tokens without precedence directives