LR(0) items and parsing in Compiler Design - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to represent an LR(0) item by placing the dot in the correct position.

Compiler Design

item = "A -> α [1] β"

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

A.

B->

C:

D=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '->' instead of the dot to mark the position.

Placing the dot at the start or end without separating α and β.

In LR(0) items, the dot (.) indicates the position of the parser in the production. It separates the already parsed part (α) from the part to be parsed (β).

2fill in blank

medium

Complete the code to define the closure of an LR(0) item set by adding items for productions starting with the symbol after the dot.

Compiler Design

if dot_position_symbol == [1]:
    add all productions of that symbol with dot at start to closure

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

Aterminal

Bepsilon

Cnon-terminal

Dend-marker

Attempts:

3 left

💡 Hint

Common Mistakes

Adding items for terminals instead of non-terminals.

Confusing epsilon with the symbol after the dot.

The closure operation adds items for all productions of the non-terminal symbol that appears immediately after the dot in any item.

3fill in blank

hard

Fix the error in the code that computes the goto function for LR(0) items by correctly moving the dot over the symbol.

Compiler Design

goto_set = {item with dot before X: move dot [1] X}

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

Abelow

Bbefore

Cabove

Dafter

Attempts:

3 left

💡 Hint

Common Mistakes

Moving the dot before the symbol instead of after.

Not moving the dot at all.

The goto function moves the dot one position to the right, i.e., after the symbol X, to represent parsing that symbol.

4fill in blank

hard

Fill both blanks to complete the LR(0) parsing table entry for a shift action on terminal 'a' in state I.

Compiler Design

if input_symbol == [1] and current_state == I:
    action = "[2] J"  # J is the next state

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

Aa

Bshift

Creduce

Daccept

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'reduce' instead of 'shift' for terminals.

Using a non-terminal symbol in place of 'a'.

In LR(0) parsing, when the input symbol is a terminal like 'a' and the parser decides to move forward, the action is a shift to the next state.

5fill in blank

hard

Fill all three blanks to complete the reduce action in the LR(0) parsing table when the dot is at the end of a production.

Compiler Design

if dot_at_end and lookahead == [1]:
    action = "[2] by production [3]"

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

A$

Breduce

CP

Dshift

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'shift' instead of 'reduce' for completed productions.

Using a terminal other than '$' as lookahead in reduce.

When the dot is at the end of a production, the parser performs a reduce action using that production. The lookahead symbol is often the end-marker '$'.

Practice

1. What does an LR(0) item represent in compiler design?

easy

A. A syntax error in the source code

B. A token recognized by the lexer

C. A grammar rule with a dot showing how much has been read

D. A semantic action to be performed

Solution

1. Step 1: Understand LR(0) item definition

   An LR(0) item is a grammar production with a dot indicating the position up to which input has been processed.

2. Step 2: Differentiate from other concepts

   Tokens are lexer outputs, errors are problems, and semantic actions are separate; only the dot notation fits LR(0) items.

3. Final Answer:

   A grammar rule with a dot showing how much has been read -> Option C

4. Quick Check:

   LR(0) item = grammar rule + dot position [OK]

Hint: LR(0) items always show a dot in grammar rules [OK]

Common Mistakes:

• Confusing LR(0) items with tokens
• Thinking LR(0) items are errors
• Mixing semantic actions with LR(0) items

2. Which of the following is the correct way to write an LR(0) item for the production A -> αβ where the dot is before β?

easy

A. A -> α · β

B. A -> · αβ

C. A -> αβ ·

D. A -> β · α

Solution

1. Step 1: Understand dot placement in LR(0) items

   The dot shows how much of the production has been seen. Before β means after α, so dot goes after α.

2. Step 2: Match the correct notation

   A -> α · β places the dot correctly as A -> α · β. Others place dot incorrectly.

3. Final Answer:

   A -> α · β -> Option A

4. Quick Check:

   Dot before β means after α [OK]

Hint: Dot shows position; before β means after α [OK]

Common Mistakes:

• Placing dot at start when it should be after α
• Putting dot at end incorrectly
• Swapping α and β positions

3. Given the grammar rule S -> a A b, what is the LR(0) item after reading a?

medium

A. S -> · a A b

B. S -> a · A b

C. S -> a A · b

D. S -> a A b ·

Solution

1. Step 1: Identify the position of the dot after reading 'a'

   Reading 'a' means the dot moves past 'a' in the production.

2. Step 2: Place the dot correctly

   So the item becomes S -> a · A b, showing 'a' is read and next is 'A'.

3. Final Answer:

   S -> a · A b -> Option B

4. Quick Check:

   Dot moves past read symbols [OK]

Hint: Dot moves right after reading a symbol [OK]

Common Mistakes:

• Keeping dot before 'a' after reading it
• Moving dot too far past unread symbols
• Confusing order of symbols

4. Identify the error in this LR(0) item: B -> α β · γ

medium

A. Dot placement is correct

B. Dot must be at the start or end only

C. Dot should be before γ, not after β

D. Dot cannot be placed between two symbols

Solution

1. Step 1: Understand valid dot positions in LR(0) items

   The dot can appear before any symbol or at the end of the production.

2. Step 2: Check the given item

   In B -> α β · γ, the dot is before γ, which is valid.

3. Final Answer:

   Dot placement is correct -> Option A

4. Quick Check:

   Dot can be anywhere before or after symbols [OK]

Hint: Dot can be before any symbol or at end [OK]

Common Mistakes:

• Thinking dot can't be between symbols
• Believing dot must be only at start or end
• Misreading dot position

5. In LR(0) parsing, what action should be taken when the parser encounters an LR(0) item with the dot at the end of a production, like A -> α ·?

hard

A. Report a syntax error

B. Shift the next input symbol

C. Accept the input string

D. Reduce by the production A -> α

Solution

1. Step 1: Understand dot at end meaning

   When the dot is at the end, it means the entire production has been recognized.

2. Step 2: Determine parser action

   The parser should reduce the recognized symbols to the non-terminal on the left side of the production.

3. Final Answer:

   Reduce by the production A -> α -> Option D

4. Quick Check:

   Dot at end means reduce [OK]

Hint: Dot at end means reduce by that production [OK]

Common Mistakes:

• Trying to shift instead of reduce
• Confusing accept with reduce
• Reporting error incorrectly