Question

1) Please explain why an LL(1) parser is a linear-time, linear-space parser.

2) Please explain why an LR(1) parser is a linear-time, linear-space parser.

Answer 1

LL(1) Parsing:
The 1st L represents that the scanning of the Input will be done from Left to Right manner and second L shows that in this Parsing technique we are going to use Left most Derivation Tree. and finally the 1 represents the number of look ahead, means how many symbols are you going to see when you want to make a decision.

An ambiguous grammer cannot be LL(1) grammer.

When a syntax has LL(1) conflicts, a choice between two alternatives can arise during parsing which can not be resolved given a single token of lookahead. Existence of LL(1) conflicts is formalised by the set of inductive rules presented . Informally, LL(1) conflicts arise in three cases: 1) Both branches of a disjunction are nullable, which means that two potentially different values are associated with the empty string by the disjunction. 2) Branches of a disjunction have non-disjoint first sets, so both branches can accept a sequence starting with the same token. Given a single token of lookahead, a parser thus cannot decide which branch to choose. 3) The should-not-follow set of the left-hand side of a sequence and the first set of the right-hand side of that sequence both contain the same token kind, k. This means that there is a point in the left-hand side (after reading the sequence of tokens ts1 from ) where reading a token of kind k will make it impossible to decide whether we should stay in the left-hand side (and then read ts2), or start parsing in the right-hand side of the sequence.

Due to backtracking, LL(1) may end up being exhaustive in that it may
backtrack to the point that it reaches the last production in which it
will try to apply. This exhaustive search means LL(1) is bounded by an
exponential.

LR(1) parsing :

An LR parsing is non-backtracking shift reduce parsing.LR(1) parser is a finite-state automaton, equipped with a stack, which uses a combination of its current state and one lookahead symbol in order to determine which action to perform next. We present a validator which, when applied to a context-free grammar G and an automaton A, checks that A and G agree. Validating the parser provides the correctness guarantees required by verified compilers and other high-assurance software that involves parsing. The validation process is independent of which technique was used to construct A.