言語がLL（1）LR（0）SLR（1）かどうかを判断する方法

StackOverflow https://stackoverflow.com/questions/475949

質問

文法がLL（1）、LR（0）、SLR（1）であるかどうかを、複雑な分析を行わずに文法を調べるだけで簡単に判断できる方法はありますか？

たとえば：BNF GrammarがLL（1）かどうかを判断するには、FirstセットとFollowセットを計算する必要があります-これは場合によっては時間がかかることがあります。

これをもっと速くする方法を知っている人はいますか？ ご協力いただければ幸いです！

役に立ちましたか？

解決

まず、ちょっとした工夫。 言語が文法を検査してLL（1）であるかどうかを判断することはできません。文法自体についてのみステートメントを作成できます。 LL（1）文法が存在する言語に対して非LL（1）文法を書くことは完全に可能です。

これで邪魔になりません：

  • 文法のパーサーを記述し、プログラムに最初に計算させ、セットやその他のプロパティをフォローさせることができます。結局のところ、それはBNF文法の大きな利点であり、機械が理解できるものです。

  • 文法を調べて、さまざまな文法タイプの制約の違反を探します。たとえば、LL（1）は左再帰ではなく右再帰を許可します。したがって、左再帰を含む文法はLL（1）ではありません。 （他の文法プロパティについては、定義にかなりの時間を費やす必要があります。今は頭の上のものを思い出せないからです：）。

他のヒント

主な質問への回答：非常に単純な文法の場合、FIRSTおよびFOLLOWセットを構築せずにLL（1）かどうかを判断できる場合があります。たとえば、

  

A <！>＃8594; A + A | a

     

はLL（1）ではありませんが、

     

A <！>＃8594; | b

is。

ただし、それよりも複雑になった場合は、分析を行う必要があります。

  

A <！>＃8594; B | a
  B <！>＃8594; A + A

これはLL（1）ではありませんが、すぐにはわかりません

算術の文法規則はすぐに非常に複雑になります：

  

expr <！>＃8594;用語{'+'用語}
  term <！>＃8594; factor {'*' factor}
  ファクター<！>＃8594;番号| '（' expr '）'

この文法は乗算と加算のみを処理し、すでに文法がLL（1）であるかどうかはすぐにはわかりません。文法に目を通すことで評価することはまだ可能ですが、文法が成長するにつれて実行可能性が低くなります。プログラミング言語全体の文法を定義する場合、ほぼ確実に複雑な分析が必要になります。

とはいえ、文法がLL（1）ではないという明白な兆候がいくつかあります<！>＃8212; A <！>＃8594;上記のA + A <！>＃8212;文法でこれらのいずれかを見つけることができれば、再帰降下パーサーを作成している場合は書き直す必要があることがわかります。しかし、文法が LL（1）であることを確認する近道はありません。

1つの側面、<！> quot;は言語/文法があいまいです<！> quot ;、は 通信を投稿および停止の問題。

本からのストレート<！> quot;コンパイラ：原則、テクニック、<！> amp;ツール<！> quot;アホ他

223ページ：

A-<！> gt;の場合、文法GはLL（1） if if and only if です。 アルファ | beta はGの2つの異なる生成物であり、次の条件が成立します。

  1. 端末がない場合<！> quot; a <！> quot; alpha と beta の両方で、<！> quot; a <！> quot;
    2. で始まる文字列を派生させます。
  2. 最大で alpha と beta のいずれかが空の文字列を派生できます
  3. beta がゼロ以上の遷移を介して空の遷移に到達できる場合、 alpha はFOLLOW（A）の終端で始まる文字列を導き出しません。同様に、0個以上の遷移を介して alpha が空の遷移に到達できる場合、 beta はFOLLOW（A）
    4. の端末で始まる文字列を導出しません

本質的に、これは文法がペアワイズ素性テストに合格し、また左再帰を含まないことを検証する問題です。または、より簡潔に、左再帰またはあいまいな文法GはLL（1）にできません。

文法が曖昧かどうかを確認します。そうである場合、あいまいな文法はLL（1）ではないため、文法はLL（1）ではありません。

ya ll（1）文法のショートカットがあります

1）if A-<！> gt; B1 | B2 | ....... | Bn     次に、first（B1）intersection first（B2）intersection .first（Bn）= empty set ll（1）grammarです

2）A-<！> gt; B1 | epsilonの場合      B1交差点のフォロー（A）は空のセットです

3）Gがすべての非端末が1つの生成のみを導出するような文法である場合、その文法はLL（1）

p0 S' → E
p1 E → id
p2 E → id ( E )
p3 E → E + id
  • LR（0）DFA、EのFOLLOWセット、SLRアクション/ gotoテーブルを構築します。
  • これはLR（0）文法ですか？答えを証明してください。
  • SLRテーブルを使用して、LRパーサー解析の手順（シフト、リダクション、アクセプト）を表示します：
    id ( id + id )
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top