5 ms·

LL(1) Parser Visualization

113 points by curling_grad 4y ago

carapace 4y ago
Reminds me of Python Tutor ( https://pythontutor.com/ 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.
atonalfreerider 4y ago
Please see my lisp parser: https://youtu.be/40ua8NRyrro https://youtu.be/40ua8NRyrro
jjice 4y ago
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.
- CyberDildonics 4y ago
  This thread is about parser visualization
  - jjice 4y ago
    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.
    - turndown 4y ago
      My advice is to always ignore people like this.
  - civopsec 4y ago
    The last paragraph redeems it since it mentions the website.
  - jonsen 4y ago
    Well it was close, it was partner visualization.
  - fsociety 4y ago
    The tangent was a nice story about compilers / parsing.
civopsec 4y ago
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).
- mrspuratic 4y ago
  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 ; }
Decabytes 4y ago
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 https://pharo.org/features#Simple_language_syntax_35
- fooker 4y ago
  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.

113 points by curling_grad 4y ago

Reminds me of Python Tutor ( https://pythontutor.com/ 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.

atonalfreerider 4y ago

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

jjice 4y ago

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.

CyberDildonics 4y ago
This thread is about parser visualization
- jjice 4y ago
  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.
  - turndown 4y ago
    My advice is to always ignore people like this.
- civopsec 4y ago
  The last paragraph redeems it since it mentions the website.
- jonsen 4y ago
  Well it was close, it was partner visualization.
- fsociety 4y ago
  The tangent was a nice story about compilers / parsing.

civopsec 4y ago

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).

mrspuratic 4y ago
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 ; }

Decabytes 4y ago

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 https://pharo.org/features#Simple_language_syntax_35

fooker 4y ago
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.