为二进制表达式创建AST

我继承了ANTLR语法，现在可以在Python Lex Yacc没有任何改变的情况下实现它。我的问题是，ANTLR通常使用非常高级别的EBNF来定义语法，而Yacc使用简单的上下文无关语法。为二进制表达式创建AST

我与AST定义的二进制表达式斗争。由ANTLR给出，它们看起来像

disjunction 
: conjunction ('||' conjunction)*

此定义存在优先原因，不要怀疑名称。

在我的CFG，它看起来像

def p_sum(self, p): 
""" sum : product product_list """ 
??? 

def p_product_list(self, p): 
""" product_list : PLUS product product_list 
| MINUS product product_list 
| epsilon 
""" 
???

一些其他的表情看起来像

def p_disjunction_1(self, p): 
""" disjunction : conjunction """ 
    p[0] = p[1] 

def p_disjunction_2(self, p): 
""" disjunction : conjunction OR disjunction """ 
    p[0] = BinaryOp(p[2], p[1], p[3], p[1].coord)

我想的是，我的AST仅由BinaryExpression节点，如第二个例子给出：

BinaryExpression（ '+'，LHS，右轴）

但这语法给了我一个因素列表。有什么办法可以用我的方式写吗？该???是我需要的地方，但表达构建我的AST，但我想不出一个好办法做到这一点。我看到的是用一元表达式列表定义一个节点，但这对我来说很难看。或者还有另一种写法的方法吗？我不敢去碰它，因为我担心我会以一种解析不同的东西的方式改变它。

来源

2013-10-22 reindeer

“原始”的形式disjunction生产的（之前已经离开了递归消除，使之适用于LL解析）被

disjunction: conjunction 
      | disjunction '|' conjunction 
      ;

这将左副脱节;如果你想正确的关联 - 例如用于赋值运算符 - 使用权递归：

assignment: expression 
      | expression '=' assignment 
      ;

（这也许不是正是你希望在赋值运算符的左边是什么，但它表明对于右关联规则的一般模式）

同样：

sum: product 
    | sum '+' product 
    | sum '-' product 
    ;

对应一个明智的分析树语法的重建应该是相当机械的，但你可能应该编写足够的测试案例，解析它们与两个语法，向你保证你的答案是正确的。

来源

2013-10-22 14:25:18 rici

你怎么知道分离生产的原始形式是什么？取代ANTLR EBNF的Kleene明星真的很容易吗？ – reindeer

@reindeer：严格地说，我不确定，因为它可能是左或右关联。但分离几乎总是左联合的，所以我自信地断言这一点。但是，我提供了两种翻译，以防万一:) – rici

@reindeer：另外，您总是用'nt：A |替换'nt：A B *' nt B'。这将生成相同的语言。所以从某种意义上说，是的，这真的很容易。 – rici

为二进制表达式创建AST

回答

相关问题