LR(0) items and parsing in Compiler Design - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an LR(0) item in compiler design?

An LR(0) item is a production rule from a grammar with a dot (•) placed at some position in the right-hand side. It shows how much of the production has been seen during parsing.

beginner

What does the dot (•) represent in an LR(0) item?

The dot indicates the current position in the production rule during parsing. It separates what has been parsed from what is expected next.

intermediate

How is an LR(0) parser different from other parsers?

An LR(0) parser uses LR(0) items to decide shifts and reductions without looking ahead at the next input symbol. It is simpler but less powerful than parsers that use lookahead.

intermediate

What is the purpose of the closure operation in LR(0) parsing?

Closure adds all possible LR(0) items that could be expected next based on the current dot position, helping the parser consider all valid next steps.

beginner

Explain the shift and reduce actions in LR(0) parsing.

Shift means moving the dot forward by reading the next input symbol. Reduce means applying a production rule when the dot is at the end, replacing the recognized symbols with the rule's left side.

What does an LR(0) item represent?

A A production with a dot showing parsing progress

B A token in the input stream

C A completed parse tree

D A lookahead symbol

An LR(0) item is a production rule with a dot indicating how much has been parsed.

In LR(0) parsing, what does the 'closure' operation do?

A Adds all items that could follow the current dot position

B Removes completed items

C Reads the next input symbol

D Generates the parse tree

Closure adds all possible items that might be expected next based on the current position.

What action does an LR(0) parser take when the dot is at the end of a production?

A Shift

B Reduce

C Accept

D Error

When the dot is at the end, the parser reduces by applying the production rule.

Which of these is NOT true about LR(0) parsers?

A They decide actions based on dot positions

B They use LR(0) items

C They use lookahead symbols

D They perform shift and reduce actions

LR(0) parsers do not use lookahead symbols; that is a feature of LR(1) parsers.

What does the dot (•) in an LR(0) item separate?

A Input from output

B Left and right sides of a production

C Tokens from non-terminals

D Parsed symbols from symbols to be parsed

The dot separates what has been parsed from what is expected next.

Describe what an LR(0) item is and how it helps in parsing.

Think about how the dot shows what part of a rule has been seen.

Explain the difference between shift and reduce actions in LR(0) parsing.

Consider what the parser does when it reads input or finishes a rule.

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