7 ms·

Parsing ought to be easier

62 points by soundsop 16y ago

jerf 16y ago
As the parsing topic has been bouncing around the past couple of days and especially as it has turned to composability of grammars I've been waiting for someone to say "parser combinator", in the style of Parsec in Haskell. I'm not that experienced in parsing, but couldn't a parser combinator approach do this almost trivially? You might have to add a bit of a concept of an escaping layer in the general case (the specific case shown is OK because a bare } is never legal in SQL but you can't count on that in general) but that doesn't seem like a terrible addition. After all, the entire purpose of parser combinators is by definition to build a grammar/parser up from atomic parsing elements and combine them into larger ones. In this case it would be something like this fragment: assignment = do varname <- legal_variable_name -- defined elsewhere _ <- char '=' exp <- expression _ <- statementTerminator return $ Assignment varname exp -- returns the corresponding AST node -- a prioritized list of all possible expressions, each -- thing in the oneOf is itself a parser expression, -- obviously missing a lot expression = oneOf [number, string, queryExpression, ...] queryExpression = do _ <- char '{' sqlValue <- sqlLanguageSelectStatement -- defined elsewhere _ <- char '}' return $ QueryExpression sqlValue although the details would vary wildly depending on the grammars in question, and as clean as this looks it's oversimplified, though parser combinators do seem to offer powerful tools for keeping your grammars clean if you use them properly and keep things well-factored just as you would any other code. (The use of the underscore is a clear way to express "I'm throwing away this value"; they are optional but I find they make my grammars more explicit. YMMV. Also if we were really going to do this there are some tweaks I'd at least consider, like explicitly terminating the sqlLanguageSelectStatement with a semicolon or something.) This really should have come up before now, so I'm assuming there's some blinding flaw in this; could someone enlighten me? (One thing that leaps to mind is that they may not be powerful enough for many cases, I don't know. I've certainly used them to implement arithmetic precedence so I know that's not an intrinsic problem but I have not pushed them to their limits.)
- andolanra 16y ago
  Slightly off-topic; a tiny bit of Parsec advice—you don't actually need the undercore at all. queryExpression can be equivalently expressed as queryExpression = do char '{' sqlValue <- sqlLanguageSelectStatement char '}' return $ QueryExpression sqlValue and it will be exactly the same parser. Incidentally, my personal preference is not to use do-notation at all and instead to use applicative functors (as they do in Real World Haskell, c.f. http://book.realworldhaskell.org/read/using-parsec.html#id652399 http://book.realworldhaskell.org/read/using-parsec.html#id65... ) I think it makes code more concise and readable. In that case, queryExpression would look like queryExpression = QueryExpression <$> (char '{' *> sqlLanguageSelectStatement <* char '}') which again does exactly the same thing. (The * > operator chains things together but throws away its left-hand side, and <* does the same but throws away its right-hand side, so you're left with the result from parsing sqlLanguageSelectStatement, and <$>, which is a synonym for fmap, reaches in and wraps the result of the parser in a QueryExpression. The only downside is you have to write the Applicative instance yourself, but because GenParser is already a monad, all you need to do is define each method to be the equivalent monad method, which they show in the link above.) As for your broad idea—the only issue is that sometimes parser combinators aren't as fast or finely tuned as a handwritten parser, and there's a chance that you'd have to do some kind of backtracking. But the short answer is yes, that is exactly what parser combinators are designed to do, and they do it pretty well and very easily.
  - jerf 16y ago
    I got the _ from HLint, which suggested it in general when discarding values in do notation. Mostly I ignored it but in parsers in particular I found it helpful. Your applicative functor approach eliminates the need for it anyhow, which is also a, uh, what's the opposite of a code smell? Code disinfectant? I'll adopt that, thanks.
- beza1e1 16y ago
  Your grammar requires a special token '{', so the parser can recognize the start of the sql statement. Likewise '}' for the end. I'm not sure, whether you can drop that and what the consequence are. You're certainly not linear anymore. It might be that the introduction of such special tokens is the "hack" required for embedding grammars into each other. Note that '{' '}' is a bad choice. For example, "x = {select * from ;};" is perfectly fine C code under the assumption that there is a type 'select'.
k4st 16y ago
Parser composability is trivial with Pratt parsers. One need only introduce the idea of denotation groups/categories, and allow one to specify a specific category along with a precedence. Add to this the ability to do ordered choice on denotations based on the first token(s) of the led/nud and you've got yourself a nice system :D
substack 16y ago
Isn't this what perl6 grammars set out to solve?
- apenwarr 16y ago
  Good point, I forgot about those! They are a very exciting feature of the perl6 design, if only because someone is finally serious about making progress in the world of parsing. Some interesting articles about perl6's parsing: http://dev.perl.org/perl6/doc/design/apo/A05.html http://dev.perl.org/perl6/doc/design/apo/A05.html (Apocalypse 5) and especially http://dev.perl.org/perl6/doc/design/exe/E05.html#A_cleaner_approach http://dev.perl.org/perl6/doc/design/exe/E05.html#A_cleaner_... (Exegesis 5) The bad news is that the syntax is rather insane and perl-like. But the good news is it's some seriously powerful stuff.
dfox 16y ago
As for the practical construction of parsers, you don't have to make special case hacks for operator precedence, you only have to express operator precedence directly in grammar (using trick that seems obvious once you see it). Recursive descent is often ideal in practice, but it is "unfashionable" mostly because it's trivial to write tools that convert grammar in "right" form to parsers, but almost impossible to write tools that converts random grammar into such "right" form. Most other subsets of CFG are significantly more complex to parse, but better suited to computer manipulation on the grammar level (typical LALR parser generator does the above mentioned trick internally and many similar transformations).
kragen 16y ago
PEGs are one class of cleanly composable grammars. OMeta uses that attribute of theirs to great advantage. And PEGs are, formally speaking, parsable in worst-case linear time, although whether that linear time is fast enough to be practical is still unknown, and it also potentially uses large linear space. I hope it's not vulgar to post yet another link to my minimal PEG parser generator in one page of code: https://github.com/kragen/peg-bootstrap/blob/master/peg.md https://github.com/kragen/peg-bootstrap/blob/master/peg.md In particular, the example here of embedding SQL in C would be pretty trivial to do as a PEG. PEGs can parse some languages that are not context-free — the example from Bryan Ford's thesis is aₓbₓcₓ, where xᵢ means "i repetitions of x". I think there are also context-free languages they can't parse, but I'm not sure. (Operator precedence parsing is particularly ugly in PEGs, since by default, they don't support left recursion. The OMeta folks figured out how to cleanly support left recursion in PEGs, but you lose the linear-time guarantee.) One very appealing attribute of PEGs is that you can conveniently extend PEGs to support parameterized productions, which could be crucial in building up a library of general-purpose parsing productions that could reasonably be used to shorten the time to define new languages. k4st claims in http://news.ycombinator.com/item?id=2330672 http://news.ycombinator.com/item?id=2330672 that Pratt top-down operator-precedence parsers are also cleanly composable. I didn't know that, and it seems like a surprising claim, but I don't really understand Pratt parsers yet. Crock has written an excellent article on Pratt parsers as his Beautiful Code chapter, and his JSLint is written with one. I think this is the same text as his chapter: http://javascript.crockford.com/tdop/tdop.html http://javascript.crockford.com/tdop/tdop.html Earley parsers can parse any context-free sentence in worst-case O(N³) time. Context-free grammars can, of course, be easily composed. Quoting Earley's abstract, "It has a time bound proportional to n³ (where n is the length of the string being parsed) in general; it has an n² bound for unambiguous grammars; and it runs in linear time on a large class of grammars, which seems to include most practical context-free programming language grammars." John Aycock has written an Earley parser generator called SPARK which is included with Python, and is reportedly pretty efficient. He's advocated using it specifically because of the composability concern. http://pages.cpsc.ucalgary.ca/~aycock/spark/ http://pages.cpsc.ucalgary.ca/~aycock/spark/ Laurie Tratt just posted this other thing about parsing that's currently on the front page of HN; it's really excellent, and duplicates much of what I've written above: http://tratt.net/laurie/tech_articles/articles/parsing_the_solved_problem_that_isnt http://tratt.net/laurie/tech_articles/articles/parsing_the_s...
elgenie 16y ago
It's odd that he talks about hacking together precedence parsing, when the very nice algorithms for doing that are well known. Check out http://en.wikipedia.org/wiki/Shunting_yard_algorithm http://en.wikipedia.org/wiki/Shunting_yard_algorithm at http://en.wikipedia.org/wiki/Operator-precedence_parser#Example_algorithm_known_as_precedence_climbing_to_parse_infix_notation http://en.wikipedia.org/wiki/Operator-precedence_parser#Exam... makes that
- beza1e1 16y ago
  Additionally, precendence climbing allows the programmer to define new operators. For example Haskell has that.
mynegation 16y ago
Most of the time when someone talks about "easy recursive-descent parser" it is not even strictly speaking a real recursive descent parser. It is usually some kind of top-down parser with horrendous tricks thrown in. Is it easier to write parsers like that? Definitely, I did my fair share of this exercise too. Is it a good thing to do? Not if you want a fast, reliable and maintainable parser. Yes, using LALR(0) (or LALR(k) or whatever) parser generator requires much more effort and disciplined thinking but in exchange you get time and memory constraint guarantees, error reporting and (sometimes) error recovery for free and may be even the tool-chain for subsequent stages (AST, attributed grammars, IR). So if I see a phrase "let it be a hack" in the text about parsing, there is a good chance that parsers written with this mindset run in exponential time. I am not saying that "recursive-descent" or any other ad hoc approach is bad. Sometimes you do have to resort to various hacks. Even original C is not, strictly speaking, a context-free language: parser has to consult a symbol table to recognize identifier class to parse source code properly. C++ (which is a textbook example of how NOT to design programming languages) made things 100x worse. But, for obvious reasons, you still need to parse those languages. So, at some point gcc developers just rewrote C++ frontend from scratch using recursive descent techniques, because it is so much easier to intervene and introduce hacks in this framework than in the rules for LALR parser generator like yacc or bison. TL;DR version of my response: use recursive descent if you have to, but using it for everything is just a demonstration of ignorance and may significantly hurt performance and maintainability.
- Rusky 16y ago
  I would actually say recursive descent is better for more complicated projects. Good error reporting in something like Bison is difficult, and that style of parser is also not necessarily any faster. IIRC, GCC uses recursive descent for (at least partially) those reasons. However, parser combinators make things even better. You get a program that looks like a grammar, just like with a parser generator, but error reporting is much easier and because you're really writing everything in the full programming language you can be much more expressive.
warrenwilkinson 16y ago
My university taught LL and LR parsing as 'compilers'. But you actually don't need anything complicated. A lisp parser is very simple, and colorForth does away with parsing entirely. Never the less, everyone pushes for yet more special case syntax in their compilers. But the more 'intelligent' parsers become, the less intelligible their own code becomes. Personally, I don't think a useful 'composable grammer' language will materialize. But an alternative exists: simple syntax that let you define your own semantics.
qixxiq 16y ago
I've always thought of setting up a programming language using unicode for a couple extra tokens (that would really assist with things like this). Could simply assign keyboard macro's for « and », and maybe one or two other useful tokens and create a far more powerful syntax. Obviously it would cause massive issues with sharing code and annoy tons of programmers; but a couple extra tokens used effectively would really really help.
bad_user 16y ago
Doing operator precedence in Antlr, which is generating LL(wildcard) parsers: expr: mult ('+' mult)* ; mult: atom ('*' atom)* ; atom: INT | '(' expr ')' ; Not much hackery there, just some look-ahead and recursion. The grammar itself is context-free and LL(k) and the implementation is trivial once you understand what pushdown automatons are (automata theory, right after finite-state machines).
wingo 16y ago
I got to the "Booya!" and tittered.
lyudmil 16y ago
I'm not sure I get the point about "hacking" around operator precedence. Isn't the normal way to get around this to define the grammar differently? For example: expression -> factor | factor + expression factor -> number | term * factor term -> number | (expression) number -> [0..9] | [1..9][0..9]+ Is this the hack the author is referring to? Why is it a hack?
- kragen 16y ago
  That's one way to hack it. Another way to hack it is to write an ambiguous grammar, but annotate the productions with precedences to tell your LALR parser generator how to resolve the ambiguities. And of course you can do what apenwarr suggests — parse with a grammar that is unambiguous but assigns the wrong precedence, and then rewrite the parse tree once it's built.

62 points by soundsop 16y ago

jerf 16y ago

As the parsing topic has been bouncing around the past couple of days and especially as it has turned to composability of grammars I've been waiting for someone to say "parser combinator", in the style of Parsec in Haskell. I'm not that experienced in parsing, but couldn't a parser combinator approach do this almost trivially? You might have to add a bit of a concept of an escaping layer in the general case (the specific case shown is OK because a bare } is never legal in SQL but you can't count on that in general) but that doesn't seem like a terrible addition. After all, the entire purpose of parser combinators is by definition to build a grammar/parser up from atomic parsing elements and combine them into larger ones. In this case it would be something like this fragment: assignment = do varname <- legal_variable_name -- defined elsewhere _ <- char '=' exp <- expression _ <- statementTerminator return $ Assignment varname exp -- returns the corresponding AST node -- a prioritized list of all possible expressions, each -- thing in the oneOf is itself a parser expression, -- obviously missing a lot expression = oneOf [number, string, queryExpression, ...] queryExpression = do _ <- char '{' sqlValue <- sqlLanguageSelectStatement -- defined elsewhere _ <- char '}' return $ QueryExpression sqlValue although the details would vary wildly depending on the grammars in question, and as clean as this looks it's oversimplified, though parser combinators do seem to offer powerful tools for keeping your grammars clean if you use them properly and keep things well-factored just as you would any other code. (The use of the underscore is a clear way to express "I'm throwing away this value"; they are optional but I find they make my grammars more explicit. YMMV. Also if we were really going to do this there are some tweaks I'd at least consider, like explicitly terminating the sqlLanguageSelectStatement with a semicolon or something.) This really should have come up before now, so I'm assuming there's some blinding flaw in this; could someone enlighten me? (One thing that leaps to mind is that they may not be powerful enough for many cases, I don't know. I've certainly used them to implement arithmetic precedence so I know that's not an intrinsic problem but I have not pushed them to their limits.)

andolanra 16y ago
Slightly off-topic; a tiny bit of Parsec advice—you don't actually need the undercore at all. queryExpression can be equivalently expressed as queryExpression = do char '{' sqlValue <- sqlLanguageSelectStatement char '}' return $ QueryExpression sqlValue and it will be exactly the same parser. Incidentally, my personal preference is not to use do-notation at all and instead to use applicative functors (as they do in Real World Haskell, c.f. http://book.realworldhaskell.org/read/using-parsec.html#id652399 http://book.realworldhaskell.org/read/using-parsec.html#id65... ) I think it makes code more concise and readable. In that case, queryExpression would look like queryExpression = QueryExpression <$> (char '{' *> sqlLanguageSelectStatement <* char '}') which again does exactly the same thing. (The * > operator chains things together but throws away its left-hand side, and <* does the same but throws away its right-hand side, so you're left with the result from parsing sqlLanguageSelectStatement, and <$>, which is a synonym for fmap, reaches in and wraps the result of the parser in a QueryExpression. The only downside is you have to write the Applicative instance yourself, but because GenParser is already a monad, all you need to do is define each method to be the equivalent monad method, which they show in the link above.) As for your broad idea—the only issue is that sometimes parser combinators aren't as fast or finely tuned as a handwritten parser, and there's a chance that you'd have to do some kind of backtracking. But the short answer is yes, that is exactly what parser combinators are designed to do, and they do it pretty well and very easily.
- jerf 16y ago
  I got the _ from HLint, which suggested it in general when discarding values in do notation. Mostly I ignored it but in parsers in particular I found it helpful. Your applicative functor approach eliminates the need for it anyhow, which is also a, uh, what's the opposite of a code smell? Code disinfectant? I'll adopt that, thanks.
beza1e1 16y ago
Your grammar requires a special token '{', so the parser can recognize the start of the sql statement. Likewise '}' for the end. I'm not sure, whether you can drop that and what the consequence are. You're certainly not linear anymore. It might be that the introduction of such special tokens is the "hack" required for embedding grammars into each other. Note that '{' '}' is a bad choice. For example, "x = {select * from ;};" is perfectly fine C code under the assumption that there is a type 'select'.

k4st 16y ago

Parser composability is trivial with Pratt parsers. One need only introduce the idea of denotation groups/categories, and allow one to specify a specific category along with a precedence. Add to this the ability to do ordered choice on denotations based on the first token(s) of the led/nud and you've got yourself a nice system :D

substack 16y ago

Isn't this what perl6 grammars set out to solve?

apenwarr 16y ago
Good point, I forgot about those! They are a very exciting feature of the perl6 design, if only because someone is finally serious about making progress in the world of parsing. Some interesting articles about perl6's parsing: http://dev.perl.org/perl6/doc/design/apo/A05.html http://dev.perl.org/perl6/doc/design/apo/A05.html (Apocalypse 5) and especially http://dev.perl.org/perl6/doc/design/exe/E05.html#A_cleaner_approach http://dev.perl.org/perl6/doc/design/exe/E05.html#A_cleaner_... (Exegesis 5) The bad news is that the syntax is rather insane and perl-like. But the good news is it's some seriously powerful stuff.

dfox 16y ago

As for the practical construction of parsers, you don't have to make special case hacks for operator precedence, you only have to express operator precedence directly in grammar (using trick that seems obvious once you see it). Recursive descent is often ideal in practice, but it is "unfashionable" mostly because it's trivial to write tools that convert grammar in "right" form to parsers, but almost impossible to write tools that converts random grammar into such "right" form. Most other subsets of CFG are significantly more complex to parse, but better suited to computer manipulation on the grammar level (typical LALR parser generator does the above mentioned trick internally and many similar transformations).

kragen 16y ago

PEGs are one class of cleanly composable grammars. OMeta uses that attribute of theirs to great advantage. And PEGs are, formally speaking, parsable in worst-case linear time, although whether that linear time is fast enough to be practical is still unknown, and it also potentially uses large linear space. I hope it's not vulgar to post yet another link to my minimal PEG parser generator in one page of code: https://github.com/kragen/peg-bootstrap/blob/master/peg.md https://github.com/kragen/peg-bootstrap/blob/master/peg.md In particular, the example here of embedding SQL in C would be pretty trivial to do as a PEG. PEGs can parse some languages that are not context-free — the example from Bryan Ford's thesis is aₓbₓcₓ, where xᵢ means "i repetitions of x". I think there are also context-free languages they can't parse, but I'm not sure. (Operator precedence parsing is particularly ugly in PEGs, since by default, they don't support left recursion. The OMeta folks figured out how to cleanly support left recursion in PEGs, but you lose the linear-time guarantee.) One very appealing attribute of PEGs is that you can conveniently extend PEGs to support parameterized productions, which could be crucial in building up a library of general-purpose parsing productions that could reasonably be used to shorten the time to define new languages. k4st claims in http://news.ycombinator.com/item?id=2330672 http://news.ycombinator.com/item?id=2330672 that Pratt top-down operator-precedence parsers are also cleanly composable. I didn't know that, and it seems like a surprising claim, but I don't really understand Pratt parsers yet. Crock has written an excellent article on Pratt parsers as his Beautiful Code chapter, and his JSLint is written with one. I think this is the same text as his chapter: http://javascript.crockford.com/tdop/tdop.html http://javascript.crockford.com/tdop/tdop.html Earley parsers can parse any context-free sentence in worst-case O(N³) time. Context-free grammars can, of course, be easily composed. Quoting Earley's abstract, "It has a time bound proportional to n³ (where n is the length of the string being parsed) in general; it has an n² bound for unambiguous grammars; and it runs in linear time on a large class of grammars, which seems to include most practical context-free programming language grammars." John Aycock has written an Earley parser generator called SPARK which is included with Python, and is reportedly pretty efficient. He's advocated using it specifically because of the composability concern. http://pages.cpsc.ucalgary.ca/~aycock/spark/ http://pages.cpsc.ucalgary.ca/~aycock/spark/ Laurie Tratt just posted this other thing about parsing that's currently on the front page of HN; it's really excellent, and duplicates much of what I've written above: http://tratt.net/laurie/tech_articles/articles/parsing_the_solved_problem_that_isnt http://tratt.net/laurie/tech_articles/articles/parsing_the_s...

elgenie 16y ago

It's odd that he talks about hacking together precedence parsing, when the very nice algorithms for doing that are well known. Check out http://en.wikipedia.org/wiki/Shunting_yard_algorithm http://en.wikipedia.org/wiki/Shunting_yard_algorithm at http://en.wikipedia.org/wiki/Operator-precedence_parser#Example_algorithm_known_as_precedence_climbing_to_parse_infix_notation http://en.wikipedia.org/wiki/Operator-precedence_parser#Exam... makes that

beza1e1 16y ago
Additionally, precendence climbing allows the programmer to define new operators. For example Haskell has that.

mynegation 16y ago

Most of the time when someone talks about "easy recursive-descent parser" it is not even strictly speaking a real recursive descent parser. It is usually some kind of top-down parser with horrendous tricks thrown in. Is it easier to write parsers like that? Definitely, I did my fair share of this exercise too. Is it a good thing to do? Not if you want a fast, reliable and maintainable parser. Yes, using LALR(0) (or LALR(k) or whatever) parser generator requires much more effort and disciplined thinking but in exchange you get time and memory constraint guarantees, error reporting and (sometimes) error recovery for free and may be even the tool-chain for subsequent stages (AST, attributed grammars, IR). So if I see a phrase "let it be a hack" in the text about parsing, there is a good chance that parsers written with this mindset run in exponential time. I am not saying that "recursive-descent" or any other ad hoc approach is bad. Sometimes you do have to resort to various hacks. Even original C is not, strictly speaking, a context-free language: parser has to consult a symbol table to recognize identifier class to parse source code properly. C++ (which is a textbook example of how NOT to design programming languages) made things 100x worse. But, for obvious reasons, you still need to parse those languages. So, at some point gcc developers just rewrote C++ frontend from scratch using recursive descent techniques, because it is so much easier to intervene and introduce hacks in this framework than in the rules for LALR parser generator like yacc or bison. TL;DR version of my response: use recursive descent if you have to, but using it for everything is just a demonstration of ignorance and may significantly hurt performance and maintainability.

Rusky 16y ago
I would actually say recursive descent is better for more complicated projects. Good error reporting in something like Bison is difficult, and that style of parser is also not necessarily any faster. IIRC, GCC uses recursive descent for (at least partially) those reasons. However, parser combinators make things even better. You get a program that looks like a grammar, just like with a parser generator, but error reporting is much easier and because you're really writing everything in the full programming language you can be much more expressive.

warrenwilkinson 16y ago

My university taught LL and LR parsing as 'compilers'. But you actually don't need anything complicated. A lisp parser is very simple, and colorForth does away with parsing entirely. Never the less, everyone pushes for yet more special case syntax in their compilers. But the more 'intelligent' parsers become, the less intelligible their own code becomes. Personally, I don't think a useful 'composable grammer' language will materialize. But an alternative exists: simple syntax that let you define your own semantics.

qixxiq 16y ago

I've always thought of setting up a programming language using unicode for a couple extra tokens (that would really assist with things like this). Could simply assign keyboard macro's for « and », and maybe one or two other useful tokens and create a far more powerful syntax. Obviously it would cause massive issues with sharing code and annoy tons of programmers; but a couple extra tokens used effectively would really really help.

bad_user 16y ago

Doing operator precedence in Antlr, which is generating LL(wildcard) parsers: expr: mult ('+' mult)* ; mult: atom ('*' atom)* ; atom: INT | '(' expr ')' ; Not much hackery there, just some look-ahead and recursion. The grammar itself is context-free and LL(k) and the implementation is trivial once you understand what pushdown automatons are (automata theory, right after finite-state machines).

wingo 16y ago

I got to the "Booya!" and tittered.

lyudmil 16y ago

I'm not sure I get the point about "hacking" around operator precedence. Isn't the normal way to get around this to define the grammar differently? For example: expression -> factor | factor + expression factor -> number | term * factor term -> number | (expression) number -> [0..9] | [1..9][0..9]+ Is this the hack the author is referring to? Why is it a hack?

kragen 16y ago
That's one way to hack it. Another way to hack it is to write an ambiguous grammar, but annotate the productions with precedences to tell your LALR parser generator how to resolve the ambiguities. And of course you can do what apenwarr suggests — parse with a grammar that is unambiguous but assigns the wrong precedence, and then rewrite the parse tree once it's built.