gpt4 book ai didi

parsing - 左结合运算符的 BNF 语法

转载 作者:行者123 更新时间:2023-12-04 10:54:59 25 4
gpt4 key购买 nike

我有以下 EBNF 带有左结合运算符的简单算术表达式的语法:

expression:
term {+ term}

term:
factor {* factor}

factor:
number
( expression )
我怎样才能把它转换成 BNF 不改变运算符结合性的语法?以下 BNF 语法对我不起作用,因为现在运算符已成为右结合:
expression:
term
term + expression

term:
factor
factor * term

factor:
number
( expression )
维基百科说:

Several solutions are:

  1. rewrite the grammar to be left recursive, or
  2. rewrite the grammar with more nonterminals to force the correct precedence/associativity, or
  3. if using YACC or Bison, there are operator declarations, %left, %right and %nonassoc, which tell the parser generator which associativity to force.

但是它没有说如何重写语法,我也没有使用任何像 YACC 或 Bison 这样的解析工具,只是简单的递归下降。我所要求的甚至可能吗?

最佳答案

expression
: term
| expression + term;

就这么简单。当然,您将需要一个具有某种描述的 LR 解析器来识别左递归文法。或者,如果递归下降,识别这样的语法是可能的,但不像右结合语法那么简单。您必须滚动一个小的递归上升解析器来匹配它。
Expression ParseExpr() {
Expression term = ParseTerm();
while(next_token_is_plus()) {
consume_token();
Term next = ParseTerm();
term = PlusExpression(term, next);
}
return term;
}

此伪代码应识别该样式的左递归语法。

关于parsing - 左结合运算符的 BNF 语法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11433047/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com