Live data from Hacker News

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

tratt.net

71–80 of 90 posts

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

#71
post #40
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…

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.

My personal favourite example is the proof that two positives can make a negative: 'yeah, right'.

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

#72

Earlier quoted context omitted.

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?

Not the person you’re asking, but basically anything that needs to happen after the initial parsing stage. So you convert your raw text into an AST, but there’s usually some processing you need to do after that.

Maybe you need to optimize the data, maybe you need to do some error checking. Lots of code is syntactically valid but not semantically valid, and usually those semantic errors will persist into the AST (in my limited experience).

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

#73
post #63

Earlier quoted context omitted.

> 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 explanatio…

Gotcha. GLR is painful to learn, you have my sympathy there. I feel like a big chunk of that is due to overly complex formalism and nomenclature around it, but it's definitely still tough, especially if you're trying to implement it efficiently. If you're interested in doing so, I recommend making sure you understand each of the following parsing algorithms in order: regexes via NFA, regexes via DFA, unambiguous LR(0) without empty productions and while ignoring time complexity, LR(0) with time complexity optimizations and with empty productions, LR(1), and then finally GLR (to handle ambiguity). The hardest part will probably be the LR(0) stage.

If you get stuck on LR(0), here's the idea: you use a state machine with a stack, and (b) treat nonterminal symbols like any other input tokens. How? Like below. Say you had the rules:

  #1: Add: Add '+' NUMBER;
  #2: Add: NUMBER;
Initially, you could be in the beginning of any of these rules: either in rule #1 offset 0 (before the Add), or in rule #2 offset 0 (before the NUMBER). Push ({(#1, 0), (#2, 0)}, ) onto your stack, where the second list is the symbols you've seen so far (nothing so far). Now consume the first token in the input; let's say it was a NUMBER (say, "55"). Go through every possible new location in your stack, and update where it could be now, and push the new candidate locations along with the symbol you just saw, filtering out any locations where you went past the end of the rule. In this case, that means pushing ({(#1, 1), (#2, 1)}, NUMBER). Now, carefully examine your stack. You've seen [, NUMBER] so far (i.e., just [NUMBER]), and you're either in the middle of rule #1, or at the end of rule #2. Well, it can't be #1, because the last symbol you saw was NUMBER, not Add. Therefore it's #2, and you've finished rule #2, which means you've recognized an Add. Therefore, pop all the symbols in the production of #2 from the stack (which leaves the stack empty), then push the output back (i.e. "reduce" it to the Add symbol). This leaves you with a stack that has just one item, ({(#1, 1)}, Add). Since you're no longer at the end of a production, consume the next input symbol, then go repeat this process, reducing as much as you can every time before consuming an input. [1]

Once you understand this intuitively (and if you stare at it long enough, you'll realize the process I just explained resembles that of a regex NFA), then learn how to optimize this by preprocessing the set of possible locations into simple integers instead of entire sets, so you don't have to do O(|rules|) work every iteration. Then move onto LR(1), which is merely about disambiguating the rules using a lookahead. After that, GLR is "just" keeping a DAG instead of a stack (and it reduces to a linked-list version of a stack if there is no ambiguity)... best of luck.

[1] I lied a little here, in that the process starts with reducing, not shifting. Because you might need to reduce (possibly multiple times) before you consume any inputs. But that's easier to explain here after the fact, than when you're initially learning it.

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

#74

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.

> and it will greatly benefit the readability also

This is the controversial part, Lisp aficionados to the contrary.

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

#75

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.

> problematic?

Unless it's a regex....

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

#76
post #39
post #38

Earlier quoted context omitted.

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.

Won't you still have to escape the closing bracket if it occurs inside the string?

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

#77
post #39

Earlier quoted context omitted.

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.

Won't you still have to escape the closing bracket if it occurs inside the string?

Only if you want to refer to it literally as a closing quote rather than having it act as a closing quote. That case is extremely rare.

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

#78

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

I also once had to pick up around the house and it was oh so terrible.

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

#79
post #40
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…

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.

Ambiguous parses aren't even the worst of it -- the worst are the ones that require real world knowledge.

"I couldn't fit the trophy in my suitcase because it was too big."

"I couldn't fit the trophy in my suitcase because it was too small."

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

#80
post #77

Earlier quoted context omitted.

Won't you still have to escape the closing bracket if it occurs inside the string?

Only if you want to refer to it literally as a closing quote rather than having it act as a closing quote. That case is extremely rare.

Its definitely rarer than double or single quotes occurring in string. But I was wondering about the parent comment's concern of passing a string through multiple levels of escaping.

> 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

Post reply on HN