言語プロセッサ

言語プロセッサ
ー第9回目ー
構文解析(続き)
今日の内容
• 構文解析
– LL(1)文法(復習)
– First集合(復習)
– Follow集合(今日のポイントの1つ)
– 構文解析表による構文解析法
– 予測的構文解析のモデル
– 構文解析表の作り方
– 動作 など
LL(1)文法
確認事項
• LL(1)文法のイメージ:
A → α|β
という規則で、αかβのどちらの書換えを選ぶ
かを決めるとき、入力の先頭記号1個を見る
ことにより、バックトラックが起きないような選
択が可能な文法。
つまり、適応するべき文法規則を、1文字先
読みすれば決定できるということ。
形式文法(復習)
確認事項
文法 G=( V, N, P, S ),
ただし、
– V: 終端記号の集合(語彙)
– N: 非終端記号の集合(構文構造記述用語集)
– P: 書換え規則の集合
– S: 開始記号
LL(1)文法の条件
1. 文法への制限
•
•
左再帰性の除去
括りだし(factoring)
2. 構文解析方法
•
•
•
Top down
再帰呼び出し
1文字先読み
確認事項
文字先読み十分性の条件は?
• First集合とFollow集合を用いて作成される
構文解析表において,表内のどのセルにも動
作が多重に定義されていないこと.
First集合
【定義】
First(α)={a | a ∈ V, α=*=>a… }
ただし、α=*=>εならば、ε∈First(α)
First集合
【First集合を求めるアルゴリズム】
以下を、どのFirst集合にも新たに追加するも
のがなくなるまで繰り返す。
1. First(ε)={ε}
2. First(aα)={a} if a∈V
(Vは終端記号の集合)
3. if( First(Y) /∋ ε)
Yは空文字列にならない。
First(Yα)= First(Y)
else
First(Yα)= (First(Y) ー {ε})∪ First(α)
4. if(X→α) First(X)= First(X) ∪First(α)
Follow集合
【定義】
Follow(X)={a | a ∈ V, S=*=>…Xa… }
Follow集合
【Follow集合を求めるアルゴリズム】
以下を、どのFollow集合にも新たに追加す
るものがなくなるまで繰り返す。
1. Follow(S)に$を加える。
2. 規則 A → αBβ (B∈N) に対して、
(ア)First(β)をFollow(B)に加える。
ただし、ε∈First(β) のときはεは加えない。
(イ)ε∈First(β)またはβ=εならば、
Follow(A)をFollow(B)に加える。
First集合とFollow集合
【定義】
1. First(α)={a | a ∈ V, α=*=>a… }
ただし、α=*=>εならば、ε∈First(α)
2. Follow(X)={a | a ∈V, S =*=> …Xa… }
First集合とFollow集合
【例】
文法G=(V,N,E,P)
P={
E→TE’,
E’ →+TE’ | ε
T→FT’
T’ →*FT’ | ε
F→(E) | i }
教科書p.86より
•
•
•
•
•
•
First(E) = First(T) = First(F) = { (, i }
First(E’) = { +, ε}
First(T’) = { *, ε}
Follow(E) = Follow(E’) = { ), $}
Follow(T) = Follow(T’) = { +, ), $}
Follow(F) = { +, *, ), $}
構文解析表による構文解析法
• 予測的構文解析のモデル
• 構文解析表の作り方
• 構文解析のアルゴリズム
予測的構文解析のモデル
入力
a+b$
X
Y
Z
$
スタック
プログラム
出力
構文解析表
構文解析表の作り方
• 入力: 文法G
• 出力: 構文解析表M
• 手順: (次のページ参照)
構文解析表作成手順
1. 文法の各規則A→αに対して、ステップ2と3を
行う。
2. 各終端記号a∈First(α)に対して、M[A, a]に
A→αを記入する。
3. ε∈First(α)ならば、各終端記号∈Follow(A)に対
して、M[A, b]にA→αを記入する。 ε∈First(α)か
つ$∈Follow(A)ならば、 M[A, $]にA→αを記入
する。
4. Mの未記入欄にerrorを記入する。
• 上記のアルゴリズムは任意の文法に対しても
適用できるが、文法によってはMの欄に対し
て複数の規則が書き込まれることがある。
【例】
P = {S →i C t S S’ | a, S’→e S | ε,
C→b }
( M[S’, ε] を求めてみよ。)
• LL(1)文法はこのようなことが起きない文法。
構文解析のアルゴリズム
1. X = a = $ ならば、”構文解析成功” を出力
し停止。
2. X = a =!= $ ならば、スタックからXをpopし、
入力ポインタを1つ進める。
3. a∈Vならば、M[X, a]を調べる。
M[X,a]={X→ABC}ならば、C,B,Aの順にス
タックにpushし、 X→ABCを実行する。
M[X,a]=errorならば、停止。
復習問題
文法
• E→E+T|T
• T→T*F|F
• F → ( E ) | id
左再帰性を除去しなさい.
参 考
(直接)左再帰性除去法
1. Aに関する左再帰性を取り除くためにまず,
A → Aα1 |Aα2|・・・|Aαm|β1|β2|・・・|βn
のようにまとめる.
2. 上記の形を基に以下のように変形する.
A → β1A’|β2A’|・・・|βnA’
A’ → α1 A’|α2A’|・・・|αmA’|ε
パターンを
覚えよう!
新たな文法規則
•
•
•
•
•
E → T E’
E’ → + T E’ | ε
T → F T’
T’ → * F T’ | ε
F → ( E ) | id
FirstとFollowを求めよ.
•
•
•
•
•
E → T E’
E’ → + T E’ | ε
T → F T’
T’ → * F T’ | ε
F → ( E ) | id
First & Follow
• (各自でやってみよう)
ここが
正念場!
構文解析表を作成する
• (各自で作成してみよう)
構文解析表
id
E
(
T → F T’
ε
E’ →ε
E’ →ε
T’ →ε
T’ →ε
T → F T’
T’ →ε
F → id
)
E → T E’
E’ → + T E’
T’
F
*
E → T E’
E’
T
+
T’ → * F T’
F→(E)
動作のトレース
• 入力: id + id * id
落ち着いてトレースしよう!
動作のトレース
スタック
$E
$E’T
$E’T’F
$E’T’id
$E’T’
$E’
入力
id+id*id
id+id*id
id+id*id
id+id*id
+id*id
+id*id
出力
E→TE’
T→FT’
F→id
T’→ε
(以下省略)
以上で構文解析の話は
ほぼ終わりです.
• 引き続き練習を積み重ねてください.
– 用語を知ること
– 用語の意味を知り,自分で説明できるように.
– なぜそのような用語が定義されているのかを考え理解す
る.
– 左再帰削除ができるように
– Factoringができるように
– Firstやfollowを自分で求められるように
– 構文解析表が作れるように
– 構文解析処理をトレースできるように
参考情報
1. 構文解析まで終われば、後は少し楽になり
ます。
2. 構文解析は解析の中でも難関部分で、
今日でも多くの研究がなされてます。
3. 構文解析の次は意味解析(解析の最終段
階)。
4. それ以後は合成の段階になります。
Let’s call it a day!
今日はここまで!
インフルエンザやノロウィルスには十分注意しましょう.