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

51–60 of 90 posts

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

#51

Post by Legend2440 »

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…

That's okay - that just means your parser needs to model what the speaker was thinking when they said it. That's extra information that's required to decode the message. It is not necessary for the same text to always mean the same thing.

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

#52

Post by dkjaudyeqooe »

derriz wrote: post #50
dkjaudyeqooe wrote: post #46

Earlier quoted context omitted.

This is entirely the case. Given a sensible grammar stated in a sensible way, it's very easy to write a nice recursive decent parser. They are fast and easy to maintain. It doesn't limit the expressiveness of your grammar unduly. Both GCC and LLVM implement recursive decent parsers for their C compilers. Parser generators are an abomination inflicted upon us by academia, solving a non problem, and poorly.

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

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

#53

Post by _0ffh »

derriz wrote: post #50
dkjaudyeqooe wrote: post #46

Earlier quoted context omitted.

This is entirely the case. Given a sensible grammar stated in a sensible way, it's very easy to write a nice recursive decent parser. They are fast and easy to maintain. It doesn't limit the expressiveness of your grammar unduly. Both GCC and LLVM implement recursive decent parsers for their C compilers. Parser generators are an abomination inflicted upon us by academia, solving a non problem, and poorly.

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…

> A hand-written recursive descent parser (with an embedded Pratt parser to handle expressions/operators)

Exactly the recipe I swear by as well!

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

#54

Post by danielvaughn »

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.

Ah interesting, yeah I did spend quite a bit of time parsing their AST, which turned out to be harder than writing the grammar itself. I’ll look into those two projects.

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

#55

Post by _0ffh »

Legend2440 wrote: post #51
thfuran wrote: post #36

Earlier quoted context omitted.

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…

That's okay - that just means your parser needs to model what the speaker was thinking when they said it. That's extra information that's required to decode the message. It is not necessary for the same text to always mean the same thing.

If I already knew what the speaker was thinking, there would be no need to parse his words at all.

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

#56

Post by thfuran »

Legend2440 wrote: post #51
thfuran wrote: post #36

Earlier quoted context omitted.

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…

That's okay - that just means your parser needs to model what the speaker was thinking when they said it. That's extra information that's required to decode the message. It is not necessary for the same text to always mean the same thing.

Fine, a parser that is a perfect oracle for authorial intent can reliably parse English. But no real parser can. And anyways, that effectively extends the English grammar to include the entire world state, which isn't really what people mean when they talk about English as a language or parsing strings—a fact which perhaps helps to illustrate the problem.

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

#57

Post by Legend2440 »

thfuran wrote: post #56
Legend2440 wrote: post #51

Earlier quoted context omitted.

That's okay - that just means your parser needs to model what the speaker was thinking when they said it. That's extra information that's required to decode the message. It is not necessary for the same text to always mean the same thing.

Fine, a parser that is a perfect oracle for authorial intent can reliably parse English. But no real parser can. And anyways, that effectively extends the English grammar to include the entire world state, which isn't really what people mean when they talk about English as a language or parsing strings—a fact which perhaps helps to illustrate the problem.

>that effectively extends the English grammar to include the entire world state

Exactly! So glad we're on the same page.

Language is created by and intended for big brains with huge amounts of knowledge about each other and about the world. Relying on external knowledge makes it extremely compact and flexible, but also means your parser needs a similar level of knowledge to function.

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

#58

Post by thfuran »

Legend2440 wrote: post #57
thfuran wrote: post #56

Earlier quoted context omitted.

Fine, a parser that is a perfect oracle for authorial intent can reliably parse English. But no real parser can. And anyways, that effectively extends the English grammar to include the entire world state, which isn't really what people mean when they talk about English as a language or parsing strings—a fact which perhaps helps to illustrate the problem.

>that effectively extends the English grammar to include the entire world state Exactly! So glad we're on the same page. Language is created by and intended for big brains with huge amounts of knowledge about each other and about the world. Relying on external knowledge makes it extremely compact and flexible, but also means your parser needs a similar level of knowledge to function.

>So glad we're on the same page

We're really not. I'm saying you've incorrectly defined the English language. By that definition, no piece of text is English.

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

#59

Post by wglb »

loevborg wrote: post #21
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.

Do you mean lisp? If yes I agree

Smalltalk is another.

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

#60

Post by gizmo686 »

Legend2440 wrote: post #51
thfuran wrote: post #36

Earlier quoted context omitted.

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…

That's okay - that just means your parser needs to model what the speaker was thinking when they said it. That's extra information that's required to decode the message. It is not necessary for the same text to always mean the same thing.

If you need to already know what the speaket meant in order to understand them, then there is no point in communication.

Human language has a pretty clear distinction between syntax and sementics. This is how we recognize that "colorless green ideas sleep furiously" are perfectly well formed, if meaningless. In contrast, "I is happy" is meaningful and unambiguous, but grammatically incorrect.

In terms of syntax, English (like most, if not all) languages is literally ambigous.

Consider the sentence structure:

Subject Verb Object Prepositional-Phrase.

This can be either:

(Subject Verb (Object Prepositional Phrase))

Or

(Subject Verb Object ) Prepositional Phrase.

For instance, consider the sentence "I saw a man with binoculars".

In any sense of the word, this example is structually ambigous.

Post reply on HN