4 ms·

This is one area that has always disappointed me. Compiler-compilers just never seem to have lived up to the promise of making it easier to define your own lang

by cletus 16y ago

This is one area that has always disappointed me. Compiler-compilers just never seem to have lived up to the promise of making it easier to define your own languages. If anything, languages like Ruby have done a far better job (albeit in a more limited way). I wonder at the reasons for this. Is this simply the wrong theoretical approach? If you look at formal grammars and how Yacc, ANTLR, etc deal with them, they're intended to be unambiguous. This is actually a problem in many ways. PEGs (Parsing Expression Grammars) are a relatively new (~10 years) development that I find far more interesting for this reason as they solve the ambiguity problem by simply ranking the alternatives, which can have hideous backtracking possibilities (and tend to expensive in space terms) but in practice seem to lead to more natural definitions (at least in my limited experience). I just have to wonder if we're going about this whole language thing the wrong way.

barrkel 16y ago
Parsing is a very small part of the problem; and classical compiler-compilers introduce an extra indirection in your build process. Defining a type system (which may be compile-time, run-time, or both) and coherent semantics is more work. Additionally, compiler-compilers exist in a particular zone of complexity. Your language has to be complex enough that it needs a dedicated parser rather than ad-hoc regex or recursive descent (and this needs to get over the hump of complicating your build process, which doesn't play well with modern IDEs, what with mixed source languages etc. (actions in rules)), yet not so complex or needing good error messages, recovery etc. that it again needs ad-hoc recursive-descent / operator precedence parsers. Most commercial compilers don't use yacc or anything like it; they instead usually use hand-written recursive descent.
kragen 16y ago
I agree that PEGs are more interesting. Formally speaking, you can parse PEGs in worst-case linear time with a packrat parser. Practically speaking, the constant factor on that worst case is still much worse than the usual case (the number of nonterminals in your grammar is a factor of the constant factor.) I've written a one-page PEG compiler-compiler (interspersed with many pages of text explaining it) at https://github.com/kragen/peg-bootstrap/blob/master/peg.md https://github.com/kragen/peg-bootstrap/blob/master/peg.md.
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.

by cletus 16y ago

barrkel 16y ago

Parsing is a very small part of the problem; and classical compiler-compilers introduce an extra indirection in your build process. Defining a type system (which may be compile-time, run-time, or both) and coherent semantics is more work. Additionally, compiler-compilers exist in a particular zone of complexity. Your language has to be complex enough that it needs a dedicated parser rather than ad-hoc regex or recursive descent (and this needs to get over the hump of complicating your build process, which doesn't play well with modern IDEs, what with mixed source languages etc. (actions in rules)), yet not so complex or needing good error messages, recovery etc. that it again needs ad-hoc recursive-descent / operator precedence parsers. Most commercial compilers don't use yacc or anything like it; they instead usually use hand-written recursive descent.

kragen 16y ago

I agree that PEGs are more interesting. Formally speaking, you can parse PEGs in worst-case linear time with a packrat parser. Practically speaking, the constant factor on that worst case is still much worse than the usual case (the number of nonterminals in your grammar is a factor of the constant factor.) I've written a one-page PEG compiler-compiler (interspersed with many pages of text explaining it) at https://github.com/kragen/peg-bootstrap/blob/master/peg.md https://github.com/kragen/peg-bootstrap/blob/master/peg.md.

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.