2 ms·
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 o
by 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 agoThis 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.