コンパイラとプログラミング⾔語
第8週 下向き構⽂解析/構⽂解析プログラム
2013年6⽉5⽇
⾦岡 晃
授業計画
1
第1週 (4/10)
コンパイラの概要 第2週
(4/24)
コンパイラの構成 第3週
(5/1)
プログラミング⾔語の形式的な 記述
第4週 (5/8)
字句解析の概要と⾮決定性有限 オートマトン
第5週 (5/15)
決定性有限オートマトン・字句 解析プログラム
第6週 (5/22)
中間試験 第7週
(5/29)
構⽂解析の概要/上向き構⽂解析
第8週 (6/5)
下向き構⽂解析/構⽂解析プ
ログラム 第9週
(6/12)
中間表現と意味解析 第10週
(6/19)
Java仮想マシンとその機械語 第11週
(6/26)
条件分岐⽂と繰り返し⽂の コード⽣成
第12週 (7/3)
関数呼び出しのコード⽣成 第13週
(7/10)
休講
(7/24 or 7/31)
期末試験
2013/6/5 コンパイラとプログラミング⾔語
【復習】第 7 週
構⽂解析の概要 / 上向き構⽂解析
コンパイラとプログラミング⾔語
コンパイラの論理的な構成
2013/6/5 コンパイラとプログラミング⾔語
3
プログラムソース ⽬的
プログラム
コンパイラ
字句解析 構⽂
解析 意味
解析 最適化 コード
⽣成
中間情報（中間語、名前表）
フェーズ
構⽂解析
• 字句解析が出⼒したトークンを読み込みながら、そのトークンの列 がプログラム⾔語の⽂法で許されているパターンと合うかを解析す る
プログラムソース 字句解析 トークントークン 構⽂解析
構⽂⽊
構⽂⽊
名前表
• 許されているパターンであれば、トークンの列は構⽂規則 に従って構成され、字句を葉とする構⽂⽊が⽣成される。
• 構⽂解析の結果、ソースプログラムの構造は構⽂⽊として 出⼒され、名前や数字などの情報は名前表に出⼒される。
構⽂解析法
2013/6/5 コンパイラとプログラミング⾔語
5
上向き構⽂解析法
（bottom-up parser)
下向き構⽂解析法
（top-down parser)
⼊⼒した記号列が構⽂規則の 右辺と⼀致した場合に左辺の 記号に置き換えていく
記号列として次に何が来るの かを仮定しながら構⽂解析を
進めていく a ＊ ( b + c )
名前 名前
因⼦
項 式
名前 因⼦
項 式
因⼦
項
因⼦
項
上向き 式
解析法構⽂
下向き構⽂
解析法
上向き構⽂解析法の例
a ＊ ( b + c )
名前 名前
因⼦
項 式
名前 因⼦
項 式
因⼦
項
因⼦
項 式
構⽂規則
<式> ::= <項> | <式>+<項>
<項> ::= <因⼦>| <項>＊<因⼦>
<因⼦> ::= <名前>|(<式>)
<名前> ::= a|b|c
<名前> ::= a|b|c
<因子> ::= <名前>|(<式>)
<項> ::= <因子>| <項>＊<因子>
<式> ::= <項> | <式>+<項>
<式> ::= <項> | <式>+<項>
<因子> ::= <名前>|(<式>)
<項> ::= <因子>| <項>＊<因子>
<式> ::= <項> | <式>+<項>
第 8 週
下向き構⽂解析 / 構⽂解析プログラム
コンパイラとプログラミング⾔語
7 2013/6/5 コンパイラとプログラミング⾔語
本⽇の到達⽬標と概要
• 到達⽬標
– 下向き構⽂解析の概要理解 – 下向き構⽂解析の問題点理解 – LL 構⽂解析の理解
• 概要
– 下向き構⽂解析の概要 – 下向き構⽂解析の問題点
• 左再帰性
• バックトラック – LL 構⽂解析
• LL(k) 構⽂解析
• LL(1) ⽂法
• LL(1) ⽂法の構成
構⽂解析法
2013/6/5 コンパイラとプログラミング⾔語
9
上向き構⽂解析法
（bottom-up parser)
下向き構⽂解析法
（top-down parser)
⼊⼒した記号列が構⽂規則の 右辺と⼀致した場合に左辺の 記号に置き換えていく
記号列として次に何が来るの かを仮定しながら構⽂解析を
進めていく a ＊ ( b + c )
名前 名前
因⼦
項 式
名前 因⼦
項 式
因⼦
項
因⼦
項
上向き 式
解析法構⽂
下向き構⽂
解析法
下向き構⽂解析法
下向き構⽂解析法
（top-down parser)
記号列として次に何が来るの かを仮定しながら構⽂解析を 進めていく
再帰的下向き構⽂解析
下向き構⽂解析の中で、構⽂解析のプログラムが 再帰的⼿続きで構成されたもの
下向き構⽂解析法：例
2013/6/5 コンパイラとプログラミング⾔語
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 ○
記号列を左から解析：
最左導出
解析（展開）に 失敗したら
前の状態に戻って やり直しを⾏う：
バックトラック
（後戻り）
左再帰的に記述されていると 解析が⾏えない場合がある
下向き構⽂解析の問題点（１）
2013/6/5 コンパイラとプログラミング⾔語
13
左再帰性の問題 左再帰性：
⽣成規則の左辺の記号が右辺の最 左の記号になっている
左再帰性のある構⽂規則の例
<式> ::= <項> | <式>+<項>
<項> ::= <因⼦>| <項>＊<因⼦>
<因⼦> ::= <名前>|(<式>)
<名前> ::= a|b|c
解析時に無限にループしてしまう
下向き構⽂解析の問題点（２）
効率が悪くなる バックトラック
（後戻り）
なぜ起こるか？
構⽂規則
<S> ::= a<A>bd
<A> ::= cb|c
双⽅のケースが
同じ終端記号（ここでは”c”） から始まっている
対策の1つ 括り出し：
共通の部分を別の規則で 独⽴させる
<S> ::= a<A>bd
<A> ::= c<B>
<B> ::= b|ε
“ε”は 無⼊⼒を意味
する
LL 構⽂解析
2013/6/5 コンパイラとプログラミング⾔語
15
⼊⼒された記号列の先頭（最も左）の⾮終端記号に適⽤すべき
⽣成規則を、それ以降の記号列を調べることによって⼀意に決 定することが可能となるようにする
LL： Left to right scan
Left most derivation
LL(k)構⽂解析
先読み記号を最⼤k個まで許すことを意味する
k=1 のとき、バックトラックのない下向き構⽂解析が可能。
そのとき、LL(1)構⽂解析を可能にする⽂法をLL(1)⽂法という
LL(1) ⽂法
与えられた⽂法Gに対する任意の⽣成規則
<A> ::= | |…|
に対してDirector(A, ) ∩ Director(A, ) = , ならば、⽂法GはLL(1)⽂法である。
First集合
First( ) = { | ∈ , ∗ ⇒ ⋯} ただし、 ∗ ⇒ なら ∈ First( ) Follow集合
Director集合
Follow( ) = { | ∈ , ∗ ⇒ ⋯ ⋯}
Director( , ) = { | ∈ , ∈ First または（ ∗ ⇒ かつ ∈ Follow( )）}
終端記号の集合は
LL(1) ⽂法の理解
2013/6/5 コンパイラとプログラミング⾔語
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 2013/6/5 コンパイラとプログラミング⾔語
