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时它失败了,rhs再次自我读取,它再次读取自己,哦,你得到它...

• 它是LL(1)语法吗？
• 如果没有,如何把它变成一个(可能吗？)？

Answer 1

引用的维基百科摘录不是EBNF的正确EBNF语法.它也不是可左派的:事实上,它是模棱两可的,所以它根本没有明确的可解析性.

一般来说,术语LL(k)和LR(k)(以及许多其他条款)适用于上下文无关文法(CFGS) (和推而广之,那些语法生成的语言).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]

笔记

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

   
   

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

3. 正式的EBNF语法允许primary为空.我把它留了出去,因为通常不需要它.