Yacc/Bison tool overview in Compiler Design - Step-by-Step Execution

Concept Flow - Yacc/Bison tool overview

Write grammar rules

↓

Input to Yacc/Bison

↓

Yacc/Bison generates parser code

↓

Compile parser code with lexer

↓

Run parser on input text

↓

Parser checks syntax and builds structure

↓

Output parse result or error

The flow shows how you write grammar rules, use Yacc/Bison to generate parser code, compile it, and then run the parser to analyze input text.

Execution Sample

Compiler Design

expression : NUMBER '+' NUMBER ;
%%
int main() {
  return yyparse();
}

This simple grammar rule tells the parser to recognize two numbers separated by a plus sign.

Analysis Table

Step	Action	Input	Parser State	Output/Result
1	Start parsing	3 + 4	Initial state	No output yet
2	Read token	3	Expect '+'	Token recognized as NUMBER
3	Read token	+	Expect NUMBER	Token recognized as '+'
4	Read token	4	Rule matched	Token recognized as NUMBER
5	Match rule	3 + 4	Rule matched: expression	Build parse tree node
6	Parsing complete		Accept state	Parse successful

💡 Parsing stops after input matches the grammar rule and parser reaches accept state.

State Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
Current Token	None	3 (NUMBER)	+	4 (NUMBER)	None
Parser State	Initial	Expect '+'	Expect NUMBER	Rule matched	Accept

Key Insights - 2 Insights

Why does the parser expect a '+' after reading the first number?

Because the grammar rule says expression is NUMBER '+' NUMBER, so after NUMBER the parser expects '+' as shown in execution_table step 3.

What happens if the input does not match the grammar rule?

The parser will not reach the accept state and will report a syntax error, stopping parsing early.

Visual Quiz - 3 Questions

Look at the execution table, what is the parser state after reading the '+' token?

A Rule matched

B Initial state

C Expect NUMBER

D Accept state

💡 Hint

Check the 'Parser State' column at Step 3 in the execution_table.

At which step does the parser build the parse tree node?

A Step 2

B Step 5

C Step 4

D Step 6

💡 Hint

Look for 'Build parse tree node' in the Output/Result column.

If the input was '3 4 +', how would the parser state change at Step 3?

A Syntax error because '+' expected but '4' found

B Expect '+' as usual

C Accept state immediately

D Rule matched early

💡 Hint

Refer to the grammar rule and the expected token at Step 3 in the execution_table.

Concept Snapshot

Yacc/Bison overview:
- Write grammar rules defining language syntax
- Yacc/Bison generates C parser code
- Compile parser with lexer
- Run parser on input text
- Parser checks syntax and builds parse tree
- Errors reported if input doesn't match grammar

Full Transcript

Yacc and Bison are tools used to create parsers from grammar rules. You write rules that describe the structure of your language. Yacc/Bison reads these rules and generates code that can analyze text input. When you run the parser on input, it reads tokens step-by-step, checks if they fit the grammar, and builds a structure called a parse tree. If the input matches the rules, parsing succeeds; otherwise, it reports errors. This process helps compilers understand programming languages.

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