IAE Academy

ISRO CS 2023 Q.11: solution and answer

ISRO 2023 · CSQ.11 · 1 mark · MCQ

In the context of parsing techniques, LL(1) refers to:

  1. (A)

    Grammars that parse the input from left to right, produce a rightmost derivation, with a lookahead of 1 symbol.

  2. (B)

    Grammars that parse the input from left to right, produce a leftmost derivation, with a lookahead of 1 symbol.

  3. (C)

    Grammars that parse the input from left to right, and backtrack at most once.

  4. (D)

    Grammars that parse the input from right to left, produce a leftmost derivation, and backtrack at most once.

See the question in the paper
ISRO CS 2023 question 11Tap to open full size

Answer and solution

ANSWER

Option (b): LL(1) grammars are parsed with a left-to-right scan, a leftmost derivation and a lookahead of 1 symbol.

Official answer: BSource: ISRO's revised and final answer key of 16 February 2024

  1. The name LL(1) has three parts: the first L is the direction of the input scan, the second L is the kind of derivation built, and the number is the lookahead.

  2. The first L means the input is read from Left to right.

  3. The second L means a Leftmost derivation is produced. A top-down parser expands the leftmost non-terminal at every step.

  4. The (1) means one lookahead symbol is enough to choose the production at each step, so no backtracking is needed. The parser decides using the parsing table entry .

  5. Option (a) is wrong: a rightmost derivation (traced in reverse) belongs to LR parsers such as LR(1), not LL(1).

  6. Option (c) is wrong: an LL(1) parser never backtracks. Its table is deterministic, so the number of backtracks is zero, not 'at most once'.

  7. Option (d) is wrong: LL(1) scans left to right, not right to left, and it does not backtrack.

  8. So option (b) is correct: left-to-right scan, leftmost derivation, one symbol of lookahead.

KEY IDEA

Read LL(k) as: first L = Left-to-right scan of the input, second L = Leftmost derivation, k = number of lookahead symbols. LR parsers instead give a Rightmost derivation in reverse.

WATCH OUT FOR

Confusing LL(1) with LR(1) and choosing the rightmost derivation option, or assuming the 1 allows one backtrack. The 1 is the lookahead length, and a predictive LL(1) parser never backtracks.

From the ISRO CS 2023 paper. Every question of this paper · The full paper (PDF, ISRO) · All 2 ISRO Parsing questions, with notes