LL(1) Parser Visualization | Hacker News Reader

LL(1) Parser Visualization

cs.princeton.edu

113 pointscurling_grad13 comments

Very tangential, but I took a compiler course my senior year of college. It was a graduate level with (in my opinion) one of the best professors in the department. He maintains a known-name ML compiler (not NJ) and has studied language theory his entire career, plus he's an excellent teacher and general person.

I worked my ass off in the class and it was a blast. Aced all the projects and almost all the homework assignments. The exams were fine too, except one section, parsing algorithms.

I had just started seeing a girl the week before our week on LR, LALR, LL, etc, and my mind did a lot of wandering during those two lectures. I had everything down for that class, except I had so little knowledge of parsing algorithms. I didn't realize how little I knew until the exam where I lost 30 points to parsing questions. That ended up dropping me to an A-.

Now whenever I see parsing algorithms mentioned, I get a little laugh. Time with a girl was definitely worth the missed points for a nerdy computer science student.

This is the site (I believe - there were a few) I used to help scrape a basic understanding together to prep me for the final exam, so I definitely recommend.

This thread is about parser visualization

I personally always liked when someone had a tangential story in the comments of a thread like this, but if this is truly out of place, I'll remove it.

My advice is to always ignore people like this.

The last paragraph redeems it since it mentions the website.

Well it was close, it was partner visualization.

The tangent was a nice story about compilers / parsing.

This is very timely. I was browsing the Pharo languages feature list^1 and they described the language as having

> Since the grammar is LL(1), it is very fast to parse

and I had never heard of that term before

1. https://pharo.org/features#Simple_language_syntax_35

Intuitively this means you never need to look at more than one token to make a decision while parsing.

This is a desirable property for sure, but if you are developing a language, it is a little bit limiting to restrict yourself to specific classes of grammars.

Reminds me of Python Tutor ( https://pythontutor.com/ )

(Not to nerd-snipe but it would be fun to write a little doggerel to make Python Tutor draw a parse tree, eh? If you do it please post a link?)

We need more tools like these.

It seems like examples for these kinds of simpler grammars tend to be pretty dry. It would be fun to use more programming language-like examples. And then you might also see what difficulties you run into with them (with their limitations).

I'm a visual problem solver, very neat to see this visualized step by step.

Last year I had a need to analyze some non-trivial network device configurations, I tried (and almost succeeded, still a work in progress) with perl, Parse::Yapp (LALR rather than LL) and hand-rolled lexer.

I found Graphviz2::Parse::Yapp was quite good, but since a lot of my grammar was (effectively) machine generated the graphs were improbably large :/ (16 A4 pages!)

Context-free LL(1) grammars are limited in terms of what can be parsed, you can do this though:

  program ::= { statement_list } $
  statement_list ::= statement statement_list
  statement_list ::= ''
  statement ::= id = expr ;
  statement ::= if ( expr ) then statement
  expr ::= id expr_tail
  expr ::= num
  expr_tail ::= + expr
  expr_tail ::= - expr
  expr_tail ::= ''
  id ::= a
  id ::= b
  num ::= 5

(cheating slightly with the final three productions so you can just paste that in as the grammar input) and successfully parse

  { if ( a ) then b = 5 ; }

Please see my lisp parser: https://youtu.be/40ua8NRyrro

Reply on news.ycombinator.com