Parsing Toolkit

This repository is a collection of parsing utilities. The primary module of interest is cfg.grammar 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 cfg.grammar module and define each of the rules on the object directly. For example:

local cfg = require('cfg.grammar')
local grammar = cfg:new('Start')
grammar['Start'] = 'A | B | "hello", ("user" | "world")'
grammar['A'] = 'a'
grammar['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 CFG 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.
• <>:copy()
  • Creates a deep copy of the grammar for use elsewhere.
• <>:cnf()
  • Convert the grammar into Chomsky normal form.
• <>:print()
  • Utility for seeing the full grammar after EBNF parsing.

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

local cfg = require('cfg.grammar')
local grammar = cfg:new('S')
...
for lhs, alts in pairs(grammar) do
  for _, rhs in ipairs(alts) do
    ...
  end
end

Parsing Algorithms

The following parsing algorithms are available, each in their own module. The parsing function exposed in each module takes in a CFG and returns a clean parse-forest grammar.

Name	Module	Type	Direction
Unger's Method	cfg.unger	Top-Down	Non-directional

Tests

We use the busted framework to manage tests. Run luarocks busted and then busted in the top-level directory of this repository to run all tests.