Conversation

sinan
@_osa1
Now that I have a parser generator front-end ready (a grammar parser) I started implementing some of the parsing algorithms that require a generator (i.e. table-driven with large tables, difficult to implement by hand). Things I learned so far:
1
6
sinan
@_osa1
- LL(1) sucks. You can't parse anything practical, and transforming grammars to LL(1) is a lot of work. Imagine recursive descent, except you can only look at the current token, no lookahead. Learned this the hard way after implementing code generation for LL(1) and ...
2
3
sinan
@_osa1
... trying to use it on some real-world language grammars. - SLR(1), LR(1), and LALR methods can use the same parser code, table and action types. The difference is in items and how you generate the parse tables.
1
sinan
@_osa1
- For a long time I thought a grammar is e.g. LR(1) if it has certain properties.. it turns out a grammar is LR(1) if it's parsed by an LR parser using LR(1) items/tables. So algorithms come first, then grammars are named based on whatever parses them.
1
1
sinan
@_osa1
So far my parser generator can generate LL(1) parser, and I have SLR(1) and LR(1) simulation ready. I'm hoping to implement code generation for SLR and LR and then publish soon. I will probably implement LALR after that.
1
1
sinan
@_osa1
I will definitely take a look at it at some point, probably after I implement LALR. I think you're right that tree-sitter uses GLR, I remember the author of tree-sitter mentioning it in a talk.
1