RSS
Twitter
Facebook
Top-down
parsing can be viewed as the problem of constructing a parse tree for the input
string, starting from the root and creating the nodes of the parse tree in
preorder. Equivalently, top-down parsing can be viewed as finding a leftmost
derivation for an input string.
At
each step of a top-down parse, the key problem is that of determining the
production to be applied for a nonterminal, say A.
Once an A-production is chosen, the rest of the parsing process consists
of "matching" the terminal symbols in the production body with the
input string.
To
find a left-most derivation for an input string, To construct parse tree for
the input starting from the root and creating the nodes of the parse tree in
preorder, Predictive parser is non-backtracking form of top-down parser,
Predictive parsers is a special case of recursive-descent parsing, General
form
of top-down parsing is recursive-descent, that may involve backtracking
A
left-recursive grammar can cause a recursive-descent parser to go into an
infinite loop. By eliminating left recursion from a grammar, left factoring the
resulting grammar, we can obtain a grammar that can be parsed by a
recursive-descent parser without backtracking – predictive parsing. The proper
alternative must be detectable by looking at only the first symbol it derives
FIRST and FOLLOW – two functions associated with a grammar G, in construction
of a predictive parser.
0 comments