What makes the use of a recursive descent parser without backtracking impossible other than left recursion and ambiguity?

Question

My initial problem was to find out whether it is possible to parse the following context-free grammar: grammar_part_1 ; grammar_part_2 (examples) and, if not, edit the grammar so that it is.

I looked for two things: left recursion and ambiguity. Unfortunately, I couldn't find any of those issues apart from the case, where you choose an ident that is similar to a terminal symbol, which is not permitted by definition.

Now, there are three solutions to this problem:

The grammar is parseable by a recursive descent parser without backtracking.
It is the parsers task to obey the definition (e.g. the given rule of "no similar terminal symbol- and ident names") where extending the ident rule with an identification terminal symbol would solve the issue.
There is another kind of grammatical issue apart from the mentioned ones that can occur with these parsers I haven't thought of.

Assuming that my third idea is right, what would these methods be and, if not, are there any other methods to find out whether a grammar is parseable by a recursive descent parser without backtracking? Is assumption 2 true?

---------------- EDIT --------------------

The grammar:

Prog   -> Def^+
Def    -> DEF Left == Expr
Left   -> MAIN : Type
        | Ident ([Ident:Type(, Ident:Type)^*]):Type
Type   -> NAT
        | BOOL
Expr   -> Num
        | TRUE
        | FALSE
        | Ident[([(Expr(, Expr)^*)])]
        | IF Expr THEN Expr [ELSE Expr] FI
Ident  -> (a|...|z)^+
Num    -> (0|...|9)^+

symbols in caps (plus '==', ':', right hand side of Ident and Num) are terminals; (), [], ^+ and ^* are notation operators. Rest is non-terminals

rici rici · Accepted Answer · 2018-05-23T14:13:52

Top-down parsing without backtracking is also impossible if two applicable productions have right-hand sides starting with the same symbol(s). That can require left-factoring.

A more complicated issue is when two non-terminals whose FIRST sets are not disjoint are both the first symbol in different productions for the same non-terminal. While a form of left-factoring might work in this case as well, there is no guarantee that an arbitrary context-free grammar can be parsed with a top-down parser without backtracking.

What makes the use of a recursive descent parser without backtracking impossible other than left recursion and ambiguity?

1 Answers