Wondering what’s next for npm?Check out our public roadmap! »

    meatloaf

    1.0.1 • Public • Published

    Meatloaf

    Generate an SLR parse table from a CFG.

    Build Status

    browser support

    Usage

    var meatloaf = require('meatloaf')
    var grammar = {
      nonTerminals: ['S', 'A', 'B']
    , terminals: ['a', 'b', '-1']
    , rules: [
        ['S', ['A']]
      , ['A', ['a', 'A']]
      , ['A', ['b', 'B']]
      , ['B', ['b']]
      ]
    }
     
    var parseTable = meatloaf(grammar)

    Output:

    ┌───────┬─────────────────┬───────────────┬───────────┬─────────────┬─────────────┐
    │       │ a               │ b             │ -1        │ A           │ B           |
    ├───────┼─────────────────┼───────────────┼───────────┼─────────────┼─────────────┤
    │ A,C,F │ [["s","C,D,F"]] │ [["s","G,I"]] │ []        │ [["g","B"]] │ []          |
    ├───────┼─────────────────┼───────────────┼───────────┼─────────────┼─────────────┤
    │ G,I   │ []              │ [["s","J"]]   │ []        │ []          │ [["g","H"]] |
    ├───────┼─────────────────┼───────────────┼───────────┼─────────────┼─────────────┤
    │ J     │ []              │ []            │ [["r",3]] │ []          │ []          |
    ├───────┼─────────────────┼───────────────┼───────────┼─────────────┼─────────────┤
    │ H     │ []              │ []            │ [["r",2]] │ []          │ []          |
    ├───────┼─────────────────┼───────────────┼───────────┼─────────────┼─────────────┤
    │ C,D,F │ [["s","C,D,F"]] │ [["s","G,I"]] │ []        │ [["g","E"]] │ []          |
    ├───────┼─────────────────┼───────────────┼───────────┼─────────────┼─────────────┤
    │ E     │ []              │ []            │ [["r",1]] │ []          │ []          |
    ├───────┼─────────────────┼───────────────┼───────────┼─────────────┼─────────────┤
    │ B     │ []              │ []            │ [["a"]]   │ []          │ []          |
    └───────┴─────────────────┴───────────────┴───────────┴─────────────┴─────────────┘

    Features

    • 100% statement and branch coverage
    • Does one thing: it generates a parse table, leaving the conflicts to you to resolve
    • Comes with a pretty ASCII table generator so you can easily visualize tables
    • Names DFA states using comma-delimited NFA states for easier debugging

    Table Structure

    parseTable is an object keyed by state. Each value is an object keyed by symbol.

    parseTable = {
      'A,C,F': {a:[inst, inst], b:[inst] /* etc... */}
    , 'G,I': {}
      /* etc... */
    }

    Each inst (instruction) is a tuple [action, destination] with possible values:

    • Shift: ['s', state]
    • Go: ['g', state]
    • Reduce: ['r', i], where grammar.rules[i] is the matched production
    • Accept: ['a']

    If there are multiple instructions for a single state/symbol. Then you have a conflict and need to resolve it. Empty arrays mean that no transition is possible from that state via that symbol.

    Visualizing Tables

    You need to install devDependencies for this feature.

    The included table2string function outputs an ASCII table for easier debugging.

    // The output of this command can be seen in the "Usage" section of this Readme
    var table2string = require('beefalo/lib/table2string')
    console.log(table2string(parseTable))
    • Each row represents a DFA state
    • Columns are the symbols in the grammar
    • DFA states are combinations of NFA states, delimited by commas

    Install

    npm i meatloaf

    DownloadsWeekly Downloads

    1

    Version

    1.0.1

    License

    MIT

    Last publish

    Collaborators

    • avatar