Skip to content

Instantly share code, notes, and snippets.

@sunnylost
Created September 7, 2015 04:12
Show Gist options
  • Save sunnylost/94fa27172305fa0c784c to your computer and use it in GitHub Desktop.
Save sunnylost/94fa27172305fa0c784c to your computer and use it in GitHub Desktop.
//https://gist.github.com/DmitrySoshnikov/29f7a9425cdab69ea68f
var grammar = {
1: [ 'S', '( S )' ],
2: [ 'S', 'e' ]
},
table = {
S: {
'(': 1,
'e': 2
}
},
stack = [ 'S', '$' ],
productionNumber = []
function parse( input ) {
input = input.replace( /\s+/g, '' )
var len = input.length,
cursor = 0,
curChar, top
for ( ; cursor < len; ) {
curChar = input[ cursor ]
top = stack.shift()
if ( top == '$' ) {
throw Error( 'parse error' )
}
if ( isTerminal( curChar ) && top === curChar ) {
cursor++
continue
}
stack.unshift.apply( stack, getProduction( top, curChar ) )
}
console.log( stack )
}
function isTerminal( c ) {
return !table.hasOwnProperty( c )
}
function getProduction( top, cur ) {
var nextProductionNumber = table[ top ][ cur ],
nextProduction = grammar[ nextProductionNumber ]
productionNumber.push( nextProductionNumber )
if ( !nextProduction ) {
throw Error( 'parse error!' )
}
return nextProduction[ 1 ].split( /\s*/g )
}
parse( ' ( ( ( e ) ) )' )
console.log( productionNumber )
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment