この文法にはどのようなパーサーが必要ですか？

Question

私は文法がLL（1）だとは思わない以外に、それを構文解析するために必要なパーザのタイプを知らないという文法を持っています。私は、ある種のバックトラックやLL（*）を持つパーサーが必要だと思っています。私は（いくつかの書き換えを必要とする場合もある）を思い付いている文法は次のとおりです。左が含まれている

abc = def g hi jk lm 
xy = aaa bbb ccc ddd eee fff jjj kkk 
foo = bar ha ha 

ゼロ以上のルール：

S: Rules 
Rules: Rule | Rule Rules 
Rule: id '=' Ids 
Ids: id | Ids id 

私は生成しようとしている言語は次のようになります識別子の後ろに等号とそれに続く1つ以上の識別子が続きます。パーサーを書くのに問題があると思う部分は、文法ではルール内のidの量は任意で、新しいルールがいつ始まるかを知る唯一の方法は、id =が見つかったときにバックトラッキングが必要なことです。

誰もこの文法とパースの最良の方法の分類を知っていますか手はパーサーで書かれていますか？

Answer 1

識別子の後に等号とそれに続く識別子の有限シーケンスが続く文法は、の正規表現です。つまり、言語の文字列はDFAまたは正規表現を使用して解析できます。ファンシーで非決定的なもの、またはLL（*）パーサーは不要です。 Γ⊂Σは識別子で起こり得るシンボルの集合である：{∈Γ}、

言語が正規であることを確認するには、イド = Uをしましょう。あなたが生成しようとしている言語は、正規表現

• で示されたID⁺ =（同上⁺）^*同上⁺

設定Γ= {a,b、...、Z}、正規表現の言語での文字列の例は次のとおりです。

• 見=私は正規言語
• にいるちょっと=それは私がで認識できることを意味DFA
• クール=あるいは正規表現

強力な解析技術を使用して、あなたの言語を解析する必要はありません。これは、正規表現やDFAを使用した解析が適切で最適なケースの1つです。

編集：

R上記の正規表現を呼び出します。R^*を解析するには、 ^*の言語を認識するDFAを生成します。これを行うには、 ^*の言語を認識するNFAをKleeneの定理から得られるアルゴリズムを用いて生成する。その後、サブセット構成を使用してNFAをDFAに変換します。結果のDFAは、すべての文字列をR^*に認識します。あなたの実装言語、必要なアクションで構築さDFAの表現を考える - たとえば、

• は
• 解析され、現在の宣言文の右側に解析された最後の識別子が最後の宣言を追加します新しい宣言文の解析を開始するために解析された最後の識別子を使用する

は、DFAの状態にエンコードすることができます。実際には、Kleeneの定理と部分集合の構築を使用することは、そのような単純な言語にとっておそらく不要です。つまり、オートマトンを実装せずに、上記の2つのアクションを持つパーサーを作成するだけです。より複雑な正規表現（例えば、プログラミング言語の語彙構造）が与えられると、変換が最良の選択肢になるでしょう。