code.ivysaur.me

plexus

A table-driven parser/lexer with no precompilation phase.

Tags: PL

plexus is a minimal recursive descent parser and lexer that works entirely at runtime. Enter your grammar using a BNF-like syntax directly into a map. The parse function takes the grammar map and your source code as input, to return a tree of nodes. No DFA/NFA lifting is performed.

Rules can be used to customise the capture behaviour. Taking FOO => BAR BAZ QUUX as an example, a FOO node would only be created if all three child nodes could be parsed sequentially. By adding an RT_RULE into the list, this behaviour can be changed. For instance, FOO => BAR RT_RULE_ONE_OF_THE_REMAINING BAZ QUUX will match BAR BAZ and BAR QUUX. Various rules are supported to emulate plus, star, and optional groupings. Certain types of lookahead can be implemented via the RT_RULE_NONE_OF_THE_REMAINING rule. There is no support for backtracking.

By default, the parser skips \s\t\r\n characters in-between other tokens; but this can be overwritten at any time via the WHITESPACE rule, which specifies the character set to skip.

The project also includes bnf2plexus, a program that uses plexus to parse grammars in (E)BNF syntax, compiling the resulting AST into Go source code targeting the plexus library. At the time of writing, the BNF support was sufficiently complete to compile Python's upstream grammar file into a plexus parser.

This is an extended, standalone, Golang version of the C++ parser used by the pexl-D compiler.

Usage (library)

See plexus_test.go for a simple example of parsing arithmetic expressions.

See cmd/bnf2plexus/bnfparse.go for a more complex example of parsing BNF using custom rules.

Usage (bnf2plexus)

Usage of bnf2plexus:
  --input filename

Output is written to stdout.

Changelog

2017-03-12 0.32