对于以分号分隔的列表，如何将产生式转换为 LL(1)？

Question

我正在阅读这本关于解析的入门书（顺便说一句，这相当不错），其中一项练习是“为您最喜欢的语言构建一个解析器”。因为我今天不想死，所以我想我可以为一些相对简单的东西做一个解析器，即简化的 CSS。

注意：本书教您如何使用递归下降算法编写 LL(1) 解析器。

因此，作为子练习，我根据我对 CSS 的了解构建语法。但我陷入了无法在 LL(1) 中转换的产生式：

//EBNF
block = "{", declaration, {";", declaration}, [";"], "}"

//BNF
<block> =:: "{" <declaration> "}"
<declaration> =:: <single-declaration> <opt-end> | <single-declaration> ";" <declaration>
<opt-end> =:: "" | ";"

这描述了一个 CSS 块。有效块可以具有以下形式：

{ property : value }
{ property : value; }
{ property : value; property : value }
{ property : value; property : value; }
...

问题在于可选的“;”最后，因为它与{“;”，声明}的起始字符重叠，所以当我的解析器在这种情况下遇到分号时，它不知道该怎么做。

这本书讨论了这个问题，但在其示例中，分号是强制性的，因此可以像这样修改规则：

block = "{", declaration, ";", {declaration, ";"}, "}"

那么，是否有可能使用 LL(1) 解析器来实现我想要做的事情？

Answer 1

我想我明白了：

//EBNF 
block = "{", decl, "}"
decl = simple-decl, [";", [decl]]
simple-decl = ...

//BNF
<block> =:: "{" <decl> "}"
<decl> =:: <simple-decl> <decl-end>
<decl-end> =:: ";" <decl-tail> | ""
<decl-tail> =:: <decl> | e

这会产生以下代码：

private function parseBlock():void {
    accept(Token.LBRACE);
    parseDecl();
    accept(Token.RBRACE);
}


//Token.IDENTIFIER is the starting token of a declaration
private function parseDecl():void {
    accept(Token.IDENTIFIER);
    if(_currentToken.kind == Token.SEMICOLON){
        accept(Token.SEMICOLON);
        if(_currentToken.kind == Token.IDENTIFIER){
            parseDecl();
        }
    }
}

我是对的吗？

Answer 2

如果允许 null 声明，则可以消除歧义：

//EBNF
block = "{", declaration, {";", declaration}, "}"
declaration = "" | ...

//BNF
<block> =:: "{" <declaration-list> "}"
<declaration-list> =:: <declaration> | <declaration> ";" <declaration-list>
<declaration> =:: "" | ...

尽管这不是必需的：

// these don't allow empty declarations
block = "{", {declaration, ";"}, end-declaration, "}"
end-declaration = "" | declaration


<block> =:: "{" <declaration-list> "}"
<declaration-list> =:: "" | <declaration> | <declaration> ";" <declaration-list>

要处理 null，请找出 null 之后可能出现的终端，并让解析器识别这些终端。对于递归下降（在 not-quite-java 中）：

/*
<block> =:: "{" <declaration-list> "}"
<declaration-list> =:: <declaration> | <declaration> ";" <declaration-list>
<declaration> =:: "" | ...
*/
Node block(tokens) {
    terminal(BLOCKBEGIN, tokens);
    Node decls = declList(tokens);
    terminal(BLOCKEND, tokens);
}
Node declList(tokens) {
    Node dcl = decl(tokens);
    if (expect(LINESEP, tokens)) {
        terminal(LINESEP, tokens);
        return new DeclarationList(dcl, declList(tokens));
    } else {
        return new DeclarationList(dcl);
    }
}
Node decl(tokens) {
    if (expect(BLOCKEND, tokens)) {
        return new Declaration();
    }
    ...
}
/*
<block> =:: "{" <declaration-list> "}"
<declaration-list> =:: "" | <declaration> | <declaration> ";" <declaration-list>
*/
Node block(tokens) {
    terminal(BLOCKBEGIN, tokens);
    Node decls = declList(tokens);
    terminal(BLOCKEND, tokens);
}
Node declList(tokens) {
    if (expect(BLOCKEND, tokens)) {
        return new DeclarationList();
    }
    Node dcl = decl(tokens);
    if (expect(LINESEP, tokens)) {
        terminal(LINESEP, tokens);
        return new DeclarationList(dcl, declList(tokens));
    } else {
        return new DeclarationList(dcl);
    } 
}

对于自上而下的解析器，该过程更加明确。构造 FOLLOWS 关系时，您可以递归地将 null 替换为生成 null 的非终结符后面的任何内容。

A → B C
B → b
C → D E
D → d | ""
E → e

FOLLOWS(B) ← FIRST(C) = FIRST(D) = {d, ""}
          += - {""} + FOLLOWS(D) = - {""} + FIRST(E) = - {""} + {e}
FOLLOWS(B) = {d, e}

然后您可以正常填写解析表。