Predictive parsers are recursive descent parsers that need no backtracking and can be constructed for a class of grammars called LL (1). The first "L" in LL (1) indicates that, scanning the input from left to right. The second "L" in LL (1) signifies that, producing a leftmost derivation. The "1" in LL (1) indicates that, using one input symbol of lookahead at each step to make parsing action decisions. Like recursive descent, the LL (1) technique is top-down, goal oriented, and predictive. Consider the grammar G5: S → iEtSS′|a S′ → eS|ԑ E → b Construct the LL (1) parsing table for the grammar G5 and use the LL (1) parsing table for the grammar G5 to check whether the grammar G5 is LL (1). Algorithm sheet: Algorithm for Constructing LL (1) Parsing Table Input: Grammar G. Output: Parsing table M. Method: For each production A → a of the grammar, do the following: Step 1: For each terminal "a" in ????? (a), add A → a to M[A, a]. Step 2: If ? is in ????? (a), then for each terminal b in ??????(A), add A → a to M[A, b]. If ԑ is in ????? (a) and $ is in ??????(A), A → a to M[A, $] as well. Step 3: If, after performing the above, there is no production at all in M[A, a], then set M[A, a] to error (which we normally represent by an empty entry in the table).
Predictive parsers are recursive descent parsers that need no backtracking
and can be constructed for a class of grammars called LL (1).
The first "L" in LL (1) indicates that, scanning the input from left to
right.
The second "L" in LL (1) signifies that, producing a leftmost derivation.
The "1" in LL (1) indicates that, using one input symbol of lookahead
at each step to make parsing action decisions.
Like recursive descent, the LL (1) technique is top-down, goal oriented,
and predictive.
Consider the grammar G5:
S → iEtSS′|a
S′ → eS|ԑ
E → b
Construct the LL (1) parsing table for the grammar G5 and use the LL (1)
parsing table for the grammar G5 to check whether the grammar G5 is LL (1).
Algorithm for Constructing LL (1) Parsing Table
Input: Grammar G.
Output: Parsing table M.
Method: For each production A → a of the grammar, do the following:
Step 1: For each terminal "a" in ????? (a), add A → a to M[A, a].
Step 2: If ? is in ????? (a), then for each terminal b in ??????(A), add
A → a to M[A, b]. If ԑ is in ????? (a) and $ is in ??????(A), A →
a to M[A, $] as well.
Step 3: If, after performing the above, there is no production at all in M[A, a],
then set M[A, a] to error (which we normally represent by an empty
entry in the table).
Step by step
Solved in 3 steps with 2 images
