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

Question

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

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

因此，作为一个子练习，我正在根据我对 CSS 的了解来构建语法。但是我被困在无法在 LL(1) 中转换的制作上:

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

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

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

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

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

书上讲了这个问题，但是在它的例子中，分号是必须的，所以规则可以这样修改:

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();
        }
    }
}

我是对的吗？