Parsing Toolkit

The following repository is a collection of parsing utilities. The primary module of interest is grammar.lua which contains facilities for constructing and interacting with CFGs. Most parsing functions take a CFG as an argument.

CFGs

Construction

To construct a CFG, import the grammar.lua module and define each of the rules on the object directly. For example:

local grammar = require('grammar')
local cfg = grammar:new('Start')
cfg['Start'] = 'A | B | "hello", ("user" | "world")'
cfg['A'] = 'a'
cfg['B'] = 'b'

The right-hand side of each rule supports the following subset of EBNF syntax:

Usage	Notation
concatenation	,
alternation	|
optional	[ ... ]
repetition	{ ... }
grouping	( ... )
terminal	" ... "

Interface

A grammar object has the following interface. Avoid defining rules with a LHS variable conflicting with these function names.

• <>:new(start)
  • Create a new CFG with start symbol start.
• <>:clean()
  • Removes nonproductive and unreachable rules.
• <>:print()
  • Utility for seeing the full grammar after EBNF parsing.

Additionally, you can iterate through each rule using pairs. For example:

local grammar = require('grammar')
local cfg = grammar:new('S')

...

for lhs, rhs in pairs(cfg) do
  ...
end

Parsing Algorithms

The following parsing algorithms are available, each in their own module.

Name	Module	Type	Direction	Time	Space
Unger's Method	unger	Top-Down	Non-directional	?	?