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)文法ですか？
  • そうでない場合、それを1つに変える方法（可能ですか？）？
4

2 に答える 2

12

引用されたウィキペディアの抜粋は、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,演算子の優先順位を示すものではありません。(意味的には、これらの演算子には結合性が定義されていませんが、構文で結合性を指定する必要があります。そうしないと、明確に解析ツリーを作成することはできません。2 つの演算子間の優先順位は意味的に重要です。)

より良いルールのセットは次のようになります。

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

これはまだ単純化しすぎていますが、多数のユースケースをカバーしています。あいまいでも左再帰でもありません。[3]

ノート

  1. ただし、コメントで指定された構文上の制約を CFG に変換するのは簡単ではない場合があります。たとえば、EBNF の ISO 標準 EBNF は、非終端の「構文上の例外」を次のように定義しています。上記のテキストの意図は、例外を通常の言語に制限することです。2 つの文脈自由言語のセットの違いは必ずしも文脈自由であるとは限らないが、文脈自由言語と通常の言語の違いは文脈自由であることが証明されているため、これは重要です。皮肉なことに、この制限を記述する「特別なシーケンス」は、定義に依存するため、文脈自由文法として表現できません。

    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 番目の部分に答えるには、2 に示すように、文法を左因数分解し、左再帰を置き換えることができます。

于 2013-11-24T19:04:30.570 に答える