14 ms·

I have a toy problem that I throw at anyone who thinks they've "solved" parsing: Haskell list comprehensions. A list comprehension takes the form "[" EXPR

by rntz 8y ago

I have a toy problem that I throw at anyone who thinks they've "solved" parsing: Haskell list comprehensions. A list comprehension takes the form "[" EXPR "|" STMT["," STMT]* "]" Where STMT is given by: STMT ::= EXPR | PAT "<-" EXPR The problem is that, until you see that "<-", you don't know whether you're supposed to be parsing a pattern PAT or an expression EXPR. This is extra hard because patterns and expressions overlap significantly; for example, "(x, Left 2)" could be either a pattern or expression. But "(x, Left (2+3))" is definitely an expression. You can get arbitrarily deep into parsing a pattern before you realize it's actually an expression! Recursive descent parsers, even with precedence climbing, can't really handle this nicely. Neither can LL or LR parsers. In fact, GHC's actual parser uses a hack: it parses patterns as expressions, and as a post-processing step checks that the expression it parsed actually was a valid pattern! This works IF your patterns are a subset of your expressions. But if there are patterns that aren't valid expressions (Racket's match-patterns have this property), then you need to get even cleverer. General-purpose parsing algorithms like GLR, GLL, parsing with derivatives, and Earley parsing (which Kegler advocates) can handle this, of course, although I'm not sure how efficiently they do it.

lifthrasiir 8y ago
I argue the parsing "problem" is not really a "problem" (for most people, anyway). When you view something as a problem, the problem should have an input and a desired output. The name of a parsing "problem" assumes that the input is a grammar and the output is a (hopefully efficient) function from a sequence of symbols to a parse tree or a boolean flag certifying that the grammar accepts given string. Naturally, solving this "problem" requires a general algorithm that works well for most or all variety of grammars. However this setting is far from the current practice: people just avoid a grammar that is hard to parse at all! Of course there are many practical grammars have ambiguities that require hacks, but there seems the maximum number of hacks permitted, and people ditch a grammar requiring too many hacks. Limiting l-value syntax to a subset of r-value syntax works because there is generally only one of them in the entire grammar. Well, even in the (LA)LR age people just resorted to the semi-automatic s-r conflict resolution without much thought. So the grammar is not an uncontrollable input; in many cases it is flexible enough to make the whole parsing "problem" irrelevant. I still believe that having a solution to the general parsing problem is nice (there are still a lot of applications with no control available to input grammars, granted), but I think its importance is somewhat overvalued.
- deleted 8y ago
  [deleted]
userbinator 8y ago
You can get arbitrarily deep into parsing a pattern before you realize it's actually an expression! C++ has a similar ambiguity with function definitions and object initialisers. Thankfully, it's an easily solved problem --- recursive descent with branching handles it just fine. In your example, when it reaches STMT, it will start parsing both EXPR and PAT in parallel, and terminate the EXPR branch when "<-" is encountered. In general, the idea is to split whenever the current position is ambiguous, and proceed until one of the branches can't (or if both branches remain valid, choose one or report an error.) Then what is left must be the correct parse.
- rntz 8y ago
  This does work, and is available in e.g. the Parsec library for Haskell, but (1) can lead to exponential worst-case backtracking behavior. (2) can produce very unhelpful error messages without careful engineering. In this case, for list comprehensions, I think you can show that you won't have exponential backtracking behavior. But it involves carefully thinking about whether patterns can nest inside of expressions nesting inside of patterns nesting... etc. It's probably still the best solution if you're writing your own parser, though.
lisper 8y ago
There is very little sport in inventing syntaxes that are hard to parse. My response, like the doctor responding to the patient who complains, "It hurts when I poke myself in the eye", is: don't do that.
- rntz 8y ago
  On the one hand, you're right. Python takes exactly this approach: it disambiguates using "for" and "if": LISTCOMP ::= [ EXPR STMT* ] STMT ::= "if" EXPR | "for" PAT "in" EXPR This is LL(1) and trivial to parse recursively. On the other hand, Haskell list comprehensions really aren't hard to parse... for humans! Most people I've talked about this have no idea that Haskell comprehensions are formally so much harder to parse than Python list comprehensions. The difficult cases just don't arise in practice. And there are plenty of places where we accept problems or algorithms which are ridiculously inefficient in theory, but fine in practice. Damas-Milner type inference, for example, takes time O(2^2^PROGSIZE) in the worst case - doubly exponential! Far worse (in theory) than the O(n^3) of general CFG parsing algorithms (which can be quite simple to implement!). And this problem doesn't just come up in Haskell list comprehensions, but also with monadic do-notation. I'd much rather write: do (x,y) <- foo z <- bar x return (x + y + z) than: do for (x,y) <- foo for z <- bar x return (x + y + z) The extra "for" (or whatever keyword you want to put there) is just syntactic noise to a human, however much easier it makes it for a computer to parse it. So I'm of two minds, really.
  - lisper 8y ago
    I think humans have an easy time because it's easy for them to look ahead (literally!) to see if there's a <- token. So if I were going to tackle this problem I would do it in two passes. In the first pass I'd just tokenize everything, and set a flag if I saw "<-". Then I'd use the value of that flag to inform the second pass about what it was parsing.

by rntz 8y ago

lifthrasiir 8y ago

I argue the parsing "problem" is not really a "problem" (for most people, anyway). When you view something as a problem, the problem should have an input and a desired output. The name of a parsing "problem" assumes that the input is a grammar and the output is a (hopefully efficient) function from a sequence of symbols to a parse tree or a boolean flag certifying that the grammar accepts given string. Naturally, solving this "problem" requires a general algorithm that works well for most or all variety of grammars. However this setting is far from the current practice: people just avoid a grammar that is hard to parse at all! Of course there are many practical grammars have ambiguities that require hacks, but there seems the maximum number of hacks permitted, and people ditch a grammar requiring too many hacks. Limiting l-value syntax to a subset of r-value syntax works because there is generally only one of them in the entire grammar. Well, even in the (LA)LR age people just resorted to the semi-automatic s-r conflict resolution without much thought. So the grammar is not an uncontrollable input; in many cases it is flexible enough to make the whole parsing "problem" irrelevant. I still believe that having a solution to the general parsing problem is nice (there are still a lot of applications with no control available to input grammars, granted), but I think its importance is somewhat overvalued.

deleted 8y ago
[deleted]

userbinator 8y ago

You can get arbitrarily deep into parsing a pattern before you realize it's actually an expression! C++ has a similar ambiguity with function definitions and object initialisers. Thankfully, it's an easily solved problem --- recursive descent with branching handles it just fine. In your example, when it reaches STMT, it will start parsing both EXPR and PAT in parallel, and terminate the EXPR branch when "<-" is encountered. In general, the idea is to split whenever the current position is ambiguous, and proceed until one of the branches can't (or if both branches remain valid, choose one or report an error.) Then what is left must be the correct parse.

rntz 8y ago
This does work, and is available in e.g. the Parsec library for Haskell, but (1) can lead to exponential worst-case backtracking behavior. (2) can produce very unhelpful error messages without careful engineering. In this case, for list comprehensions, I think you can show that you won't have exponential backtracking behavior. But it involves carefully thinking about whether patterns can nest inside of expressions nesting inside of patterns nesting... etc. It's probably still the best solution if you're writing your own parser, though.

lisper 8y ago

There is very little sport in inventing syntaxes that are hard to parse. My response, like the doctor responding to the patient who complains, "It hurts when I poke myself in the eye", is: don't do that.

rntz 8y ago
On the one hand, you're right. Python takes exactly this approach: it disambiguates using "for" and "if": LISTCOMP ::= [ EXPR STMT* ] STMT ::= "if" EXPR | "for" PAT "in" EXPR This is LL(1) and trivial to parse recursively. On the other hand, Haskell list comprehensions really aren't hard to parse... for humans! Most people I've talked about this have no idea that Haskell comprehensions are formally so much harder to parse than Python list comprehensions. The difficult cases just don't arise in practice. And there are plenty of places where we accept problems or algorithms which are ridiculously inefficient in theory, but fine in practice. Damas-Milner type inference, for example, takes time O(2^2^PROGSIZE) in the worst case - doubly exponential! Far worse (in theory) than the O(n^3) of general CFG parsing algorithms (which can be quite simple to implement!). And this problem doesn't just come up in Haskell list comprehensions, but also with monadic do-notation. I'd much rather write: do (x,y) <- foo z <- bar x return (x + y + z) than: do for (x,y) <- foo for z <- bar x return (x + y + z) The extra "for" (or whatever keyword you want to put there) is just syntactic noise to a human, however much easier it makes it for a computer to parse it. So I'm of two minds, really.
- lisper 8y ago
  I think humans have an easy time because it's easy for them to look ahead (literally!) to see if there's a <- token. So if I were going to tackle this problem I would do it in two passes. In the first pass I'd just tokenize everything, and set a flag if I saw "<-". Then I'd use the value of that flag to inform the second pass about what it was parsing.