9 ms·

What the heck is a parser-combinator?

160 points by lihaoyi 9y ago

tangus 9y ago
Here is a great explanation of parser combinators, not tied to any specific implementation: https://qntm.org/combinators https://qntm.org/combinators
ravishah 9y ago
Discount Y - Combinator
Cieplak 9y ago
Gotta 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 https://github.com/taocpp/PEGTL Parboiled - Java & Scala PEG Library https://github.com/sirthias/parboiled https://github.com/sirthias/parboiled Nom - Rust parser combinator framework https://github.com/Geal/nom https://github.com/Geal/nom Nearley - JavaScript parser toolkit https://github.com/Hardmath123/nearley https://github.com/Hardmath123/nearley Neotoma - Erlang library and packrat parser-generator for PEGs https://github.com/seancribbs/neotoma https://github.com/seancribbs/neotoma
- DominoTree 9y ago
  I've used Nom to parse a couple RFC-based protocols now, and I'm amazed at how easy and performant the result ends up being. There's a great walk-through of using it here, including fuzzing your parsers to make sure they're solid. https://github.com/Geal/langsec-2017-hackathon-code https://github.com/Geal/langsec-2017-hackathon-code
  - beefsack 9y ago
    Geal is very helpful too, he pops up around the place in the Rust community and is responsive on the nom Gitter channel.
- tommikaikkonen 9y ago
  I haven't tried pyparsing, but I enjoyed implementing a simple DSL with funcparserlib having no previous experience with parser combinators: https://github.com/vlasovskikh/funcparserlib https://github.com/vlasovskikh/funcparserlib The library has a well-written tutorial that doesn't require previous knowledge about parser combinators.
- dwenzek 9y ago
  angstrom - OCaml parser combinators built for speed and memory efficiency https://github.com/inhabitedtype/angstrom https://github.com/inhabitedtype/angstrom
- jjwiseman 9y ago
  Instaparse - Clojure/Clojurescript https://github.com/Engelberg/instaparse https://github.com/Engelberg/instaparse
- skocznymroczny 9y ago
  Pegged - PEG generator implemented in the D programming language https://github.com/PhilippeSigaud/Pegged https://github.com/PhilippeSigaud/Pegged , works in run-time or compile-time
- leeoniya 9y ago
  Nearly is pretty slow. check out Chevrotain http://sap.github.io/chevrotain/performance/ http://sap.github.io/chevrotain/performance/
- Matthias247 9y ago
  Add fparsec for F#/.Net http://www.quanttec.com/fparsec/ 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.)
manishmarahatta 9y ago
basically a parser inception, takes parser and returns parser, woah
brianberns 9y ago
This is great, but if you're going to use a parser combinator in .NET, you might as well switch to F# and use FParsec instead of hacking LINQ in C#. The F# code is so much easier to read and understand.
rebolek 9y ago
This reminds me of Red's parse http://www.red-lang.org/2013/11/041-introducing-parse.html http://www.red-lang.org/2013/11/041-introducing-parse.html
blacksmythe 9y ago
Parser combinator library in Go: https://github.com/prataprc/goparsec https://github.com/prataprc/goparsec
tel 9y ago
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<String> char : Parser<Character> always<A>(x: A): Parser<A> never<A>: Parser<A> These are parser combinators. They form the atoms at the foundation of a language for constructing parsers. For instance, we can imagine two parsers happening in sequence then<A, B>(a: Parser<A>, b: Parser<B>): Parser<(A, B)> then(char, char): Parser<(Character, Character)> Or more fancily, a two parsers happening in sequence, but the second parser being defined using the output of the first. This creates context sensitivity thenDependent<A, B>(a: Parser<A>, b: A -> Parser<B>): Parser<(A, B)> We're constructing a fundamental language for building parsers up from our atoms to larger and larger things. All we need now is a way to "run" them run<A>(p: Parser<A>): String -> Option<A> Tada---parser combinators!
- chombier 9y ago
  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.
  - lomnakkus 9y ago
    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 may return: "Nothing" if the parser doesn't match, or "a value of type t along with the rest of the unparsed input". (Obviously it'd have to be expanded to support errors properly, etc.) EDIT: Of course, I guess you could argue that they just are monadic by definition since chaining using function composition and parameter passing is the essence of a monad... Maybe that's what you were driving at?
unmole 9y ago
Another good introduction: http://theorangeduck.com/page/you-could-have-invented-parser-combinators http://theorangeduck.com/page/you-could-have-invented-parser...
flor1s 9y ago
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 better to just buy a tool which does it for you? It seems like they are available for the author's use case: http://www.ispirer.com/application-conversion/jcl-to-powershell-conversion http://www.ispirer.com/application-conversion/jcl-to-powersh...
- coldtea 9y ago
  >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.
  - yorwba 9y ago
    > 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.
    - coldtea 9y ago
      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?").
- majewsky 9y ago
  > 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.org/github.com/majewsky/sqlproxy https://godoc.org/github.com/majewsky/sqlproxy [2] https://github.com/sapcc/limes/blob/205f9980a41d75fc0315e0acc1e3daeb9853048f/pkg/db/connection.go#L48-L60 https://github.com/sapcc/limes/blob/205f9980a41d75fc0315e0ac...
LukaD 9y ago
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.
- cabalamat 9y ago
  And while we're at it, get rid of the annoying sticky header.
- Lev1a 9y ago
  ^ Someone talking sense right here, I thought some of my browser settings had changed for a minute.
  - to3m 9y ago
    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.
- kennydude 9y ago
  I want an adblock for smooth scroll js
  - pwg 9y ago
    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.
albi_lander 9y ago
Reminds me of SuperCombinators: a parser combinator framework written in Swift https://github.com/snipsco/SuperCombinators https://github.com/snipsco/SuperCombinators
arkh 9y ago
Let'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.
- sigi45 9y ago
  Not sure what you mean? Its nearly black?
  - jwilk 9y ago
    It's #5a5a5a. That's not "nearly black" is my book.
- bshimmin 9y ago
  This doesn't seem like such an egregious example to me - I tried it in a colour contrast checker and it passes WCAG AA but fails WCAG AAA for normal size text (but passes for larger text): https://snook.ca/technical/colour_contrast/colour.html#fg=5A5A5A,bg=FFFFFF https://snook.ca/technical/colour_contrast/colour.html#fg=5A... I will admit I don't find the letter spacing on that font to be particularly pleasant, and if you turn the "Cantarell" declaration off, it does become easier to read (better letter spacing and thicker strokes, which latter contributes positively to the contrast).
- pwg 9y ago
  > 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 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.).
pwm 9y ago
type Parser a :: String -> [(a, String)] "A Parser for Things Is a function from Strings To Lists of Pairs Of Things and Strings!" - Fritz Ruehr
louthy 9y ago
Wanted to leave a comment on the site, but it seems comments are broken, so I'll stick this here just in case the author sees it: You've linked to my csharp-monad library for C# parser combinators. This has been superseded by my language-ext project: https://github.com/louthy/language-ext/ https://github.com/louthy/language-ext/ It is a much more advanced and efficient port of the Haskell Parsec library. Would you mind linking to that instead? Your Sprache examples would look like this in language-ext: public static readonly Parser<JCLCommand> JCLText = from open in ch('$') from ws1 in spaces from command in asString(many(noneOf(' '))) from ws2 in spaces from content in asString(many(noneOf('"'))) select new JCLCommand(command, content); public static readonly Parser<JCLCommand> GlobalText = from variablename in asString(many(noneOf('='))) from ws2 in ch('=') from openbrack in ch('(') from filepath in asString(many(noneOf(')'))) from closebrack in ch(')') select new JCLCommand(variablename, filepath); But the power of parser combinators are their reusable nature. So I'd break that down to a set of tools: static Parser<A> token<A>(Parser<A> p) => from x in p from _ in either(spaces, eof) select x; static Parser<string> symbol(string x) => token(str(x)); static Parser<string> identifier = token(asString(many1(alphaNum))); static Parser<A> quotes<A>(Parser<A> p) => between(symbol("\""), symbol("\""), p); static Parser<A> parens<A>(Parser<A> p) => between(symbol("("), symbol(")"), p); static Parser<string> quoteText = token(quotes(asString(many(satisfy(x => x != '"'))))); static Parser<string> parensText = token(parens(asString(many(satisfy(x => x != ')'))))); Then your final parsers would look like this: static readonly Parser<JCLCommand> JCLText = from open in symbol("$") from command in identifier from content in quoteText select new JCLCommand(command, content); static readonly Parser<JCLCommand> GlobalText = from variablename in identifier from ws2 in symbol("=") from filepath in parensText select new JCLCommand(variablename, filepath); static readonly Parser<Seq<JCLCommand>> Commands = from _ in spaces from commands in many1(either(JCLText, GlobalText)) select commands; Which is much easier to understand I think. It's not exactly the same as it defines what an identifier is, but it's much more tolerant of rogue spaces because of the token parser. This is definitely the most compelling aspect of parser combinators for me, the way they compose so elegantly.
RodgerTheGreat 9y ago
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/parsing.k https://github.com/JohnEarnest/ok/blob/gh-pages/examples/par... Not particularly efficient, but fairly concise.
bitwize 9y ago
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.
wahern 9y ago
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

160 points by lihaoyi 9y ago

Here is a great explanation of parser combinators, not tied to any specific implementation: https://qntm.org/combinators https://qntm.org/combinators

ravishah 9y ago

Discount Y - Combinator

Cieplak 9y ago

Gotta 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 https://github.com/taocpp/PEGTL Parboiled - Java & Scala PEG Library https://github.com/sirthias/parboiled https://github.com/sirthias/parboiled Nom - Rust parser combinator framework https://github.com/Geal/nom https://github.com/Geal/nom Nearley - JavaScript parser toolkit https://github.com/Hardmath123/nearley https://github.com/Hardmath123/nearley Neotoma - Erlang library and packrat parser-generator for PEGs https://github.com/seancribbs/neotoma https://github.com/seancribbs/neotoma

DominoTree 9y ago
I've used Nom to parse a couple RFC-based protocols now, and I'm amazed at how easy and performant the result ends up being. There's a great walk-through of using it here, including fuzzing your parsers to make sure they're solid. https://github.com/Geal/langsec-2017-hackathon-code https://github.com/Geal/langsec-2017-hackathon-code
- beefsack 9y ago
  Geal is very helpful too, he pops up around the place in the Rust community and is responsive on the nom Gitter channel.
tommikaikkonen 9y ago
I haven't tried pyparsing, but I enjoyed implementing a simple DSL with funcparserlib having no previous experience with parser combinators: https://github.com/vlasovskikh/funcparserlib https://github.com/vlasovskikh/funcparserlib The library has a well-written tutorial that doesn't require previous knowledge about parser combinators.
dwenzek 9y ago
angstrom - OCaml parser combinators built for speed and memory efficiency https://github.com/inhabitedtype/angstrom https://github.com/inhabitedtype/angstrom
jjwiseman 9y ago
Instaparse - Clojure/Clojurescript https://github.com/Engelberg/instaparse https://github.com/Engelberg/instaparse
skocznymroczny 9y ago
Pegged - PEG generator implemented in the D programming language https://github.com/PhilippeSigaud/Pegged https://github.com/PhilippeSigaud/Pegged , works in run-time or compile-time
leeoniya 9y ago
Nearly is pretty slow. check out Chevrotain http://sap.github.io/chevrotain/performance/ http://sap.github.io/chevrotain/performance/
Matthias247 9y ago
Add fparsec for F#/.Net http://www.quanttec.com/fparsec/ 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.)

manishmarahatta 9y ago

basically a parser inception, takes parser and returns parser, woah

brianberns 9y ago

This is great, but if you're going to use a parser combinator in .NET, you might as well switch to F# and use FParsec instead of hacking LINQ in C#. The F# code is so much easier to read and understand.

rebolek 9y ago

This reminds me of Red's parse http://www.red-lang.org/2013/11/041-introducing-parse.html http://www.red-lang.org/2013/11/041-introducing-parse.html

blacksmythe 9y ago

Parser combinator library in Go: https://github.com/prataprc/goparsec https://github.com/prataprc/goparsec

tel 9y ago

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<String> char : Parser<Character> always<A>(x: A): Parser<A> never<A>: Parser<A> These are parser combinators. They form the atoms at the foundation of a language for constructing parsers. For instance, we can imagine two parsers happening in sequence then<A, B>(a: Parser<A>, b: Parser<B>): Parser<(A, B)> then(char, char): Parser<(Character, Character)> Or more fancily, a two parsers happening in sequence, but the second parser being defined using the output of the first. This creates context sensitivity thenDependent<A, B>(a: Parser<A>, b: A -> Parser<B>): Parser<(A, B)> We're constructing a fundamental language for building parsers up from our atoms to larger and larger things. All we need now is a way to "run" them run<A>(p: Parser<A>): String -> Option<A> Tada---parser combinators!

chombier 9y ago
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.
- lomnakkus 9y ago
  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 may return: "Nothing" if the parser doesn't match, or "a value of type t along with the rest of the unparsed input". (Obviously it'd have to be expanded to support errors properly, etc.) EDIT: Of course, I guess you could argue that they just are monadic by definition since chaining using function composition and parameter passing is the essence of a monad... Maybe that's what you were driving at?

unmole 9y ago

Another good introduction: http://theorangeduck.com/page/you-could-have-invented-parser-combinators http://theorangeduck.com/page/you-could-have-invented-parser...

flor1s 9y ago

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 better to just buy a tool which does it for you? It seems like they are available for the author's use case: http://www.ispirer.com/application-conversion/jcl-to-powershell-conversion http://www.ispirer.com/application-conversion/jcl-to-powersh...

coldtea 9y ago
>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.
- yorwba 9y ago
  > 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.
  - coldtea 9y ago
    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?").
majewsky 9y ago
> 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.org/github.com/majewsky/sqlproxy https://godoc.org/github.com/majewsky/sqlproxy [2] https://github.com/sapcc/limes/blob/205f9980a41d75fc0315e0acc1e3daeb9853048f/pkg/db/connection.go#L48-L60 https://github.com/sapcc/limes/blob/205f9980a41d75fc0315e0ac...

LukaD 9y ago

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.

cabalamat 9y ago
And while we're at it, get rid of the annoying sticky header.
Lev1a 9y ago
^ Someone talking sense right here, I thought some of my browser settings had changed for a minute.
- to3m 9y ago
  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.
kennydude 9y ago
I want an adblock for smooth scroll js
- pwg 9y ago
  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.

albi_lander 9y ago

Reminds me of SuperCombinators: a parser combinator framework written in Swift https://github.com/snipsco/SuperCombinators https://github.com/snipsco/SuperCombinators

arkh 9y ago

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

sigi45 9y ago
Not sure what you mean? Its nearly black?
- jwilk 9y ago
  It's #5a5a5a. That's not "nearly black" is my book.
bshimmin 9y ago
This doesn't seem like such an egregious example to me - I tried it in a colour contrast checker and it passes WCAG AA but fails WCAG AAA for normal size text (but passes for larger text): https://snook.ca/technical/colour_contrast/colour.html#fg=5A5A5A,bg=FFFFFF https://snook.ca/technical/colour_contrast/colour.html#fg=5A... I will admit I don't find the letter spacing on that font to be particularly pleasant, and if you turn the "Cantarell" declaration off, it does become easier to read (better letter spacing and thicker strokes, which latter contributes positively to the contrast).
pwg 9y ago
> 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 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.).

pwm 9y ago

type Parser a :: String -> [(a, String)] "A Parser for Things Is a function from Strings To Lists of Pairs Of Things and Strings!" - Fritz Ruehr

louthy 9y ago

Wanted to leave a comment on the site, but it seems comments are broken, so I'll stick this here just in case the author sees it: You've linked to my csharp-monad library for C# parser combinators. This has been superseded by my language-ext project: https://github.com/louthy/language-ext/ https://github.com/louthy/language-ext/ It is a much more advanced and efficient port of the Haskell Parsec library. Would you mind linking to that instead? Your Sprache examples would look like this in language-ext: public static readonly Parser<JCLCommand> JCLText = from open in ch('$') from ws1 in spaces from command in asString(many(noneOf(' '))) from ws2 in spaces from content in asString(many(noneOf('"'))) select new JCLCommand(command, content); public static readonly Parser<JCLCommand> GlobalText = from variablename in asString(many(noneOf('='))) from ws2 in ch('=') from openbrack in ch('(') from filepath in asString(many(noneOf(')'))) from closebrack in ch(')') select new JCLCommand(variablename, filepath); But the power of parser combinators are their reusable nature. So I'd break that down to a set of tools: static Parser<A> token<A>(Parser<A> p) => from x in p from _ in either(spaces, eof) select x; static Parser<string> symbol(string x) => token(str(x)); static Parser<string> identifier = token(asString(many1(alphaNum))); static Parser<A> quotes<A>(Parser<A> p) => between(symbol("\""), symbol("\""), p); static Parser<A> parens<A>(Parser<A> p) => between(symbol("("), symbol(")"), p); static Parser<string> quoteText = token(quotes(asString(many(satisfy(x => x != '"'))))); static Parser<string> parensText = token(parens(asString(many(satisfy(x => x != ')'))))); Then your final parsers would look like this: static readonly Parser<JCLCommand> JCLText = from open in symbol("$") from command in identifier from content in quoteText select new JCLCommand(command, content); static readonly Parser<JCLCommand> GlobalText = from variablename in identifier from ws2 in symbol("=") from filepath in parensText select new JCLCommand(variablename, filepath); static readonly Parser<Seq<JCLCommand>> Commands = from _ in spaces from commands in many1(either(JCLText, GlobalText)) select commands; Which is much easier to understand I think. It's not exactly the same as it defines what an identifier is, but it's much more tolerant of rogue spaces because of the token parser. This is definitely the most compelling aspect of parser combinators for me, the way they compose so elegantly.

RodgerTheGreat 9y ago

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/parsing.k https://github.com/JohnEarnest/ok/blob/gh-pages/examples/par... Not particularly efficient, but fairly concise.

bitwize 9y ago

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.

wahern 9y ago

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