コンパイラ（９） 情報工学科５年 担当　河田　進

ＬＲ構文解析 １．コンパイラ（構文解析譜）の状態 ○今構文解析がどこまで進んでいるか ○今どの生成規則についての解析を行っているか ２．１つの規則についての状態 ●Ａ→ｘｙｚについて考える ○解析を始める前　Ａ→・ｘｙｚ（ＬＲ（０）項と呼ぶ） ○ｘの受理が終わり，これからｙを受理しようとしている状 態　Ａ→ｘ・ｙｚ ○ｘｙの受理が終わり，これからｚを受理しようとしている 状態　Ａ→ｘｙ・ｚ ○ｘｙｚの受理が終わり（ハンドルｘｙｚが見つかった）Ａ に還元を行う状態　Ａ→ｘｙｚ・＃ 　（＃は還元を行う印。＃という記号があるわけではない）

ＬＲ構文解析 ３．ｘｙｚの記号の種類 ●Ａ→ａＢｂ Ｂ→ｃ について考える ○解析を始める前 Ａ→・ａＢｃ ●Ａ→ａＢｂ　Ｂ→ｃ　について考える ○解析を始める前　Ａ→・ａＢｃ 次の動作はａの受理：入力残の先頭とＶｔであるａが一致 するかどうか調べる ○ａの受理が終わり，ＶｎであるＢから生成可能な記号列を 調べる開始状態　Ａ→ａ・Ｂｂ　且つ　Ｂ→・ｃ ○ｃの受理が終わった状態　Ｂ→ｃ・＃ ハンドルｃが見つかったのでｃをＢに還元する その結果　Ａ→ａＢ・ｂ　を含む状態へ移る ○ｂの受理が終わった状態　Ａ→ａＢｂ・＃ ハンドルａＢｂが見つかったのでａＢｂをＡに還元し，何 処かにあるＸ→α・Ａβを含む状態からＸ→αＡ・βを含 む状態へ移る

ＬＲ構文解析 ４．生成規則から状態を求める Ｐ＝｛ Ｓ’→Ｓ┤ Ｓ→Ｓａ｜ＡＢｃ Ａ→ｂＡｃ｜ｄ Ｂ→ａＢ｜ε ｝ Ｐ＝｛　Ｓ’→Ｓ┤　Ｓ→Ｓａ｜ＡＢｃ　Ａ→ｂＡｃ｜ｄ 　　　　Ｂ→ａＢ｜ε　｝ ○１つの状態は複数のＬＲ（０）項の集合 構文解析開始状態（Ｉ０） 　　　　　　　（０）　　　（１）　　　（２） Ｉ０＝｛　Ｓ’→・Ｓ┤　Ｓ→・Ｓａ　Ｓ→・ＡＢｃ 　　（３）　　　（４） Ａ→・ｂＡｃ　Ａ→ ・ｄ　｝ （０）の・Ｓから（１）（２）であることが分かる （１）の・Ｓから再度（１）（２）（増えない） （２）の・Ａから（３）（４）であることが分かる

ＬＲ構文解析 ４．状態Ｉ０から分かること Ｉ０＝｛ Ｓ’→・Ｓ┤ Ｓ→・Ｓａ Ｓ→・ＡＢｃ Ａ→・ｂＡｃ Ａ→ ・ｄ ｝ Ｉ０＝｛　Ｓ’→・Ｓ┤　Ｓ→・Ｓａ　Ｓ→・ＡＢｃ Ａ→・ｂＡｃ　Ａ→ ・ｄ　｝ ○最初に受理可能なＶｔはｂまたはｄ ○ＬＲ系構文解析は上向き構文解析の１つ（ハンドルを 見つけてＶｎに還元していく） ○ＬＬ（１）のように次に受理すべきＶｔが何か類推で きる

ＬＲ構文解析 ５．状態Ｉ０から別の状態への移行 Ｉ０＝｛ Ｓ’→・Ｓ┤ Ｓ→・Ｓａ Ｓ→・ＡＢｃ Ａ→・ｂＡｃ Ａ→ ・ｄ ｝ Ｉ０＝｛　Ｓ’→・Ｓ┤　Ｓ→・Ｓａ　Ｓ→・ＡＢｃ Ａ→・ｂＡｃ　Ａ→ ・ｄ　｝ ○Ｉ０の・の後ろにあるＶｔを受理，または還元によるＶｎの生成によ り他の状態へ移る（ＬＲ（０）項の・を１つ右へ移動） 　　Ｓ Ｉ０－＞Ｉ１＝｛　Ｓ’→Ｓ・┤　Ｓ→Ｓ・ａ　｝ 　　◎・の後ろにＶｎが無いためこの２個だけ 　　◎次は┤またはａを受理（入力残の先頭記号で決まる） 　　Ａ Ｉ０－＞Ｉ２＝｛　Ｓ→Ａ・Ｂｃ Ｂ→・ａＢ　Ｂ→ ε・＃　｝ ◎Ｂ→・εというＬＲ（０）項は存在しない。何も無いものを受理 する前ということは考えられない。 ◎次はａを受理するか，ハンドルεをＢに還元するかを決めなけれ ばならない（不都合な状態）

ＬＲ構文解析 ５．状態Ｉ０から別の状態への移行 Ｉ０＝｛ Ｓ’→・Ｓ┤ Ｓ→・Ｓａ Ｓ→・ＡＢｃ Ａ→・ｂＡｃ Ａ→ ・ｄ ｝ ｂ Ｉ０＝｛　Ｓ’→・Ｓ┤　Ｓ→・Ｓａ　Ｓ→・ＡＢｃ Ａ→・ｂＡｃ　Ａ→ ・ｄ　｝ 　　ｂ Ｉ０－＞Ｉ３＝｛　Ａ→ｂ・Ａｃ Ａ→・ｂＡｃ　Ａ→ ・ｄ｝ ◎次はｂまたはｄを受理（入力残の先頭記号で決まる） 　　ｄ Ｉ０－＞Ｉ４＝｛　Ａ→ ｄ・＃　｝ ◎次はｄをＡに還元し，Ｉ４へ遷移する前のＩ０へ戻り 　　Ａ Ｉ０－＞Ｉ２によりＩ２へ移る

ＬＲ構文解析 ６．状態の集合全体 Ｐ＝｛ Ｓ’→Ｓ┤ Ｓ→Ｓａ｜ＡＢｃ Ａ→ｂＡｃ｜ｄ Ｂ→ａＢ｜ε ｝ Ｐ＝｛　Ｓ’→Ｓ┤　Ｓ→Ｓａ｜ＡＢｃ　Ａ→ｂＡｃ｜ｄ　Ｂ→ａＢ｜ε　｝ I0＝｛　Ｓ’→・Ｓ┤　Ｓ→・Ｓａ　Ｓ→・ＡＢｃ　Ａ→・ｂＡｃ　Ａ→ ・ｄ　｝ 　 S　　　　　　　　　　　　　　　　　 A I0->I1＝｛Ｓ’→Ｓ・┤　Ｓ→Ｓ・ａ｝I0->I2＝｛Ｓ→Ａ・Ｂｃ　Ｂ→・ａＢ　Ｂ→ ε・＃｝ 　ｂ　　　　　　　　　　　　　　　　　　　　　　　 　ｄ I0->I3＝｛Ａ→ｂ・Ａｃ　Ａ→・ｂＡｃ　Ａ→ ・ｄ｝　I0->I4＝｛Ａ→ ｄ・＃｝ 　 ┤　　　　　　　　　　　 　ａ　　　　　　　　　　　　Ｂ I1->I5＝｛Ｓ’→Ｓ┤・＃｝　I1->I6＝｛Ｓ→Ｓａ・＃｝　I2->I7＝｛Ｓ→ＡＢ・ｃ｝ 　ａ　　　　　　　　　　　　　　　　　　　　　　 　Ａ I2->I8＝｛Ｂ→ａ・Ｂ　Ｂ→・ａＢ　Ｂ→ ε・＃｝　I3->I9＝｛Ａ→ｂＡ・ｃ｝ 　ｂ　　　ｄ　　　ｃ　　　　　　　　　　　　　　B I3->I3　I3->I4　I7->I10＝｛Ｓ→ＡＢｃ・＃｝　I8->I11＝｛Ｂ→ａＢ・＃｝ 　ａ　　　ｃ I8->I8　I9->I12＝｛Ａ→ｂＡｃ・＃｝

ＬＲ構文解析 ７．不都合な状態 ○１つの状態にＸ→αａ・ｂβ（次にｂを受理する遷移） Ｙ→γａ・＃（γａをＹに還元しＩjへ移動する） 理由 Ｉi∋｛　Ｚ→δ・Ｙη　Ｙ→・γａ　｝ 　Ｙ Ii－＞Ij ∋｛　Ｚ→δＹ・η　｝ どちらの動作を行うかを決めなければならないので不都合 ●１つの状態に複数の遷移が存在しても，入力残の先頭記号でどちらの 遷移をするかが決まるので不都合ではない ○１つの状態に複数の還元が存在する場合 　どちらの還元を行うか決めなければならないので不都合 ○不都合な状態において動作を決定する方法の違いにより解析法の名前 が異なる（ＳＬＲ（１），ＬＡＬＲ（１）､ＬＲ（１）） ●（１）の１は手掛かりとして，これからに受理可能な記号列の長さを １（つまり次に受理可能なＶｔ）とすることを意味している

ＬＲ構文解析 状態集合練習 Ｐ＝｛　Ｓ’→Ｓ┤　Ｓ→ＡｂＳ｜ａＢｃ　Ａ→ｃＡＢ｜ｂ｜ε　Ｂ→Ｂｄ｜ｂ　｝