`ielr` initial release : build efficient LR(1) parser tables

Hello !

When writing a LR parser generator, you need a way to generate the LALR/LR(1) parser tables from an input grammar.

It turns out, this is a much harder problem that one might expect if you don't want to end up with gargantuan parser tables! This is why after some efforts, I propose this crate, that implement the best known algorithm (that I am aware of) for this problem.

Why 'ielr' ?

Because this is the name of the main algorithm used in this crate, which is described in this article.

Purpose and scope

The goal is to be able to generate LR parser tables from a grammar: nothing more.

In particular, this crate does not include:

  • A lexer.
  • An actual parser generator: once you have the tables, you still need to use them to build the parser.
  • A way to parse a grammar in a textual format: the grammar must be specified via code (e.g. grammar.add_rule(left, right);)

In other words, this is only a building block for an actual parser generator.

Features

  • LALR(1) and (minimal) LR(1) parser tables generation, with a way to specify conflict resolution.
  • A new mechanism for resolving conflict in the specific case of expressions.

Future

I would love to see people use this crate if they need it, and report what they think would improve it. Although I am fairly confident that the algorithm is correct (and correctly implemented), I am much less sure about the ergonomics, so feedback about this would be very welcome !

In the future, I would like to implement LR(k) tables generation for k > 1... But right now it seems a bit daunting :slightly_smiling_face:.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.