Skip to content

ben-ng/meatloaf

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

5 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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

About

Generate an SLR parse table from a CFG

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published