Here is a great explanation of parser combinators, not tied to any specific implementation:
What the heck is a parser-combinator?
31–40 of 74 posts
Re: What the heck is a parser-combinator?
#32Consider 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…
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.
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.
Re: What the heck is a parser-combinator?
#33Earlier quoted context omitted.
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.
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.
Re: What the heck is a parser-combinator?
#34Consider 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…
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).
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.
Re: What the heck is a parser-combinator?
#35Gotta love Parsec for Haskell and pyparsing for Python. Some other awesome parsing libs: PEGTL - C++ Parsing Expression Grammar Template Library https://github.com/taocpp/PEGTL Parboiled - Java & Scala PEG Library https://github.com/sirthias/parboiled Nom - Rust parser combinator framework https://github.com/Geal/nom Nearley - JavaScript parser toolkit https://github.com/Hardmath123/nearley Neotoma - Erlang library a…
Add fparsec for F#/.Net http://www.quanttec.com/fparsec/
I used that 2 times and found it pretty easy to use, once I had grasped all the operators (like .>>, .>>., , etc.)
Re: What the heck is a parser-combinator?
#36Earlier quoted context omitted.
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).
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"?
Re: What the heck is a parser-combinator?
#37Let's rant a little: why the fuck can't you use some darker color for your text? Fucking tired of no-contrast website which are a pain to read. I hate having to use a DOM inspector to change some color to #000 so I can see if the content is useful. I guess I should be happy it is not an only-js blog.
> why ... can't you use some darker color for your text?
Just add the "zap colors" bookmarklet from this page: https://www.squarefree.com/bookmarklets/zap.html to a tool-bar menu in your browser (add some of the others for other annoyances if you like). Then when you find a page like this with a non-black color, just poke the "zap colors" bookmarklet and the color will change to black (a few others will change too, such as those pages that like redefining the colors for links, etc.).
Re: What the heck is a parser-combinator?
#38Consider 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…
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.
Re: What the heck is a parser-combinator?
#39Earlier quoted context omitted.
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.
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…
I realize I misread parent comment functions:
always(x: A): Parser
thenDependent(a: Parser, b: A -> Parser): Parser
always(x: A): Parser
thenDependent(a: Parser, b: A -> Parser): Parser
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.
Re: What the heck is a parser-combinator?
#40Consider 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…
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