C05/Rev 1.0 アナログ信号の コンピュータへの取り込み...C05 ア ナログ信号→コンピュ ータ 基礎からのメカトニクスセミ AD変換の入力特性
コンパイラ解説資料集 - Mie...
Transcript of コンパイラ解説資料集 - Mie...
コンパイラ 解説資料集 2
下向き構文解析 2
文脈自由文法の等価変換 4
下向き構文解析向け文法 LL(1) 6
字句集合 First, Follow 8
LL(1)文法か否かの判定 9
字句集合の性質と計算法 11
LL(1)文法に基づく下向き構文解析 13
拡張文脈自由文法に基づく下向き構文解析 15
lex による字句解析と下向き構文解析 17
LR構文解析 19
LR構文解析表と解析動作 20
LR構文解析表の計算 22
LR(1)文法 24
yacc による衝突の調査 26
lex と yacc による字句解析と上向き構文解析 28
山田 俊行
http://www.cs.info.mie-u.ac.jp/~toshi/lectures/compiler/
2020年 5月
1
コンパイラ 解説資料 (山田)
下向き構文解析
構文解析器を,文法に沿った再帰手続きの集まりとして実現する.この構文解析の実行順は,最左導出
による規則の適用順,つまり,解析木を根から葉に向けて作る順序に対応する.
●文法 (論理式)
1 : exp → ( exp op exp )
2 : exp → ! exp
3 : exp → VAR
4 : exp → CON
5 : op → ||
6 : op → &&
●構文解析アルゴリズム
def parse_exp():
read_token()
exp()
if token_type() != END_TOKEN:
error()
def exp():
if token_type() == ’(’:
print(’1: exp -> ( exp op exp )’)
read_token()
exp()
op()
exp()
if token_type() == ’)’:
read_token()
else:
error()
elif token_type() == ’!’:
print(’2: exp -> ! exp’)
read_token()
exp()
elif token_type() == ’VAR’:
print(’3: exp -> VAR’)
read_token()
elif token_type() == ’CON’:
print(’4: exp -> CON’)
read_token()
else:
error()
def op():
if token_type() == ’||’:
print(’5: op -> ||’)
read_token()
elif token_type() == ’&&’:
print(’6: op -> &&’)
read_token()
else:
error()
2
補助関数
token_type() 現在の先読み字句
read_token() 入力を読み進めて先読み字句を更新
error() 誤り処理
END_TOKEN 入力終端を表す字句の種類
注意点• 生成規則の各左辺について,それを読む解析関数を作る• 規則の右辺の非終端記号に対応する解析関数を呼ぶ• 規則の右辺の終端記号を照合したら,read_token() で入力を読み進める
• 常に 1字句先読みして,各構文解析関数を呼ぶ
●実行結果
入力が ( CON && ( ! VAR || VAR ) ) のとき
結果 (選んだ規則の列)
1: exp -> ( exp op exp )
4: exp -> CON
6: op -> &&
1: exp -> ( exp op exp )
2: exp -> ! exp
3: exp -> VAR
5: op -> ||
3: exp -> VAR
対応する 最左導出・適用規則・読み込み済み字句列
exp
⇒ ( exp op exp ) 1 (
⇒ ( CON op exp ) 4 ( CON
⇒ ( CON && exp ) 6 ( CON &&
⇒ ( CON && ( exp op exp ) ) 1 ( CON && (
⇒ ( CON && ( ! exp op exp ) ) 2 ( CON && ( !
⇒ ( CON && ( ! VAR op exp ) ) 3 ( CON && ( ! VAR
⇒ ( CON && ( ! VAR || exp ) ) 5 ( CON && ( ! VAR ||
⇒ ( CON && ( ! VAR || VAR ) ) 3 ( CON && ( ! VAR || VAR
( CON && ( ! VAR || VAR ) )
入力が ! VAR && VAR のとき
結果
2: exp -> ! exp
3: exp -> VAR
syntax error at token ’&&’
3
コンパイラ 解説資料 (山田)
文脈自由文法の等価変換
2種類の等価変換 (括り出し,左再帰の除去)を使って文法を変形し,生成する言語を変えずに,下向き
構文解析に適した文法を得る.
●括り出し (factoring)
例:代入文
右辺の先頭に共通部分がある文法の例
1 : stm → ID = NUM
2 : stm → ID = ID
1 : stm → ID = atom
2 : atom → NUM
3 : atom → ID
変換前の規則の右辺から共通の先頭部分 ID = を括り出し,変換後の規則 1 にまとめて,
変換前の二つの規則の差分を表す新規則を変換後の規則 2, 3 として追加した.
例:算術式
右辺の先頭と末尾に共通部分がある文法の例
1 : exp → ( exp + exp )
2 : exp → ( exp * exp )
3 : exp → VAR
4 : exp → NUM
1 : exp → ( exp op exp )
2 : exp → VAR
3 : exp → NUM
4 : op → +
5 : op → *
変換前の規則 1, 2 の右辺から共通部分 ( exp と exp ) を括り出し,変換後の規則 1 にま
とめて,変換前の規則 1, 2 の差分を表す新規則を変換後の規則 4, 5 として追加した.
括り出しの一般形
右辺の先頭と末尾に共通部分がある規則の変換
A → αβ1γ
A → αβ2γ
A → αBγ
B → β1
B → β2
上記の代入文の例のように,γ が空列で左側の共通部分 αだけを括り出す特別な場合を,
左括り出しと呼ぶ.
4
●左再帰の除去
定義
文法が左再帰 :⇐⇒ A⇒+ Aα となる変数 A ∈ V と文法記号列 α ∈ (V ∪ T )∗ がある
例:数列
0個以上のものの並びを表す文法の例
1 : list → list NUM
2 : list → ε
1 : list → NUM list
2 : list → ε
例:区切り付き数列
区切り記号や演算子を挟んだ,1個以上のものの並びを表す文法の例
1 : seq → seq , NUM
2 : seq → NUM
1 : seq → NUM seq ′
2 : seq ′ → , NUM seq ′
3 : seq ′ → ε
具体的な字句列に対する解析木の対応を考えると,変換の意味が分かりやすい.
seq
eeeeeeeeeeRRRRRR
seq
llllllRRRRRR
seq
NUM , NUM , NUM
seq
mmmmm SSSSS
seq ′
kkkkk ZZZZZZZZZ
seq ′
kkkkk VVVVV
seq ′
NUM , NUM , NUM ε
変換前の左の文法は,NUMの後に字句列 , NUM が 0個以上並ぶ列を表す.変換後の右
の文法は,空列 εの前に字句列 , NUM が 0個以上並んで先頭に NUM がある列を表す.
区切り記号や演算子を,変換前には左結合的に扱うのに対して,変換後には右結合的に扱
う.このことは,構文解析の実行順序に影響する.
左再帰の除去の一般形
βα · · ·α の形の列を生成する左再帰規則の変換
A → Aα
A → β
A → βαA′
A′ → αA′
A′ → ε
●参考文献
以下の文献では,左括り出しや左再帰除去について,さらに一般的化した等価変換を解説している.
• 『プログラミング言語処理系』,佐々政孝,岩波書店,1980.4.4節 下向き構文解析.
• 『コンパイラ』,第 2版,A. V. エイホ,M. S. ラム,R. セシィ,J. D. ウルマン,サイエンス社,
2009.4.3節 文法の記述.
5
コンパイラ 解説資料 (山田)
下向き構文解析向け文法 LL(1)
文法を下向き構文解析に適した形に変えるには,先読み字句に基づいて適切な規則を選べるように,
文法の等価変換 や 規則の書き換え をする.構文解析器を手書きで作りやすいか判断するには,どんな
文法が下向き構文解析に適するかを定式化した LL(1) という条件を使う.
●先頭字句の重なり解消
例:数と識別子 の代入文
文 → ID = NUM
| ID = ID
文 → ID = 値
値 → NUM
| ID
規則の右辺で先頭字句が重なると,再帰下降型の構文解析器で,先読みの 1字句だけでは
適切な規則が決まらない.括り出しの等価変換を使って,先頭の共通部分を一つにまとめ
れば,この不都合を解消できる.
例:数の和
式 → 式 + 式
| NUM
式 → ( 式 + 式 )
| NUM
左の文法で,入力 NUM の解析には下の規則を使うが,NUM + NUM の解析 (最左導出)
は上の規則の適用から始める.同じ先読み字句でも選ぶべき規則が違うので,先読みの 1
字句だけでは適用規則が決まらない.規則の右辺が非終端記号 (文法の変数)から始まると
き,その記号から導出できる先頭字句との重なりも防ぐ必要がある.
文法に終端記号 (区切り記号やキーワード)を追加して規則を書き換えることでも,先頭字句
の重なりを防げる.なお,左の文法は曖昧である (例えば,字句列 NUM + NUM + NUM
の演算子を左結合と右結合で解釈する 2通りの解析木が作れる).式の範囲を括弧で示す
右の文法では,曖昧さも解消されている.
構文解析できる文法の条件
上記の二つの例のように,文法に空列 εが現れない場合,右辺から導出できる先頭字句が
重ならなければ,再帰下降型で構文解析できる.記号列 αから導出できる先頭字句の集合
を First(α)で表せば,この条件は
左辺が同じで右辺が異なる任意の規則 A→ αと A→ α′ について
First(α) ∩ First(α′) = ∅
と表せる.
6
●後続字句を考慮した先頭字句の重なり解消
例:数列
列 → 列 NUM
| ε
列 → NUM 列
| ε
規則に空列 εがあると,右辺から導出できる先頭字句の重なりを防ぐだけでは不十分であ
る.左の文法による,入力 NUM の最左導出は,まず上の規則で「列」から「列 NUM」
を生成し,次に下の規則で「列」から「ε」を生成する.つまり,先読み字句が NUM とい
う情報だけでは,解析時にどちらの規則を使うか決められない.
この問題を解消するには,左の文法の左再帰を除去し,文法の右辺の「列」の後に字句が続
かないようにする.そうすれば,入力の終端に達したときだけ下の規則を選べばよくなる.
構文解析できる文法の条件:LL(1)文法
規則 A→ αの右辺 αから空列 εを導出できるとき,規則の先読み字句として,αから導
出できる先頭字句の他に,字句列の導出で Aに続く字句も含める必要がある.
文法記号列 αから導出できる先頭字句の集合 First(α)を
First(α) :=
{{a ∈ T | α⇒∗ aβ となる β ∈ (V ∪ T )∗ がある } (α ̸⇒∗ εのとき)
{a ∈ T | α⇒∗ aβ となる β ∈ (V ∪ T )∗ がある } ∪ {ε} (α⇒∗ εのとき)
で定め,開始記号 S からの導出で左辺 Aに続く字句の集合 Follow(A)を
Follow(A) := {a ∈ T ∪ {$} | S$⇒∗ αAaβ となるα ∈ T ∗, β ∈ (V ∪ T ∪ {$})∗ がある }
と定める.ただし $は入力終端を表す記号で,$ ̸∈ V ∪ T とする.規則の先読み候補とな
る字句の集合 Director(A→ α) を
Director(A→ α) :=
{First(α) (α ̸⇒∗ εのとき)
First(α) \ {ε} ∪ Follow(A) (α⇒∗ εのとき)
と定めれば,再帰下降型で構文解析できる文法の条件は
左辺が同じで右辺が異なる任意の規則 A→ αと A→ α′ について
Director(A→ α) ∩ Director(A→ α′) = ∅
と表せる.この条件を満たす文脈自由文法を LL(1)文法という.
●参考文献
LL(1)文法の詳細は,以下の文献で解説されている.
• 『プログラミング言語処理系』,佐々政孝,岩波書店,1980.4.4節 下向き構文解析.
• 『コンパイラ』,第 2版,A. V. エイホ,M. S. ラム,R. セシィ,J. D. ウルマン,サイエンス社,
2009.4.4節 下向き構文解析.
7
コンパイラ 解説資料 (山田)
字句集合 First, Follow
下向き構文解析に適する文法 LL(1) の定義には,字句集合 First と Follow が使われる.文法が LL(1)
であるか否かを判定するには,これらの集合の計算に習熟する必要がある.
●文法
例:整数列
1 : 列 → 列 数 4 : 符号 → +
2 : | ε 5 : | −3 : 数 → 符号 NUM 6 : | ε
●先頭字句集合 First
定義
First(α) :=
{{ a | α⇒∗ a · · · } (α ̸⇒∗ ε)
{ a | α⇒∗ a · · · } ∪ { ε } (α⇒∗ ε)
例+ ∈ First(列 数) と NUM ∈ First(列 数) を定義に沿って確認
列 数 規則
⇒ 数 2
⇒ 符号 NUM 3
⇒ + NUM 4
列 数 規則
⇒ 数 2
⇒ 符号 NUM 3
⇒ NUM 6
●後続字句集合 Follow
定義
Follow(A) := { a | S $⇒∗ · · · Aa · · · } (S は文法の開始記号)
例+ ∈ Follow(列) と $ ∈ Follow(列) を定義に沿って確認
列 $ 規則
⇒ 列 数 $ 1
⇒ 列 符号 NUM $ 3
⇒ 列 + NUM $ 4
列 $
⇒∗ 列 $ (0ステップの導出)
8
コンパイラ 解説資料 (山田)
LL(1)文法か否かの判定
LL(1) 文法は,再帰下降型の構文解析に適する文法である.規則右辺の First集合,規則左辺の Follow
集合,規則の Director集合,の 3種類の集合を求めて,文法が LL(1) か否かを判定する.
● LL(1)でない文法の例 (整数列)
First集合 (右辺が導出する先頭字句か空列 ε)
A → α
列 → 列 数
| ε
数 → 符号 NUM
符号 → +
| -
| ε
First(α)
(ア) 右辺 αの先頭字句や ε
(イ) 右辺 αの先頭の変数の First (ε以外)
(ウ) 直前の変数が εを導出できるとき,右辺の残りの First
Follow集合 (左辺の後続字句か入力終端 $)
A → α
列 → 列 数
| ε
数 → 符号 NUM
符号 → +
| -
| ε
First(α)
{+, -,NUM}{ε}{+, -,NUM}{+}{-}{ε}
Follow(A)
(ア) 開始記号に続く $
(イ) 右辺中の Aに続く列の First (ε以外)
(ウ) 右辺中の Aに続く列が εを導出できるとき,その左辺の Follow
Director集合 (規則の先読みの候補字句か入力終端 $)
A → α
列 → 列 数
| ε
数 → 符号 NUM
符号 → +
| -
| ε
First(α)
{+, -,NUM}{ε}{+, -,NUM}{+}{-}{ε}
Follow(A)
{$, +, -,NUM}
{$, +, -,NUM}{NUM}
Director(A→ α)
(ア) 右辺 αの First (ε以外)
(イ) 右辺 αの First に ε があるとき,左辺 Aの Follow
9
● LL(1)文法の例 (整数列)
整数列の文法は,「列」の規則間で先読み字句が重なる.左再帰の除去で文法を等価変換す
れば,この問題を解消できる.
A → α
列 → 数 列
| ε
数 → 符号 NUM
符号 → +
| -
| ε
First(α) Follow(A) Director(A→ α)
● LL(1)でない文法の例 (含意の論理式)
論理定数 CON と含意 => からなる論理式を表す次の文法が LL(1) か否かを調べるため,
先読み字句の集合を計算する.この文法には ε が現れないので,各規則の先読み字句は
First 集合だけで決まる.
A → α
式 → 素式 => 式
| 素式
素式 → ( 式 )
| CON
First(α)
{(,CON}{(,CON}{(}{CON}
左辺が「式」の二つの規則間に共通の先読み字句 (と CONがあるので,この文法は LL(1)
ではない.
● LL(1)文法の例 (含意の論理式)
先読み字句の重なりを解消するため,括り出しで文法を等価変換する.変換後の文法に対
して First, Follow, Director,の 3種類の集合を計算する.
A → α
式 → 素式 式′
式′ → => 式
| ε
素式 → ( 式 )
| CON
First(α)
{(,CON}{=>}{ε}{(}{CON}
Follow(A)
{$, )}{$, )}
{$, ), =>}
Director(A→ α)
{(,CON}{=>}{$, )}{(}{CON}
左辺が「式」の規則は,一つしかないので先読み字句の重なりを生まない (実際には,こ
の規則の Director 集合を求めなくても LL(1) の判定ができる).「式′」の規則の先読み字
句の集合は,{=>} と {$, )} で互いに素である.「素式」の規則の先読み字句集合も,{(}と {CON} で重ならない.以上のことから,変換後の文法は LL(1) である.
10
コンパイラ 解説資料 (山田)
字句集合の性質と計算法
3種類の字句集合 First, Follow, Director が満たす性質に基づいて,これらの計算法を導く.
●字句集合の性質
文脈自由文法 (V, T, P, S) についての First, Follow, Director の性質を以下にまとめる.以下の説明で,
A,B ∈ V , a ∈ T , α, β, γ ∈ (V ∪ T )∗ を断りなく使う.
先頭字句集合 First(α) の性質
(0) First(α) ⊆ T ∪ {ε}(1) α = ε のとき,First(α) = {ε}(2) α = aβ のとき,First(α) = {a}(3) α = Aβ かつ A→ γ ∈ P のとき,
(a) First(α) ⊇ First(γ) \ {ε}(b) ε ∈ First(γ) ならば First(α) ⊇ First(β)
後続字句集合 Follow(A) の性質
(0) Follow(A) ⊆ T ∪ {$}(1) A = S のとき,Follow(A) ∋ $
(2) B → αAβ ∈ P のとき,(a) Follow(A) ⊇ First(β) \ {ε}(b) ε ∈ First(β) ならば Follow(A) ⊇ Follow(B)
先読み字句集合 Director(A→ α) の性質
(0) Director(A→ α) ⊆ T ∪ {$}(1) Director(A→ α) ⊇ First(α) \ {ε}(2) ε ∈ First(α) ならば Director(A→ α) ⊇ Follow(A)
以上の性質に基づいて,各集合を反復改良により求める簡潔なアルゴリズム (次ページ)を導ける.
11
●字句集合の計算法
文脈自由文法 (V, T, P, S) についての First, Follow, Director を計算するアルゴリズムを以下にまとめ
る.以下の説明で,A,B ∈ V , a ∈ T , α, β, γ ∈ (V ∪ T )∗ を断りなく使う.
First の計算(0) B → αβ ∈ P を満たす各 β について First(β)← ∅(1) First(ε)← {ε}(2) B → αaβ ∈ P を満たす各 a, β について First(aβ)← {a}(3) 以下を,First が変わらなくなるまで反復
B → αAβ ∈ P と A→ γ ∈ P を満たす各 A, β, γ について(a) First(Aβ)← First(Aβ) ∪ (First(γ) \ {ε})(b) ε ∈ First(γ) ならば First(Aβ)← First(Aβ) ∪ First(β)
Follow の計算(0) 各 A について Follow(A)← ∅(1) Follow(S)← {$}(2) 以下を,Follow が変わらなくなるまで反復
B → αAβ ∈ P を満たす各 B,A, β について(a) Follow(A)← Follow(A) ∪ (First(β) \ {ε})(b) ε ∈ First(β) ならば Follow(A)← Follow(A) ∪ Follow(B)
Director の計算各 A→ α ∈ P について,以下を実行(1) Director(A→ α)← First(α) \ {ε}(2) ε ∈ First(α)ならば Director(A→ α)← Director(A→ α)∪Follow(A)
なお,このアルゴルズムは,各集合の計算法を正しく理解する助けとなるよう,簡潔さを重視している.
効率的な計算には,さらに工夫が要る.
12
コンパイラ 解説資料 (山田)
LL(1) 文法に基づく下向き構文解析
言語を LL(1) 文法で書ければ,再帰下降型の構文解析器を系統的に作れる.
●文法 (数リスト)
次の文法は,同じ左辺の生成規則間で先読み字句が重ならないので,LL(1) 文法である.先読み字句集
合 Directorは,先頭字句と後続字句の集合 First, Followより求める.
First Follow Director
1 : numlist → [ seq ] [ $ [ NUM ] [
2 : seq → numlist seq [ [
3 : | NUM seq NUM NUM
4 : | ε ε ] ]
●構文解析器
LL(1) 文法の生成規則に沿って解析の手続きを書けば,構文解析器が作れる.文法の各変数 A に対応す
る解析手続きの先頭で,先読み字句がどの Director 集合に属すかを調べる.Director(A→ α) に属すな
ら,右辺 α の解析を始め,(左辺が A の規則の)どの Director 集合にも属さないなら,誤り処理をする.
プログラムdef match_token(token):
if token_type() == token:read_token()
else:error()
def parse_numlist():read_token()numlist()if token_type() != END_TOKEN:
error()
def numlist(): # Director(1) = { [ }print(’1: numlist -> [ seq ]’)match_token(’[’)seq()match_token(’]’)
def seq():if token_type() == ’[’: # Director(2) = { [ }
print(’2: seq -> numlist seq’)numlist()seq()
elif token_type() == ’NUM’: # Director(3) = { NUM }print(’3: seq -> NUM seq’)match_token(’NUM’)seq()
elif token_type() == ’]’: # Director(4) = { ] }print(’4: seq -> (EMPTY)’)
else:error()
補助関数
token_type() 現在の先読み字句
read_token() 入力を読み進めて先読み字句を更新
error() 誤り処理
END_TOKEN 入力終端を表す字句の種類
13
●実行結果
解析木入力の字句列 [ NUM [ ] ]
numlist
ppppppppppppp
NNNNNNNNNNNNN
[ seq
qqqqqqqqqqqqq
MMMMMMMMMMMMM ]
NUM seq
qqqqqqqqqqqqq
MMMMMMMMMMMMM
numlist
ppppppppppppp
NNNNNNNNNNNNNseq
[ seq ] ε
ε
再帰下降構文解析は,解析木を根から葉に向けて下向きに作る順に実行される.
文法木による表示
numlist1:pppppppp
NNNNNNNN
[ seq ]
seq
2:qqqqqqqq
LLLLLLLL
numlist seq
seq
3:qqqqqqqq
LLLLLLLL
NUM seq
seq
4:
ε
実行順
入力が字句列 [ NUM [ ] ] のときの出力
1: numlist -> [ seq ]
3: seq -> NUM seq
2: seq -> numlist seq
1: numlist -> [ seq ]
4: seq -> (EMPTY)
4: seq -> (EMPTY)
解析手続きの規則選択の順序は,解析木の先行順走査に対応する.
プログラムに手を加えて,各解析手続きの先頭で (を表示し,規則の選択時にその番号を
表示し,各解析手続きの末尾で )を表示するよう変える.すると,同じ入力字句列に対す
る出力は,次のように変わる.
(1(3(2(1(4))(4))))
これは,解析木の走査で,先行順と後行順の処理の併用に対応する.
14
コンパイラ 解説資料 (山田)
拡張文脈自由文法に基づく下向き構文解析
生成規則の右辺に 選択・反復 を許すと,文法や解析器が作り易くなる.
●文法 (数リスト)
文脈自由文法による記述
数リストは,数リストや数を 0個以上並べて [ ] で囲んだものである.
numlist → [ seq ]
seq → numlist seq | NUM seq | ε
拡張文脈自由文法による記述
「数リストや数」の部分に選択 | を使い,「0個以上並べて」の部分に反復 ⋆ を使うと,
数リストの文法を一つの生成規則で簡潔に書ける.
numlist → [ 【 numlist | NUM 】⋆ ]
部分式の範囲を明示するために,他の記号と区別できる括弧【 】を使う.
●構文解析 (数リスト)
先読み字句の重なり
拡張文脈自由文法に対しても,構文解析手続きが右辺の適切な部分式を選べるよう,先読
み字句の重なりを調べる.
上記の拡張文脈自由文法では,二つの選択候補の先読み字句集合 First( numlist ) と
First( NUM ) が,それぞれ { [ } と { NUM } であり,重ならない.また,反復継続時の先頭字句集合 First( numlist | NUM ) = { [, NUM } と,反復終了後の後続字句集合Follow(【 numlist | NUM】⋆ ) = { ] } も重ならない.
プログラム
構文解析器の作り方は,通常の文脈自由文法の場合と同様である.異なる点は,右辺の選
択の部分式に対して if 文等の選択文を使い,右辺中の反復の部分式に対して while 文等
の反復文を使う点である.また,先読み字句の集合を,右辺中の適切な部分式を選ぶため
に使える.
def parse_numlist():read_token()numlist()if token_type() != END_TOKEN:
error()
def numlist():match_token(’[’)while token_type() in [’[’, ’NUM’]: # First( numlist | NUM )
if token_type() == ’[’: # First( numlist )numlist()
elif token_type() == ’NUM’: # First( NUM )match_token(’NUM’)
else:error()
match_token(’]’)
15
●文法 (算術式)
拡張文脈自由文法による記述
1 : exp → fact 【【 + | - 】 fact 】⋆
2 : fact → atom【【 * | / 】atom 】⋆
3 : atom → ( exp ) | ID | NUM
●構文解析 (算術式)
プログラム
# 記法: | は選択,@ は反復,[ ] は文法の部分式の範囲の明示
def exp():print(’1: exp -> fact [ [ + | - ] fact ] @’)fact()while token_type() in [’+’, ’-’]: # First( [ + | - ] fact )
if token_type() == ’+’: # First( + )match_token(’+’)
else: # First( - )match_token(’-’)
fact()
def fact():print(’2: fact -> atom [ [ * | / ] atom ] @’)atom()while token_type() in [’*’, ’/’]: # First( [ * | / ] atom )
if token_type() == ’*’: # First( * )match_token(’*’)
else: # First( * )match_token(’/’)
atom()
def atom():print(’3: atom -> ( exp ) | ID | NUM’)if token_type() == ’(’: # First( ( exp ) )
match_token(’(’)exp()match_token(’)’)
elif token_type() == ’ID’: # First( ID )match_token(’ID’)
elif token_type() == ’NUM’: # First( NUM )match_token(’NUM’)
else:error()
実行結果
入力が字句列 NUM * ID + NUM / ( ID - NUM ) のときの出力 (適用規則列)
1: exp -> fact [ [ + | - ] fact ] @2: fact -> atom [ [ * | / ] atom ] @3: atom -> ( exp ) | ID | NUM3: atom -> ( exp ) | ID | NUM2: fact -> atom [ [ * | / ] atom ] @3: atom -> ( exp ) | ID | NUM3: atom -> ( exp ) | ID | NUM1: exp -> fact [ [ + | - ] fact ] @2: fact -> atom [ [ * | / ] atom ] @3: atom -> ( exp ) | ID | NUM2: fact -> atom [ [ * | / ] atom ] @3: atom -> ( exp ) | ID | NUM
16
コンパイラ 解説資料 (山田)
lex による字句解析と下向き構文解析
lex による字句解析器を使って簡易的に作った,算術式の構文解析器の例を示す.
● lex 記述
/** arith.l -- 算術式の構文解析** 使い方: flex arith.l && gcc lex.yy.c -lfl && ./a.out < input.txt*/
%{enum { END_TOKEN = 0, ID = 128, NUM = 129 }; // 1文字でない字句のコードvoid error(void); // 字句定義で使う関数%}
%%
[-+*/()] return *yytext; // 1文字の字句[a-zA-Z][a-zA-Z0-9]* return ID; // 識別子の字句[0-9]+ return NUM; // 数の字句[ \t\n]+ // 空白類を無視. error(); // 他の文字は誤り
%%
int token;void error(void) { printf("syntax error at ’%c’\n", *yytext); exit(1); }void read_token(void) { token = yylex(); }void match_token(int tok) { if (token == tok) read_token(); else error(); }
// 文法の記法: 選択は | 反復は @ 部分式の範囲指定は [ ]
void parse_fact(void);void parse_atom(void);
void parse_exp(void) {printf("1: exp -> fact [ [ + | - ] fact ] @\n");parse_fact();while (token == ’+’ || token == ’-’) { // First( [ [ + | - ] fact )
if (token == ’+’) // First( + )match_token(’+’);
else // First( - )match_token(’-’);
parse_fact();}
}
void parse_fact(void) {printf("2: fact -> atom [ [ * | / ] atom ] @\n");parse_atom();while (token == ’*’ || token == ’/’) { // First( [ [ * | / ] atom )
if (token == ’*’) // First( * )match_token(’*’);
else // First( / )match_token(’/’);
parse_atom();}
}
void parse_atom(void) {printf("3: atom -> ( exp ) | ID | NUM\n");if (token == ’(’) { // First( ( exp ) )
match_token(’(’);parse_exp();match_token(’)’);
} else if (token == ID) { // First( ID )match_token(ID);
} else if (token == NUM) { // First( NUM )match_token(NUM);
} else {error();
}}
int main(void) {read_token();parse_exp();if (token != END_TOKEN) error();return 0;
}
17
●文法 (算術式)
算術式の文法は,拡張文脈自由文法の選択 | や反復 ⋆ を使うと簡潔に書ける.
1 : exp → fact 【【 + | - 】 fact 】⋆
2 : fact → atom【【 * | / 】atom 】⋆
3 : atom → ( exp ) | ID | NUM
優先度の低い記号ほど,開始記号に近い規則に書く.
●解析木
字句列 NUM * ID + NUM / ( ID - NUM ) の解析木
exp
eeeeeeeeeeeeeeeeYYYYYYYYYYYYYYYY
fact
hhhhhhhhhhhVVVVVVVVVVV + fact
hhhhhhhhhhhVVVVVVVVVVV
atom * atom atom / atom
rrrrrr
rLLL
LLLL
NUM ID NUM ( exp
qqqqqqMMMMMM )
fact - fact
atom atom
ID NUM
●実行結果
入力が文字列 100*x + 50/(num-1) のときの構文解析器の出力 (適用規則列)
1: exp -> fact [ [ + | - ] fact ] @
2: fact -> atom [ [ * | / ] atom ] @
3: atom -> ( exp ) | ID | NUM
3: atom -> ( exp ) | ID | NUM
2: fact -> atom [ [ * | / ] atom ] @
3: atom -> ( exp ) | ID | NUM
3: atom -> ( exp ) | ID | NUM
1: exp -> fact [ [ + | - ] fact ] @
2: fact -> atom [ [ * | / ] atom ] @
3: atom -> ( exp ) | ID | NUM
2: fact -> atom [ [ * | / ] atom ] @
3: atom -> ( exp ) | ID | NUM
●参考文献
• 『lex & yacc』,J. R. レビン,T. メイソン,D. ブラウン,アスキー,1994.
• flex: The Fast Lexical Analyzer, https://github.com/westes/flex/, 2020年 5月 13日閲覧.
18
コンパイラ 解説資料 (山田)
LR構文解析
上向き構文解析法の一つである LR 構文解析では,最右導出の逆順に沿って,シフト (入力の読み込み)
と還元 (生成規則の認識)を繰り返して解析を進める.
●文法 (論理式)
1 : exp → exp || exp 論理和
2 : exp → ! exp 否定
3 : exp → VAR 変数
●最右導出の逆順 (還元列)
! VAR || VAR
⇐ ! exp || VAR
⇐ exp || VAR
⇐ exp || exp
⇐ exp
●解析の実行順
スタック 入力
! VAR || VAR
!
VAR || VAR
! VAR
|| VAR
! exp
|| VAR
exp
|| VAR
exp ||
VAR
exp || VAR
exp || exp
exp
19
コンパイラ 解説資料 (山田)
LR構文解析表と解析動作
LR構文解析表の使い方を通して,シフト (入力の読み込み)と還元 (規則の認識)の解析動作を学ぶ.
●文法 (論理式)
1 : 式 → 式 || 素式 3 : 素式 → ! VAR
2 : 式 → 素式 4 : 素式 → VAR
● LR構文解析表
構文解析表によってスタック付きオートマトンの動作を定める.上記の文法に沿って構文
解析をするための解析表を以下の左に示し,その読み方を右に示す.
$ || ! VAR 式 素式0 s5 s7 1 41 acc s22 s5 s7 33 r1 r14 r2 r25 s66 r3 r37 r4 r4
si シフトshift
入力を読んで次状態 iをプッシュ
rj 還元reduce
規則 j の右辺の記号数だけポップし,(スタック上の状態,j の左辺) の欄に書かれた次状態をプッシュ
acc 受理accept
解析成功
空白 拒否reject
解析失敗
●構文解析の動作
構文解析表に沿ってスタック付きオートマトンを動かせば,構文解析ができる.入力字句
列 ! VAR || VAR に対する LR 構文解析の最初の 3段階の動作は次の通りである.
スタック 記号列 (参考) 残り入力 動作0 ! VAR || VAR $ s50 5 ! VAR || VAR $ s60 5 6 ! VAR || VAR $ r30 4 素式 || VAR $
初期状態では,スタックは,状態列 0 (記号列は空列) で始め,残り入力は,入力字句列に
終端 $を付加した ! VAR || VAR $で始める.スタック最上段 (最右)の状態 0と,残
り入力の先頭 (最左)の記号 !から,構文解析表の欄 (0, !)に書かれた次動作 s5を得る.
動作 s5 (状態 5へのシフト)では,入力を 1字句読み,次状態 5をプッシュする.つまり,
記号列に残り入力の先頭の記号 !を移し,スタックに状態 5を積む.スタック上は状態 5
で入力先頭は VARだから,表の欄 (5,VAR)の次動作 s6を得る.動作 s6も同様である.
動作 r3 (規則 3による還元)では,規則 3の右辺の記号数だけ状態や記号をポップし,表
の (スタック上の状態, 規則 3の左辺) の欄に書かれた次状態をプッシュする.規則 3の
右辺 ! VARの記号数は 2だから,まず,スタック上から状態 5と 6を,記号列から ! と
VAR を取り除く.スタック上の状態は 0になり,規則 3の左辺は「素式」だから,解析表
の (0, 素式) の欄に書かれた次状態 4を得て,この状態をスタックに積む.記号列にも,還
元に使った規則 3の左辺の記号「素式」を積む.
20
●構文解析の動作 (続き)
文法と構文解析表を再掲する.
1 : 式 → 式 || 素式
2 : 式 → 素式
3 : 素式 → ! VAR
4 : 素式 → VAR
$ || ! VAR 式 素式0 s5 s7 1 41 acc s22 s5 s7 33 r1 r14 r2 r25 s66 r3 r37 r4 r4
入力字句列 ! VAR || VAR に対する LR 構文解析の全動作は次の通りである.
スタック 記号列 (参考) 残り入力 動作0 ! VAR || VAR $ s5 push 50 5 ! VAR || VAR $ s6 push 60 5 6 ! VAR || VAR $ r3 pop× 2 (0,素式) push 40 4 素式 || VAR $ r2 pop× 1 (0,式) push 10 1 式 || VAR $ s2 push 20 1 2 式 || VAR $ s7 push 70 1 2 7 式 || VAR $ r4 pop× 1 (2,素式) push 30 1 2 3 式 || 素式 $ r1 pop× 3 (0,式) push 10 1 式 $ acc
●解析木上での LR構文解析動作
上記の LR構文解析の動作は,解析木の深さ優先順の走査と対応する.シフト動作は葉の訪
問時に起こり,還元動作は葉以外の節の帰りがけの訪問時 (後行順での処理時)に起こる.
· 式
nnnnnnnnnnnnnn
PPPPPPPPPPPPPP·
· 式 · || · 素式 ·
· 素式
~~~~
~~~~
~
@@@@
@@@@
@· · VAR ·
· ! · VAR ·
●参考文献
上向き構文解析の詳細は,以下の文献で解説されている.
• 『プログラミング言語処理系』,佐々政孝,岩波書店,1980.4.6節 上向き構文解析.
• 『コンパイラ』,第 2版,A. V. エイホ,M. S. ラム,R. セシィ,J. D. ウルマン,サイエンス社,
2009.4.4~4.8節.
21
コンパイラ 解説資料 (山田)
LR構文解析表の計算
スタック付きのオートマトンの動作を適切に定めることにより,文法から LR構文解析表を作る.
●文法 (論理式)
0 : 式′ → 式 新たな開始記号から始める規則を,終了判定用に加える.
1 : 式 → 式 || 素式2 : 式 → 素式3 : 素式 → ! VAR
4 : 素式 → VAR
●解析位置の変化
解析処理がどの段階まで進んだかを,規則内での着目位置で捉える.規則の右辺に点 · を置いて解析位置を表し,記号を読むたびに位置を進める.
[式′ → ·式]0a
式��
ε
��
[式→ ·式||素式]1a
式��
ε
��
[式→ ·素式]2a
素式��
ε
��
︷ ︸︸ ︷左辺が式
[素式→ · !VAR]3a
!��
[素式→ ·VAR]4a
VAR
��
︷ ︸︸ ︷左辺が素式
[式′ →式 · ]0b
[式→式 · ||素式]1b
||��
[式→素式 · ]2b
[素式→ ! ·VAR]3b
VAR
��
[素式→ VAR · ]4b
[式→式|| ·素式]1c
素式��
ε
��
[素式→ !VAR · ]3c
[式→式||素式 · ]1d
各列の最下段にある,規則末尾の解析位置 · は,右辺を左辺に還元できることを表す.
●オートマトンの構成 と 解析木の走査
初期位置から始めて,同じ記号列で移れる解析位置の集合を,解析状態と捉える.
(0) {0a, 1a, 2a, 3a, 4a}式wwpppppp
素式��
!''NNNNNN
VAR,,XXXXXXXXXXXX
(1) {0b, 1b}||
��
(4) {2b} (5) {3b}VAR
��
(7) {4b}
(2) {1c, 3a, 4a}素式
��VAR
DD
!33ffffffffffff
(6) {3c}
(3) {1d}
· 式′ ·
· 式ddddddddd [[[[[[[[[
·
· 式 · || · 素式 ·
· 素式jjjjj TTTTT
· · VAR ·
· ! · VAR ·
オートマトンの状態遷移は,解析木の後行順走査による節の訪問に対応する.また,規則
による右辺から左辺への還元は,オートマトンの遷移を規則右辺の逆順に遡ってから,改
めて左辺の記号で遷移することに対応する.
22
●状態遷移表
オートマトンは,状態遷移表でも表せる.
$ || ! VAR 式 素式(0) 開始 (5) (7) (1) (4)
(1) 受理 (2)
(2) (5) (7) (3)
(3) 還元(4) 還元(5) (6)
(6) 還元(7) 還元
開始 :追加規則の開始位置が属す状態受理 : 〃 終了位置 〃
還元 :元の規則の終了位置 〃
●還元時の先読み字句
LR構文解析では,それまでの入力と先読み字句に基づき,いつ還元するかを決める.
解析位置 Aへの還元時の先読み字句の候補y y[ A → α · β , a ]
B の解析直前
[ A → α · B β , a ]
ε
99K First(βa)
∈
[ B → · γ , b ]
規則 B → γ の右辺の開始直前
X の解析直前
[ A → α · X β , a ]
Xy 記号一つ解析が進む
[ A → αX · β , a ]
X の解析直後
0a
[式′ → ·式 , $ ]
1a 3a
[式→ ·式||素式 , $ / || ] [素式→ · !VAR , $ / || ]
2a 4a
[式→ ·素式 , $ / || ] [素式→ ·VAR , $ / || ]
2b 4b
[式→素式 · , $ / || ] [素式→ VAR · , $ / || ]
各規則の還元位置 (終了位置)での先読み候補
還元位置 解析状態 先読み 還元に使う規則0b [式′ →式 · , $ ] ∈ (1) $ 0 : (受理)
1d [式→式||素式 · , $ / || ] ∈ (3) $ か || 1 :
2b [式→素式 · , $ / || ] ∈ (4) $ か || 2 :
3c [素式→ !VAR · , $ / || ] ∈ (6) $ か || 3 :
4b [素式→ VAR · , $ / || ] ∈ (7) $ か || 4 :
23
コンパイラ 解説資料 (山田)
LR(1)文法
LR(1)文法は,上向き構文解析に適する文法である.構文解析表でのシフトや還元の衝突の有無により,
文法が LR(1)か否かを判定する.
●文法 (曖昧な論理式)
次の文法は,複数の解析木をもつ字句列があるので曖昧である.構文定義に不向きなこの
文法に対する LR構文解析表の問題点を調べ,構文解析に適する文法の条件を理解する.
1 : 式 → 式 || 式
2 : 式 → ! 式
3 : 式 → VAR
式qqqq
VVVVVVVV
式 式qqqq NNNN
式 式
VAR || VAR || VAR
式 式
式
NNNN qqqq式
式
VVVVVVVVqqqq
式}}
} WWWWWWWW
式nnnnn PPPPP
式 式
! VAR || VAR
式 式
式
AAA qqqq
式
WWWWWWWWnnnnn
●状態遷移表と構文解析表
上の文法に規則 0 : 式′ →式 を加えて,各規則の解析位置の集合を 0a–0b, 1a–1d, 2a–2c,
3a–3bで表す.このとき,解析状態として {0a,1a,2a,3a}, {0b,1b}, {1c,1a,2a,3a}, {1d,1b},{2b,1a,2a,3a}, {2c,1b}, {3b} の 7状態が得られ,これらを順に 0から 6で表す.状態遷移
表を次の左に示す.
|| ! VAR 式0 4 6 11 22 4 6 33 24 4 6 55 26
$ || ! VAR 式0 s4 s6 11 acc s22 s4 s6 33 r1 r1/s24 s4 s6 55 r2 r2/s26 r3 r3
先読み記号は,追加規則の全位置で $,他の規則の全位置で $ か ||,である.遷移表に
還元を加えると,(3, ||) と (5, ||) の欄でシフトと重なってしまい,解析動作が一つに決
まらない.得られる構文解析表を上の右に示す.
●解析動作の衝突
衝突 (conflict) · · · 構文解析表の同じ欄に複数の動作が入ること.シフト・還元 衝突 · · · 表の同じ欄での,シフトと還元の重なり (例: 上記の解析表).
還元・還元 衝突 · · · 表の同じ欄での,複数の還元の重なり.
上の解析表の (3, ||) の欄での衝突の原因は,解析位置 1b [式→式 · ||式 ] でのシフトと
1d [式→ 式||式 · ] での還元との重なりであり,(5, ||) の欄での衝突の原因は,同じ 1b
でのシフトと 2c [式 → !式 · ] での還元との重なりである.これらは,曖昧性を示す上記の左と右の解析木にそれぞれ対応する.
24
●衝突の解消
曖昧な文法に対して LR構文解析表を作ると,複数の解析木のそれぞれに対応する解析動
作が可能なために,衝突が起こる.
シフト︷ ︸︸ ︷式 || 式 · || 式︸ ︷︷ ︸還元
シフト︷ ︸︸ ︷! 式 · || 式︸ ︷︷ ︸還元
同じ演算子間の シフト・還元 衝突については,演算子が左結合なら還元動作を選び,演
算子が右結合ならシフト動作を選べば,解析動作の非決定性を解消できる.違う演算子間
の シフト・還元 衝突については,左の演算子の優先度が高いなら還元を,右の演算子の
優先度が高いならシフトを選べばよい.
文法の等価変換や (非等価な)変形も,曖昧さを回避して解析動作を一意に定める有効な手
段である.例えば,前述の論理式の文法については,次の左の文法へと等価変換して,論
理和 || が左結合的であることや,否定 ! の優先度が || より高いことを明示すればよい.
通常の論理式では,右の文法のように括弧を使って優先順位を明示できる.
式 → 式 || 素式
式 → 素式
素式 → ! 素式
素式 → VAR
式 → 式 || 否定式
式 → 否定式
否定式 → ! 否定式
否定式 → 素式
素式 → ( 式 )
素式 → VAR
● LR(1)文法
衝突のない LR(1) 構文解析表ができる文法を LR(1)文法 という.これは,構文解析表と
入力だけで動作が決まる,上向き構文解析に適した文法である.
下向きの構文解析に適した LL(1)文法とは異なり,左再帰の規則があっても (衝突がなけ
れば)構文解析ができる.多くのプログラミング言語は,構文を LR(1)文法として定義で
きる.上記の変形後の二つの文法は,どちらも LR(1)文法である.
●参考文献
LR構文解析の理論については,以下の文献が参考になる.
• 『コンパイラ』,第 2版,A. V. エイホ,M. S. ラム,R. セシィ,J. D. ウルマン,サイエンス社,
2009.4.6節 LR構文解析の序: 単純 LR,4.7節 さらに強力な LR構文解析器.
• Introduction to the Theory of Computation, 3rd edition, M. Sipser, Cengage Learning, 2013. Section
2.4 Deterministic Context-Free Languages.
25
コンパイラ 解説資料 (山田)
yacc による衝突の調査
yacc を使えば,文法から LR構文解析表を自動生成でき,解析動作の衝突の有無を調べられる.
●文法 (長さ 2以下の識別子列)
次の曖昧な文法を使って LR構文解析表を作り,解析動作の衝突が生じることを yacc で確かめる.
1 : 列 → 値 値
2 : | 値
3 : 値 → ID
4 : | ε
この文法のもとでは,長さ 1の入力字句列 ID に対して,次の 4通りの解析木ができる.
列
値
ε ID
値 値
列
AAAAAAAAA
}}}}}}}}}
列
値
ID ε
値 値
列
AAAAAAAAA
}}}}}}}}}
● yacc 記述
/* idseq.y -- 長さ2以下の識別子列(曖昧な文法) */
%token ID // yacc での文法記述に使う字句の指定
%%
// 文法規則の右辺は : で始め | で区切り ; で終える
seq : val val // 列 → 値 値| val // │ 値;
val : ID // 値 → ID
| /* 空列 */ // │ ε;
%%
26
●衝突の調査
$ bison idseq.y # bison は yacc 互換の構文解析器生成ツール
idseq.y: conflicts: 1 shift/reduce, 1 reduce/reduce
$ bison -r all idseq.y # -r all でオートマトンの全情報を .output に出力$ cat idseq.output # 衝突の詳細を確認
State 0 conflicts: 1 shift/reduce
State 3 conflicts: 1 reduce/reduce
(中略)
状態 0
0 $accept: . seq $end
1 seq: . val val
2 | . val
3 val: . ID
4 | . [$end, ID]
ID shift, and go to state 1
ID [reduce using rule 4 (val)]
$default reduce using rule 4 (val)
seq go to state 2
val go to state 3
(中略)
状態 3
1 seq: val . val
2 | val . [$end]
3 val: . ID
4 | . [$end]
ID shift, and go to state 1
$end reduce using rule 2 (seq)
$end [reduce using rule 4 (val)]
$default reduce using rule 2 (seq)
val go to state 5
実行結果から,シフト・還元 衝突 (shift/reduce conflict) と還元・還元 衝突 (reduce/reduce conflict)
がそれぞれ一つずつあることが分かる.
結果を詳しく見ると,状態 0 で,字句 IDのシフトと規則 4 : 値→ ε での還元が衝突し,状態 3 で,規
則 2 : 列→値 での還元と規則 4 : 値→ ε での還元が衝突している,ということが分かる.シフト・還
元の衝突は前述の左の解析木に対応し,還元・還元の衝突は右の解析木に対応する.
●参考文献
• 『lex & yacc』,J. R. レビン,T. メイソン,D. ブラウン,アスキー,1994.
• GNU Bison — The Yacc-compatible Parser Generator,
https://www.gnu.org/software/bison/manual/bison.html, 2020年 5月 13日閲覧.
27
コンパイラ 解説資料 (山田)
lex と yacc による字句解析と上向き構文解析
lex と yacc を併用すれば,字句と言語の構文定義から,字句解析器と構文解析器を自動生成できる.
●文法 (曖昧な論理式)
次の曖昧な文法から生成される LR構文解析表に,曖昧さ解消規則を付加して,上向き構文解析器を作る.
1 : 式 → 式 || 式
2 : 式 → ! 式
3 : 式 → VAR
この文法は曖昧なため,LR構文解析表で衝突が生じるが,|| が左結合で,! の優先度が || よりも高
い,と約束して,衝突を解消する.例えば,入力字句列 VAR || VAR || VAR と ! VAR || VAR に
対して,次の解析木を得る構文解析器を実現する.
式
gggggggggggggOOOOOOO
式
oooooooOOOOOOO 式
式 式
VAR || VAR || VAR
式
ffffffffffffffTTTTTTTTTT
式
xxxx
xxIII
III式
式
! VAR || VAR
最右導出の逆順 (つまり最左還元の順) は,解析木の内部節の後行順走査に対応する.左の解析木での還
元規則が 3, 3, 1, 3, 1 の順で,右の解析木での還元規則が 3, 2, 3, 1 の順となる解析器ができればよい.
● lex 記述
/* logic.l -- 論理式の字句解析器の仕様 */
%{// 字句解析プログラムに必要な C 言語の宣言#include "logic.tab.h"void yyerror(char *);%}
%%
// 字句構文 と 字句認識動作
! return ’!’; // 1文字の字句"||" return OR; // 複数の文字からなる字句[a-z]+ return VAR; // 変数の字句[ \t\n]+ // 空白類を無視. yyerror("illegal token"); // 他の文字は誤り
%%
// 字句解析プログラムで使う C 言語の関数定義
void yyerror(char *msg) { printf("%s at ’%c’\n", msg, *yytext); exit(1); }
28
● yacc 記述
/* logic.y -- 論理式の構文解析器の仕様 */
%{// 構文解析プログラムで使う C 言語の宣言#include <stdio.h>int yylex(void);void yyerror(char *);%}
// 文法記述のための yacc (bison) 用の宣言
%token OR VAR // 字句解析器と併用する字句
%left OR // OR が左結合 → シフト・還元 衝突 で還元を選択%nonassoc ’!’ // ’!’ を OR より優先 → 〃
%%
// 言語の文法 と 還元動作の C プログラム片
exp : exp OR exp { printf("1: exp -> exp OR exp\n"); }| ’!’ exp { printf("2: exp -> ! exp\n"); }| VAR { printf("3: exp -> VAR\n"); };
%%
// 構文解析プログラムで使う C 言語の関数定義
int main(void) { return yyparse(); }
●実行結果
$ flex logic.l # lex.yy.c を生成$ bison -d logic.y # logic.tab.c を生成し,-d で logic.tab.h も生成$ gcc lex.yy.c logic.tab.c -lfl # 実行ファイルを作成し,-lfl で flex 用ライブラリとリンク
$ echo ’p || q || r’ | ./a.out
3: exp -> VAR3: exp -> VAR1: exp -> exp OR exp3: exp -> VAR1: exp -> exp OR exp
$ echo ’! p || q’ | ./a.out
3: exp -> VAR2: exp -> ! exp3: exp -> VAR1: exp -> exp OR exp
指定した結合性と優先度に沿って,適切な還元順で構文解析が実行される.
●詳細情報
$ flex -T logic.l # 正規表現と状態遷移$ bison -v logic.y && cat logic.output # 文法と状態遷移$ bison -g logic.y && dot -Tpng logic.dot | display # オートマトン
29