11 ms·

Consider the most basic parsers you might want. For instance, a parser that only succeeds if it matches a string exactly, a parser that matches any single chara

by tel 9y ago

Consider the most basic parsers you might want. For instance, a parser that only succeeds if it matches a string exactly, a parser that matches any single character and always succeeds, a parser that matches nothing and returns some constant, a parser that always fails. They're all simple and stupid and let's give them names: string("foobar") : Parser<String> char : Parser<Character> always<A>(x: A): Parser<A> never<A>: Parser<A> These are parser combinators. They form the atoms at the foundation of a language for constructing parsers. For instance, we can imagine two parsers happening in sequence then<A, B>(a: Parser<A>, b: Parser): Parser<(A, B)> then(char, char): Parser<(Character, Character)> Or more fancily, a two parsers happening in sequence, but the second parser being defined using the output of the first. This creates context sensitivity thenDependent<A, B>(a: Parser<A>, b: A -> Parser): Parser<(A, B)> We're constructing a fundamental language for building parsers up from our atoms to larger and larger things. All we need now is a way to "run" them run<A>(p: Parser<A>): String -> Option<A> Tada---parser combinators!

chombier 9y ago
Monadic parser combinators! There is a nice paper on the subject by Graham Hutton and Erik Meijer. It's a very good introduction to both parser combinators and monads, and it's very readable even for beginners.
- lomnakkus 9y ago
 Hm? I don't see why these would have to be monadic. A simple type Parser t = Input -> Maybe (t, Input) or similar would be enough? Simple function composition gets you the rest of the way. (I grant you, it might be a bit tedious to write parsers this way, and monadic notation certainly makes it more pleasant in most cases.) For anyone following along at home: think function which takes input + current position and may return: "Nothing" if the parser doesn't match, or "a value of type t along with the rest of the unparsed input". (Obviously it'd have to be expanded to support errors properly, etc.) EDIT: Of course, I guess you could argue that they just are monadic by definition since chaining using function composition and parameter passing is the essence of a monad... Maybe that's what you were driving at?
 - Mehdi2277 9y ago
 Yeah that type is enough to make a monad. In slightly fancy language the type you just wrote is just StateT Input Maybe. Monadic mostly makes me think of bind which is just about chaining (technically also return is needed, but here return is just always succeed and give that value) and parsers have a natural notion of run one after the other.
 - lomnakkus 9y ago
 > In slightly fancy language the type you just wrote is just StateT Input Maybe. Except the newtype -- which was kind of my point :).
 - tel 9y ago
 It's only a monad if you define it to be. It's also "just" an applicative if you like. The monadic part arises when people actually _use_ bind and then you lose some information that might be nice for optimizations.
 - chombier 9y ago
 I realize I misread parent comment functions: always<A>(x: A): Parser<A> thenDependent<A, B>(a: Parser<A>, b: A -> Parser): Parser<(A, B)> as: always<A>(x: A): Parser<A> thenDependent<A, B>(a: Parser<A>, b: A -> Parser): Parser which would make a monad provided the monad laws are satisfied. Of course you don't have to write parser combinators that way, but I found it pretty practical compared to dealing with nested tuples for the sequence parser. Check out Hutton and Meijer's article for more details.
 - Tarean 9y ago
 The problem with monadic parsers is that they are too powerful. If you have two options string "foo" <|> string "for" It would be nice to automatically rewrite this as string "fo" >> (char 'o' <|> char 'r') But if we try to analyze monadic parsers like that we run into the halting problem. Applicative parsers are less powerful so we can left factor them automatically. There were some attempts to combine applicative and monadic parsers which resulted in arrow syntax but that kind of feels like the worst of both worlds for many cases.
- lihaoyi 9y ago
 Notably, you hardly ever need Monadic parser combinators. Applicative parser combinators work fine in almost all cases. FastParse lets you use parser combinators monadically, but that's only necessary in uncommon cases. The three I've come across are length + data-of-length constructs (more common in binary parsing than text), having your parser validate matched XML tags/closing-tags, and indentation-delimited-block parser (e.g. when parsing Python). For the vast majority of programming-language-like things, Applicative parser combinators are enough, including languages with complex syntax such as Scala.
amelius 9y ago
But what is the class of grammar they support? I suspect these combinators are not very powerful compared to e.g. LR(k) parsers, and provide a false sense of modularity. (E.g. a minor grammar change leading to a large scale rewrite).
- Mehdi2277 9y ago
  Roughly, context sensitive can be covered by monadic parsers, while applicative parsers are context free. LR(k) also corresponds to context free parsers. So, at least for monadic combinators they are more powerful. I also think they're fairly modular. The primitive parsers are fairly easy to write and once you have a small library (or use an existing one like Parsec) of them it is fairly easy to put them together (in haskell do notation helps too). The only other kind of parsers I have personal experience coding is recursive descent which I had more trouble trying to keep track of.
  - amelius 9y ago
    Ok, but what about the efficiency of LR(k) parsers implemented using monads? Further, do monads warn the user when there is an ambiguity in the "grammar"?
    - vorg 9y ago
      > monadic combinators are more powerful [than context free parsers] Monadic parsers can do context-sensitive things that context free parsers can't, but they can't have unordered options which context free parsers can. So really monadic parsers have different powers to context-free. > do monads warn the user when there is an ambiguity in the "grammar"? You don't have ambiguity in the grammar because monadic parsers only provide ordered options.
      - dozzie 9y ago
        > You don't have ambiguity in the grammar because monadic parsers only provide ordered options. Oh, but you do have ambiguity in the grammar, except that parser returns one of the possible parse trees deterministically and thus doesn't warn you that the input could be parsed differently. This leads to the false impression that your grammar is unambiguous.
davidgl 9y ago
I didn't really 'get' parser combinators until I watched the following introduction (showing how to build a parser library from scratch in F#): https://skillsmatter.com/skillscasts/9731-understanding-parser-combinators-a-deep-dive https://skillsmatter.com/skillscasts/9731-understanding-pars.... Highly recommended.
- bhrgunatha 9y ago
  Or watch on youtube: https://www.youtube.com/watch?v=RDalzi7mhdY https://www.youtube.com/watch?v=RDalzi7mhdY No need to create an account or login
  - davidgl 9y ago
    Great find
  - hyperion2010 9y ago
    This is a great talk. I especially like his comment here [0] about obfuscated infix operators since he opens his talk with "hopefully this talk will get you over the confusion about what `.>>.` and company mean" and then 20 minutes later he just has the line `let ( .>>. ) = andThen`. That was easy. https://youtu.be/RDalzi7mhdY?t=1898 https://youtu.be/RDalzi7mhdY?t=1898
userbinator 9y ago
It sounds vaguely like refactoring a recursive-descent parser.
- WorldMaker 9y ago
  It can certainly help to look at a parser-combinatory as a more rigorous, less artisanal/home-cooked recursive-descent parser. Good parser-combinators offer a lot more than just recursive-descent ways of looking at the parsing world, but if you are familiar with how you might do things in a recursive-descent way I think that familiarity can help in learning a parser-combinatory library. For similar reasons, too, I think PEG-style grammars are more often conceptually closer than BNF grammars for early learning/thinking in parser-combinators. But again a good parser-combinator library will have power beyond what you might consider the possibility space afforded by just PEG-style grammars, especially as you start to get into higher order combinators.
  - chubot 9y ago
    What's an example of something that can be recognized with parser combinator but not PEGs? Do parser combinators have the notion of arbitrary lookahead or backtracking?
    - louthy 9y ago
      Parser combinators can do look-ahead and backtracking, yes. You definitely pay for it in efficiency however (especially look-ahead).
motet_a 9y ago
I have the overall feeling that most people don’t realize that parser combinators are nothing more that disguized recursive descent parsers. Personally I love both.
- tel 9y ago
  They're not, though. They're a formal language for talking about all kinds of parsers. You can implement them as recursive descent if you want. You can also compile them into formal FSAs if you want.
- jhpriestley 9y ago
  Parser combinators are a quite general technique which has been applied to PEG parsing, Earley parsing, and many other specific algorithms. Recursive descent is common because it is easy to implement and allows the resulting combinators to form a Monad.
Tarean 9y ago
In languages that allow abstraction over generic types you can also reuse a lot of infrastructure to write parsers. For instance you can parse a string by chaining a bunch of char parsers: string :: String -> Parser String string s = mapM char s On the other hand this probably degrades from c-like performance to python levels so some higher level builtins that are easy to optimize and compile into efficient assembly might be a better idea.
omaranto 9y ago
Is that really how the term is used? I would have naively thought that among your examples only 'then' and 'thenDependent' are parser combinators, and that 'string("foobar")', 'char', 'always(x)' and 'never' are simply called parsers. (Maybe 'string', as opposed to the evaluated 'string("foobar")', should be called a combinator even though it doesn't take any parsers as arguments...) Just like I'd call '+' and '*' arithmetic operators but I'd call '3' a number.
- DonaldPShimoda 9y ago
 In my experience (limited) yes, this is how the term is used. "Combinator" != "combiner". A combinator is a thing which is combined with other combinators. When you combine two combinators, you end up with yet another combinator which can be combined with other combinators. Very composable, in the functional spirit of things.
 - omaranto 9y ago
 I'm not so sure, and however wrote the Wikipedia page seems to agree with me. The first sentence is "In computer programming, a parser combinator is a higher-order function that accepts several parsers as input and returns a new parser as its output." Also people name the type something like Parser<A>, not ParserCombinator<A>.
- tel 9y ago
 Combinator is a pretty overloaded term, it's difficult to pin down. In practice, something like `never` would be called a combinator, though. Also, in theory a combinator is just an expression of no free variables. S-K-I calculus is the canonical set of "combinators" and all three of them could be considered "functions" but also could be considered "atoms". So perhaps it's just vague.

by tel 9y ago

chombier 9y ago

Monadic parser combinators! There is a nice paper on the subject by Graham Hutton and Erik Meijer. It's a very good introduction to both parser combinators and monads, and it's very readable even for beginners.

lomnakkus 9y ago
Hm? I don't see why these would have to be monadic. A simple type Parser t = Input -> Maybe (t, Input) or similar would be enough? Simple function composition gets you the rest of the way. (I grant you, it might be a bit tedious to write parsers this way, and monadic notation certainly makes it more pleasant in most cases.) For anyone following along at home: think function which takes input + current position and may return: "Nothing" if the parser doesn't match, or "a value of type t along with the rest of the unparsed input". (Obviously it'd have to be expanded to support errors properly, etc.) EDIT: Of course, I guess you could argue that they just are monadic by definition since chaining using function composition and parameter passing is the essence of a monad... Maybe that's what you were driving at?
- Mehdi2277 9y ago
 Yeah that type is enough to make a monad. In slightly fancy language the type you just wrote is just StateT Input Maybe. Monadic mostly makes me think of bind which is just about chaining (technically also return is needed, but here return is just always succeed and give that value) and parsers have a natural notion of run one after the other.
 - lomnakkus 9y ago
 > In slightly fancy language the type you just wrote is just StateT Input Maybe. Except the newtype -- which was kind of my point :).
 - tel 9y ago
 It's only a monad if you define it to be. It's also "just" an applicative if you like. The monadic part arises when people actually _use_ bind and then you lose some information that might be nice for optimizations.
- chombier 9y ago
 I realize I misread parent comment functions: always<A>(x: A): Parser<A> thenDependent<A, B>(a: Parser<A>, b: A -> Parser): Parser<(A, B)> as: always<A>(x: A): Parser<A> thenDependent<A, B>(a: Parser<A>, b: A -> Parser): Parser which would make a monad provided the monad laws are satisfied. Of course you don't have to write parser combinators that way, but I found it pretty practical compared to dealing with nested tuples for the sequence parser. Check out Hutton and Meijer's article for more details.
 - Tarean 9y ago
 The problem with monadic parsers is that they are too powerful. If you have two options string "foo" <|> string "for" It would be nice to automatically rewrite this as string "fo" >> (char 'o' <|> char 'r') But if we try to analyze monadic parsers like that we run into the halting problem. Applicative parsers are less powerful so we can left factor them automatically. There were some attempts to combine applicative and monadic parsers which resulted in arrow syntax but that kind of feels like the worst of both worlds for many cases.
lihaoyi 9y ago
Notably, you hardly ever need Monadic parser combinators. Applicative parser combinators work fine in almost all cases. FastParse lets you use parser combinators monadically, but that's only necessary in uncommon cases. The three I've come across are length + data-of-length constructs (more common in binary parsing than text), having your parser validate matched XML tags/closing-tags, and indentation-delimited-block parser (e.g. when parsing Python). For the vast majority of programming-language-like things, Applicative parser combinators are enough, including languages with complex syntax such as Scala.

amelius 9y ago

But what is the class of grammar they support? I suspect these combinators are not very powerful compared to e.g. LR(k) parsers, and provide a false sense of modularity. (E.g. a minor grammar change leading to a large scale rewrite).

Mehdi2277 9y ago
Roughly, context sensitive can be covered by monadic parsers, while applicative parsers are context free. LR(k) also corresponds to context free parsers. So, at least for monadic combinators they are more powerful. I also think they're fairly modular. The primitive parsers are fairly easy to write and once you have a small library (or use an existing one like Parsec) of them it is fairly easy to put them together (in haskell do notation helps too). The only other kind of parsers I have personal experience coding is recursive descent which I had more trouble trying to keep track of.
- amelius 9y ago
  Ok, but what about the efficiency of LR(k) parsers implemented using monads? Further, do monads warn the user when there is an ambiguity in the "grammar"?
  - vorg 9y ago
    > monadic combinators are more powerful [than context free parsers] Monadic parsers can do context-sensitive things that context free parsers can't, but they can't have unordered options which context free parsers can. So really monadic parsers have different powers to context-free. > do monads warn the user when there is an ambiguity in the "grammar"? You don't have ambiguity in the grammar because monadic parsers only provide ordered options.
    - dozzie 9y ago
      > You don't have ambiguity in the grammar because monadic parsers only provide ordered options. Oh, but you do have ambiguity in the grammar, except that parser returns one of the possible parse trees deterministically and thus doesn't warn you that the input could be parsed differently. This leads to the false impression that your grammar is unambiguous.

davidgl 9y ago

I didn't really 'get' parser combinators until I watched the following introduction (showing how to build a parser library from scratch in F#): https://skillsmatter.com/skillscasts/9731-understanding-parser-combinators-a-deep-dive https://skillsmatter.com/skillscasts/9731-understanding-pars.... Highly recommended.

bhrgunatha 9y ago
Or watch on youtube: https://www.youtube.com/watch?v=RDalzi7mhdY https://www.youtube.com/watch?v=RDalzi7mhdY No need to create an account or login
- davidgl 9y ago
  Great find
- hyperion2010 9y ago
  This is a great talk. I especially like his comment here [0] about obfuscated infix operators since he opens his talk with "hopefully this talk will get you over the confusion about what `.>>.` and company mean" and then 20 minutes later he just has the line `let ( .>>. ) = andThen`. That was easy. https://youtu.be/RDalzi7mhdY?t=1898 https://youtu.be/RDalzi7mhdY?t=1898

userbinator 9y ago

It sounds vaguely like refactoring a recursive-descent parser.

WorldMaker 9y ago
It can certainly help to look at a parser-combinatory as a more rigorous, less artisanal/home-cooked recursive-descent parser. Good parser-combinators offer a lot more than just recursive-descent ways of looking at the parsing world, but if you are familiar with how you might do things in a recursive-descent way I think that familiarity can help in learning a parser-combinatory library. For similar reasons, too, I think PEG-style grammars are more often conceptually closer than BNF grammars for early learning/thinking in parser-combinators. But again a good parser-combinator library will have power beyond what you might consider the possibility space afforded by just PEG-style grammars, especially as you start to get into higher order combinators.
- chubot 9y ago
  What's an example of something that can be recognized with parser combinator but not PEGs? Do parser combinators have the notion of arbitrary lookahead or backtracking?
  - louthy 9y ago
    Parser combinators can do look-ahead and backtracking, yes. You definitely pay for it in efficiency however (especially look-ahead).

motet_a 9y ago

I have the overall feeling that most people don’t realize that parser combinators are nothing more that disguized recursive descent parsers. Personally I love both.

tel 9y ago
They're not, though. They're a formal language for talking about all kinds of parsers. You can implement them as recursive descent if you want. You can also compile them into formal FSAs if you want.
jhpriestley 9y ago
Parser combinators are a quite general technique which has been applied to PEG parsing, Earley parsing, and many other specific algorithms. Recursive descent is common because it is easy to implement and allows the resulting combinators to form a Monad.

Tarean 9y ago

In languages that allow abstraction over generic types you can also reuse a lot of infrastructure to write parsers. For instance you can parse a string by chaining a bunch of char parsers: string :: String -> Parser String string s = mapM char s On the other hand this probably degrades from c-like performance to python levels so some higher level builtins that are easy to optimize and compile into efficient assembly might be a better idea.

omaranto 9y ago

Is that really how the term is used? I would have naively thought that among your examples only 'then' and 'thenDependent' are parser combinators, and that 'string("foobar")', 'char', 'always(x)' and 'never' are simply called parsers. (Maybe 'string', as opposed to the evaluated 'string("foobar")', should be called a combinator even though it doesn't take any parsers as arguments...) Just like I'd call '+' and '*' arithmetic operators but I'd call '3' a number.

DonaldPShimoda 9y ago
In my experience (limited) yes, this is how the term is used. "Combinator" != "combiner". A combinator is a thing which is combined with other combinators. When you combine two combinators, you end up with yet another combinator which can be combined with other combinators. Very composable, in the functional spirit of things.
- omaranto 9y ago
 I'm not so sure, and however wrote the Wikipedia page seems to agree with me. The first sentence is "In computer programming, a parser combinator is a higher-order function that accepts several parsers as input and returns a new parser as its output." Also people name the type something like Parser<A>, not ParserCombinator<A>.
tel 9y ago
Combinator is a pretty overloaded term, it's difficult to pin down. In practice, something like `never` would be called a combinator, though. Also, in theory a combinator is just an expression of no free variables. S-K-I calculus is the canonical set of "combinators" and all three of them could be considered "functions" but also could be considered "atoms". So perhaps it's just vague.