手写解析器中翻译语法文件

Question

我一直在尝试编写自己的编译器，以便于教育目的，并且我遇到了一个问题。我采用了递归下降的方法，并具有一些关于lex和yacc/bison的先前知识。

到目前为止，我只是试图处理解析方面的问题，而不考虑AST或代码生成的生成。

我正在尝试为这个特定语法文件部分编写表达式解析。

primary_expression
    : IDENTIFIER
    | CONSTANT
    | STRING_LITERAL
    | '(' expression ')'
    ;

postfix_expression
    : primary_expression
    | postfix_expression '[' expression ']'
    | postfix_expression '(' ')'
    | postfix_expression '(' argument_expression_list ')'
    | postfix_expression '.' IDENTIFIER
    | postfix_expression PTR_OP IDENTIFIER
    | postfix_expression INC_OP
    | postfix_expression DEC_OP
    ;

到目前为止，我有这段代码。

void Parser::primaryExpression()
{
    if (accept(Token::eIdentifier))
    {

    }
    else if (accept(Token::eIntNumber))
    {

    }
    else if (accept('('))
    {
        expression();
        expect(')');
    }
}
void Parser::postfixExpression()
{

}

我在处理后缀表达式的递归时遇到了一些问题，不知道如何继续使用postfixExpression函数。

我觉得对于递归下降解析器，我应该以不同的方式安排我的语法。

有人能指点我正确的方向吗？

- Sanctus2099

---

请查看我的SO答案，了解如何编写递归下降解析器：https://dev59.com/v3E95IYBdhLWcg3wlu6z#2336769 - Ira Baxter

Answer 1

请注意，postfix_expression总是首先解析primary_expression，因此首要任务是调用primaryExpression()。

然后，如果下一个字符是剩余七个规则中递归postfix_expression后面跟随的任何字符，则正在解析postfix_expression。这将给您另一个posfix_expression，因此您需要再次重复。

我不会为您编写C++代码，但是在伪代码中：

postfixExpression()
{
    primaryExpression();
    while (next character is any of the characters that follow
           postfix_expression in the remaining seven rules)
    {
         parse_the_appropriate_rule();
    }
}

- Sam Varshavchik

Answer 2

左递归在LL（递归下降）解析器中很难处理 - 你需要识别它并将其转换为循环而不是递归调用。一般来说，你想将左递归重构为

A → α | A β

然后你的递归下降例程就变成了

parseA() {
    parseAlpha();
    while (lookaheadMatchesBeta())
        parseBeta();
}

请注意，这需要足够的前瞻来区分FIRST(β)和FOLLOW(A)，以便找到所有可以匹配β的尾随物的结尾。

这与消除LL语法中左递归的过程相同 - 你实际上是用以下规则替换上面的规则：

A → α A' A' → ε | β A'

然后将parseAPrime中的尾递归调用替换为循环并将其内联到parseA中。

对您的语法执行此操作并使用代码中使用的接受/期望技术，您会得到类似以下的东西：

void Parser::postfixExpression() {
    primaryExpression();
    while (true) {
        if (accept('[')) {
            expression();
            expect(']');
        } else if (accept('(')) {
            if (accept(')')) {
            } else {
                argumentExpressionList();
                expect(')'); }
        } else if (accept('.')) {

               ⋮

        } else if (accept(Token::DEC_OP)) {
        } else {
            break;
        }
    }
}

- Chris Dodd