时间戳

首页 > 解决方案 > 递归下降解析器：RPN [2] 的中缀

algorithm - 递归下降解析器：RPN [2] 的中缀

问题描述

这是我继续尝试制作一个递归下降解析器——LL(1)——它接受中缀表达式并输出 RPN。这是我的第一个问题的链接，@rici 回答得非常出色，我希望我通过这个修改后的实现来公正地回答他。我的新语法如下（不支持一元运算符）：

expr -> term (+|-) term | term
term -> exponent (*|/) exponent | exponent
exponent -> factor ^ factor | factor
factor -> number | ( expr )

在他的回答中，@rici 指出了Norwell 的语法：

我们通常将一元否定运算符放在乘法和取幂之间

我试图在这里合作：

expr -> term (+|-) term | term
term -> exponent1 (*|/) exponent1 | exponent1
exponent1 -> (+|-) exponent | exponent 
exponent -> factor ^ factor | factor
factor -> number | ( expr )

对第一个语法进行编码使得不能接受 uary(+/-) 数字，并且只能接受二进制 -/+ 运算符。该解决方案适用于我尝试过的许多问题（可能是错误的，希望了解更多）。然而，仔细检查后，第二个失败了，我被迫回到我第一个使用的“hack”。正如@rici 指出的那样：

顺便说一句，您的输出不是逆波兰表示法（而且没有括号也不是明确的），因为您在操作数之前输出一元运算符。

公平地说，他确实指出添加额外的 0 操作数很好，我认为它会起作用。但是，如果我这样做13/-5，其等效中缀将是13/0-5 及其 RPN 13 0 / 5 -。或者也许我误解了他的观点。

最后把钉子钉在棺材里@rici 还指出：

左递归消除将删除左关联运算符和右关联运算符之间的区别

因此，这意味着几乎不可能确定任何运算符的关联性，即所有运算符都相同且没有不同。此外，这意味着对于简单的 LL(1) 解析器来说，如果不是不可能的话，尝试支持许多左右关联运算符将是非常困难的。

这是我的语法的C代码实现：


#include <stdio.h>
#include <stdlib.h>

void error();
void factor();
void expr();
void term();
void exponent1();
void exponent();
void parseNumber();
void match(int t);

char lookahead;
int position=0;
int main() {
  lookahead = getchar();
  expr();
return 0;
}

void error() {
  printf("\nSyntax error at lookahead %c pos: %d\n",lookahead,position);
  exit(1);
}


void factor() {
 if (isdigit(lookahead)) {
      parseNumber();
     // printf("lookahead at %c",lookahead);
  } else if(lookahead =='('){
      match('(');
      expr();
      match(')');
  }else {
      error();
      }
}

void expr(){
    term();
    while(1){
        if(!lookahead||lookahead =='\n') break;
        if(lookahead=='+'|| lookahead=='-'){
            char token  = lookahead;
            match(lookahead);
            term();
            printf(" %c ", token);
        }else {
            break;
        }
    }
}

void term(){
    exponent1();
    while(1){
        if(!lookahead||lookahead =='\n') break;
        if(lookahead=='/'|| lookahead=='*'){
            char token = lookahead;
            match(lookahead);
            exponent1();
            printf(" %c ", token);
        }else {
            break;
        }
    }
}

void exponent1(){
    if(lookahead=='-'||lookahead=='+'){
        char token  = lookahead;
        match(lookahead);
        //having the printf here:
        printf("%c", token);
        //passes this:
        //  2+6*2--5/3      := 2.00 6.00 2.00  *  + 5.00 3.00  /  -
        // -1+((-2-1)+3)*-2 := -1.00 -2.00 1.00  - 3.00  + -2.00  *  + (not actual RPN @rici mentions)
        //but fails at:
        // -(3/2)           := -3.00 2.00  /
        // -3/2             := -3.00 2.00  /
        exponent();
        // but having the printf here
        //printf("%c ", token);
        // fails this -1+((-2-1)+3)*-2 := 1.00 - 2.00 - 1.00  - 3.00  + 2.00 -  *  +
        // since it is supposed to be
        //  1.00 - -2.00 1.00 - 3.00 + -2.00 * +
        //  but satisfies this:
        // -(3/2) := 3.00 2.00  / -
        // (-3/2) := 3.00 - 2.00  /
    }else {
        exponent();
        //error();
    }
}

void exponent(){
    factor();
        while(1){
        if(!lookahead||lookahead =='\n') break;
        if(lookahead=='^'){
            char token  = lookahead;
            match('^');
            factor();
            printf(" ^ ");
        }else {
            break;
        }
    }
}

void parseNumber() {
  double number = 0;
  if (lookahead == '\0'|| lookahead=='\n') return;
  while (lookahead >= '0' && lookahead <= '9') {
    number = number * 10 + lookahead - '0';
    match(lookahead);
  }
  if (lookahead == '.') {
    match(lookahead);
    double weight = 1;
    while (lookahead >= '0' && lookahead <= '9') {
      weight /= 10;
      number = number + (lookahead - '0') * weight;
      match(lookahead);
    }
  }
  printf("%.2f ", number);
  //printf("\ncurrent look ahead at after exiting parseNumber %c\n",lookahead);
}
void match(int t) {
  if (lookahead == t){
    lookahead = getchar();
    position++;
    }
  else error();

}

那么这是否意味着我应该放弃 LL(1) 解析器而改用 LR 解析器呢？或者可以增加前瞻数量有帮助，如果有很多路径，那么它可能会缩小范围，减少前瞻的前瞻。例如：

-(5 ;; 看起来很奇怪

-(5;; 可能是 - ( exp )

或者

--5 ;; 可能有很多东西

--5;; 应该是 -- 运算符和输出说 #

编辑：

  1. 我认为有一个更大的前瞻将很难协调。所以也许有类似分流场算法的东西，我喜欢窥视下一个运算符，并根据运算符的优先级，alogrthim 将确定要执行的函数调用。类似于使用实际运行程序的实际堆栈。所以 pop 将是一个返回，而 push 将是一个函数调用。不知道我怎么能用递归下降来协调它。

  2. 也许窥视的优先级应该决定前瞻长度？

标签： algorithmparsingbnfinfix-notationrecursive-descent

解决方案

  1. 增加前瞻并没有帮助。

  2. 这是算术表达式的常用 LALR(1) 语法，包括求幂：

    expr -> sum
sum -> sum (+|-) product | product
product -> product (*|/) prefix | prefix
prefix -> (+|-) prefix | exponent 
exponent -> atom ^ exponent | atom
atom -> number | ( expr )

    您可以在整个 Internet 上找到构建语法的模型的示例，尽管您也会找到许多示例，其中始终使用相同的非终结符，并且使用优先声明处理由此产生的歧义。

    exponent请注意与其他二元运算符之间的结构差异。exponent是右递归的（因为求幂是右结合的）；其他的是左递归的（因为其他二元运算符是左关联的）。

  3. 当我说您可以通过添加显式 0 来解决前缀运算符字符的歧义时，我并不是说您应该编辑输入以插入 0。那是行不通的，因为（正如您所注意到的）它得到一元运算符的优先级错误。我的意思是递归下降 RPN 转换器应该是这样的：

    void parsePrefix(void) {
  if (lookahead=='-'||lookahead=='+') {
    char token = lookahead;
    match(lookahead);
    fputs("0 ", stdout);
    parsePrefix();
    printf("%c ", token);
  }
  else {
    parseExponent();
  }
}

    这会精确地输出 0 它需要去的地方。

    警告：以下段落是纯粹的意见，不符合 StackOverflow 的政策。如果这会冒犯你，请不要阅读它。（在这种情况下，也许你应该跳过这个答案的其余部分。）

    恕我直言，这确实是一个 hack，但 RPN 的使用也是如此。如果您正在构建一个 AST，您只需构建一个具有单个操作数的 unaryOperator AST 节点。不会有歧义的问题，因为在评估期间不需要再次解释令牌。无论出于何种原因，参加过常规编译器理论课程的学生似乎都认为 AST 在某种程度上是一种复杂的技术，在必要时应避免使用，必须不惜一切代价避免左递归，并且有道德编码自己的 LL 解析器而不是仅仅使用标准可用的 LALR 解析器生成器的价值。我不同意所有这些事情。特别是，我建议您从创建 AST 开始，因为它会使几乎所有其他事情变得更容易。另外，如果您想了解解析，从使用标准工具开始，专注于编写清晰的、自记录的语法，并使用有关您尝试解析的输入的句法结构的信息。稍后您可以了解解析器生成器的工作原理，如果您真的觉得这很有趣的话。同样，我绝不会从准确评估sin()功能。这并没有为学生提供有关如何使用三角函数（例如，旋转一个角度）的任何见解，这无疑是三角学中最重要的部分。一旦学生对三角学、如何使用它，特别是在典型问题领域中精确计算的要求有了深刻的理解，那么他们可能想看看泰勒展开式和其他计算技术。但大多数人都会满足于打电话sin()，我认为这很完美。

  4. 如果您真的想使用递归下降解析器，那就去吧。他们当然可以工作。

    当您将语法编码到可执行程序中时会发生什么，您将慢慢开始偏离可以在其他程序中使用的语法表示，例如语法着色器和静态分析器。部分原因是您使用的语法已经丢失了语法的重要方面，包括关联性，而这些功能直接编码到您的解析器代码中。最终的结果往往是只维护解析器代码，让理论语法腐烂。当代码本身是“语法”时，它不再可用作您语言语法的实际文档。

    但我并不是说它不能完成。它肯定是可以做到的，并且在实际使用中有很多很多的解析器都是这样做的。

  5. 调车场算法（以及一般的运算符优先级解析）是一种自下而上的技术，就像 LR 解析一样，它们都不需要递归解析器。如果出于某种原因你真的想使用递归，你可以使用 Pratt 解析器，但是自下而上的解析比递归下降有一个巨大的实际优势：它消除了不可控堆栈溢出的可能性。所以很难推荐在生产解析器中使用递归下降，除非输入文本被严格控制以避免可能的堆栈溢出攻击。这可能不适用于未与未经验证的输入一起使用的编译器。但是你的编译器真的是这样吗？您是否从未从外国网站下载源代码压缩包然后输入./configure && make all？:-)

推荐阅读