Course contentsShow
← Computer Science
Lesson 1964 of 2,87244. Lexical Analysis and ParsingFree lesson

LR(0) Items and Item Sets

Defining LR(0) items as grammar productions with a dot marking parsing progress.

LR(0) Items and Item Sets

You'll learn: How LR(0) items use a dot notation to track exactly where the parser is within a grammar production.

What Is an LR(0) Item?

An LR(0) item is simply a grammar production with a special dot (•) inserted somewhere on the right-hand side. The dot marks how much of that production the parser has already recognized and what it expects to see next.

Think of it like a bookmark in a recipe: if your recipe says "mix flour, eggs, and milk," an item might show "mix flour • eggs and milk" — meaning you've already mixed the flour and you're looking for eggs next.

The Dot's Meaning

Given a production like E → E + T, we can create several LR(0) items:

  • E → • E + T (just starting, haven't seen anything yet)
  • E → E • + T (recognized an E, expecting + next)
  • E → E + • T (recognized E and +, expecting T)
  • E → E + T • (recognized everything, ready to reduce)

The dot slides from left to right as parsing progresses.

Item Sets (Collections)

An item set (or item collection) groups together all LR(0) items that represent possible states of the parser at a given moment. When the parser is in one state, it might be simultaneously tracking multiple possible productions, so it maintains a whole set of items.

These item sets form the foundation for building LR parsing tables, helping the parser decide whether to shift (consume the next token) or reduce (apply a production rule).

Key Takeaway: LR(0) items add a dot to grammar productions to mark parsing progress, creating a snapshot of what's been recognized and what's expected next; collections of these items represent parser states.