Predictive parsing in Compiler Design - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to identify the first step in predictive parsing.

Compiler Design

predictive_parser = [1](grammar)

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

Astart_parsing

Bcreate_parse_table

Cinitialize_table

Dcompute_follow

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing parse table creation with starting the parsing process.

Trying to compute FOLLOW sets before building the table.

The first step in predictive parsing is to create the parse table from the grammar.

2fill in blank

medium

Complete the code to check if the input symbol matches the top of the stack in predictive parsing.

Compiler Design

if stack_top == [1]:

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

Ainput_symbol

Bnon_terminal

Cend_marker

Depsilon

Attempts:

3 left

💡 Hint

Common Mistakes

Checking against non-terminal instead of input symbol.

Confusing epsilon with input symbols.

In predictive parsing, we compare the top of the stack with the current input symbol to decide the next action.

3fill in blank

hard

Fix the error in the code that selects the production rule from the parse table.

Compiler Design

production = parse_table[[1]][input_symbol]

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

Anon_terminal

Bstart_symbol

Cinput_symbol

Dstack_top

Attempts:

3 left

💡 Hint

Common Mistakes

Using input symbol as the row index instead of non-terminal.

Using start symbol instead of current non-terminal.

The parse table is indexed by the current non-terminal on the stack and the input symbol.

4fill in blank

hard

Fill both blanks to complete the predictive parsing step that updates the stack after selecting a production.

Compiler Design

stack.pop()
for symbol in reversed([1]):
    if symbol != [2]:
        stack.push(symbol)

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

Aproduction

Bepsilon

Cinput_symbol

Dstack_top

Attempts:

3 left

💡 Hint

Common Mistakes

Pushing epsilon onto the stack.

Using input symbol instead of production symbols.

After popping the non-terminal, the parser pushes the production's right side symbols onto the stack, skipping epsilon.

5fill in blank

hard

Fill all three blanks to complete the predictive parser loop that processes input until acceptance or error.

Compiler Design

while stack and input_pointer < len(input_string):
    stack_top = stack.peek()
    current_input = input_string[input_pointer]
    if stack_top == [1]:
        stack.pop()
        input_pointer += 1
    elif stack_top in [2]:
        production = parse_table[stack_top][current_input]
        stack.pop()
        for symbol in reversed(production):
            if symbol != [3]:
                stack.push(symbol)
    else:
        raise SyntaxError('Parsing error')

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

Acurrent_input

Bnon_terminals

Cepsilon

Dterminals

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing terminals and non-terminals in conditions.

Pushing epsilon onto the stack.

The parser matches terminals by comparing stack top with current input, expands non-terminals using the parse table, and skips epsilon symbols.

Practice

1. What is the main purpose of predictive parsing in compiler design?

easy

A. To optimize the runtime performance of a program

B. To analyze sentences using a stack and parsing table without backtracking

C. To generate machine code from source code

D. To translate high-level code into assembly language

Solution

1. Step 1: Understand predictive parsing function

   Predictive parsing analyzes sentences by using a stack and a parsing table to decide the next step without guessing or backtracking.

2. Step 2: Differentiate from other compiler tasks

   Generating machine code, optimizing runtime, and translating to assembly are later compiler stages, not parsing.

3. Final Answer:

   To analyze sentences using a stack and parsing table without backtracking -> Option B

4. Quick Check:

   Predictive parsing = stack + table analysis [OK]

Hint: Parsing means analyzing structure, not generating code [OK]

Common Mistakes:

• Confusing parsing with code generation
• Thinking predictive parsing guesses or backtracks
• Mixing parsing with optimization tasks

2. Which of the following is a correct component used in predictive parsing?

easy

A. Parsing table

B. Backtracking stack

C. Hash map for variables

D. Symbolic debugger

Solution

1. Step 1: Identify key components of predictive parsing

   Predictive parsing uses a parsing table and a stack to decide which grammar rule to apply next.

2. Step 2: Eliminate unrelated options

   Backtracking stack is not used because predictive parsing avoids backtracking. Hash maps and debuggers are unrelated to parsing tables.

3. Final Answer:

   Parsing table -> Option A

4. Quick Check:

   Parsing table is essential in predictive parsing [OK]

Hint: Parsing table guides decisions without guessing [OK]

Common Mistakes:

• Assuming backtracking is part of predictive parsing
• Confusing parsing table with data structures for variables
• Mixing debugging tools with parsing components

3. Given the grammar rules:
S -> a A b
A -> c | ε
and the input string acb, what will the predictive parser do at the point it reads c?

medium

A. Throw a syntax error

B. Apply rule A -> ε and skip c

C. Backtrack to try another rule

D. Apply rule A -> c and consume c

Solution

1. Step 1: Check the input and grammar at A

   The input symbol is c. The grammar allows A -> c or A -> ε.

2. Step 2: Use predictive parsing table logic

   Since the next input is c, the parser chooses A -> c to match the input symbol and consume it.

3. Final Answer:

   Apply rule A -> c and consume c -> Option D

4. Quick Check:

   Input matches rule A -> c [OK]

Hint: Match input symbol with rule start, no backtracking [OK]

Common Mistakes:

• Choosing epsilon rule when input symbol matches
• Thinking parser backtracks on mismatch
• Assuming syntax error without checking rules

4. Identify the error in this predictive parsing step:
Grammar: S -> a S b | ε
Input: a a b b
Parser applies S -> ε immediately at the start.

medium

A. Parser should backtrack after epsilon

B. Input string is invalid for the grammar

C. Incorrect application of epsilon rule too early

D. No error, parsing is correct

Solution

1. Step 1: Analyze grammar and input

   The grammar allows S -> a S b or S -> ε. The input starts with a, so epsilon should not be chosen immediately.

2. Step 2: Understand predictive parsing rules

   Predictive parsing uses lookahead to decide rules. Since input is a, it should apply S -> a S b first, not epsilon.

3. Final Answer:

   Incorrect application of epsilon rule too early -> Option C

4. Quick Check:

   Epsilon only if input doesn't match other rules [OK]

Hint: Check input symbol before choosing epsilon rule [OK]

Common Mistakes:

• Applying epsilon rule without checking input
• Assuming input is invalid without parsing
• Expecting backtracking in predictive parsing

5. You have a grammar with rules:
E -> T E'
E' -> + T E' | ε
T -> int
How would you construct the predictive parsing table entry for non-terminal E' and input symbol +?

hard

A. Use rule E' -> + T E' because input is '+'

B. Use rule E' -> ε because '+' is not in T

C. No entry needed because '+' is terminal

D. Use rule E' -> T E' to start parsing

Solution

1. Step 1: Identify first sets for E'

   The first set of E' includes '+' because of the rule E' -> + T E'.

2. Step 2: Match input symbol '+' with rule

   Since input is '+', the parser uses the rule E' -> + T E' in the parsing table for E' and '+'.

3. Final Answer:

   Use rule E' -> + T E' because input is '+' -> Option A

4. Quick Check:

   Input '+' matches E' -> + T E' [OK]

Hint: Match input with first set of non-terminal rules [OK]

Common Mistakes:

• Choosing epsilon rule when input matches '+'
• Confusing terminals with non-terminals in table
• Ignoring first sets in table construction