News for hackers. Stuff that matters.

A comment on What the heck is a parser-combinator?.

Re:What the heck is a parser-combinator? by tel on Wednesday June 21, 2017 @12:30AM (#14600662)
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<B>): 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<B>): 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!
[ Parent | on HN ]
Re:What the heck is a parser-combinator? by davidgl on Wednesday June 21, 2017 @05:47AM (#14602363)
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-pars.... Highly recommended.
[ Parent | on HN ]
Re:What the heck is a parser-combinator? by bhrgunatha on Wednesday June 21, 2017 @06:13AM (#14602452)
Or watch on youtube: https://www.youtube.com/watch?v=RDalzi7mhdY

No need to create an account or login

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by hyperion2010 on Wednesday June 21, 2017 @12:57PM (#14605588)
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

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by davidgl on Wednesday June 21, 2017 @08:16AM (#14603039)
Great find
[ Parent | on HN ]
Re:What the heck is a parser-combinator? by omaranto on Wednesday June 21, 2017 @12:10PM (#14605017)
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.

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by tel on Wednesday June 21, 2017 @01:48PM (#14606173)
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.

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by DonaldPShimoda on Wednesday June 21, 2017 @01:00PM (#14605607)
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.

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by omaranto on Wednesday June 21, 2017 @01:22PM (#14605894)
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>.
[ Parent | on HN ]
Re:What the heck is a parser-combinator? by amelius on Wednesday June 21, 2017 @04:51AM (#14602059)
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).

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by Mehdi2277 on Wednesday June 21, 2017 @05:19AM (#14602230)
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.
[ Parent | on HN ]
Re:What the heck is a parser-combinator? by amelius on Wednesday June 21, 2017 @05:31AM (#14602292)
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"?

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by vorg on Wednesday June 21, 2017 @07:40AM (#14602803)
> 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.

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by dozzie on Wednesday June 21, 2017 @08:46AM (#14603238)
> 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.

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by marcosdumay on Wednesday June 21, 2017 @02:02PM (#14606322)
The parser implements an unambiguous grammar. But it may not be the grammar you were thinking it was.

Specifically, it makes it impossible for you to even write down that ambiguous grammar you wanted.

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by fusiongyro on Wednesday June 21, 2017 @12:53PM (#14605529)
> Further, do monads warn the user when there is an ambiguity in the "grammar"?

I'm not aware of a parser combinator library that does this. The way you build parser combinators in Haskell doesn't exactly preclude it from being done but it wouldn't be totally trivial either.

Googling for it didn't turn up much that wasn't a veiled reference to this paper:

http://richard.myweb.cs.uwindsor.ca/PUBLICATIONS/PADL_08.pdf

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by marcosdumay on Wednesday June 21, 2017 @01:57PM (#14606270)
If you mean big O efficiency, it doesn't make any difference if you are creating a monad, applicative, or an state machine. Complexity comes explicitly in the parser construction, so if you write a monadic parser using only LR(k) combinators, you will get an LR(k) parser. If you write some backtracking, you will get worse complexity.
[ Parent | on HN ]
Re:What the heck is a parser-combinator? by tel on Wednesday June 21, 2017 @07:58AM (#14602906)
They're pretty damn efficient and nicely modular if you're okay with not having context sensitivity. Most of the time you're okay with not have context sensitivity, imo.

Context sensitivity as I wrote it here is the most powerful but least optimizable version. There are plenty of tricks to improve optimization. You can even write a "cut" combinatory to break backtracking.

It's a huge design space. The answer to all of your questions will probably be: it depends.

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by Tarean on Wednesday June 21, 2017 @10:06AM (#14603884)
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.
[ Parent | on HN ]
Re:What the heck is a parser-combinator? by chombier on Wednesday June 21, 2017 @03:45AM (#14601731)
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.

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by lihaoyi on Wednesday June 21, 2017 @05:07AM (#14602152)
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.

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by lomnakkus on Wednesday June 21, 2017 @04:20AM (#14601906)
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?

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by Mehdi2277 on Wednesday June 21, 2017 @05:08AM (#14602163)
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.
[ Parent | on HN ]
Re:What the heck is a parser-combinator? by tel on Wednesday June 21, 2017 @01:50PM (#14606196)
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.
[ Parent | on HN ]
Re:What the heck is a parser-combinator? by lomnakkus on Wednesday June 21, 2017 @07:39AM (#14602798)
> In slightly fancy language the type you just wrote is just StateT Input Maybe.

Except the newtype -- which was kind of my point :).

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by chombier on Wednesday June 21, 2017 @06:13AM (#14602451)
I realize I misread parent comment functions:

  always<A>(x: A): Parser<A>
  thenDependent<A, B>(a: Parser<A>, b: A -> Parser<B>): Parser<(A, B)>
as:

  always<A>(x: A): Parser<A>
  thenDependent<A, B>(a: Parser<A>, b: A -> Parser<B>): Parser<B>
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.

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by Tarean on Wednesday June 21, 2017 @10:16AM (#14603968)
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.

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by userbinator on Wednesday June 21, 2017 @06:47AM (#14602582)
It sounds vaguely like refactoring a recursive-descent parser.
[ Parent | on HN ]
Re:What the heck is a parser-combinator? by WorldMaker on Wednesday June 21, 2017 @11:49AM (#14604810)
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.

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by chubot on Wednesday June 21, 2017 @12:13PM (#14605058)
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?

[ Parent | on HN ]
Re:What the heck is a parser-combinator? by louthy on Wednesday June 21, 2017 @02:57PM (#14606873)
Parser combinators can do look-ahead and backtracking, yes. You definitely pay for it in efficiency however (especially look-ahead).
[ Parent | on HN ]
Re:What the heck is a parser-combinator? by motet_a on Wednesday June 21, 2017 @08:58AM (#14603323)
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.
[ Parent | on HN ]
Re:What the heck is a parser-combinator? by tel on Wednesday June 21, 2017 @09:00AM (#14603337)
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.
[ Parent | on HN ]
Re:What the heck is a parser-combinator? by jhpriestley on Wednesday June 21, 2017 @09:18AM (#14603474)
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.
[ Parent | on HN ]