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.
Parsing: The Solved Problem That Isn't (2011)
71–80 of 90 posts
Re: Parsing: The Solved Problem That Isn't (2011)
#72Earlier 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?
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)
#73Earlier 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…
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)
#74Parsing 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.
This is the controversial part, Lisp aficionados to the contrary.
Re: Parsing: The Solved Problem That Isn't (2011)
#75Common 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.
Unless it's a regex....
Re: Parsing: The Solved Problem That Isn't (2011)
#76Earlier 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.
Re: Parsing: The Solved Problem That Isn't (2011)
#77Earlier 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?
Re: Parsing: The Solved Problem That Isn't (2011)
#78Earlier 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
Re: Parsing: The Solved Problem That Isn't (2011)
#79Earlier 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.
"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)
#80Earlier 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.
> 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