Genera albero di sintassi per semplici operazioni matematiche

Question

Sto provando a generare un albero di sintassi, per una determinata stringa con semplici operatori matematici (+, -, *, /, e parentesi). Data la stringa "1 + 2 * 3":

http://img248.imageshack.us/img248/3213/misc9928.png

Si dovrebbe restituire un array come questo:

["+", 
[1, 
    ["*", 
    [2,3] 
    ] 
] 
] 

Ho fatto una funzione di trasformare "1 + 2 * 3" [1, "+", 2, "*", 3].

Il problema è: non ho idea di dare la priorità a determinate operazioni.

Il mio codice è:

function isNumber(ch){ 
    switch (ch) { 
     case '0': 
     case '1': 
     case '2': 
     case '3': 
     case '4': 
     case '5': 
     case '6': 
     case '7': 
     case '8': 
     case '9': 
     case '.': 
      return true; 
     break; 
     default: 
      return false; 
      break; 
    } 
} 

function generateSyntaxTree(text){ 
    if (typeof text != 'string') return []; 
    var code = text.replace(new RegExp("[ \t\r\n\v\f]", "gm"), ""); 
    var codeArray = []; 
    var syntaxTree = []; 

    // Put it in its on scope 
    (function(){ 
     var lastPos = 0; 
     var wasNum = false; 
     for (var i = 0; i < code.length; i++) { 
      var cChar = code[i]; 
      if (isNumber(cChar)) { 
       if (!wasNum) { 
        if (i != 0) { 
         codeArray.push(code.slice(lastPos, i)); 
        } 
        lastPos = i; 
        wasNum = true; 
       } 
      } else { 
       if (wasNum) { 
        var n = Number(code.slice(lastPos, i)); 
        if (isNaN(n)) { 
         throw new Error("Invalid Number"); 
         return []; 
        } else { 
         codeArray.push(n); 
        } 
        wasNum = false; 
        lastPos = i; 
       } 
      } 
     } 
     if (wasNum) { 
      var n = Number(code.slice(lastPos, code.length)); 
      if (isNaN(n)) { 
       throw new Error("Invalid Number"); 
       return []; 
      } else { 
       codeArray.push(n); 
      } 
     } 
    })(); 

    // At this moment, codeArray = [1,"+",2,"*",3] 

    return syntaxTree; 
} 

alert('Returned: ' + generateSyntaxTree("1 + 2 * 3")); 

Answer 1

Il modo per eseguire un parser verso il basso, se non si utilizza FLEX/BISON o qualsiasi altro pacchetto simile, è prima di scrivere un tokenizzatore in grado di analizzare i token di input e di servizio.

Fondamentalmente è necessario un tokenizer che fornisce getNextToken, peekNextToken e skipNextToken.

Quindi si scende usando questa struttura.

// parser.js 
var input, currToken, pos; 

var TOK_OPERATOR = 1; 
var TOK_NUMBER = 2; 
var TOK_EOF = 3; 

function nextToken() { 
    var c, tok = {}; 

    while(pos < input.length) { 
    c = input.charAt(pos++); 
    switch(c) { 
     case '+': 
     case '-': 
     case '*': 
     case '/': 
     case '(': 
     case ')': 
    tok.op = c; 
    tok.type = TOK_OPERATOR; 
    return tok; 

     case '0': 
     case '1': 
     case '2': 
     case '3': 
     case '4': 
     case '5': 
     case '6': 
     case '7': 
     case '8': 
     case '9': 
    tok.value = c; 
    tok.type = TOK_NUMBER; 
    return tok; 

     default: 
    throw "Unexpected character: " + c; 
    } 
    } 
    tok.type = TOK_EOF; 
    return tok; 
} 

function getNextToken() { 
    var ret; 

    if(currToken) 
    ret = currToken; 
    else 
    ret = nextToken(); 

    currToken = undefined; 

    return ret; 
} 

function peekNextToken() { 
    if(!currToken) 
    currToken = nextToken(); 

    return currToken; 
} 

function skipNextToken() { 
    if(!currToken) 
    currToken = nextToken(); 
    currToken = undefined; 
} 

function parseString(str) { 
    input = str; 
    pos = 0; 

    return expression(); 
} 


function expression() { 
    return additiveExpression(); 
} 

function additiveExpression() { 
    var left = multiplicativeExpression(); 
    var tok = peekNextToken(); 
    while(tok.type == TOK_OPERATOR && (tok.op == '+' || tok.op == '-')) { 
     skipNextToken(); 
     var node = {}; 
     node.op = tok.op; 
     node.left = left; 
     node.right = multiplicativeExpression(); 
     left = node; 
    tok = peekNextToken(); 
    } 
    return left; 
} 

function multiplicativeExpression() { 
    var left = primaryExpression(); 
    var tok = peekNextToken(); 
    while(tok.type == TOK_OPERATOR && (tok.op == '*' || tok.op == '/')) { 
     skipNextToken(); 
     var node = {}; 
     node.op = tok.op; 
     node.left = left; 
     node.right = primaryExpression(); 
     left = node; 
    tok = peekNextToken(); 
    } 
    return left; 
} 

function primaryExpression() { 
    var tok = peekNextToken(); 
    if(tok.type == TOK_NUMBER) { 
    skipNextToken(); 
    node = {}; 
    node.value = tok.value; 
    return node; 
    } 
    else 
    if(tok.type == TOK_OPERATOR && tok.op == '(') { 
    skipNextToken(); 
    var node = expression(); // The beauty of recursion 
    tok = getNextToken(); 
    if(tok.type != TOK_OPERATOR || tok.op != ')') 
     throw "Error) expected"; 
    return node  
    } 
    else 
    throw "Error " + tok + " not exptected"; 
} 

Come si può vedere, si avvia richiedendo l'operazione privilegiata almeno, che richiede la successiva operazione di maggiore privilegiata come il suo termine a destra ea sinistra, e così via. Gli operatori unari hanno una struttura leggermente diversa. La cosa bella è la ricorsione alla fine quando si incontra una parentesi.

Ecco una pagina di prova che utilizza il parser e rende il parse-tree (aveva il codice per esso, che in giro ...)

<html> 
<head> 
<title>tree</title> 
<script src="parser.js"></script> 
</head> 

<body onload="testParser()"> 

<script> 

function createTreeNode(x, y, val, color) { 
    var node = document.createElement("div"); 
    node.style.position = "absolute"; 
    node.style.left = "" + x; 
    node.style.top = "" + y; 

    node.style.border= "solid"; 
    node.style.borderWidth= 1; 
    node.style.backgroundColor= color; 

    node.appendChild(document.createTextNode(val)); 

    return node; 
}; 

var yStep = 24; 
var width = 800; 
var height = 600; 

var RED = "#ffc0c0"; 
var BLUE = "#c0c0ff"; 

container = document.createElement("div"); 
container.style.width = width; 
container.style.height = height; 
container.style.border = "solid"; 

document.body.appendChild(container); 

var svgNS = "http://www.w3.org/2000/svg"; 

function renderLink(x1, y1, x2, y2) 
{ 
    var left = Math.min(x1,x2); 
    var top = Math.min(y1,y2); 

    var width = 1+Math.abs(x2-x1); 
    var height = 1+Math.abs(y2-y1); 

    var svg = document.createElementNS(svgNS, "svg"); 
    svg.setAttribute("x", left); 
    svg.setAttribute("y", top); 
    svg.setAttribute("width", width); 
    svg.setAttribute("height", height); 

    var line = document.createElementNS(svgNS,"line"); 

    line.setAttribute("x1", (x1 - left)); 
    line.setAttribute("x2", (x2 - left)); 
    line.setAttribute("y1", (y1 - top)); 
    line.setAttribute("y2", (y2 - top)); 
    line.setAttribute("stroke-width", "1"); 
    line.setAttribute("stroke", "black"); 
    svg.appendChild(line); 

    var div = document.createElement("div"); 
    div.style.position = "absolute"; 
    div.style.left = left; 
    div.style.top = top; 
    div.style.width = width; 
    div.style.height = height; 

    div.appendChild(svg); 
    container.appendChild(div); 
} 

function getHeight(dom) { 
    var h = dom.offsetHeight; 
    return h; 
} 

function getWidth(dom) { 
    var w = dom.offsetWidth; 
    return w; 
} 

function renderTree(x, y, node, width, height) 
{ 
    if(height < 1.5*yStep) 
    height = 1.5*yStep; 

    var val; 
    if(node.op) { 
     val = node.op; 
     color = BLUE; 
    } 
    else 
     if(node.value) { 
    val = node.value; 
    color = RED; 
     } 
     else 
    val = "?"; 

    var dom = createTreeNode(x, y, val, color); 
    container.appendChild(dom); 

    var w = getWidth(dom); 
    var h = getHeight(dom); 

    var nx, ny; 

    var child; 

    if(node.left) { 
    nx = x - width/2; 
    ny = y+height; 
    var child = renderTree(nx, ny, node.left, width/2, height/2); 
     renderLink(x+w/2, y+h, nx+getWidth(child)/2, ny); 
    } 

    if(node.right) { 
    nx = x + width/2; 
    ny = y+height; 

    child = renderTree(nx, ny, node.right, width/2, height/2); 
     renderLink(x+w/2, y+h, nx+getWidth(child)/2, ny); 
    } 
    return dom; 
} 

var root; 

function testParser() 
{ 
    var str = "1+2*5-5*(9+2)"; 

    var exp = document.createElement("div"); 
    exp.appendChild(document.createTextNode(str)); 
    container.appendChild(exp); 
    var tree = parseString(str); 
    renderTree(width/2, 20, tree, width/2, 4*yStep); 
} 

</script> 

</body> 
</html> 

Answer 2

Avete letto sulla teoria dietro parser? Wikipedia (come sempre) ha alcuni buoni articoli da leggere:

• LR parser
• Recursive descent parser

Answer 3

ho costruito una piccola calcolatrice divertente una volta e aveva lo stesso problema come voi, che ho risolto da edificio l'albero della sintassi senza tenere in mente la precedenza degli ordini, in primo luogo. Ogni nodo ha un valore di precedenza, e quando si valutano le non-costanti, controllerei il nodo sinistro: se ha precedenza più bassa, ruoterò l'albero in senso orario: portalo in valutazione e valutalo prima, allo stesso modo per nodo giusto. allora proverei solo a valutare di nuovo. Sembrava funzionare abbastanza bene per me.

Answer 4

La cosa da fare è quello di utilizzare un generatore di parser come flex o ANTLR (la ricerca su google ne troverà una per la tua lingua).

Ma se si sta facendo questo per divertimento o per imparare come funzionano i parser, cercare wikipedia per parser di discendenza ricorsiva.

Un semplice parser di discesa ricorsivo può essere facilmente realizzato per espressioni semplici come questa.È possibile definire la grammatica come:

<expression> ::= <term> | <term> <add_op> <expression> 
<term> ::= <factor> | <factor> <mul_op> <term> 
<factor> ::= (<expression>) | <number> 
<add_op> ::= + | - 
<mul_op> ::= * |/

Si noti che, facendo la regola per <term> contiene la regola per <factor> questa grammatica fa in modo avvengono tutte le operazioni di moltiplicazione/divisione più bassa nel albero sintattico di qualsiasi addizione/sottrazione. Ciò garantisce che tali operazioni vengano valutate per prime.