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.
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.
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.)
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.
I have used yacc and its offspring like bison for a long time. Writing the grammars is really simple, but debugging them is really arcane. The problem is that the place where the parser generator discovers the error can be some distance from where you introduced the ambiguity. Grammars have their own debugging style, particularly with yacc/bison output. Eventually you have an aha moment and you start looking for an improper empty state or trying a reduction at the wrong place in the parse tree. It isnt hard if you grasp it and probably an intractable bitch if you dont.
I will agree however, that the parser and the bison source look like someone barfed C all over the floor, unless someone has given it serious TLC in the past dozen years.
What do people use yacc and other parsing tools for these days?
Looking at the uses page for ANTLR yesterday, it seems to be entirely DSL (query languages etc) and language tools (Java src code transformers, coverage checkers etc).
It seems that if you just need a text format, you'll probably settle for JSON (if you're happy to output data-structures directly) or XML (if you need to design a schema or interop with one). They are both general, non-tailored formats, making specific formats easy to extend. Less specific, more flexible.
Recently it was said here that most modern programming languages (surprisingly) use hand-made recursive descent parsers. This gives maximum power and performance, at the cost of complexity and being a lot of work.
BTW: javacc is a nice update of yacc IMHO, using EBNF, eg. you can write repetition with an * instead of breaking it into A:: aA|- . But it doesn't seem to have an active community around it (cf ANTLR), which is sadly a crucial factor for practical use.
However, I personally have always written manual recursive descent parsers (including XML formats), instead of using tools. For me, yacc et. al. just get in the way. But it's such a cool idea! BTW: There's a body of research called "grammarware", that didn't seem to take off; and I've heard that everyone who looks at grammars believes that can make it simple and easy to use, and set out to do so, but no one ever succeeds (...yet, anyway). http://www.cs.vu.nl/grammarware/
In my humble (and I admit, extremely unpopular) opinion, XML represents an amazing leap forward towards this goal: an XML Schema (or a DTD) is a grammar, and many parsing issues just disappear using this simpler, less powerful approach. For example, it has to be deterministic (aka 1-unambiguous); you can't have recursion within the one level of an element (aka tree grammar). I just wish it weren't so ghastly and soul-destroying to use. You have to look past the surface to see its disguised beauty (its beauty is "very effectively disguised").
11 comments
[ 3.7 ms ] story [ 46.7 ms ] threadI 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.
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.
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.
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.
I will agree however, that the parser and the bison source look like someone barfed C all over the floor, unless someone has given it serious TLC in the past dozen years.
Looking at the uses page for ANTLR yesterday, it seems to be entirely DSL (query languages etc) and language tools (Java src code transformers, coverage checkers etc).
It seems that if you just need a text format, you'll probably settle for JSON (if you're happy to output data-structures directly) or XML (if you need to design a schema or interop with one). They are both general, non-tailored formats, making specific formats easy to extend. Less specific, more flexible.
Recently it was said here that most modern programming languages (surprisingly) use hand-made recursive descent parsers. This gives maximum power and performance, at the cost of complexity and being a lot of work.
BTW: javacc is a nice update of yacc IMHO, using EBNF, eg. you can write repetition with an * instead of breaking it into A:: aA|- . But it doesn't seem to have an active community around it (cf ANTLR), which is sadly a crucial factor for practical use.
However, I personally have always written manual recursive descent parsers (including XML formats), instead of using tools. For me, yacc et. al. just get in the way. But it's such a cool idea! BTW: There's a body of research called "grammarware", that didn't seem to take off; and I've heard that everyone who looks at grammars believes that can make it simple and easy to use, and set out to do so, but no one ever succeeds (...yet, anyway). http://www.cs.vu.nl/grammarware/
In my humble (and I admit, extremely unpopular) opinion, XML represents an amazing leap forward towards this goal: an XML Schema (or a DTD) is a grammar, and many parsing issues just disappear using this simpler, less powerful approach. For example, it has to be deterministic (aka 1-unambiguous); you can't have recursion within the one level of an element (aka tree grammar). I just wish it weren't so ghastly and soul-destroying to use. You have to look past the surface to see its disguised beauty (its beauty is "very effectively disguised").
funfact: Eric Schmidt wrote lex http://en.wikipedia.org/wiki/Lex_(software) Now, you might pooh-pooh lex for various reasons, but you can't call Eric a non-technical CEO.
[1] http://handlebars.strobeapp.com/
[2] http://zaach.github.com/jison/
Here's the spec itself: https://github.com/Ruby/Ruby/blob/trunk/parse.y