5

我正在为一个宠物项目编写解析器，出于教育目的，我想手动而不是使用解析器生成器。不幸的是，许多在线资源（以及我在大学学习的编译器课程）都假设某种 LL(k) 语法。我不想保留语法，因为左递归非终结符，例如

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

在类似野牛的解析器生成器中可能实现的功能似乎大大简化了语法。

手动解析这种语法的最简单方法是什么？到目前为止，我的研究告诉我递归下降不是一种选择，原因解释在这里，并且使用递归上升的 LR 解析可能是一个不错的选择，尽管有几个站点停下来提到它不直观。

4

2 回答 2

4

如果您想为一种玩具语言构建一个主要递归下降解析器，其唯一的左递归或多或少是标准表达式语法，那么您应该考虑使用 Pratt 解析器 ( Java ) ( Javascript )。或者（等效地，事实证明），您可以使用运算符优先级解析器；该算法在 Dragon 书中得到了很好的描述，并且有很多使用调车场算法的可用示例（但请注意；许多热情地发现该算法并立即将其写在博客上的人与可靠的权威相去甚远。）

松散解析的注意事项：

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

起点是这个，*用于 Kleene 星，?用于可选和( )分组：

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

递归下降解析器可以轻松处理上面的*and?运算符，并且没有左递归，这样就足够了。

请注意，C 具有强制转换表达式的笨拙，除非您知道第一个带括号的表达式包含类型而不是表达式，否则它在语法上与函数调用无法区分。但是，出于松散解析的目的，可以使用上述语法将它们当作函数调用来解析。

C++ 使用尖括号作为运算符和模板参数更难处理。我见过的许多语法着色器完全忽略了模板参数大小写；让它们正确是一个挑战，但可能是值得的。

编辑评论：

如果您愿意，请忽略这一点，但我个人认为，学习使用自下而上的 LR 解析器，尤其是 GLR 解析器，比试图将一种语言硬塞进一个受限的解析算法，尤其是其中的细节语法的一部分被隐藏为代码路径。但是话虽如此，如果只是为了看看野牛解析器可以变得更加优雅和简单，同时做一个野牛和手动生成的解析器可能是有价值的。

于 2013-07-29T15:40:50.080 回答
0

递归下降解析器很容易，一旦您了解它们只是 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;
            }
        }
    }

我认识很多人都对允许解析器生成自动化的工具发誓，但我个人喜欢了解语言如何进行词法分析和解析的细节，所以我从不让这些工具为我做这些有趣的工作。

于 2018-04-14T02:51:32.207 回答