Remix clone Hacker News

Interesting, could you give some more detail?

▲ wyager 9 days ago | parent [-]

I tried googling to find an article, and I found some stuff explaining it, but this seems to be deeper lore than I thought it was.

Basically, a monadic parser combinator can have code that "inspects" a previously parsed value (context-sensitivity) but an applicative parser cannot.

Imagine an input like "3 alice bob dave", with a number and then that many names.

We want to parse

   data Parsed = Parsed {count :: Int, names :: [Name]}

Example: monadic parser:

  count <- parseInt
  names <- parseN count name
  return (Parsed count names)

You need to know the value of count before you keep parsing. Context-sensitive.

Applicative parsers don't let you "inspect" the parsed values. You can do stuff like

  Parsed <$> parseInt <*> many name

But if it's not clear where in the input the list of name ends without looking at the output of `parseInt`, you're hosed. There's no way to inspect the output of "parseInt" while you are parsing with an applicative parser.

You could do something like:

      Parsed <$> literal "1" <*> replicateM 1 name
  <|> Parsed <$> literal "2" <*> replicateM 2 name
  <|> ...

where you have an alternative case for each possible number, but obviously this does not generalize to parse realistic inputs.

Technically, you can use Haskell's laziness to parse this particular grammar efficiently enough using applicatives+alternatives to construct an infinite parse tree, but that's kind of an advanced edge case that won't work in most languages.

▲

BoiledCabbage 9 days ago | parent [-]

Thanks, and yes that makes perfect sense. It's a useful way to think about the problem space.

And then it does lead back to your "????" - which presumably represents the answer to the question of "What's the simplest abstraction that allows one to build a "Parser" (would this still be using combinators??) that is powerful enough to parse regular languages, but, by design, not powerful enough to parse context-free languages?"

	▲	wyager 9 days ago \| parent [-]
		Yeah, exactly. I don't know what it would look like. It would be nice if the answer was "functorial", since that's at the bottom of the functor-applicative-monad hierarchy, but functor doesn't provide any way to actually combine the combinators, so that's out.