Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Just Write the Parser

tiarkrompf.github.io

Post reply on HN
Print view View original

31–40 of 85 posts

Re: Just Write the Parser

#31

Post by LeonB »

tiarkrompf wrote: post #22
blcArmadillo wrote: post #15

Earlier quoted context omitted.

Yeah I think something is broken because at least in chrome when you try to type in the left box the following exception keeps being thrown in the console VM463:82 Uncaught TypeError: Cannot read property 'startContainer' of undefined at HTMLPreElement.eval (eval at run (eval at runScriptElement (octopus-2.js:525)), :82:40)

I just pushed a fix for Chrome (apparently it doesn't report affected selection ranges for input events). Hope it works now!

it works for me now on Chrome.

Re: Just Write the Parser

#32

Post by mannykannot »

ben509 wrote: post #13

> Why simpler is better and why you don't need a parser generator. As far as I can see, this isn't fully answered, unless the claim is strictly limited to the question of need. In my case, I certainly want a parser generator. I'm working on a language, and I did a very early version using a hand-rolled recursive descent parser. Then I realized I wanted a syntax that was human friendly, so I graduated to megaparsec. T…

Once, I wanted a parser, and being the sort of person who thinks there is value in seeing what other people have done before, I took a look at parser generators.

The learning curve seemed long and steep, much more than seemed necessary for my modest requirements, so I rolled my own.

I got a parser out of the exercise, but also an appreciation for why the tools exist, and a new-found motivation for learning how to use them.

Re: Just Write the Parser

#33

Post by tofflos »

tiarkrompf wrote: post #22
blcArmadillo wrote: post #15

Earlier quoted context omitted.

Yeah I think something is broken because at least in chrome when you try to type in the left box the following exception keeps being thrown in the console VM463:82 Uncaught TypeError: Cannot read property 'startContainer' of undefined at HTMLPreElement.eval (eval at run (eval at runScriptElement (octopus-2.js:525)), :82:40)

I just pushed a fix for Chrome (apparently it doesn't report affected selection ranges for input events). Hope it works now!

Thanks! It works for me now in Edge (Chromium).

Re: Just Write the Parser

#35

Post by musicale »

tiarkrompf wrote: post #9

Author here - happy to answer questions, as always. Thanks also for feedback on the format of the article. It's a bit of an experiment on how to present dense information effectively. Some more rationale here: https://tiarkrompf.github.io/notes/?/octopus-notes/

What's the best way to handle unary "-" and other unary operators?

I'd like to be able to write expressions like "-2^-(2+2)" or "a cos b + a sin b".

For "-2^-(2+2)" note that exponentiation has higher precedence than negation.

Re: Just Write the Parser

#36

Post by pklausler »

wrs wrote: post #16

One reason to use a parser generator for a new language is that it will tell you that your language is inherently ambiguous or otherwise broken in a way you didn’t realize. A hand-coded parser tends to just codify your bad assumptions. It can actually be a good idea to maintain a YACC (or other) grammar for your language just to run the tool as a kind of “grammar linter”, even if you’re going to write the parser by h…

If you construct your parser in some kind of declarative fashion (e.g., a parser combinator DSL), you can do that kind of error checking directly on the same spec that you compile to produce your parser.

Re: Just Write the Parser

#37

Post by thequux »

samatman wrote: post #21

An alternate title: "Just Shotgun Parse Your Inputs". This isn't bad advice across the board , but it is bad advice for many applications. This is how you end up with context-sensitive formats, or ones where the semantics of a particular particle require running the parser, or worse. It exposes a rich surface area for exploitation with adversarial inputs. That said, the advantages cited at the front of the article ar…

I agree with everything you say, except your advice to use a parser combinator library, because most implement PEGs. Hammer is, of course, an exception to this, as long as you call `h_compile` to tell it to use a different backend.

Why not use PEGs? In short, they don't actually remove ambiguity from your grammar, but rather hide it in ways that are difficult to reason about. You're still dependent on code as a definition of the language that you accept, and worse, that code is very fragile in the face of refactoring. Further, the lexical analysis step is generally the source of most ambiguity, and most parser combinator libraries make it extremely inconvenient to parse something that isn't a character stream. (Hammer is actually worse than most here; it's not possible to use it to parse anything other than streams of bytes, though perhaps it can be excused because of the limitations of C)

Re: Just Write the Parser

#38

Post by thequux »

pklausler wrote: post #36
wrs wrote: post #16

One reason to use a parser generator for a new language is that it will tell you that your language is inherently ambiguous or otherwise broken in a way you didn’t realize. A hand-coded parser tends to just codify your bad assumptions. It can actually be a good idea to maintain a YACC (or other) grammar for your language just to run the tool as a kind of “grammar linter”, even if you’re going to write the parser by h…

If you construct your parser in some kind of declarative fashion (e.g., a parser combinator DSL), you can do that kind of error checking directly on the same spec that you compile to produce your parser.

Most parser combinator DSLs use PEGs to parse, which don't actually prevent ambiguity, but instead hide it. I strongly recommend using something that compiles your declarative grammar into LL(k) or LALR(k)

Re: Just Write the Parser

#39

Post by myk9001 »

musicale wrote: post #35
tiarkrompf wrote: post #9

Author here - happy to answer questions, as always. Thanks also for feedback on the format of the article. It's a bit of an experiment on how to present dense information effectively. Some more rationale here: https://tiarkrompf.github.io/notes/?/octopus-notes/

What's the best way to handle unary "-" and other unary operators? I'd like to be able to write expressions like "-2^-(2+2)" or "a cos b + a sin b". For "-2^-(2+2)" note that exponentiation has higher precedence than negation.

Take a look at "Parsing expressions by precedence climbing"[1] by Eli Bendersky.

See the "Other resources" section for other approaches to this problem.

1: https://eli.thegreenplace.net/2012/08/02/parsing-expressions...

Re: Just Write the Parser

#40

Post by spullara »

samatman wrote: post #21

An alternate title: "Just Shotgun Parse Your Inputs". This isn't bad advice across the board , but it is bad advice for many applications. This is how you end up with context-sensitive formats, or ones where the semantics of a particular particle require running the parser, or worse. It exposes a rich surface area for exploitation with adversarial inputs. That said, the advantages cited at the front of the article ar…

ANTLR 4 is a joy to work with if folks on this thread haven't tried it.
Post reply on HN