parsingcompiler-constructioncompiler-optimizationtop-down

can a top-down parser detect ungrammaticality an input string?

I read that its possible to do this ,

Will it require backtracking?

What would be the sketch from recovering from the parsing errors .

Solution

  • The way a top down parser can detect the ungrammaticality, i.e. the invalidity of an input string is, for example:

    if you have the non-terminal A on the top of your stack for instance, and the next token in your input string is the symbol b,

    then go to your parse table and go to the row for A, and the column for b, and if there is an empty cell, then the input string is invalid.

    A method to recover would be to entry panic mode, where you skip tokens in the input string until you find one in the synchronising set, and then pop A off the stack and continue.

    several ways of choosing the synchronising set, it could be follow(A) for example