3 ms·
That's likely because most C compilers (in my experience) use top-down parsers (LL) rather than bottom-up ones (LR). In contrast to LR parsers, LL parsers are
by groovy2shoes 9y ago
That's likely because most C compilers (in my experience) use top-down parsers (LL) rather than bottom-up ones (LR).
In contrast to LR parsers, LL parsers are quite easy to write and maintain by hand (recursive descent, parser combinators, etc.), and the nature of such hand-written parsers makes it comparatively easy to step outside theoretical bounds and implement context-sensitive portions of the grammar. Such parsers have some other benefits, too, like being easier to debug and making it easier to provide useful error messages (but see Menhir for OCaml, for example, which offers some improvements in these areas over traditional LR parser generators).
What Appel has said is true—it's rare to encounter hand-written LR(1) or LALR(1) parsers in practice. However, many practical languages are easy enough to parse with hand-written top-down parsers that it's quite common to encounter hand-written LL(1)-ish parsers in practice.
- delhanty 9y agoThank you - that's very useful information! I had been wondering how one was meant to provide meaningful error messages for code that failed to parse or failed to lex using the LR approach and looks like maybe the answer is "with difficulty", which is definitely a downer.
- tjalfi 9y agoPhillipe Charles Phd thesis[0] describes a method for generating good error messages with an LALR parser generator. lpg[1] implements these techniques. [0] http://jikes.sourceforge.net/documents/thesis.pdf http://jikes.sourceforge.net/documents/thesis.pdf [1] https://sourceforge.net/projects/lpg/ https://sourceforge.net/projects/lpg/