Ebnf – 这是 LL(1) 语法吗？

我发现了以下内容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 时失败，它再次读取自身，再次读取自身，oh， 你说对了...

• 它是 LL(1) 语法吗？
• 如果不是，如何将其变成一个（可能？）？

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

一般来说，条款LL(k) and 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。但更重要的是，它并不表明结合性或优先级| and ,运营商。 （从语义上讲，这些运算符没有定义的结合性，但语法仍应指定结合性；否则，不可能明确地创建解析树。两个运算符之间的优先级在语义上很重要。）

一套更好的规则是：

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

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

Notes

1. 不过，注释中指定的语法约束可能不容易转化为 CFG。例如，ISO标准EBNF对EBNF定义了非终结符“语法异常”，如下：
   
   syntactic exception =
   ? a syntactic-factor that could be replaced
     by a syntactic-factor containing no
     meta-identifiers
   ?

   
   上述文本的目的是将异常限制为常规语言。这很重要，因为两种上下文无关语言之间的设定差异不一定是上下文无关的，而上下文无关语言和常规语言之间的差异可以证明是上下文无关的。讽刺的是，描述这种限制的“特殊序列”不能表达为上下文无关语法，因为它依赖于定义元标识符。 （如果它说“一个不包含元标识符的语法因素”，那么在不诉诸特殊序列的情况下就很容易编写，但显然这不是意图。）

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

3. 正式的 EBNF 语法允许primary为空。我省略了它，因为通常不需要它。