I have been informed parser parses unambiguous context free grammars of $DCFL$.

I was wondering if there could be a parser which could make a parsing table for unambiguous grammars of $NCFL$?

Note: This has been discussed here briefly in comments.


There are a number of general parsing algorithms (Earley, GLR, GLL, etc.) which can handle arbitrary context free grammars, even ambiguous grammars. (For ambiguous grammars, an entire parse forest is produced, usually as a spaghetti-like graph structure, because grammars can produce an infinite number of parses, or an exponential number if null cycles are removed.)

What these parsers cannot do is parse any grammar in time linear to the length of the input. It could take up to cubic time, although GLR parsers can parse unambiguous grammars in quadratic time even if the grammar is non-deterministic. (In practice, GLR parsers tend to be close to linear time for typical applications, because the grammars are "mostly" deterministic and unambiguous.)


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.