LL(1) Validator

LL(1) Validator is a javascript package that checks if a given a context-free grammar is a LL(1) grammar.

Demo

https://ll1-validator.netlify.com/

User manual

The user manual can be found here.

Install

npm install --save ll1-validator

Usage

const ll1Validator = require('ll1-validator');
const input = `
S -> A q;
A -> a A;
A -> ;
`;
const result = ll1Validator.validate(input);
console.log(result);

{
  "grammar": {
    "S": [
      [
        {
          "type": parsers.NONTERMINAL,
          "value": "A"
        },
        {
          "type": parsers.TERMINAL,
          "value": "q"
        }
      ]
    ],
    "A": [
      [
        {
          "type": parsers.TERMINAL,
          "value": "a"
        },
        {
          "type": parsers.NONTERMINAL,
          "value": "A"
        }
      ],
      []
    ]
  },
  "startSymbol": "S",
  "rulesNumber": 3,
  "terminals": [
    "a",
    "q"
  ],
  "nonTerminals": [
    "A",
    "S"
  ],
  "warnings": [],
  "nullableRules": {
    "A": [
      false,
      true
    ],
    "S": [
      false
    ]
  },
  "nullableNonTerminals": {
    "A": true,
    "S": false
  },
  "firstSets": {
    "A": [
      [
        [
          "a"
        ],
        [
          "a"
        ],
        [
          "a"
        ]
      ],
      [
        [],
        [],
        []
      ]
    ],
    "S": [
      [
        [
          "q"
        ],
        [
          "a",
          "q"
        ],
        [
          "a",
          "q"
        ]
      ]
    ]
  },
  "followSets": {
    "A": [
      [
        "q"
      ],
      [
        "q"
      ]
    ],
    "S": [
      [
        "↙"
      ],
      [
        "↙"
      ]
    ]
  },
  "firstSetsDependencies": {
    "A": [
      {},
      {}
    ],
    "S": [
      {}
    ]
  },
  "followSetsDependencies": {
    "follow_nonTerminals": {
      "A": [
        "A"
      ],
      "S": []
    },
    "follow_terminals": {
      "A": [
        [
          "q"
        ]
      ],
      "S": [
        [
          "↙"
        ]
      ]
    }
  },
  "lookAheads": {
    "A": [
      [
        "a"
      ],
      [
        "q"
      ]
    ],
    "S": [
      [
        "a",
        "q"
      ]
    ]
  },
  "isLL1": true,
  "lookAheadsConflicts": {
    "A": [],
    "S": []
  }
}

Running in a browser

If you want to use LL(1) Validator in a browser we recommend you to use Webpack. You also need to mock some Node.js modules by putting this lines in your webpack.config.js.

node: {
  fs: 'empty',
  module: 'empty',
  net: 'empty',
},

For more information see the ANTLR documentation.

Built With

• ANTLR - A powerful parser generator for reading, processing, executing, or translating structured text or binary files.

Versioning

We use SemVer for versioning. For the versions available, see the releases on this repository.

Contributing

1. Fork the repo
2. Create your feature branch (git checkout -b feature/fooBar)
3. Commit your changes (git commit -am 'Add some fooBar')
4. Push to the branch (git push origin feature/fooBar)
5. Create a new Pull Request

License

Distributed under the MIT License. See LICENSE for more information.

Authors

• Andrea Cattaneo (www.andreacattaneo.dev)
• Matteo Locatelli