I've copy/pasted the code of your reverse polish evaluator in python in this interactive blog post: http://blog.klipse.tech/python/2016/09/22/python-reverse-pol...
LL and LR Parsing Demystified (2013)
21–30 of 37 posts
Re: LL and LR Parsing Demystified (2013)
#22Earlier quoted context omitted.
> A planned future article will break open the black box for more details about the inner workings of these algorithms. Was this article ever written?
Good question. Not so far. I can't quite see how to do it without getting bogged down in details. The "traditional" algorithms and grammar classes (Strong LL, Full LL, LR(0), etc) are complicated, and yet few people use these. The ones people actually do use (LL(star), ALL(star), GLR, IELR, LALR, etc) tend to be even more complicated. Maybe the thing to do is to illustrate a few of the most basic algorithms by exampl…
Earley parsing is simple and general.
Re: LL and LR Parsing Demystified (2013)
#23tl;dr use ANTLR But actually, I did read this excellent article for the second time. However, unless you are skilled in the art, you should be using ANTLR4, Honey Badger. Terence Parr deserves a Turing award. For parsing, most upper div compiler classes start off with CFGs, dip briefly into LL recursive descent and then conclude with LALR. If people remember anything, it's SHIFT/REDUCE. Unfortunately, there doesn't s…
Honestly, having written a few a parsers, i prefer PEG with recursive descent, or parser combinator.
I find recursive descent parsers are easy to understand, write, debug(you can drop in a breakpoint a follow it through), and the resultant code is actually readable and clean. It's also fairly easy to add error reporting and recovery. As long as you don't do complicated stuff, they're really fast to.
You don't particularly need to be an expert to write recursive descent parsers either.
Re: LL and LR Parsing Demystified (2013)
#24tl;dr use ANTLR But actually, I did read this excellent article for the second time. However, unless you are skilled in the art, you should be using ANTLR4, Honey Badger. Terence Parr deserves a Turing award. For parsing, most upper div compiler classes start off with CFGs, dip briefly into LL recursive descent and then conclude with LALR. If people remember anything, it's SHIFT/REDUCE. Unfortunately, there doesn't s…
There are plenty of other parser generators than ANTLR and interesting parsing techniques that fit the bill. Not that there's anything wrong with ANTLR. The last few time when I've been working on programming language prototypes, I've written the parser using Parsec parser combinators in Haskell. It's super fast and easy to use, however it's more like syntactic sugar for recursive descent parsers than a rigorous pars…
[deleted]
Re: LL and LR Parsing Demystified (2013)
#25Earlier quoted context omitted.
Good question. Not so far. I can't quite see how to do it without getting bogged down in details. The "traditional" algorithms and grammar classes (Strong LL, Full LL, LR(0), etc) are complicated, and yet few people use these. The ones people actually do use (LL(star), ALL(star), GLR, IELR, LALR, etc) tend to be even more complicated. Maybe the thing to do is to illustrate a few of the most basic algorithms by exampl…
Out of curiosity, where would one find an explanation (potentially dry, long, and complicated) of the algos you mention here? In other words - how did you get to know them?
> Out of curiosity, where would one find an explanation (potentially dry, long, and complicated) of the algos you mention here?
> In other words - how did you get to know them?
My book recommendation: Dick Grune, Ceriel J.H. Jacobs - Parsing Techniques: A Practical Guide (Second Edition). Many people will also recommend the "dragon book" (Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman - Compilers: Principles, Techniques, and Tools (Second edition)), which is not a bad book.
If you want to dive deeply into parsing and want to read about all the details over hundreds of pages, the Grune-Jacobs book is clearly the recommdendation. On the other hand, if you just want to understand the theory behind the parsing stage of a compiler (as one part of a compiler - and there are lots of other parts, too), you will probably prefer the dragon book.
Re: LL and LR Parsing Demystified (2013)
#26Earlier quoted context omitted.
By far my favorite survey book on the subject is "Parsing Techniques: A Practical Guide" by Grune and Jacobs. Here is my Amazon review of the book: https://www.amazon.com/gp/customer-reviews/R17E19PSPM2UO9
This book seems to be available at : http://dickgrune.com/Books/PTAPG_1st_Edition/
This is the first edition. The current edition is the second edition.
Re: LL and LR Parsing Demystified (2013)
#27I've learned a lot about LALR and GLR using Bison in combination with Ruby.
Bison and Flex are available as apt packages on Ubuntu and there is heaps of documentation.
The Ruby angle means you don't have to roll your own AST structures. Also, Ruby's 'VALUE' type is easily passed around in Bison grammar.
example:
https://github.com/cjhdev/slow_blink/blob/master/etc/slow_bl...
Re: LL and LR Parsing Demystified (2013)
#28I fail to see the mystery. In my opinion, state machines are the most straight-forward parts of programming.
There is a learning curve with lex and yacc but if you cannot ever use these programs then what can you really call yourself a programmer?
It's the endless search for a "new" programming language and the layers upon layers of needless abstraction created by today's "programmers" that I find mystifying.
Re: LL and LR Parsing Demystified (2013)
#29Happy to see this show up here again. It's one of my articles that I'm most proud of. I'm happy to answer any questions about it.
I do wish you'd put the XML example next to Lisp, just for laughs:
12 3