CUP/JLex

CUP/JLex
情報科学実験Ⅱ
コンパイラ
識別子
字句解析器
ID ASSIGN ID ADD CONST
(トークン列)
構文解析器
rlt := left + 20
(ソースプログラム)
ASSIGN
VAR
ld [%fp - 8], %o1
ld [%fp - 12], %o2
add %o1,%o2,%o1
st %o1, [%fp - 4]
(アセンブリコード)
コード生成器
ADD
VAR CONST
(中間表現)
コンパイラ
フロントエンド
字句解析器
構文解析器
バックエンド
コード生成器
コンパイラコンパイラ
• 目的言語の仕様記述からコンパイラを自
動生成する(1960年中頃から)
一括生成困難
構文解析部(Yacc),字句解析部(Lex)
の自動生成(1970年代はじめ)
CUP/Jlex : Yacc/LexのJava版
BNF(Backus-Naur Form)
• S1とS2を文,Eを式として,
“if E then S1 else S2”は文である
• 文のクラスをstmt,式のクラスをexprとして,
stmt → if expr then stmt else stmt
終端記号(太文字)
生成規則
非終端記号(斜体)
BNF(Backus-Naur Form)
• E → E + E | E * E | ( E ) | - E | id
E
- E
- ( E )
導出
- ( id )
還元
解析木
• E → E + E | E * E | ( E ) | - E | id
E
- E
- ( E )
- ( id )
E
E
E
-
(
id
)
曖昧さ
E → E + E | E * E | ( E ) | - E | id
• id+id*id の構文解析
E
E
E
E
id
E
+
id
*
E
E
E
id
id
E
+
id
E
*
id
曖昧さの除去
E → E + E | E * E | ( E ) | - E | id
E→ E + T | T
T→ T * F | F
F → ( E ) | - F | id
曖昧さの除去
E→ E + T | T
T→ T * F | F
F → ( E ) | - F | id
E
E
T
T
T
F
F
id
+
id
F
*
id
構文解析ルーチン生成系
• Yacc(Yet Another Compiler Compiler)
• 処理系:CUP(Constructor of Useful Parser)
> java java_cup.Main < minimal.cup
> javac parser.java
CUPによる文法記述
Minimal.cup
parser.java
入力
java java_cup.Main
javac
java parser
構文解析プログラム
parser.java
parser.class
出力
expr_list → expr_list expr_part | expr_part
expr_part → expr ;
expr → NUMBER | expr PLUS expr | expr TIMES expr | ( expr )
Minimal.cup :
構文解析ルーチン生成系
• 生成される構文解析器の動作
規則の右辺に
マッチすれば,
左辺で置換え
シフト
入力
E→E+T|T
T→T*F|F
F → ( E ) | digit
digit
+
E
構文スタック
-
digit
···
構文解析ルーチン生成系
• 生成される構文解析器の動作
– 還元
ポップ
プッシュ
digit
E→E+T|T
T→T*F|F
F → ( E ) | digit
F
+
E
構文スタック
-
入力
digit
···
構文解析ルーチン生成系
• 生成される構文解析器の動作
– 還元
ポップ
プッシュ
F
E→E+T|T
T→T*F|F
F → ( E ) | digit
入力
T
+
E
構文スタック
-
digit
···
構文解析ルーチン生成系
• 生成される構文解析器の動作
– 還元
ポップ
T
+
入力
E
E→E+T|T
T→T*F|F
F → ( E ) | digit
E
構文スタック
digit
プッシュ
···
構文解析ルーチン生成系
• 生成される構文解析器の動作
– シフト
プッシュ
E→E+T|T
T→T*F|F
F → ( E ) | digit
-
E
構文スタック
入力
digit
···
expr_list → expr_list expr_part | expr_part
expr_part → expr ;
expr → NUMBER | expr PLUS expr | expr TIMES expr | ( expr )
Minimal.cup :
宣言
翻訳規則
構文解析ルーチン生成系
• 宣言部
–
–
–
–
–
先頭 : packageやimportの宣言を書く.
action code {: … :}; アクションクラス内にコピー.
parser code {: … :}; 構文解析クラス内にコピー.
init with {: … :}; 構文解析の最初に実行.
scan with {: … :}; トークンを取り出すときに
呼び出すべき字句解析のメソッド.
– terminal classname name1, name2, ...;
使用する終端記号(トークン)の宣言.
classは属性の型名(なくても良い).
– non terminal classname name1, name2, ...;
使用する非終端記号の宣言.
classは属性の型名(なくても良い).
構文解析ルーチン生成系
• 翻訳規則部
<左辺> → <選択肢1>|<選択肢2>|···|<選択肢n>
コロン2つと=
<左辺> ::= <選択肢1> {: 意味動作1 :}
|<選択肢2> {: 意味動作2 : }
···
|<選択肢n> {: 意味動作n : }
セミコロン
;
構文解析ルーチン生成系
• 翻訳規則部の意味動作
– 意味動作は対応する生成規則の還元の際に実行
– 右辺の属性は,終端記号あるいは非終端記号
の後に,コロンを付けて変数を指定する.例 expr:e1
– 左辺の属性は,RESULTという変数で表現される.
– 意味アクション内では,属性の変数名を記述する
だけで,参照可.例 {:e1.intValue()+e2.intValue() :}
– 多くの場合,左辺の属性値を右辺の属性値を使っ
て計算する.
expr ::= expr:e1 PLUS expr:e2
{: RESULT = new Integer(e1.intValue() + e2.intValue()); :}
構文解析ルーチン生成系
• トークンの意味値
– 字句解析ルーチンからjava_cup.runtime.Symbol
クラスのインスタンスとして受け渡す.
Class Symbol {
int sym;
/* トークン型*/
int left, right; /* トークンのソースファイルでの位置*/
Object value; /*意味値*/
Symbol(int s, int l, int r, Object v) {
sym=s, left=l; right=r; value=v;
}
}
注:トークン型は,symクラスのstatic変数の値として表現されている.
構文解析ルーチン生成系
• 曖昧な文法の利用法
– +,-,*,/を式の生成規則に記述したい.
E → E + T | E - E | E * E | E / E | ( E ) | - E | number
文法が曖昧 ··· 競合
• 電卓プログラム(minimalNoprec1.cup,minimalNoprec2.cup)
minimalNoprec2.cupの実行結果:
構文解析ルーチン生成系
• 競合の解決
– Yaccによる暗黙の解決
還元-還元競合: 最初の方に書かれた規則を
優先する.
シフト-還元競合: シフトを優先する.
– ユーザ指定によるシフト-還元競合の解決
終端記号に優先順位と結合性を与える.
構文解析ルーチン生成系
• ユーザ指定による競合の解決
Precedence left PLUS, MINUS;
··· PLUSとMINUSの優先順位が同じで左結合.
Precedence right POW; ··· POWは右結合.
Precedence nonassoc EQ, LE, GT; ··· 結合性をも
たない.
– トークンは後の方で宣言されるほど優先順位が
高い
同じ行は
同じ優先順位
優先順位が高い
precedence left PLUS, MINUS;
precedence left TIMES, DIVIDE, MOD;
precedence left UMINUS;
構文解析ルーチン生成系
• ユーザ指定による競合の解決
– 生成規則の優先順位を強制的に変更する.
<生成規則> %prec <終端記号>
precedence left PLUS, MINUS;
precedence left TIMES, DIVIDE;
precedence left UMINUS;
他の入力よりも
expr ::= expr PLUS expr
生成規則の順位が高い
| expr MINUS expr
| expr TIMES expr
還元が優先
| expr DIVIDE expr
| MINUS expr %prec UMINUS
;
• 電卓プログラム
(minimal.cup)
字句解析ルーチン生成系
• Lex (LEXical analysis program generator)
• 処理系 ··· JLex
Yylexクラスの定義を含む
Lexによる仕様記述
minimal.lex
java Jlex.Main
minimal.lex.java
> java java_cup.Main < minimal.cup
> java JLex.Main minimal.lex
> mv minimal.lex.java Yylex.java
> javac –d . *.java
実行: > java Example.parser
トークン表示プログラム(minimal.lex)
ユーザコード
Jlex修飾子
正規表現規則
字句解析ルーチン生成系
• ユーザコード
– packageやimport宣言を記述.
• Jlex修飾子
– %{と%}でくくった部分は,字句解析クラス内にコピー.
– %init{と%init}でくくった部分は,字句解析クラスの
コンストラクタにコピー.
– %eofval{と%eofval}でくくった部分は,ファイルの終わ
りに達したときに返す値を指定.
– %lineを指定すると,yyline変数で,行番号を参照可.
– %charを指定すると,yychar変数で,文字数を参照可.
– %cupを指定すると,CUP用のインタフェースを備える.
– <マクロ名> <正規表現>
・・・正規表現のマクロ指定.{マクロ名}で参照
字句解析ルーチン生成系
• 正規表現の記述
. ···
[ ] ···
*
+
?
|
^
$
···
···
···
···
···
···
改行を除く任意の文字
[と]で囲まれた文字の内,どれか1つ.
^で始まると,その文字以外.
- は範囲を意味する.
0個以上の繰返し
1個以上の繰返し
あるか無いか.
どちらか一方
パターン先頭の^は,入力行の先頭.
パターン最後の$は,入力行の最後
字句解析ルーチン生成系
• グループ化と予約文字のエスケープ
( ) ···
パターンをまとめる.
\ ··· 次の文字をエスケープする.
” ” ··· ”と”で囲まれた部分をエスケープする.
• 曖昧さを除去する規則
– 最長の文字列を表現するパターンを選択
– 2箇所にマッチする場合は,最初のパターン
例 if8
例:
コード生成
プログラムデータ
宣言と境界設定
入出力用
文字列ラベル
実行はmain
ラベルから開始
計算コード
メモリ領域の開放
領域サイズのマクロ
メモリ領域
の確保
コード生成
• 計算コード
– 操作なし: nop
– レジスタ(reg):
%g0(=0),%g1,%g2,%g3,%g4,%g5,%g6,%g7
%i0,%i1,%i2,%i3,%i4,%i5,%i6(%fp),%i7
%o0,%o1,%o2,%o3,%o4,%o5,%o6(%sp),%o7
%l0,%l1,%l2,%l3,%l4,%l5,%l6,%l7
– メモリ参照(mem): [%fp-offset]
– メモリからレジスタへのロード: ld mem,reg
– レジスタからメモリへのストア: st reg,mem
– reg1からreg2への転送: mov reg1,reg2
– reg1とreg2の加算(結果reg3): add reg1,reg2,reg3
– reg1とreg2の減算(結果reg3): sub reg1,reg2,reg3
– regの反転: neg reg
コード生成
• 関数(func)の呼出し: call func,0
手前でセットされた,%o0の値が第1引数,
%o1が第2引数,%o2が第3引数・・・.返値は%o0.
• reg1とreg2の乗算:
mov reg1,%o0
call .umul,0
mov reg2,%o1
• reg1とreg2の除算: .divを乗算と同様に呼び出す.
• ラベル(label): label:
• 無条件ジャンプ:
b label
nop
コード生成
• reg1とreg2の関係演算: cmp reg1,reg2
• 条件ジャンプ: 次の命令の後にnop.
–
–
–
–
–
–
>: bg label
<: bl label
>=: bge label
<=: ble label
== : be label
!= : bne label
コード生成
• データセグメントへの文字列(string)割付:
.seg “data”
label:
.ascii “string\0”
.seg “text”
.align 4
• データセグメントデータ(label)のregへのロード:
sethi %hi(label),tmpreg
or tmpreg,%lo(label),reg
コード生成
• (スタック上での)データ領域の用意:
sethi %hi(label),tmpreg
add tmpreg,%lo(label),reg
save %sp,reg,%sp
・・・
label = -areasize
• データ領域の開放:
ret
restore
コード生成
• 入出力scanf(“%d”,&mem),printf(“%d”,reg):
– 文字列部分は前もってIO0/IO1(出/入)として定義.
IO0:
.ascii "%d\0"
IO1:
.ascii "%d\0"
.seg "text"
.align 4
コード生成
• regの出力:
sethi %hi(IO0),%o1
or %o1,%lo(IO0),%o0
call printf,0
mov reg,%o1
• mem(オフセットoffset)への入力:
sethi %hi(IO1),%o1
or %o1,%lo(IO1),%o0
call scanf,0
sub %fp,offset,%o1