4 ms·
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
by 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 agoSlightly 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 agoI 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 agoYour 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'.
- qixxiq 16y agoI don't believe that is valid C code; you can't assign a variable to a block.
- beza1e1 16y agoOk, i should have tried it. It does not work with a declaration. However, this code compiles just fine: int main(void) { int select = 6, from = 2; int x = {select * from}; printf("%d\n",x); // prints 12 return 0; } gcc and clang only complain the missing include for printf. cparser (which i'm working on) prints "warning: extra curly braces around scalar initializer".
- jerf 16y agoI was just copying from the post. It's not exactly how I would do it but I thought doing what I thought should be done would just distract the problem. One way or another you need some sort of delimiter, in the sense of delimiting the grammar domains, be it a explicit delimiter like a character (pair) or an implicit one like trying to guess which subgrammar you're trying to use. In the case of smashing two grammars together I would tend to prefer an explicit delimiter, because it lowers the need to coordinate between the two grammars, a difficulty that you demonstrated there.
- chriseidhof 16y agoThis can work, but your grammar will be wildly ambiguous. A better way to achieve this is to compose grammars (instead of parsers) and construct the parsers only after the final composition is done. There is a paper that deals with a very similar problem to this: composing Haskell Read instances. Instead of deriving Read instances for each datatype, they derive grammars, and only produce the parser at the last step. This allows the parser to be optimized. It is a very dense paper, not easy to read but definitely worth it: http://www.fing.edu.uy/~mviera/papers/VSL08.pdf http://www.fing.edu.uy/~mviera/papers/VSL08.pdf