コンパイラとプログラミング言語
第8週 下向き構文解析/構文解析プログラム
2014年5月28日 金岡 晃
授業計画
1
第1週 (4/9)
コンパイラの概要 第2週
(4/16)
コンパイラの構成 第3週
(4/23)
プログラミング言語の形式的な 記述
第4週 (4/30)
プログラミング言語の形式的な 記述
第5週 (5/7)
字句解析の概要と非決定性有限 オートマトン、決定性有限オー トマトン・字句解析プログラム 第6週
(5/14)
中間試験 第7週
(5/21)
構文解析の概要/上向き構文解析
第8週 (5/28)
下向き構文解析/構文解析プ ログラム
第9週 (6/4)
中間表現と意味解析 第10週
(6/11)
Java仮想マシンとその機械語 第11週
(6/18)
条件分岐文と繰り返し文の コード生成
第12週 (6/25)
関数呼び出しのコード生成 第13週
(7/2)
休講 第14週
(7/9)
休講
(7/23- 8/5)
期末試験
2014/5/28 コンパイラとプログラミング言語
【復習】第 7 週
構文解析の概要 / 上向き構文解析
コンパイラとプログラミング言語
コンパイラの論理的な構成
2014/5/28 コンパイラとプログラミング言語
3
ソース
プログラム 目的
プログラム コンパイラ
字句 解析
構文 解析
意味
解析 最適化 コード
生成
中間情報（中間語、名前表）
フェーズ
構文解析
• 字句解析が出力したトークンを読み込みながら、そのトークンの列 がプログラム言語の文法で許されているパターンと合うかを解析す る
ソース
プログラム 字句解析 トークン 構文解析
構文木
名前表
• 許されているパターンであれば、トークンの列は構文規則 に従って構成され、字句を葉とする構文木が生成される。
• 構文解析の結果、ソースプログラムの構造は構文木として 出力され、名前や数字などの情報は名前表に出力される。
構文解析法
2014/5/28 コンパイラとプログラミング言語
5
上向き構文解析法
（bottom-up parser)
下向き構文解析法
（top-down parser)
入力した記号列が構文規則の 右辺と一致した場合に左辺の 記号に置き換えていく
記号列として次に何が来るの かを仮定しながら構文解析を
進めていく a ＊ ( b + c )
名前 名前
因子 項 式
名前 因子 項 式
因子 項
因子 項
上向き 式
構文 解析法
下向き 構文 解析法
上向き構文解析法の例
a ＊ ( b + c )
名前 名前
因子 項 式
名前 因子 項 式
因子 項
因子 項
式
構文規則
<式> ::= <項> | <式>+<項>
<項> ::= <因子>| <項>＊<因子>
<因子> ::= <名前>|(<式>)
<名前> ::= a|b|c
<名前> ::= a|b|c
<因子> ::= <名前>|(<式>)
<項> ::= <因子>| <項>＊<因子>
<式> ::= <項> | <式>+<項>
<式> ::= <項> | <式>+<項>
<因子> ::= <名前>|(<式>)
<項> ::= <因子>| <項>＊<因子>
<式> ::= <項> | <式>+<項>
第 8 週
下向き構文解析 / 構文解析プログラム
コンパイラとプログラミング言語
7 2014/5/28 コンパイラとプログラミング言語
本日の到達目標と概要
• 到達目標
– 下向き構文解析の概要理解 – 下向き構文解析の問題点理解 – LL 構文解析の理解
• 概要
– 下向き構文解析の概要 – 下向き構文解析の問題点
• 左再帰性
• バックトラック – LL 構文解析
• LL(k) 構文解析
• LL(1) 文法
• LL(1) 文法の構成
構文解析法
2014/5/28 コンパイラとプログラミング言語
9
上向き構文解析法
（bottom-up parser)
下向き構文解析法
（top-down parser)
入力した記号列が構文規則の 右辺と一致した場合に左辺の 記号に置き換えていく
記号列として次に何が来るの かを仮定しながら構文解析を
進めていく a ＊ ( b + c )
名前 名前
因子 項 式
名前 因子 項 式
因子 項
因子 項
上向き 式
構文 解析法
下向き 構文 解析法
下向き構文解析法
下向き構文解析法
（top-down parser)
記号列として次に何が来るの かを仮定しながら構文解析を 進めていく
再帰的下向き構文解析
下向き構文解析の中で、構文解析のプログラムが 再帰的手続きで構成されたもの
下向き構文解析法：例
2014/5/28 コンパイラとプログラミング言語
11
構文規則
<S> ::= a<A>bd
<A> ::= cb|c
入力
acbd
入力記号 適用対象文法 比較対象 解析結果 acbd <S> ::= a<A>bd
acbd a<A>bd ○
cbd <A> ::= cb|c
cbd cb ○
d <S> ::= a<A>bd a<A>bd × cbd <A> ::= cb|c
cbd c ○
bd <S> ::= a<A>bd
bd bd ○
解析手順
下向き構文解析：ポイント
入力記号 適用対象文法 比較対象 解析結果 acbd <S> ::= a<A>bd
acbd a<A>bd ○
cbd <A> ::= cb|c
cbd cb ○
d <S> ::= a<A>bd a<A>bd × cbd <A> ::= cb|c
cbd c ○
bd <S> ::= a<A>bd
bd bd ○
記号列を
左から解析：
最左導出
解析（展開）に 失敗したら
前の状態に戻って やり直しを行う：
バックトラック
（後戻り）
左再帰的に記述されていると 解析が行えない場合がある
下向き構文解析の問題点（１）
2014/5/28 コンパイラとプログラミング言語
13
左再帰性の問題 左再帰性：
生成規則の左辺の記号が右辺の最 左の記号になっている
左再帰性のある構文規則の例
<式> ::= <項> | <式>+<項>
<項> ::= <因子>| <項>＊<因子>
<因子> ::= <名前>|(<式>)
<名前> ::= a|b|c
解析時に無限にループしてしまう
下向き構文解析の問題点（２）
効率が悪くなる バックトラック
（後戻り）
なぜ起こるか？
構文規則
<S> ::= a<A>bd
<A> ::= cb|c
双方のケースが
同じ終端記号（ここでは”c”） から始まっている
対策の1つ 括り出し：
共通の部分を別の規則で 独立させる
<S> ::= a<A>bd
<A> ::= c<B>
<B> ::= b|ε
“ε”は 無入力 を意味
する
LL 構文解析
2014/5/28 コンパイラとプログラミング言語
15
入力された記号列の先頭（最も左）の非終端記号に適用すべき 生成規則を、それ以降の記号列を調べることによって一意に決 定することが可能となるようにする
LL：
Left to right scan
Left most derivation
LL(k)構文解析
先読み記号を最大k個まで許すことを意味する
k=1 のとき、バックトラックのない下向き構文解析が可能。
そのとき、LL(1)構文解析を可能にする文法をLL(1)文法という
LL(1) 文法
与えられた文法Gに対する任意の生成規則
<A> ::= 𝑎1|𝑎2|…|𝑎𝑛 に対して
Director(A, 𝑎𝑖) ∩ Director(A, 𝑎𝑗) = 𝜙 , 𝑖 ≠ 𝑗 ならば、文法GはLL(1)文法である。
First集合
First(𝛼) = {𝑎|𝑎 ∈ 𝑇, 𝛼∗ ⇒ 𝑎 ⋯} ただし、𝛼∗ ⇒ 𝜖 なら 𝜖 ∈ First(𝛼) Follow集合
Director集合
Follow(𝐴) = {𝑎|𝑎 ∈ 𝑇, 𝑆∗ ⇒ ⋯ 𝐴𝑎 ⋯}
Director(𝐴, 𝛼) = {𝑎|𝑎 ∈ 𝑇, 𝑎 ∈ First(𝛼) または（𝛼∗ ⇒ 𝜖 かつ 𝜖 ∈ Follow(𝐴)）}
𝑇は
終端記号の集合
LL(1) 文法の理解
2014/5/28 コンパイラとプログラミング言語
17
First集合
First(𝛼) = {𝑎|𝑎 ∈ 𝑇, 𝛼∗ ⇒ 𝑎 ⋯} ただし、𝛼∗ ⇒ 𝜖 なら 𝜖 ∈ First(𝛼) 記号列 𝛼 の先頭に現れることができる終端記号の集合
Follow集合
Follow(𝐴) = {𝑎|𝑎 ∈ 𝑇, 𝑆∗ ⇒ ⋯ 𝐴𝑎 ⋯}
非終端記号𝐴 の直後に現れることができる終端記号の集合 Director集合
Director(𝐴, 𝛼) = {𝑎|𝑎 ∈ 𝑇, 𝑎 ∈ First(𝛼) または（𝛼∗ ⇒ 𝜖 かつ 𝑎 ∈ Follow(𝐴)）}
非終端記号𝐴 を記号列 𝛼に展開するかどうかを決める集合
First(𝛼)と、 𝛼が無入力ならFollow(𝐴) を合わせた終端記号の集合
LL(1) 文法かチェックしてみよう
<式> ::= <項> | <式>+<項>
<項> ::= <因子>| <項>＊<因子>
<因子> ::= <名前>|(<式>)
<名前> ::= a|b|c
<S> ::= a<A>bd
<A> ::= cb|c
<S> ::= a<A>bd
<A> ::= c<B>
<B> ::= b|ε
LL(1)文法でない
LL(1)文法でない
LL(1)文法でない
<S> ::= a<A>d
<A> ::= b<B>
<B> ::= c|ε LL(1)文法である
本日の到達目標と概要
• 到達目標
– 下向き構文解析の概要理解 – 下向き構文解析の問題点理解 – LL 構文解析の理解
• 概要
– 下向き構文解析の概要 – 下向き構文解析の問題点
• 左再帰性
• バックトラック – LL 構文解析
• LL(k) 構文解析
• LL(1) 文法
• LL(1) 文法の構成
19 2014/5/28 コンパイラとプログラミング言語
