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

51–60 of 74 posts

Re: What the heck is a parser-combinator?

#51

Post by yorwba »

coldtea wrote: post #17
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…

> One problem is dealing with features which language A supports and language B doesn't. That's not a problem with parsers or parser-combinators though. That's a problem with converting from one DB to another.

> That's a problem with converting from one DB to another.

The article is about converting JCL to PowerShell, so I'd say it's related.

Re: What the heck is a parser-combinator?

#52

Post by jhpriestley »

motet_a wrote: post #49
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…

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.

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.

Re: What the heck is a parser-combinator?

#53

Post by RodgerTheGreat »

I implemented a basic set of primitive parsers and combinators here in K, along with a usage example- a complete parser for the bittorrent "Bencode" data interchange format:

https://github.com/JohnEarnest/ok/blob/gh-pages/examples/par...

Not particularly efficient, but fairly concise.

Re: What the heck is a parser-combinator?

#54

Post by Tarean »

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…

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.

Re: What the heck is a parser-combinator?

#55

Post by Tarean »

chombier wrote: post #39
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…

I realize I misread parent comment functions: always (x: A): Parser thenDependent (a: Parser , b: A -> Parser ): Parser as: always (x: A): Parser thenDependent (a: Parser , b: A -> Parser ): Parser 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.…

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.

Re: What the heck is a parser-combinator?

#57

Post by coldtea »

yorwba wrote: post #51
coldtea wrote: post #17

Earlier quoted context omitted.

> One problem is dealing with features which language A supports and language B doesn't. That's not a problem with parsers or parser-combinators though. That's a problem with converting from one DB to another.

> That's a problem with converting from one DB to another. The article is about converting JCL to PowerShell, so I'd say it's related.

Kinda, that's the example the article uses, but the core is about the use of parser-combinators for the job (even the title is "What the heck is a parser-combinator?").

Re: What the heck is a parser-combinator?

#58

Post by WorldMaker »

userbinator wrote: post #41
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…

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

Re: What the heck is a parser-combinator?

#59

Post by pwg »

kennydude wrote: post #56
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.

I want an adblock for smooth scroll js

Install NoScript. Run in default deny JS mode.

No smooth scroll js. In fact, I read the whole article and never even realized there was any smooth scroll js anywhere.

Re: What the heck is a parser-combinator?

#60

Post by omaranto »

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 '*' arithmetic operators but I'd call '3' a number.

Post reply on HN