What the heck is a parser-combinator? • Hacker News Board

Re: What the heck is a parser-combinator?

#71

Post by marcosdumay » Wed, Jun 21, 2017, 5:57 PM UTC

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

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.

Re: What the heck is a parser-combinator?

#72

Post by marcosdumay » Wed, Jun 21, 2017, 6:02 PM UTC

dozzie wrote: post #47

vorg wrote: post #43

Earlier quoted context omitted.

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

> 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.

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.

Re: What the heck is a parser-combinator?

#73

Post by louthy » Wed, Jun 21, 2017, 6:57 PM UTC

chubot wrote: post #61

WorldMaker wrote: post #58

Earlier quoted context omitted.

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?

Parser combinators can do look-ahead and backtracking, yes. You definitely pay for it in efficiency however (especially look-ahead).

Re: What the heck is a parser-combinator?

#74

Post by SteveBash » Fri, Jun 23, 2017, 2:51 AM UTC

majewsky wrote: post #28

flor1s wrote: post #12

A few years ago I worked on a similar kind of project as part of my bachelors. We were converting SQL for Oracle to SQL for Microsoft SQL Server. One problem is dealing with features which language A supports and language B doesn't. Another problem is that it is a huge amount of work to match all syntax elements as well as all library usages. In fact, I guess it's not a good thing to say on HackerNews, but isn't it b…

> We were converting SQL for Oracle to SQL for Microsoft SQL Server. I had a similar problem a few months ago with a Golang application that uses Postgres in production, but SQLite for unit tests. Since Go's SQL support has pluggable driver backends, I made a generic proxy driver [1] that can rewrite the incoming query, and used that in my application to rewrite from Postgres to SQLite syntax [2]. [1] https://godoc.o…

Why just not use a local postgres instead of sqlite, your case seems like overengineering to me.