I am trying to clearly define various terms related to top down parser "so that I can relate them and come up with clear classification". Now this efforts might seem unnecessary as the terms I am talking are pretty basics, but I am trying this all for sake of 100% clarity.

The dragon book defines predictive parsing as follows:

A special case of recursive descent parsing, where no backtracking is required. Predictive parsing chooses the correct A-production by looking ahead at the input a fixed number of symbols, typically we may look only at one (that is, the next input symbol).

It defines $LL(k)$ grammars as follows:

The class of grammars for which we can construct predictive parsers looking $k$ symbols ahead in the input is sometimes called the $LL(k)$ class.

Now I have following doubts:

  1. Is the definition of $LL(k)$ parsers same as that of $LL(k)$ class of grammars above?

  2. Is above definition of "predictive parsing" correct? Are the two definitions of predictive parsing and LL(k) parsing same? and hence the two concepts are also same?

  3. If answer to above (Q2) is NO, then in what other (than $LL(k)$) way, we can implement predictive parsers?

  4. Is the above definition of predictive parsers correct? It says "a special case of recursive descent parsing, ...". Cant we implement predictive parsers with non recursive descent approach?

  5. Similarly, cant we implement $LL(k)$ parser with non recursive descent approach (which I know we can)?

  6. Question 4 and 5 asks for non recursive descent approach for predictive and $LL(k)$ parsers, which are essentially non backtracking. Can we implement backtracking parser with non recursive descent approach (without lookahead) (pink box below)?

  7. Is "bruteforce parsing" same as "recursive descent parsing without lookahead"? I have just heard of "bruteforce parsing", how we define it?

  8. Is below classification looks correct?

    enter image description here

(Sorry for so many questions, but I believe they make sense together.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.