• 検索結果がありません。

( ) ( ) lex LL(1) LL(1)

N/A
N/A
Protected

Academic year: 2021

シェア "( ) ( ) lex LL(1) LL(1)"

Copied!
23
0
0

読み込み中.... (全文を見る)

全文

(1)コンパイラ 解説資料集 コンパイラの構成 コンパイラの解析部 (フロントエンド) コンパイラの合成部 (バックエンド) 正規表現 有限オートマトン 正規表現からオートマトンへの変換. lex による字句解析 文脈自由文法 文脈自由文法による導出と解析木 最左導出と解析木 最右導出と解析木 解析木の先行順走査 解析木の後行順走査 下向き構文解析器 文脈自由文法の等価変換 下向き構文解析向け文法 LL(1) LL(1) か否かの判定. 山田 俊行 http://www.cs.info.mie-u.ac.jp/~toshi/lectures/compiler/. 平成 29 年 5 月 14 日. 1.

(2) コンパイラ 第 1 回 解説資料 (山田). コンパイラの構成. コンパイラは,ソースコードを受け取り,何段階かの処理で中間段階の表現を経て,命令列を生成する.. ●構成図. .   文字列. ソースコード. ? 字句解析. 字句列. ? 構文解析. . @ @ @. @ PP i PP @ PP PP R P@ q P 解析木/構文木 1 記号表      ?    ) 意味解析・中間コード生成 中間コード. 命令列. ? 最適化・目的コード生成 ?.  . . 目的コード. . ●基本用語 フロントエンド (front end) コンパイラの処理の前半部分で,ソースコードを解析 バックエンド (back end) コンパイラの処理の後半部分で,目的コードを合成 フェーズ (phase) 処理の論理的なまとまり ※上図の. が各フェーズ. パス (pass) ソースプログラムを先頭から順に読んで行う 1 度の処理 ※いくつかのフェーズを一つのパスにまとめる. 2.

(3) コンパイラ 第 1 回 解説資料 (山田). コンパイラの解析部 (フロントエンド). コンパイラの前半部分であるフロントエンドでは,ソースコードを解析して各要素のもつ意味を調べる. ●ソースコード. var left, right; fun int main() { left = 0; right = 10; return ((left + right) / 2); } ↓. 字句解析. ●トークン列. VAR. ID:left. { (. ID:left = ( ID:left. ↓. 構文解析. ,. ID:right. ;. FUN. INT. ID:main. (. ). NUM:0 ; ID:right = NUM:10 ; RETURN + ID:right ) / NUM:2 ) ; }. ●構文木/解析木.  PROG. (hh (( hhhh (((( hh h . (( SEQ VAR. HH  H.     – SEQ FUN. X HH   HX  X    H X X H  X .     H    – – SEQ SEQ left main INT. . . HH PPP    P P  H    . right = – SEQ.  HH @  @ H   .  = SEQ left 0. @ @ @ @    . right 10 – RET . .  /. @ @  + 2. @ @ .  left right. 3.

(4) コンパイラ 第 1 回 解説資料 (山田). コンパイラの合成部 (バックエンド). コンパイラの後半部分であるバックエンドでは,解析で得たプログラムの情報を元に命令列を合成する. ●抽象構文木. =. HH  H. val. /. HH  H. m. *. HH  H. + n ↓. +. @ @. n. 1. @ @. 1. 意味解析・中間コード生成. ●中間コード. tmp1 tmp2 tmp3 val ↓. = = = =. n + 1 n + 1 tmp1 * tmp2 tmp3 / m. 最適化. tmp1 = n + 1 tmp3 = tmp1 * tmp1 val = tmp3 / m ↓. 目的コード生成. ●目的コード. LD ADD ST LD MUL ST LD DIV ST. R1 n R1 1 tmp1 R1 R1 tmp1 R1 tmp1 tmp3 R1 R1 tmp3 R1 m val R1. 4.

(5) コンパイラ 第 2 回 解説資料 (山田). 正規表現. 正規表現は,選択・連接・反復 を使って文字列集合を表す記法であり,字句の構文を正確に書ける. ●正規表現の定義 文字集合 Σ 上の正規表現を,以下の場合分けで帰納的に定義する.. • ∅ と ϵ は正規表現 • a ∈ Σ ならば,a は正規表現 • R と S が正規表現ならば,選択 (R | S),連接 (R S),反復 (R∗ ) は正規表現 正規表現の括弧を省くときには,選択や連接が結合的(左右どちらから考えても同じ)で,優先順位が 選択 < 連接 < 反復 の順であると約束する.最外の括弧も省ける. ●正規表現が表す文字列集合 正規表現は文字列の集合を表す.その対応を次の表に示す. 正規表現. 文字列集合. 意味. ∅ ϵ. ∅ {ε}. 空集合. a R|S RS. {a} LR ∪ LS { xy | x ∈ LR , y ∈ LS }. 文字単体. { x1 x2 · · · xn | n ≥ 0, x1 , x2 , . . . , xn ∈ LR }. 反復. R. ∗. 空列単体 選択 連接. ここで,ε は (長さ 0 の) 空文字列,xy は文字列 x の後に文字列 y を並べたもの,また,この表では,正 規表現 R と S が表す文字列集合を LR と LS で表した. ●正規表現による字句構文の定義例. 2 進定数の字句構文の定義を正規表現を使って書く.2 進定数とは,集合 { 0, 1 } 上の長さ 1 以上の文字 列のうち,先頭が 0 なら長さが 1,という条件を満たすものである,と定義する.正規表現を使えば,こ の定義は,2 進定数 ::= 0 | 1 ( 0 | 1 )∗ と簡潔に書ける. ●参考文献. • 『オートマトン 言語理論 計算論 I』,第 2 版, J. ホップクロフト,R. モトワニ,J. ウルマン,サイエンス社,2003. 形式言語と計算機械についての標準的な教科書,第 3 章 正則表現と正則言語 を参照.. • 『詳説 正規表現』,第 3 版, J. E. F. フリードル,オライリー・ジャパン,2008. 正規表現の仕組みや利用法の詳しい解説.. 5.

(6) コンパイラ 第 2 回 解説資料 (山田). 有限オートマトン. 有限オートマトンは,文字列の認識機械の数学モデルである.入力を 1 文字ずつ読んで状態遷移し, 入力文字列がパターンに合うかを判定できる. ●有限オートマトンの定義. (決定性) 有限オートマトンは,次の五つ組 (Q, Σ, δ, q0 , F ) で定まる. Q · · · 状態の有限集合 Σ · · · 入力文字の有限集合 δ q0 F. ··· ··· ···. 遷移関数,状態 q と入力文字 a から次状態 δ(q, a) を決定 開始状態,q0 ∈ Q 受理状態集合,F ⊆ Q. ●有限オートマトンの図示 有限オートマトンは,遷移図でも表せる.状態は円内に書き,遷移は入力文字を添えた矢印で表す.開 始状態は始点に状態がない矢印の終点に示し,受理状態は 2 重丸で表す.. a,b / ?>=< 89:; 89:; 0123 7654 / ?>=< A B    0,1,% %     ?>=< 89:; C J a,b,0,1,%. a,b,0,1. この例で,状態集合は Q = { A, B, C },入力文字集合は Σ = { a, b, 0, 1, % },遷移関数 δ は,以下の遷移 表でも表せる.開始状態は q0 = A,受理状態集合は F = { B } である.. δ. a. b. 0. 1. %. A. B. B. C. C. C. B C. B C. B C. B C. B C. C C. 有限オートマトンは,初期状態から始めて,入力文字列を 1 文字ずつ読み,現状態と読んだ文字に応じ て状態遷移する.入力を読み終えたときに受理状態なら,入力文字列を (正しい綴りとして) 受理する. 例えば,入力文字列 ab1 は,このオートマトンで受理される.状態が A, B, B, B と遷移し,入力を読み 終えた状態 B が受理状態だからである.一方,入力文字列 b0%a は,このオートマトンで受理されない. 状態が A, B, B, C, C と遷移し,入力を読み終えた状態 C が受理状態でないからである. ●参考文献. • 『オートマトン 言語理論 計算論 I』,第 2 版, J. ホップクロフト,R. モトワニ,J. ウルマン,サイエンス社,2003,第 2 章 有限オートマトン.. 6.

(7) コンパイラ 第 2 回 解説資料 (山田). 正規表現からオートマトンへの変換. 字句構文を正規表現で書けば,構文に合う文字列を受理する抽象機械 (字句解析器) へと自動変換できる.. ●正規表現 (字句構文の定義に使用). 0 | 1 ( 0 | 1 )∗ ↓. 再帰的に合成. ●非決定性有限オートマトン (複数の遷移先や空語遷移を許可). / ?>=< 89:; B. ε. 0 / ?>=< 89:; C. ε ε. ?>=< / 89:; A. ε. % 1 / ?89:; ε / ?>=< ?>=< 89:; >=< 89:; E F G. z ε ε / ?>=< 89:; H ε. ε ?>=< 89:; / I. 0 / 89:; ?>=< J. 89:; - ?>=< M. 1 / 89:; ?>=< N. ) 89:; ?>=< 7654 0123 9 D. ε / 89:; ε / 89:; ?>=< ?>=< K > L D ε. ε ↓. 遷移先を集合に統合. ●決定性有限オートマトン (状態と入力から遷移先が一つに決定). 0, 1

(8) =< /?> 89{ }:;. 0, 1 ?> /. =< -, 89 (){ C, D }*+ :; 3 h 0hhhhh hhhh ?> =< /89{ A, B, E }:; 1 0 VVVV 1 VV+

(9)

(10) ?> /. =< 0 ?> -, =< 1 /?/. -, > =< -, / /. 89 (){ F, G, H, I, M, L, D }*+ :; 89 (){ J, K, H, I, M, L, D }*+ :;o 89 (){ N, K, H, I, M, L, D }*+ :; 7 0 1 ↓. 区別できない状態を統合. ●状態数最小の決定性有限オートマトン (字句解析に使用). 0, 1  7654 0123 !"# 0, 1 / 7654 0123 : '&%$ u 0uuu uu u 0123I / 7654 II 0, 1 II I  1 I7654 $ '&%$ 0123 !"#. 7.

(11) コンパイラ 第 2 回 補助資料 (山田). lex による字句解析. lex を使うと,字句解析プログラムを自動生成できる.lex 記述では,字句の構文規則を正規表現で与え, 動作規則をコード片として書く. ● lex 記述の例 /* * cprime.l -- CPrime 言語の字句構文の flex 記述 * * 使い方: flex cprime.l && gcc lex.yy.c -lfl && ./a.out < input.txt */ %% var fun void int if else while return "==" "!=" "<=" ">=" [+\-*/%<>=(){},;] [0-9]+ [_a-zA-Z][_a-zA-Z0-9]* [ \t\n]+ .. printf("VAR "); printf("FUN "); printf("VOID "); printf("INT "); printf("IF "); printf("ELSE "); printf("WHILE "); printf("RETURN "); printf("EQ "); printf("NEQ "); printf("LEQ "); printf("GEQ "); printf("%c ", *yytext); printf("NUM:%s ", yytext); printf("ID:%s ", yytext); /* 空白類を無視 */ printf("??? "); /* 誤り */. %% int main(void) { yylex(); printf("\n"); return 0; }. ●実行例 入力 if else while return var fun void int + - * / % > >= < <= == != = ( ) { } , ; 123 value @ var x; fun void main() { x = 5; }. 出力 IF ELSE WHILE RETURN VAR FUN LEQ EQ NEQ = ( ) { } , ; FUN VOID ID:main ( ) { ID:x. VOID INT + - * / % > NUM:123 ID:value ??? VAR = NUM:5 ; }. 8. GEQ < ID:x ;.

(12) コンパイラ 第 3 回 解説資料 (山田). 文脈自由文法. 文脈自由文法は,生成規則を使って記号列の集合を表す記法であり,言語の構文定義を正確に書ける. ●文脈自由文法の定義 文脈自由文法 (context-free grammar) は,次の四つ組 (V, T, P, S) で定まる.. V. ···. 変数 (variable)(非終端記号ともいう) の有限集合. T P. ··· ···. 終端記号 (terminal symbol) の有集限合. S. ···. 開始記号 (start symbol),S ∈ V. 生成規則 (production rule) A → α の有限集合,A ∈ V, α ∈ (V ∪ T )∗. ここで,V ∪ T の要素を文法記号といい,規則の右辺 α は 0 個以上の文法記号が並んだ列である. ●文法による構文定義の例 文脈自由文法を使えば,コンパイラが扱う言語の構文を厳密に定義できる.字句解析で得られる字句を 終端記号とみなし,一つの構文単位に対して文法の変数 (非終端記号) を割り当てて,各構文の生成のし かたを規則として書く. 識別子 ID,数 NUM,四則演算,括弧,からなる算術式の集合を,次の文脈自由文法で定める.. 1:. E. → (E+E). 5:. E. → ID. 2: 3: 4:. E E E. → (E-E) → (E*E) → (E/E). 6:. E. → NUM. この例で,非終端記号の集合は V = { E },終端記号の集合は T = { (, ), +, -, *, /, ID, NUM },生成規 則の集合 P は上の 6 個の規則からなる集合,開始記号は E ,である.なお,生成規則の左の番号は,解 説のためのもので文法の一部ではない.左辺が同じ生成規則をまとめて,次のように書いてもよい.. E → ( E + E ) | ( E - E ) | ( E * E ) | ( E / E ) | ID | NUM ●文法による導出 文法に沿った正しい終端記号 (字句) 列は,開始記号から始めて生成規則を繰り返し使って導出できる. 上記の文法による導出の例を示す.. E ⇒ ( E + E ) ⇒ ( ( E * E ) + E ) ⇒ ( ( NUM * E ) + E ) ⇒ ( ( NUM * ID ) + E ) ⇒ ( ( NUM * ID ) + NUM ) 生成規則を使って,左辺に一致する部分を,対応する右辺に書き換える.これを ⇒ で示す.この書き換 えの繰り返しを導出といい,⇒∗ で表す.上の導出例で使った規則の番号は,順に 1, 3, 6, 5, 6 である. ●文法が生成する言語 文法が生成する言語とは,開始記号からの導出で得られる終端記号列すべての集合. { w ∈ T ∗ | S ⇒∗ w } である.. 9.

(13) ● CPrime 言語の文法 (参考). C に似た小さな言語の構文を,以下の文脈自由文法で定義する. プログラム. →. 変数宣言 関数定義列. 変数宣言. →. var 識別子系列 ;. 関数定義. →. fun 型 識別子 ( 識別子列 ) { 変数宣言 文列 }. 型. →. void. 文. → | | | | | | |. ID ( 式列 ) ; ID = 式 ; if ( 式 ) 文 else 文 if ( 式 ) 文 while ( 式 ) 文 { 文列 } return 式 ; return ;. 式 等値演算列 比較式 比較演算列 加減式 加減演算列 乗除式 乗除演算列 符号式. → → → → → → → → → | → | | |. 比較式 等値演算列 等値演算子 比較式 加減式 比較式列 比較演算子 加減式 乗除式 加減演算列 加減演算子 乗除式 符号式 乗除式列 乗除演算子 符号式 加減演算子 素式 素式 NUM (式) ID ( 式列 ) ID. 等値演算子 比較演算子 加減演算子 乗除演算子. → → → →. == | != > | < | + | * | / |. 関数定義列. →. 関数定義 関数定義列. 識別子列 識別子系列. → → |. 識別子系列 | ε ID , 識別子系列 ID. 文列. →. 文 文列. 式列 式系列. → → |. 式系列 | ε 式 , 式系列 式. 素式. |. |. ε. int. |. >=. 等値演算列. |. ε. 比較演算列. |. ε. 加減演算列. |. ε. 乗除演算列. |. ε. |. <=. % |. ε. ε. ●参考文献. • 『オートマトン 言語理論 計算論 I』,第 2 版, J. ホップクロフト,R. モトワニ,J. ウルマン,サイエンス社,2003,第 5 章 文脈自由文法と言語.. 10.

(14) コンパイラ 第 3 回 解説資料 (山田). 文脈自由文法による導出と解析木. 文脈自由文法に従って記号列を導出すると,導出に対応する解析木が定まる. ●算術式の導出と解析木 文法. 1: 2: 3:. E E E. → ( E + E ) → ( E - E ) → ( E * E ). 4:. E. → ( E / E ). 5: 6:. → ID → NUM. E E. 最右導出. 最左導出 E ⇒左 ⇒左 ⇒左 ⇒左 ⇒左. (E (( E ( ( ID ( ( ID ( ( ID. +E ) +E ) + ID ) + ID ). /E /E /E /E / NUM. E ⇒右 ⇒右 ⇒右 ⇒右 ⇒右. 4 1 5 5 6. ) ) ) ) ). (E (E (( E + E ) ( ( E + ID ) ( ( ID + ID ). /E / NUM / NUM / NUM / NUM. E X  HX XXX HH X   E E HH  @ @ H E E. 解析木. ( ( ID + ID ) /. NUM. ). 6: 7:. E E. ●算術式の曖昧な文法 文法. 解析木. 1: 2: 3:. E E E. → E + E → E - E → E * E. 4: 5:. E E. → E / E → (E). E Z  Z  E E HH  H E @ @ E E ( ID + ID ) / NUM. → ID → NUM. E  @  @ E E @ @ E. E. ID + ID / NUM. 11. E HH H E. E @ @ E. E. ID + ID / NUM. ) ) ) ) ). 4 6 1 5 5.

(15) コンパイラ 第 4 回 解説資料 (山田). 最左導出と解析木. 文法を使って開始記号から字句列を導出できるとき,最左導出 と 解析木 (と適用した規則の列) が, それぞれ 1 対 1 に対応する.. ●文法 (論理式). 1: 2:. exp exp. → →. exp && exp ! exp. 論理積. 3: 4:. exp exp. → →. VAR CON. 変数. 否定 定数. ●適用規則列. 2 1 3 4 否定 論理積 変数 定数. -. 最左展開. ? 展開部抽出. . 先行順走査. ●最左導出. 下向き最左展開. ?. ●解析木. exp  y. exp HHH  H exp ! HHH  H exp exp &&. ⇒ ! exp  y ⇒ ! exp  y. &&. exp. ⇒ ! VAR &&. exp  y. ⇒ ! VAR && CON. VAR. CON. ●解析木の下向き構築 (最左展開). 2 否定 exp →. 1 論理積 →. exp HH   H exp !. 3 変数 →. exp HH   H exp !   HH  H exp && exp. 4 定数 →. exp HH   H exp !   HH  H exp && exp VAR. 12. exp HH   H exp !   HH  H exp && exp VAR. CON.

(16) コンパイラ 第 4 回 解説資料 (山田). 最右導出と解析木. 文法を使って開始記号から字句列を導出できるとき,最右導出 と 解析木 (と適用した規則の列) が, それぞれ 1 対 1 に対応する. ●文法 (論理式). 1:. exp. →. exp && exp. 論理積. 2: 3:. exp exp. → →. ! exp VAR. 否定. 4:. exp. →. CON. 定数. 変数. ●適用規則列. 1 4 2 3  - 3 2 4 1 - 積 定 否 変 変 否 定 積  逆順. 最右展開. ? 展開部抽出. 上向き構築. 後行順走査. ●最右導出. ?. ●解析木. exp  y ⇒ exp. &&.     y. exp  y. ⇒ exp  y. && CON. ⇒ ! exp  y. && CON. 生成. x    . ⇒ ! VAR && CON. exp   HHH   H exp exp && @ @ exp. !. CON. 還元. VAR. ●解析木の上向き構築. 3. 2. 4. 1. 変数. 否定. 定数. 論理積. →. →. →. →. exp exp (空). VAR. !. exp. @ @ exp. !. VAR. @ @ exp VAR. 13. exp CON. exp  HH  H exp && exp @ @ exp ! CON VAR.

(17) コンパイラ 第 4 回 解説資料 (山田). 解析木の先行順走査. 木の先行順走査では,深さ優先順で節を走査し,各節を初めて訪れた時 (行きがけ) に処理を実行する. 下向き構文解析では,解析木の先行順走査に沿って処理が進む. ●先行順走査の例. exp HHH   H H . !. exp HHH  H   H. exp. VAR. &&. 木の項表現 ( ( )) ( ) exp !, exp exp VAR , &&, exp( CON ). exp. CON. ●再帰アルゴリズム. def traverse( T ) visit( T の根 ) n = T の子の数 for i = 1 to n traverse( T の i 番目の子 ) ●実行例. traverse( exp( !, exp( exp( VAR ), &&, exp( CON ) ) ) ) visit( exp ) traverse( ! ) visit( ! ) traverse( exp( exp( VAR ), &&, exp( CON ) ) ) visit( exp ) traverse( exp( VAR ) ) visit( exp ) traverse( VAR ) visit( VAR ) traverse( && ) visit( && ) traverse( exp( CON ) ) visit( exp ) traverse( CON ) visit( CON ). 14. 1 exp 2 ! 3 exp 4 exp 5 VAR 6 && 7 exp 8 CON.

(18) コンパイラ 第 4 回 解説資料 (山田). 解析木の後行順走査. 木の後順走査では,深さ優先順で節を走査し,各節を最後に訪れた時 (帰りがけ) に処理を実行する. 上向き構文解析では,解析木の後行順走査に沿って処理が進む.. ●後行順走査の例. exp HH  HH   H. !. exp HH  HH   H. exp. VAR. &&. 木の項表現 ( ( )) ( ) exp !, exp exp VAR , &&, exp( CON ). exp. CON. ●再帰アルゴリズム. def traverse( T ) n = T の子の数 for i = 1 to n traverse( T の i 番目の子 ) visit( T の根 ) ●実行例 traverse( exp( !, exp( exp( VAR ), &&, exp( CON ) ) ) ) traverse( ! ) visit( ! ) traverse( exp( exp( VAR ), &&, exp( CON ) ) ) traverse( exp( VAR ) ) traverse( VAR ) visit( VAR ) visit( exp ) traverse( && ) visit( && ) traverse( exp( CON ) ) traverse( CON ) visit( CON ) visit( exp ) visit( exp ) visit( exp ). 15. 1. !. 2 3. VAR exp. 4. &&. 5 6 7 8. CON exp exp exp.

(19) コンパイラ 第 4 回 解説資料 (山田). 下向き構文解析器. 構文解析器を,文法に沿った再帰手続きの集まりとして実現する.この構文解析の実行順は,最左導出 による規則の適用順,つまり,解析木を根から葉に向けて作る順序に対応する. ●文法 (論理式). 1:. exp. →. ( exp op exp ). 2: 3:. exp exp. → →. ! exp VAR. 4: 5: 6:. exp op op. → → →. CON || &&. ●構文解析アルゴリズム 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(). 16.

(20) 補助関数. 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 ) ⇒ ( CON op exp ) ⇒ ( CON && exp ). 1 4 6. ( ( CON ( CON &&. ⇒ ( CON && ( exp op exp ) ) ⇒ ( CON && ( ! exp op exp ) ). 1 2. ( CON && ( ( CON && ( !. ⇒ ( CON && ( ! VAR op exp ) ) ⇒ ( CON && ( ! VAR || exp ) ) ⇒ ( CON && ( ! VAR || VAR ) ). 3 5 3. ( CON && ( ! VAR ( CON && ( ! VAR || ( CON && ( ! VAR || VAR ( CON && ( ! VAR || VAR ) ). 入力が ! VAR && VAR のとき 結果. 2: exp -> ! exp 3: exp -> VAR syntax error at token ’&&’. 17.

(21) コンパイラ 第 4 回 解説資料 (山田). 文脈自由文法の等価変換. 2 種類の等価変換 (括り出し,左再帰の除去) を使って文法を変形し,生成する言語を変えずに,下向き 構文解析に適した文法を得る. ●括り出し (factoring) 例:代入文 右辺の先頭に共通部分がある文法の例. 1:. stm. →. ID = NUM. 1 : stm. → ID = atom. 2:. stm. →. ID = ID. 2 : atom 3 : atom. → NUM → ID. 変換前の規則の右辺から共通の先頭部分 ID = を括り出し,変換後の規則 1 にまとめて, 変換前の二つの規則の差分を表す新規則を変換後の規則 2, 3 として追加した. 例:算術式 右辺の先頭と末尾に共通部分がある文法の例. 1:. exp. →. ( exp + exp ). 1 : exp. → ( exp op exp ). 2: 3:. exp exp. → →. ( exp * exp ) VAR. 2 : exp 3 : exp. → VAR → NUM. 4:. exp. →. NUM. 4 : op 5 : op. → + → *. 変換前の規則 1, 2 の右辺から共通部分 ( exp と exp ) を括り出し,変換後の規則 1 にま とめて,変換前の規則 1, 2 の差分を表す新規則を変換後の規則 4, 5 として追加した. 括り出しの一般形 右辺の先頭と末尾に共通部分がある規則の変換. A → A →. αβ1 γ αβ2 γ. A B. → →. αBγ β1. B. →. β2. 上記の代入文の例のように,γ が空列で左側の共通部分 α だけを括り出す特別な場合を, 左括り出しと呼ぶ.. 18.

(22) ●左再帰の除去 定義 文法が左再帰. :⇐⇒ A ⇒+ Aα となる変数 A ∈ V と文法記号列 α ∈ (V ∪ T )∗ がある. 例:数列. 0 個以上のものの並びを表す文法の例 1:. list. → list NUM. 1 : list. →. NUM list. 2:. list. → ε. 2 : list. →. ε. 例:区切り付き数列 区切り記号や演算子を挟んだ,1 個以上のものの並びを表す文法の例. 1: 2:. seq seq. → seq , NUM → NUM. 1 : seq 2 : seq ′. → →. NUM seq ′ , NUM seq ′. 3 : seq ′. →. ε. 具体的な字句列に対する解析木の対応を考えると,変換の意味が分かりやすい.. seq. seq   . seq HH H ′ seq P QPP Q Q P seq ′ P QPP Q QP. seq   . NUM , NUM , NUM. 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 節 文法の記述.. 19.

(23) コンパイラ 第 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(α′ ) = ∅ と表せる.. 20.

(24) ●後続字句を考慮した先頭字句の重なり解消 例:数列 列. → 列 NUM | ε. 列. → |. NUM 列 ε. 規則に空列 ε があると,右辺から導出できる先頭字句の重なりを防ぐだけでは不十分であ る.左の文法による,入力 NUM の最左導出は,まず上の規則で「列」から「列 NUM」 を生成し,次に下の規則で「列」から「ε」を生成する.つまり,先読み字句が NUM とい う情報だけでは,解析時にどちらの規則を使うか決められない. この問題を解消するには,左の文法の左再帰を除去し,文法の右辺の「列」の後に字句が続 かないようにする.そうすれば,入力の終端に達したときだけ下の規則を選べばよくなる. 構文解析できる文法の条件:LL(1) 文法 規則 A → α の右辺 α から空列 ε を導出できるとき,規則の先読み字句として,α から導 出できる先頭字句の他に,字句列の導出で A に続く字句も含める必要がある. 文法記号列 α から導出できる先頭字句の集合 First(α) を { {a ∈ T | α ⇒∗ aβ となる β ∈ (V ∪ T )∗ がある } First(α) := {a ∈ T | α ⇒∗ aβ となる β ∈ (V ∪ T )∗ がある } ∪ {ε}. (α ̸⇒∗ ε のとき) (α ⇒∗ ε のとき). で定め,開始記号 S からの導出で左辺 A に続く字句の集合 Follow(A) を. Follow(A) := {a ∈ T ∪ {$} | S$ ⇒∗ αAaβ となるα ∈ T ∗ , β ∈ (V ∪ T ∪ {$})∗ がある } と定める.ただし $ は入力終端を表す記号で,$ ̸∈ V ∪ T とする.規則の先読み候補とな る字句の集合 Director(A → α) を { First(α) Director(A → α) := 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 節 下向き構文解析.. 21.

(25) コンパイラ 第 5 回 解説資料 (山田). LL(1) 文法か否かの判定. LL(1) 文法は,再帰下降型の構文解析に適する文法である.規則右辺の First 集合,規則左辺の Follow 集合,規則の Director 集合,の 3 種類の集合を求めて,文法が LL(1) か否かを判定する. ● LL(1) でない文法の例 (整数列). First 集合 (右辺が導出する先頭字句か空列 ε) A → α → |. 列. → 符号 → | 数. |. First(α). 列 数. ε 符号 NUM. + ε. (ア) 右辺 α の先頭字句や ε (イ) 右辺 α の先頭の非終端記号の First (ウ) 直前の非終端記号が ε を生成できるとき,右辺の残りの First Follow 集合 (左辺の後続字句か入力終端 $) A → α. First(α). 列. →. 列 数. {+, -, NUM}. 数. | →. ε 符号 NUM. {ε} {+, -, NUM}. → | |. + ε. {+} {-} {ε}. 符号. Follow(A). (ア) 開始記号に続く $ (イ) 右辺中の A に続く列の First (ウ) 右辺中の A に続く列が ε を生成できるとき,その左辺の Follow Director 集合 (規則の先読みの候補字句か入力終端 $) A → α 列. → |. → 符号 → 数. | |. First(α). Follow(A). {+, -, NUM} {ε}. {$, +, -, NUM}. +. {+, -, NUM} {+}. {$, +, -, NUM} {NUM}. ε. {-} {ε}. 列 数. ε 符号 NUM. (ア) 右辺 α の First (イ) 右辺 α の First に ε があるとき,左辺 A の Follow 22. Director(A → α).

(26) ● LL(1) 文法の例 (整数列) 符号付き数列の文法は, 「列」の規則間で先読み字句が重なる.左再帰の除去で文法を等価 変換すれば,この問題を解消できる.. A → α 列. →. | 数 → 符号 → | |. First(α). Follow(A). Director(A → α). 数 列. ε 符号 NUM + ε. ● LL(1) でない文法の例 (含意の論理式) 論理定数 CON と含意 => からなる論理式を表す次の文法が LL(1) か否かを調べるため, 先読み字句の集合を計算する.この文法には ε が現れないので,各規則の先読み字句は. First 集合だけで決まる. A → α 式. →. | 素式 → |. First(α). 素式 => 式. {(, CON}. 素式. {(, CON} {(} {CON}. ( 式 ) CON. 左辺が「式」の二つの規則間に共通の先読み字句 ( と CON があるので,この文法は LL(1) ではない. ● LL(1) 文法の例 (含意の論理式) 先読み字句の重なりを解消するため,括り出しで文法を等価変換する.変換後の文法に対 して First, Follow, Director,の 3 種類の集合を計算する.. A → α 式 ′. 式. → →. | 素式 → |. First(α). Follow(A). Director(A → α). => 式. {(, CON} {=>}. {$, )} {$, )}. {(, CON} {=>}. ε ( 式 ) CON. {ε} {(} {CON}. {$, ), =>}. {$, )} {(} {CON}. 素式 式′. 左辺が「式」の規則は,一つしかないので先読み字句の重なりを生まない (実際には,こ の規則の Director 集合を求めなくても LL(1) の判定ができる). 「式’」の規則の先読み字 句の集合は,{=>} と {$, )} で互いに素である. 「素式」の規則の先読み字句集合も,{(} と {CON} で重ならない.以上のことから,変換後の文法は LL(1) である.. 23.

(27)

参照

関連したドキュメント

[r]

Mochizuki, Topics in Absolute Anabelian Geometry III: Global Reconstruction Algorithms, RIMS Preprint 1626 (March 2008)..

※ 1

参加方式 対面方式 オンライン方式 使用可能ツール zoom Microsoft Teams. 三重県 鈴鹿市平田中町1-1

いまし *1 加を累ぬる \ovalbox{\tt\small REJECT} よ,乗と号し,減を累ぬる□□ \ovalbox{\tt\small REJECT}

方式で 45 ~ 55 %、積上げ方式で 35 ~ 45% 又は純費用方式で 35 ~ 45 %)の選択制 (※一部例外を除く)

BIGIグループ 株式会社ビームス BEAMS 株式会社アダストリア 株式会社ユナイテッドアローズ JUNグループ 株式会社シップス

三洋電機株式会社 住友電気工業株式会社 ソニー株式会社 株式会社東芝 日本電気株式会社 パナソニック株式会社 株式会社日立製作所