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

31–40 of 90 posts

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

#31

Post by thfuran »

throwbadubadu wrote: post #28
Legend2440 wrote: post #23

Earlier quoted context omitted.

But I don't want to be able to parse only highly restricted languages. I want to be able to parse anything , including natural language or even non-languages like raw audio. My brain can do it, why can't my computer?

Yes, never do humans misunderstand each other, or instructions are not clear to everyone and totally unambiguous, and luckily no language has pure differentiation of meaning by intonation, and, and.. and...

Yeah, natural languages don't have a specification or canonical parser implementation, so they cannot be reliably parsed.

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

#32

Post by convolvatron »

PH95VuimJjqBqy wrote: post #27
Nevermark wrote: post #24

Common example of complications of two grammars being combined: C code and character strings. Double quotes in C code mean begin and end of a string. But strings contain quotes too. And newlines. Etc. So we got the cumbersome invention of escape codes, and so characters strings in source (itself a character string) are not literally the strings they represent.

at no point in my life have I ever considered escape codes to be problematic. ugly, yes. problematic? no.

until you need to get your string through several levels of escape. how many backslashes to add? depends on how deep your pipe is and how each of those layers is defined

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

#33

Post by ReleaseCandidat »

danielvaughn wrote: post #13
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…

> [incremental parsing] I don't know if that's specific to tree-sitter though

No, it isn't. And incremental parsing is older than 2011 too (like at least the 70s).

For example: https://dl.acm.org/doi/pdf/10.1145/357062.357066

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

#34

Post by Legend2440 »

thfuran wrote: post #31
throwbadubadu wrote: post #28

Earlier quoted context omitted.

Yes, never do humans misunderstand each other, or instructions are not clear to everyone and totally unambiguous, and luckily no language has pure differentiation of meaning by intonation, and, and.. and...

Yeah, natural languages don't have a specification or canonical parser implementation, so they cannot be reliably parsed.

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.

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

#36

Post by thfuran »

Legend2440 wrote: post #34
thfuran wrote: post #31

Earlier quoted context omitted.

Yeah, natural languages don't have a specification or canonical parser implementation, so they cannot be reliably parsed.

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 truth, most isn't all, and there's no universally agreed upon threshold for acceptance.

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

#37

Post by ReleaseCandidat »

marcusf wrote: post #4
temp123789246 wrote: post #2

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

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.

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

#38

Post by samus »

convolvatron wrote: post #32
PH95VuimJjqBqy wrote: post #27

Earlier quoted context omitted.

at no point in my life have I ever considered escape codes to be problematic. ugly, yes. problematic? no.

until you need to get your string through several levels of escape. how many backslashes to add? depends on how deep your pipe is and how each of those layers is defined

The only alternative is extracting them to other files or designing specialized string formats.

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

#39

Post by lisper »

samus wrote: post #38
convolvatron wrote: post #32

Earlier quoted context omitted.

until you need to get your string through several levels of escape. how many backslashes to add? depends on how deep your pipe is and how each of those layers is defined

The only alternative is extracting them to other files or designing specialized string formats.

There is one obvious "specialized string format" that solves 99% of all escaping issues: use «balanced quotes». The real problem isn't escaping, it is that the same character is used both to open and close strings.

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

#40

Post by lisper »

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…

My favorite example, due to Douglas Hofstadter:

Politicians lie.

Cast iron sinks.

Politicians lie in cast iron sinks.

It's not actually ambiguous, but I think it's a lovely illustration of the subtleties of the problem.

An actually ambiguous example: I saw a politician lying in a cast iron sink.

Post reply on HN