mikedevice / first-follow

Utility for FIRST, FOLLOW, PREDICT set generation aiding in custom programming language creation

first-follow

A small tool for calculating first, follow and predict sets for the grammar. Its size is only 390 bytes (minified and gzipped). No dependencies. Size Limit controls the size.

Installation

$ npm install first-follow

Demo

You can try this tool here.

Example

const firstFollow = require('first-follow');

const rules = [
  // S -> a b A
  {
    left: 'S',
    right: ['a', 'b', 'A']
  },

  // A -> b c
  {
    left: 'A',
    right: ['b', 'c']
  },

  // A -> ε
  {
    left: 'A',
    right: [null]
  }
];

const { firstSets, followSets, predictSets } = firstFollow(rules);

console.log(firstSets);
/*
 *  // S: a
 *  // A: b, ε
 *
 *  {
 *    S: ['a'],
 *    A: ['b', null]
 *  }
 */


console.log(followSets);
/*
 *  // S: ┤
 *  // A: ┤
 *
 *  {
 *    S: ['\u0000'],
 *    A: ['\u0000']
 *  }
 */

console.log(predictSets);
/*
 *  // 1: a
 *  // 2: b
 *  // 3: ┤
 * 
 *  {
 *    '1': ['a'],
 *    '2': ['b'],
 *    '3': ['\u0000']
 *  }
*/

Rules

Input

The grammar is represented by array of objects. Each object describes the only one rule. The rule's object contains two required fields:

• left — specifies the left part of the rule. A single nonterminal: A, B, Program, Expression, etc.
• right — specifies the right part of the rule. It contains terminals and nonterminals or empty chain (epsilon): A + B, d * A, ε, etc.

Output

• The firstSets object's keys are nonterminals and values are first sets for these nonterminals.
• The followSets object's keys are nonterminals and values are follow sets for these nonterminals.
• The predictSets object's keys are rules numbers (starting from 1) and values are predict sets for these rules.

Definitions

• An empty chain (ε) is represented by null.
• An end mark (┤) is represented by \u0000.

first-follow's Issues

Add success indicator

When source grammar changes slightly, user not always can see, what changes has been occurred. So, it's need to add an indicator of success result.

Add button for epsilon

How can I deploy the gh-pages like yours on my mechine?

As is. e.g.: https://mikedevice.github.io/first-follow/

Support alternation

You should be able to split it up into multiple rules internally. Additionally, other EBNF features or maybe even a modified version of the spec on the wiki would be useful.

Add auto replacing special characters

It's need to replace special characters combinations with unicode characters

• combination of "->" need to replace with right arrow character;
• think about combination for empty chain (maybe \eps);

Also it is necessary to handle it at paste from clipboard

Save grammar to local storage

Support for use kebab-case

Hi! @MikeDevice
Thank you for your good project.
I have a problem that non-terminals can't be kebab-case (or hyphen-case)...
For example when I write Type-specifier int, your code can't understand it.