Which of the following grammars is LR(1)?

Concept

A grammar is LR(1) when its canonical LR(1) item collection has no parsing conflict while using one lookahead symbol.

A completed item [X → α•, t] requests a reduction on lookahead t, whereas an item with terminal t after the dot requests a shift on t. If both occur in one state, there is a shift/reduce conflict.

Application

1. For A → aAb | bAb | a | b, after reading aa a reachable state contains [A → a•, b] together with [A → •bAb, b] and [A → •b, b]. On lookahead b, that state requests both reduction by A → a and a shift, so it has a conflict.

2. For A → aAa | aAb | c, a recursive-prefix state contains no completed item; a state reached after the inner A shifts only a or b; and the states containing A → c•, A → aAa•, or A → aAb• contain only completed items. Thus no state mixes a shift and a reduction.

3. For A → A + A | a, a state after A + A contains [A → A + A•, +] together with [A → A• + A, +]. It requests both reduction and a shift on +, so it has a conflict.

4. The conjunction of A → aAb | bAb | a | b and A → aAa | aAb | c is false because A → aAb | bAb | a | b has the conflict shown above.

Contrast

• A → aAb | bAb | a | b is unambiguous in its generated-string pattern, but unambiguity alone does not guarantee the LR(1) property.

• A → A + A | a is ambiguous for a + a + a unless associativity is supplied.

• A → aAa | aAb | c keeps shift states and completed-item states separate.

Cross-check

The grammar A → aAa | aAb | c is even LR(0): its LR(0) states have either shift items or one completed production, but not both. Every LR(0) grammar is LR(1), which independently confirms the result.

Therefore, the LR(1) grammar is A → aAa | aAb | c.