5

我在维基百科上找到了以下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) 语法吗？
  • 如果没有，如何将其变成一个（可能？）？
4

2 回答 2

12

引用的 Wikipedia 摘录不是 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。但更重要的是，它并不表示|and,运算符的关联性或优先级。（语义上，这些运算符没有定义的关联性，但语法仍应指定一个；否则，不可能明确地创建解析树。两个运算符之间的优先级在语义上很重要。）

一套更好的规则是：

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为空。我把它省略了，因为它通常不需要。

于 2013-11-24T19:35:31.123 回答
2

简而言之，不，您的语法不是LL(1)。

第一个原因是rhs你已经发现的左递归。我假设，您编写了一个递归下降解析器（或其他基于 LL(1) 语法的东西）。这种解析器无法处理左递归规则，因为它们会导致所谓的 FIRST/FIRST 冲突的特殊情况（参见1）。

要解决此问题并回答问题的第二部分，您可以将语法左分解并替换左递归，如2所示。

于 2013-11-24T19:04:30.570 回答