Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What the heck is a parser-combinator?

kimpel.com

Post reply on HN
Print view View original

61–70 of 74 posts

Re: What the heck is a parser-combinator?

#61

Post by chubot »

WorldMaker wrote: post #58
userbinator wrote: post #41

Earlier quoted context omitted.

It sounds vaguely like refactoring a recursive-descent parser.

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 th…

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?

Re: What the heck is a parser-combinator?

#62

Post by fusiongyro »

amelius wrote: post #36
Mehdi2277 wrote: post #34

Earlier quoted context omitted.

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…

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"?

> 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

Re: What the heck is a parser-combinator?

#63

Post by hyperion2010 »

bhrgunatha wrote: post #40
davidgl wrote: post #38

Earlier quoted context omitted.

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.

Or watch on youtube: https://www.youtube.com/watch?v=RDalzi7mhdY No need to create an account or login

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

Re: What the heck is a parser-combinator?

#64

Post by DonaldPShimoda »

omaranto wrote: post #60
tel wrote: post #9

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 char : Parser always (x: A): Parser never : Parser These are parse…

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 '*' a…

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.

Re: What the heck is a parser-combinator?

#65

Post by bitwize »

A tiny, elemental parser in a universe where parsers are closed under certain parser composition operators. Such tiny parsers can be combined using such operators to produce a bigger parser which could theoretically parse anything.

Re: What the heck is a parser-combinator?

#66

Post by to3m »

Lev1a wrote: post #48
LukaD wrote: post #16

Slightly off-topic but please stop this js smooth scroll nonsense. If I wanted to use smooth scroll I would have enabled it in my browser.

^ Someone talking sense right here, I thought some of my browser settings had changed for a minute.

Sing it! I wonder what purpose it is even supposed to serve?

The weird thing is that all people have to do to make this stuff work is: nothing at all. But for some reason that's just too much effort.

Re: What the heck is a parser-combinator?

#67

Post by omaranto »

DonaldPShimoda wrote: post #64
omaranto wrote: post #60

Earlier quoted context omitted.

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 '*' a…

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.

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, not ParserCombinator.

Re: What the heck is a parser-combinator?

#68

Post by wahern »

Here's a JSON parser in LPeg, the excellent PEG parser from one of the Lua authors. The function "decode" returns the final, complete tree data structure.

  local lpeg = require"lpeg"
  local P, S, R, V = lpeg.P, lpeg.S, lpeg.R, lpeg.V
  local C, Cc, Cf, Cg, Ct = lpeg.C, lpeg.Cc, lpeg.Cf, lpeg.Cg, lpeg.Ct

  local function to8(n)
    ... -- Lua code to normalize UTF-16 to UTF-8
  end

  local unicode = P"u" * (R("09", "AF", "af")^4 / to8)
  local named = C'"' + C"\\" + C"/" + (P"b" * Cc"\b") + (P"f" * Cc"\f") + (P"n" * Cc"\n") + (P"r" * Cc"\r") + (P"t" * Cc"\t")
  local escaped = P"\\" * (named + unicode)
  local unescaped = C((P(1) - S'\\"')^1)
  local qstring = Ct(P'"' * (unescaped + escaped)^0 * P'"') / table.concat

  local exp = S"Ee" * S"-+"^-1 * R"09"^1
  local frac = P"." * R"09"^1
  local number = (S"-+"^-1 * R"09"^1 * frac^-1 * exp^-1) / tonumber

  local boolean = (P"true" * Cc(true)) + (P"false" * Cc(false))
  local null = P"null" * Cc(nil)
  local space = S" \t\r\n"^0

  local JSON = { "Value",
    Value = space * (V"Object" + V"Array" + V"Simple") * space,
    Object = Cf(Ct"{" * space * Cg(qstring * space * P":" * V"Value" * P","^-1 * space)^0 * P"}", rawset),
    Array = Ct(P"[" * space * (V"Value" * P","^-1 * space)^0 * P"]"),
    Simple = number + boolean + null + qstring,
  }

  local function decode(txt)
    return lpeg.match(JSON, txt)
  end

Re: What the heck is a parser-combinator?

#69

Post by tel »

omaranto wrote: post #60
tel wrote: post #9

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 char : Parser always (x: A): Parser never : Parser These are parse…

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 '*' a…

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.

Re: What the heck is a parser-combinator?

#70

Post by tel »

Mehdi2277 wrote: post #33
lomnakkus wrote: post #25

Earlier quoted context omitted.

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 ma…

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.

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.
Post reply on HN