如何手动解析左递归文法是最简单的方法？

Question

如何手动解析左递归文法是最简单的方法？

parsinglanguage-agnosticgrammarcompiler-theory

8

我正在为一个个人项目编写解析器，并且出于教育目的，希望手动编写而不是使用解析器生成器。不幸的是，许多在线资源（以及我在大学里上的编译器课程）都假定某种LL(k)文法。但我不想左因子化文法，因为存在左递归的非终结符。

E ::= E * E
    | E / E
    | E + E
    | E - E
    | ...

在类似bison的解析器生成器中可能出现的语法，可以极大地简化语法。手动解析这样的语法最简单的方法是什么？我目前的研究告诉我，由于在此处解释的原因，递归下降不是一个选项，而使用递归上升的LR解析可能是一个不错的选择，尽管有几个网站提到它是非直观的。

- Matt Kline

尝试使用左递归Packrat扩展（它们与手写解析器完全兼容）。它看起来几乎像是递归下降解析，但需要一些备忘录的样板代码。在这里查看详细信息：http://www.vpri.org/pdf/tr2007002_packrat.pdf - SK-logic

看看我的SO答案，了解如何手动编写解析器：https://dev59.com/v3E95IYBdhLWcg3wlu6z#2336769 对于“左递归”，必须始终有一条替代规则；您可以通过首先检查替代规则并在找到后循环回来来手动编写此规则。 - Ira Baxter

2个回答

1

递归下降分析器很容易，一旦你理解它们只是BNF的反（或者说是相反的）就行了。

我最近写的一个部分如下：

/**
 * Parse an addition or subtraction expression.
 *
 * <p/><code><pre>
 * AdditiveExpression
 *     MultiplicativeExpression
 *     AdditiveExpression "+" MultiplicativeExpression
 *     AdditiveExpression "-" MultiplicativeExpression
 * </pre></code>
 *
 * @return an expression
 */
Expression parseAdditiveExpression()
    {
    Expression expr = parseMultiplicativeExpression();
    while (peek().getId() == Id.ADD || peek().getId() == Id.SUB)
        {
        expr = new RelOpExpression(expr, current(), parseMultiplicativeExpression());
        }
    return expr;
    }

/**
 * Parse a multiplication / division / modulo expression.
 *
 * <p/><code><pre>
 * MultiplicativeExpression
 *     PrefixExpression
 *     MultiplicativeExpression "*" PrefixExpression
 *     MultiplicativeExpression "/" PrefixExpression
 *     MultiplicativeExpression "%" PrefixExpression
 *     MultiplicativeExpression "/%" PrefixExpression
 * </pre></code>
 *
 * @return an expression
 */
Expression parseMultiplicativeExpression()
    {
    Expression expr = parsePrefixExpression();
    while (true)
        {
        switch (peek().getId())
            {
            case MUL:
            case DIV:
            case MOD:
            case DIVMOD:
                expr = new RelOpExpression(expr, current(), parsePrefixExpression());
                break;

            default:
                return expr;
            }
        }
    }

我知道很多人喜欢使用自动生成解析器的工具来进行自动化，但我个人更喜欢了解语言的词法分析和语法分析的细节，所以我从不让工具代替我完成这有趣的工作。

- cpurdy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rici · Accepted Answer

如果你想为一个玩具语言构建一个大部分基于递归下降的解析器，其唯一的左递归在更或多或少标准的表达式语法中，则应考虑使用Pratt解析器（Java）（Javascript）。或者（等效地），您可以使用运算符优先级解析器；该算法在龙书中有很好的描述，并且有很多使用逆波兰算法的可用示例（但请注意，许多热情地发现此算法并立即将其写入博客的人远非可靠权威）。

对于宽松分析的注意事项：

如果您想解析表达式语法，并且不关心运算符的优先级（例如，如果您只需要对代码进行语法着色），则可以轻松地重新构建表达式语法以避免左递归。

起点是这个，使用*表示Kleene星号，?表示可选项，( )表示分组：

expression: term (INFIX term)*
term: PREFIX* operand postfix*
operand: ID
       | CONSTANT 
       | '(' expression ')'
       ;
postfix: POSTFIX
       | '[' expression ']'
       | '(' ( expression (',' expression)* )? ')' 
       ;

递归下降解析器可以轻松处理上述代码中的 * 和 ? 运算符，并且没有左递归，因此应该足够。

请注意，C语言有强制类型转换表达式的笨拙之处，这些表达式在语法上无法与函数调用区分开来，除非您知道第一个带括号的表达式包含类型而不是表达式。然而，为了宽松的解析目的，使用上述语法将其解析为函数调用是可以的。

C++使用尖括号既作运算符又作模板参数，更难处理。我看到许多语法着色器完全忽略了模板参数的情况；正确处理它们是一项挑战，但可能是值得的。

编辑评论:

如果你愿意，可以忽略这一点，但我个人认为学习如何使用自下而上的LR解析器，特别是GLR解析器，比尝试将语言塞入受限制的解析算法中要更加丰富和有益。尤其是在代码路径中模糊了语法细节的情况下。但是话虽如此，如果只是为了看到bison解析器可以更加优雅简单，那么做一个bison和手动生成的解析器都是有价值的。