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

Parsing: The Solved Problem That Isn't (2011)

tratt.net

Post reply on HN
Print view View original

11–20 of 90 posts

Re: Parsing: The Solved Problem That Isn't (2011)

#11

Post by norir »

temp123789246 wrote: post #2

Have there been any notable innovations in parsing since this was written?

I feel that most of the time the two options are presented as either write a handwritten parser or use a parser generator. A nice third way is to write a custom parser generator for the language you wish to parse. Handwritten parsers do tend to get unwieldy and general purpose parser generators can have inscrutable behavior for any specific language.

Because the grammar for a parser generator is usually much simpler than most general purpose programming languages, it is typically relatively straightforward to handwrite a parser for it.

Re: Parsing: The Solved Problem That Isn't (2011)

#12

Post by taeric »

Karellen wrote: post #7
taeric wrote: post #3

My current view of what makes parsing so difficult is that people want to jump straight over a ton of intermediate things from parsing to execution. That is, we often know what we want to happen at the end. And we know what we are given. It is hoped that it is a trivially mechanical problem to go from one to the other. But this ignores all sorts of other steps you can take. Targeting multiple execution environments i…

What have those other things got to do with parsing though? Granted, they rely on parsing having already happened , but I don't see how there's much feedback from those considerations to the way that parsers work, or are written, or - as the article discussed - can be combined?

You can easily view it as having nothing to do with it. My push is that it is the point of parsing. You don't parse directly into understanding/execution. You parse into another representation, one that we never directly talk about, so that you can then move it into the next level.

Even English can be parsed first into the sounds. This is why puns work. Consider the joke, "why should you wear glasses to math class? It helps with division." That only works if you go to the sounds first. And you will have optionality in where to go from there.

So, for parsing programs, we often first decide on primitives for execution. For teaching, this is often basic math operations. But in reality, you have far more than the basic math operations. And, as I was saying, you can do more with the intermediate representation than you probably realize at the outset.

Re: Parsing: The Solved Problem That Isn't (2011)

#13

Post by danielvaughn »

temp123789246 wrote: post #2

Have there been any notable innovations in parsing since this was written?

I'm not super familiar with the space, but tree-sitter seems to take an interesting approach in that they are an incremental parser. So instead of re-parsing the entire document on change, it only parses the affected text, thereby making it much more efficient for text editors.

I don't know if that's specific to tree-sitter though, I'm sure there are other incremental parsers. I have to say that I've tried ANTLR and tree-sitter, and I absolutely love tree-sitter. It's a joy to work with.

Re: Parsing: The Solved Problem That Isn't (2011)

#16

Post by amelius »

kazinator wrote: post #15

Parsing computer languages is an entirely self-inflicted problem. You can easily design a language so it doesn't require any parsing techniques that were not known and practical in 1965, and it will greatly benefit the readability also.

End-comment

Re: Parsing: The Solved Problem That Isn't (2011)

#17

Post by o11c »

temp123789246 wrote: post #2

Have there been any notable innovations in parsing since this was written?

Not sure, but I at least am certainly aware of possibilities that such writeups exclude.

In particular, you can do (a subset of) the following in sequence:

* write your own grammar in whatever bespoke language you want

* compose those grammars into a single grammar

* generate a Bison grammar from that grammar

* run `bison --xml` instead of actually generating code

* read the XML file and implement your own (trivial) runtime so you can easily handle ownership issues

In particular, I am vehemently opposed to the idea of implementing parsers separately using some non-proven tool/theory, since that way leads to subtle grammar incompatibilities later.

Re: Parsing: The Solved Problem That Isn't (2011)

#19

Post by lgas »

amelius wrote: post #16
kazinator wrote: post #15

Parsing computer languages is an entirely self-inflicted problem. You can easily design a language so it doesn't require any parsing techniques that were not known and practical in 1965, and it will greatly benefit the readability also.

End-comment

)

Re: Parsing: The Solved Problem That Isn't (2011)

#20

Post by mrkeen »

EdSchouten wrote: post #9

What I find annoying about using parser generators is that it always feels messy integrating the resulting parser into your application. So you write a file that contains the grammar and generate a parser out of that. Now you build it into your app and call into it to parse some input file, but that ends up giving you some poorly typed AST that is cluttered/hard to work with. Certain parser generators make life easie…

Parser combinators is what I've been loving in the last few years.

Pros: * They're just a technique/library that you can use in your own language without the seperate generation step.

* They're simple enough that I often roll my own rather than using an existing library.

* They let you stick code into your parsing steps - logging, extra information, constructing your own results directly, e.g.

* The same technique works for lexing and parsing - just write a parser from bytes to tokens, and a second parser from tokens to objects.

* Depending on your languages syntax, you can get your parser code looking a lot like the bnf grammar you're trying to implement.

Cons: * You will eventually run into left-recursion problems. It can be nightmarish trying to change the code so it 'just works'. You really need to step back and grok left-recursion itself - no handholding from parser combinators.

* Same thing with precedence - you just gotta learn how to do it. Fixing left-recursion didn't click for me until I learned how to do precedence.

Post reply on HN