parsing - Ebnf – 这是 LL(1) 文法吗？

Question

我找到了以下 EBNF在维基百科上，描述 EBNF:

letter = "A" | "B" | "C" | "D" | "E" | "F" | "G"
   | "H" | "I" | "J" | "K" | "L" | "M" | "N"
   | "O" | "P" | "Q" | "R" | "S" | "T" | "U"
   | "V" | "W" | "X" | "Y" | "Z" ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
symbol = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">"
   | "'" | '"' | "=" | "|" | "." | "," | ";" ;
character = letter | digit | symbol | "_" ;

identifier = letter , { letter | digit | "_" } ;
terminal = "'" , character , { character } , "'" 
     | '"' , character , { character } , '"' ;

lhs = identifier ;
rhs = identifier
 | terminal
 | "[" , rhs , "]"
 | "{" , rhs , "}"
 | "(" , rhs , ")"
 | rhs , "|" , rhs
 | rhs , "," , rhs ;

rule = lhs , "=" , rhs , ";" ;
grammar = { rule } ;

现在，由于我对解析器和语法的了解有限，我不知道这是否是 LL(1) 语法。我试图为它编写一个解析器，但是在尝试读取 rhs 时失败了，它再次读取自身，再次读取自身，哦，你明白了......

它是 LL(1) 语法吗？

如果没有，如何将其变成一个(可能？)？

Answer 1

引用的维基百科摘录不是 EBNF 的正确 EBNF 语法。它也不是左可解析的:实际上，它是不明确的，所以它根本不是可以明确解析的。

一般来说，条款LL(k)和 LR(k) (以及许多其他此类条款)适用于 上下文无关语法 (CFG) (以及，通过扩展，由这些语法生成的语言)。 EBNF 不是描述 CFG 的形式主义。它被设计为一种描述上下文无关语言的形式主义，因此应该可以从给定的 EBNF 语法创建一个 CFG(但请参阅注 1)，但 EBNF 语法规则和单个语法规则之间没有直接对应关系在 CFG 中生产。

也就是说，您通常可以通过使用一些标准转换来直接创建 CFG。例如:

{ ... }

可以用生成的非终结符 M'' 替换，并添加以下产生式:( ε 是空字符串)

M'  → ...
M'' → ε
M'' → M' M''

上面的变换没有引入左递归，所以不会人为地把原文法变成非LL(1)。

引用语法中最重要的错误[注2]是歧义EBNF规则:

rhs = identifier
    | terminal
    | "[" , rhs , "]"
    | "{" , rhs , "}"
    | "(" , rhs , ")"
    | rhs , "|" , rhs
    | rhs , "," , rhs
    ;

它也是左递归的，因此它不会对应于 LL(1) CFG。但更重要的是，它不表示 | 的结合性或优先级。和 ,运营商。 (在语义上，这些运算符没有定义的结合性，但语法仍应指定一个；否则，就不可能明确创建解析树。两个运算符之间的优先级在语义上很重要。)

一套更好的规则是:

primary = identifier
        | terminal
        | "[" , rhs , "]"
        | "{" , rhs , "}"
        | "(" , rhs , ")"
        ;
factor  = primary , { "|" , primary } ;
rhs     = factor ,  { "," , factor } ;

这仍然过于简单化，但它涵盖了大量用例。它既不模糊也不左递归。 [3]

备注

但是，注释中指定的语法约束可能不容易转换为 CFG。例如，EBNF 的 ISO 标准 EBNF 将非终结符“语法异常”定义如下:syntactic exception =
   ? a syntactic-factor that could be replaced
     by a syntactic-factor containing no
     meta-identifiers
   ?
上述文本的意图是将异常(exception)限制为常规语言。这很重要，因为两种上下文无关语言之间的集合差异不一定是上下文无关的，而上下文无关语言和常规语言之间的差异可以证明是上下文无关的。具有讽刺意味的是，描述此限制的“特殊序列”不能表示为上下文无关文法，因为它取决于元标识符的定义。 (如果它说“一个不包含元标识符的句法因素”，那么无需诉诸特殊序列就可以轻松编写，但显然这不是本意。)

维基百科的摘录还有一个重要的错误。它将两种类型的带引号的字符串定义为具有相同的主体，但这是不正确的；双引号字符串不能包含双引号字符，单引号字符串不能包含单引号字符。所以使用标识符character在这两个定义中都是不正确的。

正式的 EBNF 文法允许 primary为空。我忽略了它，因为通常不需要它。