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

61–70 of 90 posts

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

#61

Post by thaumasiotes »

thfuran wrote: post #36
Legend2440 wrote: post #34

Earlier quoted context omitted.

They don't have a short parser. They can be parsed, it just requires a huge amount of priors and world knowledge. Rule-based parsers are too simple.

No, they cannot be reliably parsed. There is no unambiguously correct parsing for many (or, arguably, any) strings. Two people could say the same thing in the same context and mean different things by it. You can't even definitively say whether what they said/wrote is valid English. Sure, there are strings most would agree are and strings most would agree aren't, but even taking consensus opinion as the source of tru…

> There is no unambiguously correct parsing for many (or, arguably, any) strings.

My favorite funny phenomenon in this area is when a sentence has two unambiguously different parses that mean exactly the same thing.

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

#62

Post by ubolonton_ »

IshKebab wrote: post #49
danielvaughn wrote: post #13

Earlier quoted context omitted.

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…

In my experience incremental parsing doesn't really make much sense. Non-incremental parsing can easily parse huge documents in milliseconds. Also Tree Sitter only does half the parsing job - you get a tree on nodes, but you have to do your own parse of that tree to get useful structures out. I prefer Chumsky or Nom which go all the way.

What do you mean by “parse of that tree to get useful structures out”? Can you provide some concrete examples?

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

#63

Post by pcfwik »

dataflow wrote: post #43
pcfwik wrote: post #5

There was an interesting discussion two years ago regarding nonobvious issues with PEGs: https://news.ycombinator.com/item?id=30414683 https://news.ycombinator.com/item?id=30414879 I spent a year or two working with PEGs, and ran into similar issues multiple times. Adding a new production could totally screw up seemingly unrelated parses that worked fine before. As the author points out, Earley parsing with some disa…

> I spent a year or two working with PEGs > Earley parsing with some disambiguation rules Any idea why GLR always gets ignored?

At least in my personal case: GLR sounds great in theory, but I like to implement things 'from scratch' when possible. Both PEGs and the basic Earley algorithm are incredibly simple to write up and hack on in a few hundred lines of insert-favorite-language-here.

GLR would probably have (much) better performance but I'm usually not parsing huge files (or would hand-roll one if I were). I've not yet found an explanation of GLR (or even LR for that matter) that's quite as simple as PEGs or Earley (suggestions welcome tho!).

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

#64

Post by Guthur »

dkjaudyeqooe wrote: post #52
derriz wrote: post #50

Earlier quoted context omitted.

Agree completely. Having used a bunch of parser generators (Antlr and bison most extensively) and written a parser combinator library, I came to the conclusion that they're a complete waste of time for practical applications. A hand-written recursive descent parser (with an embedded Pratt parser to handle expressions/operators) solves all the problems that parser generators struggle with. The big/tricky "issue" menti…

> handle expressions/operators Precedence climbing is a natural and efficient way to parse expressions in a recursive decent parser. It's used by Clang in LLVM. https://eli.thegreenplace.net/2012/08/02/parsing-expressions...

Make them all s-expr with prefix notation solves even that generally, correct?

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

#66

Post by dboreham »

ReleaseCandidat wrote: post #37
marcusf wrote: post #4

Earlier quoted context omitted.

An extremely layman answer is that most interesting innovation in parsing in relatively modern times has happened seems to be in the context of IDE's. I.e. incremental, high-performance parsing to support syntax highlighting, refactoring, etc. etc. (I may be talking out of my ass here.)

Actually the most important step of parsers (as even non-incremental, slow (or better: not fast) parsers are fast enough) is error recovery (error resilience) from syntax errors (mostly half written or half deleted code). What is time consuming is e.g. type-checking. Semantic checking in general, like exhaustiveness checks of pattern matches, syntax checking is fast.

In the days of punched cards error recovery was important.

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

#67

Post by wittystick »

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.

[dead]

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

#68

Post by dboreham »

norir wrote: post #11
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…

You could write a language with which to specify that custom parser. Oh wait...

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

#69

Post by LgWoodenBadger »

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.

Just like email addresses. The specification/rfc/whatever could have defined a reg-ex that determines a valid address, instead of the essential impossibility we have today.

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

#70

Post by crq-yml »

taeric wrote: post #12
Karellen wrote: post #7

Earlier quoted context omitted.

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? I…

I agree, I think syntax could be defined as "the whole problem" if you see it holistically. Approaches that avoid scaling an intermediary grammar from lower-level tokens like the Lisp or Forth construction of "the parse directly maps to a data structure, and the data structure has the semantics" are robust. The reason why they aesthetically offend comes down to familiarity and tooling: infix expressions "look like math" - they please someone with prior training - but often act to hide important machine-level details. And the grammar helps to spread around the architecture of the language so that a syntax error compiles as a different semantic. Versus an approach like APL with a richer token set, or a ColorForth that packs in more semantic value by assigning tags to each word and making that part of the presentation.

I've moved towards designing languages now that operate over CSV source. That adds an extra dimension while still enabling convenient editing - just turn off all the parsing behavior in the spreadsheet and you can edit it as "plain text". Although, column alignment isn't always desirable in this case.

Post reply on HN