制作计算器语法，用javacc生成二叉树 [英] Make a calculator's grammar that make a binary tree with javacc

问题描述

我需要制作一个简单的计算器(带有infix运算符)解析器，以处理+，-，*和/以及float和variable运算符. 为此，我使用了javacc，并使用jjtree制作了此语法.它可以工作，但不能确保最终的树将是我需要的二叉树. 我想要类似5 * 3 + x-y的东西来生成以下树:

I need to make a simple calculator (with infix operator) parser that handle the operators +,-,*,/ and float and variable. To make this I used javacc, and I have made this grammar with jjtree. It works but it doesn't ensure that the final tree will be a binary tree, which I need. I want something like 5*3+x-y to generate the following tree :

  *
 / \
5   +
   / \
  3   -
     / \
    x   y

要做到这一点，什么是合适的语法，而不是左递归?

What would be a proper grammar to do that, that would not be left-recursive ?

推荐答案

类似于以下内容的树会为您提供所需的树.

Something like the following will give you the tree you asked for.

void sum():
{}
{
    term()
    [    plus() sum()
    |    minus() sum()
    |    times() sum()
    |    divide() sum()
    |    modulo() sum()
    ]
}


void term() :
{}
{
    "(" sum() ")" | Number() | Variable()
}

----

要获得反映优先级和关联性的树，可以使用确定的节点.请参阅JJTree文档.

To get a tree that reflects precedence and associativity, you can use definite nodes. See the JJTree documentation.

void sum() #void {} :
{
    term()
    (   plus() term() #BinOp(3)
    |   minus() term() #BinOp(3)
    )*
}

void term() #void {} :
{
    factor()
    (   times() factor() #BinOp(3)
    |   divide() factor() #BinOp(3)
    |   modulo() factor() #BinOp(3)
    )*
}

void factor() #void :
{}
{
    "(" sum() ")" | Number() | Variable()
}

这篇关于制作计算器语法，用javacc生成二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！