6 ms·

Undershoot: Parsing theory in 1965

102 points by dedalus 8y ago

agumonkey 8y ago
Superb website with loads of content. This https://jeffreykegler.github.io/personal/timeline_v3 https://jeffreykegler.github.io/personal/timeline_v3 is also worth your time twofolds.
- rain1 8y ago
  lol this dude hates PEG parsers
joe_the_user 8y ago
The thing is that writing a parser requires that a person to understand what a formal language is. Overall, only a subset of programmers understand even this, so parsing has a certain inherent hardness to it (you can't just use a library or just use an object). Of course, the problem of how to create a parser is solvable any number of ways if you mean how to convert an unambiguously specified formal language into a parser. But that doesn't mean basic challenges don't remain. Especially because a formal language is hard to understand (and can be ambiguous) and because what one wants the language to actually do something, there is a further trickiness involved (you have to bridge interface between syntax and semantics). So which way to solve the problem of parsing become a complex decision. But it's not so much "we don't know how to efficiently do this yet" but rather "there is no one-size fits all approach."
- seanmcdirmid 8y ago
  You’d be surprised how many programmers don’t understand (or at least think about) a formal language and manage to write a parser. Heck, it explains why a lot of languages have bizarre hacky syntax. The problem of writing a high performance parser and the problem of writing just a parser at all are fairly isolated. I’ve written many parsers during my career but don’t consider myself a parsing person by any means (though the number of people who have written incremental parsers for IDEs is probably countable on one or two hands, most people don’t think about that as a parser problem).
CalChris 8y ago
I’m a little surprised that ANTLR and L* don’t make the list (ANTLR from the practitioner POV and L* from theory).
PhantomGremlin 8y ago
If parsing is "complicated", then there's another solution. Don't play the game. Change the rules. Play a different game. My understanding (and, since this is the Interwebs I will quickly be corrected if I'm wrong) is that Python is easy to parse; a lot of the battles about adding features to the language involve keeping the grammar simple. And yet Python is eminently useful, despite being simple to parse. I'm reminded of how we didn't understand how to specify a simple grammar in the "good old days". E.g. take ancient FORTRAN. The for-loop in FORTRAN is actually called do. And you specify the end of the loop by numerical statement label (found in columns 1 thru 5). Thus: DO 10 I = 1, 7 some stuff here, loop done for I = 1,2,3,4,5,6,7 10 final line of loop But spaces aren't significant. So if you write the following statement DO 10 I = (1, 7) You get something totally different. You set the value of the complex variable DO10I to (1,7). Bheech. Who wants to parse that? (And yet, there were very capable FORTRAN compilers back in the 1960s!)
- lisper 8y ago
  > Python is easy to parse Lisp is even easier.
  - deleted 8y ago
    [deleted]
  - HumanDrivenDev 8y ago
    And Forth easier still.
    - kazagistar 8y ago
      Isn't forth actually a regular language, and parsable on a finite state machine?
      - howerj 8y ago
        On the contrary, it requires a Turing machine to parse fully.
lisper 8y ago
At the end, Kegler links to this comprehensive overview of the history of parsing: https://jeffreykegler.github.io/personal/timeline_v3 https://jeffreykegler.github.io/personal/timeline_v3 which contains this easily overlooked but IMHO extremely significant statement: "a recursive descent implementation can parse operator expressions as lists, and add associativity in post-processing" Personally, it has always seemed like a no-brainer to me that this is clearly the Right Answer. It is a mystery to me that the computing world at large has spent so much effort on a problem whose solution is actually very straightforward if you just give in on one tiny little piece of theoretical purity. See http://www.flownet.com/ron/lisp/parcil.lisp http://www.flownet.com/ron/lisp/parcil.lisp for my own implementation of such a parser. As you will see if you count LOCs, it's very, very simple by parser standards, and yet it handles all the "hard" problems: associativity, precedence, infix and prefix operators.
- fao_ 8y ago
  Hey, do you know of any papers or more writing about this? (Or even keywords that would aid a search). Reading code is one thing, but being able to read code alongside a paper or web article increases the types of information and makes it much more digestible for me.
  - lisper 8y ago
    No paper, sorry. I kinda wrote it by the seat of my pants. The main point is that I could write it by the seat of my pants, and it works, and the code is pretty short and IMHO readable.
- userbinator 8y ago
  Not at all experienced in Lisp, but I believe this is the core algorithm in that parser... (cond ((and (binop? $next) (> new-priority priority)) (scan) (loop (list op result (parse-expression new-priority)))) (t result))))) ...and is what amounts to the widely-used "precedence climbing" algorithm described here: https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing I like to think of it more as a clever refactoring of recursive descent that condenses all the very similar recursive functions at each level into one which is parameterised by level, and also handles associativity by choosing whether to recurse (right-associative) or loop (left-associative) with the RHS after a binary operator.
lower 8y ago
I'm sorry, but this is just rambling. He goes on about theorists and practitioners without actually saying anything about the problem at all. He doesn't explain why he thinks the current state of the art isn't the solution. What does he want to do that isn't handled well? There are many ways in which parsing can be improved in practice and theory. Actual technical aspects would be more interesting.

102 points by dedalus 8y ago

Superb website with loads of content. This https://jeffreykegler.github.io/personal/timeline_v3 https://jeffreykegler.github.io/personal/timeline_v3 is also worth your time twofolds.

rain1 8y ago
lol this dude hates PEG parsers

joe_the_user 8y ago

The thing is that writing a parser requires that a person to understand what a formal language is. Overall, only a subset of programmers understand even this, so parsing has a certain inherent hardness to it (you can't just use a library or just use an object). Of course, the problem of how to create a parser is solvable any number of ways if you mean how to convert an unambiguously specified formal language into a parser. But that doesn't mean basic challenges don't remain. Especially because a formal language is hard to understand (and can be ambiguous) and because what one wants the language to actually do something, there is a further trickiness involved (you have to bridge interface between syntax and semantics). So which way to solve the problem of parsing become a complex decision. But it's not so much "we don't know how to efficiently do this yet" but rather "there is no one-size fits all approach."

seanmcdirmid 8y ago
You’d be surprised how many programmers don’t understand (or at least think about) a formal language and manage to write a parser. Heck, it explains why a lot of languages have bizarre hacky syntax. The problem of writing a high performance parser and the problem of writing just a parser at all are fairly isolated. I’ve written many parsers during my career but don’t consider myself a parsing person by any means (though the number of people who have written incremental parsers for IDEs is probably countable on one or two hands, most people don’t think about that as a parser problem).

CalChris 8y ago

I’m a little surprised that ANTLR and L* don’t make the list (ANTLR from the practitioner POV and L* from theory).

PhantomGremlin 8y ago

If parsing is "complicated", then there's another solution. Don't play the game. Change the rules. Play a different game. My understanding (and, since this is the Interwebs I will quickly be corrected if I'm wrong) is that Python is easy to parse; a lot of the battles about adding features to the language involve keeping the grammar simple. And yet Python is eminently useful, despite being simple to parse. I'm reminded of how we didn't understand how to specify a simple grammar in the "good old days". E.g. take ancient FORTRAN. The for-loop in FORTRAN is actually called do. And you specify the end of the loop by numerical statement label (found in columns 1 thru 5). Thus: DO 10 I = 1, 7 some stuff here, loop done for I = 1,2,3,4,5,6,7 10 final line of loop But spaces aren't significant. So if you write the following statement DO 10 I = (1, 7) You get something totally different. You set the value of the complex variable DO10I to (1,7). Bheech. Who wants to parse that? (And yet, there were very capable FORTRAN compilers back in the 1960s!)

lisper 8y ago
> Python is easy to parse Lisp is even easier.
- deleted 8y ago
  [deleted]
- HumanDrivenDev 8y ago
  And Forth easier still.
  - kazagistar 8y ago
    Isn't forth actually a regular language, and parsable on a finite state machine?
    - howerj 8y ago
      On the contrary, it requires a Turing machine to parse fully.

lisper 8y ago

At the end, Kegler links to this comprehensive overview of the history of parsing: https://jeffreykegler.github.io/personal/timeline_v3 https://jeffreykegler.github.io/personal/timeline_v3 which contains this easily overlooked but IMHO extremely significant statement: "a recursive descent implementation can parse operator expressions as lists, and add associativity in post-processing" Personally, it has always seemed like a no-brainer to me that this is clearly the Right Answer. It is a mystery to me that the computing world at large has spent so much effort on a problem whose solution is actually very straightforward if you just give in on one tiny little piece of theoretical purity. See http://www.flownet.com/ron/lisp/parcil.lisp http://www.flownet.com/ron/lisp/parcil.lisp for my own implementation of such a parser. As you will see if you count LOCs, it's very, very simple by parser standards, and yet it handles all the "hard" problems: associativity, precedence, infix and prefix operators.

fao_ 8y ago
Hey, do you know of any papers or more writing about this? (Or even keywords that would aid a search). Reading code is one thing, but being able to read code alongside a paper or web article increases the types of information and makes it much more digestible for me.
- lisper 8y ago
  No paper, sorry. I kinda wrote it by the seat of my pants. The main point is that I could write it by the seat of my pants, and it works, and the code is pretty short and IMHO readable.
userbinator 8y ago
Not at all experienced in Lisp, but I believe this is the core algorithm in that parser... (cond ((and (binop? $next) (> new-priority priority)) (scan) (loop (list op result (parse-expression new-priority)))) (t result))))) ...and is what amounts to the widely-used "precedence climbing" algorithm described here: https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing I like to think of it more as a clever refactoring of recursive descent that condenses all the very similar recursive functions at each level into one which is parameterised by level, and also handles associativity by choosing whether to recurse (right-associative) or loop (left-associative) with the RHS after a binary operator.

lower 8y ago

I'm sorry, but this is just rambling. He goes on about theorists and practitioners without actually saying anything about the problem at all. He doesn't explain why he thinks the current state of the art isn't the solution. What does he want to do that isn't handled well? There are many ways in which parsing can be improved in practice and theory. Actual technical aspects would be more interesting.