如何将生产转换为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; }
...

问题在于可选的";" 最后,因为它与{";",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();
        }
    }
}

我是我没错吧？