Occam Grammar Utilities

Occam's grammar utilities.

Contents

• Introduction
• Installation
• Example
• Usage
• Building
• References
• Contact

Introduction

This package provides the means to eliminate left recursion, the Achilles heel of top-down parsers, in both its direct and indirect forms.

Installation

With npm:

npm install occam-grammar-utilities

You can also clone the repository with Git...

git clone https://github.com/djalbat/occam-grammar-utilities.git

...and then install the dependencies with npm from within the project's root directory:

npm install

You can also run a development server, see the section on building later on.

Example

There is a small development server that can be run from within the project's directory with the following command:

npm start

The example will then be available at the following URL:

http://localhost:8888

The source for the example can be found in the src/example.js file and corresponding src/example folder. You are encouraged to try the example whilst reading what follows. You can rebuild it on the fly with the following command:

npm run watch-debug

The development server will reload the page whenever you make changes.

One last thing to bear in mind is that this package is included by way of a relative rather than a package import. If you are importing it into your own application, however, you should use the standard package import.

Usage

The eliminateLeftRecursion(...) function should be used as follows:

import { BNFLexer } from "occam-lexers";
import { BNFParser } from "occam-parsers";
import { arrayUtilities } from "necessary";
import { eliminateLeftRecursion } from "occam-grammar-utilities";

const { first } = arrayUtilities;

const bnfLexer = BNFLexer.fromNothing(),
      bnfParser = BNFParser.fromNothing(),
      bnf = `

        ...

      `,
      tokens = bnfLexer.tokensFromBNF(bnf);
      
let rules = bnfParser.rulesFromTokens(tokens);

rules = eliminateLeftRecursion(rules);

Any combination of lexer and parser can be used, not just the basic ones. The point is that the rules employed by the parser were those generated by the BNF lexer and parser and then passed to the eliminateLeftRecursion(...) function.

Building

Automation is done with npm scripts, have a look at the package.json file. The pertinent commands are:

npm run build-debug
npm run watch-debug

References

There is an accompanying paper:

• Eliminating Left Recursion without the Epsilon

Contact

• [email protected]