LL(1)文法

質問

Ｓ→ｃＴ
Ｔ→ｃＴｄ｜ε
で表せる文法はＬＬ（１）文法なんでしょうか?
分かる方、ご教授願います。

回答No.1

pureh · ベストアンサー

結論から言えば、ＬＬ（１）文法です。

ＦＩＲＳＴ，ＦＯＬＬＯＷ，ＤＩＲＥＣＴＯＲの定義、および、
これらを使ったＬＬ（１）文法の定義は、既知のものとして話を進めます。

ＦＩＲＳＴ（Ｓ）＝｛ｃ｝
ＦＩＲＳＴ（Ｔ）＝｛ｃ，ε ｝

ＦＯＬＬＯＷ（Ｓ）＝｛＄｝
ＦＯＬＬＯＷ（Ｔ）＝ＦＯＬＬＯＷ（Ｓ）∪｛ｄ｝＝｛＄，ｄ｝

１）ＤＩＲＥＣＴＯＲ（Ｓ，ｃＴ）＝ＦＩＲＳＴ（ｃＴ）－｛ε｝＝｛ｃ｝
２）ＤＩＲＥＣＴＯＲ（Ｔ，ｃＴｄ）＝ＦＩＲＳＴ（ｃＴｄ）－｛ε｝＝｛ｃ｝
３）ＤＩＲＥＣＴＯＲ（Ｔ，ε ）＝ＦＯＬＬＯＷ（Ｔ）＝｛＄，ｄ｝

２∩３＝φ　なので、ＬＬ（１）文法である。

　注　記号＄は、文末（あるいは、入力末尾）を表す。

私が参考にした文献は、
　岩波講座　ソフトウェア科学　ｖｏｌ．５
『プログラミング言語処理系』，佐々正孝　著
ですが、他にも良書はたくさん有ると思います。

お礼

回答どうもありがとうございました。
お礼が遅れて済みませんでした。