Does top-down parsing on a left-recursive grammar makes any sense?
by ajiten from LinuxQuestions.org on (#6DHPX)
A parser operates in a recursive manner, with multiple NTs introduce, to implement precedence of different operators.
A left-recursive grammar cannot handle left-associative grammar, as can into infinite loop.
For each NT Symbol being derived, from top to down, in Left-to-right search for possible match of the right-hand side; have a possibility that the same derivation rule is "unnecessarily" called again.
This problem, can lead to infinite recursion.
So, top down parsing for a left-recursive grammar is a failure.
Can we then simply ignore parsing by top-down parser, on a left-recursive grammar?
Hence, is it completely errorneaus to draw parse tree for such a grammar, for top-down parse?
If not, is it possible, to find for a given left-recursive grammar, and a specific statement, to get an idea of the number of attempts it takes to construct the parse tree (i.e., assuming an unambiguous grammar)?
Say, have an arithmetic expression handling left-recursive grammar, with two precedence classes of operators, addop={+,-}, mulop={*,\}; as shown below,
[code]
expr -> expr + term | expr -term | term
term -> term * factor | term / factor | factor
factor -> factor digit | digit
digit -> 0| ... | 9
A left-recursive grammar cannot handle left-associative grammar, as can into infinite loop.
For each NT Symbol being derived, from top to down, in Left-to-right search for possible match of the right-hand side; have a possibility that the same derivation rule is "unnecessarily" called again.
This problem, can lead to infinite recursion.
So, top down parsing for a left-recursive grammar is a failure.
Can we then simply ignore parsing by top-down parser, on a left-recursive grammar?
Hence, is it completely errorneaus to draw parse tree for such a grammar, for top-down parse?
If not, is it possible, to find for a given left-recursive grammar, and a specific statement, to get an idea of the number of attempts it takes to construct the parse tree (i.e., assuming an unambiguous grammar)?
Say, have an arithmetic expression handling left-recursive grammar, with two precedence classes of operators, addop={+,-}, mulop={*,\}; as shown below,
[code]
expr -> expr + term | expr -term | term
term -> term * factor | term / factor | factor
factor -> factor digit | digit
digit -> 0| ... | 9