Document

コンパイラ資料
２章字句解析
字句解析の役割
原始プログラム
int fact(int n)
{
int x,y;
if(n=0) x:=1
...
字句解析
ルーチントークン列
構文解析
ルーチン
〈int〉〈id,”fact” 〉〈lparen〉〈int〉〈id,”n”〉
〈rparen〉〈lbrace〉〈int〉〈id,”x”〉
〈comma〉〈id,”y”〉〈semi〉〈if〉〈lparen〉
〈id,”n”〉〈rel,EQ〉〈num,0〉〈rparen〉
〈id,”x”〉〈assign〉〈num,1〉 ....
原始プログラムを字句の種類を表すトークンの列に変換
字句、トークン、パターン、
• 字句は原始プログラムに現れる文字列で
意味を持つ最小の単位
• トークンは字句の種類をあらわし、構文解
析で利用される
• パターンはトークンがあらわす種類の字句
の集合
（kittyコンパイラの）
トークン、パターン、字句
トークン
パターン
if のみ
if
<または … または>=
rel
id
assign
op
semi
num
literal
字句の例
if
<,<=,=,<>,>,>=
英字で始まる英数字列
pi, count, D2
:= のみ
:=
+, -, *, /,
*
; のみ
;
任意の数値定数(整数)
314,0,6455
“core dumped”
“と”の間の文字列
トークンの属性
• トークンだけではもとの情報（数値など）は
失われる。トークンに付随してもと情報を
保持するものがトークンの属性
• トークンの属性は構文解析では使われな
いが記号表参照やコード生成で使われる
トークンの属性の例
x :＝ x*2 ;
のトークンとその属性の対は
<id , “x” >
<assign >
<id, “x” >
<op, prod >
<num, 2>
<semi>
パターンの記述
パターンの記述には正規表現を用いる。
正規表現とその意味:
a はアルファベットの記号を意味するメタ記号、
r(L),s (L)をそれぞれ正規表現r,sのあらわすパターンとして、
正規表現
パターン
f
f
ε
{ε}
a
r ｜s
rs
r*
{a }
r(L) ∪ s (L)
r(L) s (L)
r(L)*
正規表現の例
kittyの識別子：
英字で始まる英数字
(A|B|…|Z|a|b|…|z)
(A|B|…|Z|a|b|…|z|0|1|…|9)*
正規定義
正規表現に名前をつけて、別の正規表現の中で使
えるようにする。
d1  r1
d 2  r2
...
d n  rn
riは {d1 , d 2 ,, di 1}上の正規表現
正規定義の例
kittyの識別子(正規定義版)
letter → A|B|…|Z|a|b|…|z
digit → 0|1|…|9
id → letter(letter|digit)*
略記法
rr *を r
r|εをr?

A|B|Cを[ABC],A|B|…|Zを[A-Z]
と略記する。
略記による正規定義の例
Pascalの符号なし数の正規定義
digit → [0-9]
digits → digit+
optional_fraction → ( . digits)?
optional_exponent → (E(+|-)? digits)?
num → digits optional_fraction
optional_exponent
問い： C言語の浮動小数点定数のパターンを正規定義で書け。
課題: iddfa
• 英字で始まる英数字を受理する有限オー
トマトンを状態遷移図で書け。
• 実装せよ。(標準入力をテープとし、受理し
たときYes,受理しないときNoと印字する)
字句の認識：オートマトンとの違い
1. 複数の字句が連続
x>0
どうやって切り分けるか？
開始
⇒ 字句の切り出し
2. xyz
0
x y z3変数なのかxyzで１つか？
英字
オートマトンならすべて受理
1
⇒ 字句定義で最長一致に限定
英字
字句切り出し
1. 入力バッファの途中で有限オートマトンを模倣
するにはヘッドに対応する走査用のポインタ
（前進ポインタ）の他にテープ左端をあらわす
字句先頭ポインタを用いる。
2. パターンごとに状態遷移図を用い、
1. 受理に失敗したら前進ポインタを字句先頭ポインタ
位置に戻して別のトークンの状態遷移図を調べる。
2. 成功したら字句先頭ポインタを前進ポインタの位置
に移して次の字句を調べる。
字句先頭ポインタと前進ポインタ
buf
x
p
x
<
0
bp
left
buf
1
p
1
xp1受理後
<
0
ｌeft : 字句先頭ポインタ（左端）
left
bp
bp:
前進ポインタ（ヘッド）
開始
最長一致
0
• xyz
最も長くなるように切り取る
英字
英字
1
other
2
*
出る矢印がない状態: 確定
*つき状態で終ったときは1文字オーバーラン
⇒ヘッドを１文字戻し（UNREAD）, 手前の状態で確定
最長一致の例２
開始
>
0
=
3
6
*
other
relの認識（属性値つき）
開始
<
0
LE
NE
LT
EQ
>
3
=
other
6
GE
*
GT
字句解析用オートマトンの
動作まとめ
1. 状態遷移先がある限りヘッドを進めながら遷移を繰り
返す。
2. 最後に到達した状態に*がついていたら最後の状態
遷移とヘッド移動をなかったことにして戻す。
3. 現在の状態が受理状態なら属性値を大域変数
1.
2.
string yy_val
int yy_ival
//文字列用
//整数値用
に書き込み、その状態の番号(≧0)を返す。
受理状態でなければヘッドを左端に戻し、
REJECT(=－1)を返す。
属性値の型
enum Relation {//関係演算子（不等号）の種類
LT, EQ, GT, LE, NE, GE
};
union Attribute {//属性値用共用体
int i_value;
Relation relation;
};
DFAクラス
class DFA{
virtual int move(int state, char c)=0;
public:
bool accept(void);
//acceptは受理したとき
//token,yy_val,attributeをセットして
//trueを返す。
}
class IDDFA : public DFA{
int move(int state, char c);
}
字句解析手順（inr限定）
1. 文字バッファに読み込む。
2. ヘッドをバッファ先頭にセットし次を繰り返す。
a.
id, num, relの各オートマトンで受理するか否かを
順にテストする。（ヘッド位置を左端として開始。左
端が終端なら1へ）
① どれか受理したら（結果を格納してから）左端をヘッド位
置まで進めて次の字句へ（）。（受理しなかったときにヘ
ッドを左端まで戻すのはオートマトンの責任）
② どれも受理しなかったらエラーメッセージ
課題：inr
標準入力からid, num, relの３種類の字句を
すべて認識して、おのおののトークン名（と、
あれば属性値）を印字するプログラムinrを
かけ。
inr実装ヒント
• トークン型をenum Tokenで定義
• すべてのオートマトン共通の仕事（ヘッドの
制御など）はDFAクラスで。オートマトン固
有の仕事（状態遷移など）はIDDFAなどの
派生クラスで。
• 状態遷移関数そのものでmoveをつくると
遷移ごとに受理判定のコストがかかる。
⇒ 受理状態か否かは遷移時にわかるは
ず。受理したら直ちに制御を返す。
要求駆動 demand driven
トークン
要求
字句解析
ルーチン
構文解析
ルーチン
トークン, 属性値
• 外部モジュールからのトークン要求は
get_token()呼び出しで行う。
• get_token()の戻り値でトークン（および属性値）を
要求元に伝達。
課題：ddinr（要求駆動版inr）
前課題を要求駆動型字句解析器で実現せよ。
“inrlexer.cpp”
get_token() は標準入力の次のトークン,属性値
からなる構造体を返す。
“ddinr.cpp”
get_token()をつかってinrとおなじことをやる。
ddinr実装ヒント
• get_token()呼び出し時に
– バッファが処理済なら再読み込み
– 左端の更新
を行ってから受理テスト
kittyの字句仕様
•
•
•
•
•
•
•
•
識別子: 英字で始まる英数字
数値: 数字列
関係演算子: =、 <>、 <=、 >=、 <、 >
代入演算子: :=
算術演算子: +、－、*、/ (別々のトークン)
論理演算子: &、|、 ! 、=> (別々のトークン)
括弧など: (、 )、 {、 }、 ;、 , (別々)
予約語: if else while true false return bool int
print (別々)
kitty字句解析器トークン一覧
id 識別子
num 数値
rel 関係演算子 =, ....
assign 代入演算子 :=
plus
+
minus －
prod
*
div
/
and
&
or
|
not
!
impl =>
lparen
rparen
lbrace
rbrace
semi
comma
(
)
{
}
;
,
if
else
while
true
false
return
bool
int
print
予約語とその他の記号
• while
英数以外(‘\0’
含む)
＊
開始
w
h
i
l
e
英数
reject
与えられた予約語文字列を検出するDFAの
acceptを模倣する関数
bool accept_by_as(Token t, string* str)
を作る。（IDの検出より優先。）
英字以外の記号からなる字句の場合も含めて考えよ
課題：字句解析器 lexer
• kittyの字句解析器lexerを実装せよ。
• lexerのget_tokenを利用するプログラム（ク
ライアント）を適宜作成してテストせよ。
注意：コンパイラでは(次章で学ぶ)構文解析
器がクライアントになる

Download Report