人気ブログランキング | 話題のタグを見る

電卓パーサ(構文木版その2)

<script>
// Pattern Matcher Module
// written by tnomura, Feb. 9, 2016
// This is a public domain software

P = (function() {

function Node( value ) {
this.value = value
this.left = null
this.right = null
}

var line = ""
stack = []
stack2 = []

function setline( ln ) { line = ln }
function getline() { return line }
function push( dat ) { stack.push( dat ) }
function pop() { return stack.pop() }
function getstack() { return stack }

function lex( re ) {
return function() {
var match = line.match( re )
if ( match ) {
line = line.replace( re, "" )
stack.push( new Node(match[0]) )
return true
}
return false
}
}

function pat( pattern, action ) {
return function () {
var trackback = line
var stacklength = stack.length
if (pattern()) {
action()
return true
} else {
line = trackback
stack = stack.slice(0, stacklength)
return false
}
}
}

function many( pattern ) {
return (function() {
while( pattern() ) {}
return true
})
}

function append( rightNode, operatorNode, leftNode ) {
operatorNode.left = leftNode
operatorNode.right = rightNode
stack.push( operatorNode )
}

function postorderTraversal( node ) {
if ( node.left ) {
postorderTraversal( node.left )
}
if ( node.right ) {
postorderTraversal( node.right )
}
stack2.push( node.value )
}

function parsetree(node) {
stack2 = []
postorderTraversal(node)
return stack2
}

return {
node: Node,
setLine: setline,
getLine: getline,
push: push,
pop: pop,
getStack: getstack,
lex: lex,
pat: pat,
many: many,
append: append,
parseTree: parsetree
}

})()

// Definition of The Grammar

var spacing = P.pat( P.lex(/^\s*/), P.pop )
var number = function() {return P.lex(/^[0-9]+/)() && spacing() }
var star = function() {return P.lex(/^[*/]/)() && spacing() }
var plus = function() {return P.lex(/^[+-]/)() && spacing() }
var lparen = function() {return P.lex(/^[(]/)() && spacing() }
var rparen = function() {return P.lex(/^[)]/)() && spacing() }

var stnum = P.pat( function() {return star() && primary()}, function() {
P.append( P.pop(), P.pop(), P.pop() )
})

var term = function() {return primary() && P.many( stnum )() }

var adterm = P.pat( function() {return plus() && term()}, function() {
P.append( P.pop(), P.pop(), P.pop() )
})

var expr = function() {return term() && P.many( adterm )() }

var paren = P.pat( function() {return lparen() && expr() && rparen() }, function() {
P.pop(); var a = P.pop(); P.pop()
P.push( a )
})

var primary = function() {return number() || paren() }

// Main Program

P.setLine("(3 - 1) * ( 2 + 4)")
expr()
var result = P.pop()
a_lert( JSON.stringify( result ) )
a_lert( P.parseTree( result ) )
</script>

by tnomura9 | 2016-02-14 22:02 | JavaScript | Comments(0)
<< 正規表現に変数を使う 電卓パーサ(構文木版) >>