3 ms·
To see what compiler compilers are meant to do, you have to look back at the 60s/70s. Back then, people implementing a programming language wrote their own lexe
by sqrt17 16y ago
To see what compiler compilers are meant to do, you have to look back at the 60s/70s. Back then, people implementing a programming language wrote their own lexer/parser, in some kind of spaghetti code. Compiler compilers fixed this by providing a means to
(i) give a grammar in a declarative fashion (i.e., so that you can still figure out what it does, without getting entangled in the states of a GOTO-heavy and implicit state machine)
(ii) make that grammar run well.
The alternative approach is to have (close to) no grammar at all - this is why Lisp's S-expressions are such a fabulous thing: you can describe anything that you could describe in a context-free language, without any heavy grammar lifting necessary.
The relatively new trend of using GLR parsing (i.e., parsing fully context free languages, using chart packing) is necessary because people need to parse grammars that are not designed to be in LR(k), for example a general parser for COBOL that allows it to parse several dialects of it.
In general, you want to avoid both the problem of having to jump through vicious hoops to get your grammar into LR shape (which defeats the point of (i) - it makes your grammar unreadable and difficult to implement), and the problem of exponential parsing times - which you don't care about when parsing relatively unambiguous 10-100 line fragments, but which will be in your way once you're dealing with realistic programs of 1000-10000 lines.
To do that, PEGs (or more generally top-down parsing - this has been around for ages, including Prolog's DCG grammars) need to introduce some means of limiting the backtracking to avoid the exponential blowup that you'd get there; however, wrongly placed cuts (i.e., instructions to disallow backtracking) destroy the declarative nature of the grammar and could introduce nasty problems.