时间戳

首页 > 解决方案 > 制作语法解析器（C++ 编译器的一部分）

c++ - 制作语法解析器（C++ 编译器的一部分）

问题描述

我正在制作一个用 C++ 编写的编译器。

目前，它从同一文件夹中的输入文件中获取文本，并且我可以成功地去除所有连续字符的字符串，按字符/关键字/标识符的类型进行隔离（即，它将'int'和'bool'识别为关键字，并且它将“单词”存储在字符串向量中，而将“令牌类型”作为整数存储在同一索引处的整数向量中）。

所以我目前处于存储和分类所有输入的阶段，准备检查语法。

...我认为我对理论有很好的理解，但是我想出的所有解析语法的方法都有严重的缺陷。作为参考，这是应该能够处理任何赋值或声明语句构造的结构，从通用语句开始：

<Statement> -> <Declarative>
<Declarative> -> <Type> <id>

<Statement> -> <Assign>
<Assign> -> <ID> = <Expression>;

<Expression> -> <Expression> + <Term> | <Expression> - <Term> | <Term>

<Term> -> <Term> * <Factor> | <Term> / <Factor> | <Factor>

<Factor> -> ( <Expression> ) | <ID> | <num> 

<ID> -> id

我的目标是让编译器能够按顺序读取每个标记，并按照读取的顺序告诉它是什么 Expression/Term/Factor/ID。

我仍在尝试提出一个函数来解析给定语句的语法。有没有办法让它“内联”或“一次 1 个令牌”，还是我被卡住了？在尝试调试不起作用的东西之前，我正在尝试设计这个 - 所以我希望我的伪代码的一般设计可以告诉你我做错了什么。

和里面的东西<angle brackets>是令牌类型

方法 A：“整行”- 读取行中的第一个标记，向前查找以查找 ';' 并从那里操纵

until reach end of file (while loop)
   determine statement type (if)
   if the <type> and <id> are the same, the immediate next step to be taken is the same
      need to determine length of statement to be parsed (find start and end of current 'line')
      in <type> and <id> cases, it should be 'current' to 'index of next ;' (length of statement should be from <type> or <id> to the next ';')
   if <type>, should be easy - target format is <type> <id>;
      if token pattern matches that, then is valid, and is noted as such in output
   if <id>, more complex, is assignment
      if token 0 is <id>, token 1 (=) and token 'index' (;) should be the same every time
         between 1 and 'index' is the <expression> to evaluate

...而且我不知道如何评估该<expression>部分，因为它需要某种递归

方法 B：“保存状态” - 函数获得一些输入，说明语句的先前“状态”是什么

until reach end of file (while loop)
   get passed int to represent previous state, determine current token
      if 0, the statement is starting
         if <type>, expect to be a declaration statement
            return 1
         else if <id>, expect assignment statement
            return 3
      if 1, <type> found previously
         if current token is <id>
            return 2
      if 2, <type> <id> found previously
         if current token is ';'
            return 0, statement complete
      if 3, <id> found previously
         if current token '='
            return 4
      if 4, <id> = found previously
         expression needs evaluation, expect rat's nest of code here

这就是我到目前为止所拥有的。

附录：方法C，这是我刚才的一个想法，看起来很乱：

添加类似 4 个不同的函数，所有这些函数都可以相互调用：

function 1 - to read/determine if it's a declaration or assignment statement
function 2 - to determine if an Expression is addition, subtraction, or a Term
function 3 - to determine if a Term is multiplication, division, or a Factor
function 4 - to determine if a Factor is an expression but in parenthesis, an identifier, or a number

最后一种方法似乎很容易受到巨大递归和内存泄漏的影响，但它似乎也更容易隔离问题。

标签： c++recursionvectorsyntaxcompiler-construction

解决方案

正如评论中已经指出的那样，您的方法 C 被称为递归下降并且是要走的路，但不能处理左递归。那么如何处理呢？

你可以重写你的语法来删除左递归，你会想出这样的东西：

<Expression>     -> <Term> <ExpressionTail>
<ExpressionTail> -> + <Term> <ExpressionTail> | - <Term> <ExpressionTail> | ε

如果你直接把它翻译成代码，你最终会得到类似的东西：

Expression* parseExpression() {
    Expression* operand = parseTerm();
    ExpressionTail* tail = parseExpressionTail();
    return new Expression(operand, tail);
}

ExpressionTail* parseExpressionTail() {
    if (current token is '+' or '-') {
        char operator = current token;
        move to next token;
        Expression* operand = parseTerm();
        ExpressionTail* tail = parseExpressionTail();
        return new OperatorExpressionTail(operator, operand, tail);
    } else {
        return new EmptyExpressionTail();
    }
}

但是有几个问题：

首先，重写后的语法明显不如原来的可读性。当然，您可以通过记录一个版本的语法并实现另一个版本来避免这个问题，但是代码的结构仍然包含相同的复杂性。为每个级别的左递归定义使用单独parseFooTail()的方法肯定会很烦人并且会使代码混乱。

然而，最重要的警告是我们正在生成的树的结构：在上面的代码中，生成的树直接基于重写的语法，看起来不像原始语法的树。这棵树很难使用，因为我们甚至不能直接访问运算符的正确操作数——我们必须迭代尾指针。我们想要的是生成一棵树，其中每个中缀表达式都表示为一个带有运算符和两个操作数的节点，就像在原始语法中一样。

为此，我们可以用return new Expression(operand, tail)迭代尾部并从中构造适当的表达式树的代码替换。或者我们可以完全摆脱结构并通过将左操作数作为参数传递ExpressionTail直接在内部生成该树：parseExpressionTail

Expression* parseExpression() {
    Expression* operand = parseTerm();
    return parseExpressionTail(operand);
}

Expression* parseExpressionTail(Expression* leftOperand) {
    if (current token is '+' or '-') {
        char operator = current token;
        move to next token;
        Expression* rightOperand = parseTerm();
        Expression* newLeftOperand = new InfixExpression(operator, leftOperand, rightOperand);
        return parseExpressionTail(newLeftOperand);
    } else {
        return leftOperand;
    }
}

现在这将产生我们想要的那种树，但它仍然不是特别好阅读。你可能注意到的一件事是它parseExpressionTail现在是尾递归的，这意味着它可以很容易地重写为循环。一旦我们这样做了，该函数将不再是直接递归的，因此它可以内联到parseExpression. 所以让我们这样做：

Expression* parseExpression() {
    Expression* leftOperand = parseTerm();
    while (current token is '+' or '-') {
        char operator = current token;
        move to next token;
        Expression* rightOperand = parseTerm();
        expression = new InfixExpression(operator, leftOperand, rightOperand);
    }
    return leftOperand;
}

如果我们回顾一下语法，我们可能会注意到expressionTail最好将其描述为“匹配模式(+ | -) <Term>零次或多次”。因此，如果我们在语法符号中引入重复运算符（如*正则表达式或{}EBNF 中使用的），我们可以将其重写为

<Expression> -> <Term> ((+ | -) <Term>)*

或者

<Expression> -> <Term> {(+ | -) <Term>}

取决于您喜欢哪种表示法。现在，如果您首先使用此符号编写语法，则可以以比首先递归编写然后重新编写尾递归更直接的方式提出上述代码：您可以使用重复运算符编写语法任何有意义的地方，然后while在将语法转换为代码时，只要看到重复运算符就只需使用循环。

现在我们已经找到了一种在递归下降解析器中解析中缀表达式的完全可行的方法，但是parseFoo一旦你有很多优先级，对于每个优先级都有一个单独的方法仍然会变得很烦人，同样的道理也适用于递归下降解析器。每个优先级的语法中的非终结符。在语法层面上，我们可以通过简单地像这样模糊地编写语法来解决这个问题：

<Expression> -> <Expression> + <Expression>
              | <Expression> - <Expression>
              | <Expression> * <Expression>
              | <Expression> / <Expression>
              | <Factor>

然后，您可以通过将每个运算符的优先级和关联性与语法分开列出来消除歧义。对于解析器代码，我们想做同样的事情：有一个包含每个运算符及其优先级和关联性的表，然后有一个函数可以通过简单地遍历该表来解析所有中缀表达式。

实现这一点的方法是对其他所有内容使用递归下降，但在解析中缀表达式的函数内部使用专门的算法，例如优先爬升（参见Eli Bendersky 的这篇博客文章和/或维基百科上的解释）。

推荐阅读