إنشاء شجرة بناء الجملة لعمليات الرياضيات البسيطة

Question

أحاول إنشاء شجرة بناء الجملة ، لسلسلة معينة مع مشغلي الرياضيات البسيط (+، -، *، /، و saterhesis). بالنظر إلى السلسلة "1 + 2 * 3":

يجب أن تعيد صفيف مثل هذا:

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

لقد قمت بوظيفة لتحويل "1 + 2 * 3" في [1 ، " +" ، 2 ، " *" ، 3].

المشكلة هي: ليس لدي أي فكرة لإعطاء الأولوية لبعض العمليات.

الكود الخاص بي هو:

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

إن طريقة القيام بمحلل أعلى لأسفل ، إن لم تكن تستخدم Flex/Bison أو أي حزمة مماثلة أخرى هي كتابة رمز رمزي يمكنه أولاً تحليل الإدخال وتقديم الرموز المميزة.

في الأساس ، تحتاج إلى رمز مميز يوفر getNextToken و PeekNextToken و SkipnextToken.

ثم تعمل في طريقك إلى أسفل باستخدام هذا الهيكل.

// 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";
}

كما ترون ، تبدأ من خلال طلب العملية الأقل امتيازًا ، والتي تتطلب العملية المميزة المرتفعة التالية كمصطلح يسار وهكذا. عوامل Unary لديها بنية مختلفة قليلا. الشيء الأنيق هو التكرار في النهاية عندما يتم مواجهة قوسين.

فيما يلي صفحة تجريبية تستخدم المحلل وتجعل الشجرة المحلية (كان لها الرمز الذي يدور حوله ...)

<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

هل قرأت على النظرية وراء المحللين؟ ويكيبيديا (كما هو الحال دائمًا) لديها بعض المقالات الجيدة لقراءة:

• LR Parser
• محلل النسب العودية

Answer 3

الشيء الذي يجب فعله هو استخدام مولد محلل مثل Flex أو Antlr (سيجد البحث في Google لغتك).

ولكن إذا كنت تفعل هذا من أجل المتعة أو لتعلم كيف يعمل المحللون ، فابحث عن ويكيبيديا للحصول على محلل النسب العودية.

يمكن بسهولة صنع محلل نسب متكرر بسيط للتعبيرات البسيطة مثل هذا. يمكنك تحديد القواعد النحوية على النحو التالي:

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

لاحظ أنه من خلال وضع القاعدة ل <term> تحتوي على القاعدة ل <factor> تتأكد هذه القواعد النحوية من حدوث جميع عمليات الضرب/التقسيم في شجرة التحليل أكثر من أي إضافة/طرح. هذا يضمن تقييم تلك العمليات أولاً.

Answer 4

لقد قمت ببناء آلة حاسبة صغيرة ممتعة مرة واحدة ولدي نفس المشكلة التي قمت بحلها عن طريق بناء شجرة بناء الجملة دون وضع الأسبقية في الاعتبار ، أولاً. كل عقدة لها قيمة الأسبقية ، وعند تقييم غير الممتازين ، كنت أتحقق من العقدة اليسرى: إذا كان لها أسبقية أقل ، فسوف أقوم بتدوير الشجرة في اتجاه عقارب الساعة: العقدة اليمنى. ثم سأحاول التقييم مرة أخرى. يبدو أنه يعمل بشكل جيد بما يكفي بالنسبة لي.