Implemented parsing algorithms

This page summarizes the different parsing algorithms that are implemented in the Hime Parser Generator:
  • LR(k) family
    • LR(0)
    • LR(1)
    • LALR(1), based on the LR(0) kernels
    • LR(*), still in an experimental stage. The tool can generate the automaton, but the algorithm is not yet fully implemented in the redistributable package.
  • GLR family
    • RNGLR (1), the RNGLR algorithm on the LR(1) automaton
    • RNGLALR(1), the RNGLR algorithm on the LALR(1) automaton

From the command line tool, only LALR(1) and RNGLALR(1) are available. It is so because the others do not present particular interest to the majority of the users. Using the library CentralDogma, it is possible to generate parsers for any of these methods.

About RNGLR

The right-nulled generalized LR parsing method is a member of the LR bottom-up parsing methods. It improves over Tomita's GLR method primarily by allowing the early reduction of grammar rules in some cases: Items of the form [A -> alpha . gamma, l] where gamma can produce the empty string allows the reduction of the A -> alpha gamma rule on the l lookahead.

References

Last edited May 14, 2013 at 2:56 PM by lwouters, version 4

Comments

No comments yet.