Top-Down Parser
The top-down parsing strategy, as we learned in the previous chapter, parses the input and begins building a parse tree from the root node, gradually progressing down to the leaf nodes. The following are examples of top-down parsing:
Recursive Descent Parsing is a technique for parsing data in a recurs
Recursive descent is a top-down parsing strategy in which the input is read from left to right and the parse tree is built from the top down. Procedures are used for all terminal and non-terminal entities. This parsing method parses the input recursively to create a parse tree, which may or may not need backtracking. However, the grammar connected with it (if not factored) will result in backtracking. Predictive parsing is a type of recursive-descent parsing that does not involve any backtracking.
Because it uses context-free grammar, which is recursive in nature, this parsing technique is considered recursive.
Back-tracking
Top-down parsers begin at the root node (start symbol) and replace the input text with the production rules (if matched). Take the following CFG example to see what I mean:
S → rXd | rZd
X → oa | ea
Z → ai
A top-down parser will behave like this for an input string: read:
It will begin with S from the production rules and match its yield to the input's left-most letter, r. S (S rXdvery )'s production corresponds to it. As a result, the top-down parser moves on to the next input letter ('e'). The parser tries to expand non-terminal 'X' from the left (X oa). It doesn't match the next symbol in the input. As a result, the top-down parser goes backwards to find X's next production rule, (X ea).
The parser now matches all of the input letters in the correct order. The string is valid.
|
|
|
|
|
Predictive Parser is a programme that predicts what will happen next.
A predictive parser is a recursive descent parser that can anticipate which production will be used to replace the input string. Backtracking is not an issue for the predictive parser.
The predictive parser employs a look-ahead pointer to complete its responsibilities, which links to the next input symbols. To avoid backtracking, the predictive parser imposes various constraints on the language and only accepts LL(k) grammars.
To parse the input and build a parse tree, predictive parsing employs a stack and a parsing table. The end sign $ appears in both the stack and the input to indicate that the stack is empty and the input has been eaten. To make any decisions about the input and stack element combination, the parser turns to the parsing table.
For a single instance of input, the parser may have more than one production to pick from in recursive descent parsing, whereas in predictive parsing, each step has only one production to choose from. There may be times when no production matches the input string, resulting in the parsing algorithm failing.
LL PARSER
LL Parser is a programme that allows you to parse long
An LL Parser is a programme that accepts LL grammar. LL grammar is a subset of context-free grammar with specific limitations in order to obtain a simplified form that is easier to implement. Both recursive-descent and table-driven methods can be used to implement LL grammar.
The LL parser is abbreviated as LL (k). The first L in LL(k) denotes left-to-right parsing, the second L represents left-most derivation, and k represents the number of look aheads. Because k = 1 in most cases, LL(k) can alternatively be written as LL (1).
Algorithm for LL Parsing
Because the size of the table grows exponentially with the value of k, we can stick to deterministic LL(1) for parser explanation. Second, if a grammar isn't LL(1), it's almost certainly not LL(k) for any given k.
The following is an LL(1) Parsing algorithm:
Input:
string ω
parsing table M for grammar G
Output:
If ω is in L(G) then left-most derivation of ω,
error otherwise.
Initial State : $S on stack (with S being start symbol)
ω$ in the input buffer
SET ip to point the first symbol of ω$.
repeat
let X be the top stack symbol and a the symbol pointed by ip.
if X∈ Vt or $
if X = a
POP X and advance ip.
else
error()
endif
else /* X is non-terminal */
if M[X,a] = X → Y1, Y2,... Yk
POP X
PUSH Yk, Yk-1,... Y1 /* Y1 on top */
Output the production X → Y1, Y2,... Yk
else
error()
endif
endif
until X = $ /* empty stack */
If A | are two distinct G productions, a grammar G is LL(1):
Both and derive strings beginning with a when there is no terminal.
Only one of and can result in an empty string.
If t is true, no string beginning with a terminal is derived in FOLLOW (A).