B演習(言語処理系演習)第一回

B演習(言語処理系演習)第3回
字句解析
田浦
今日の予定

字句解析インタフェース
• 今週の課題
字句の定義
 字句解析器の仕組み(概要)

• 下請け部品 char_buf, char_stream, int_stack
まめ知識: デバッガ
 デバッグに関する若干の抽象論

字句解析器とは
字句解析器
(tokenizer)
)
Identifier (n)
(
identifier (fib)
def
‘d’ ‘e’ ‘f’ ‘ ’ ‘f’ ‘i’ ‘b’ ‘(’ ‘n’ ‘)’ ‘:’
今週の課題

字句解析器の作成とそのテスト
• テストプログラム: ファイルから字句を読み出して，
読み出された字句をその順に表示
• 表示の仕方
•
•
•
•
TOK_KW_FOR
TOK_LITERAL_INT (35)
TOK_ID (x)
etc.
• テストデータとその正解があるのでそれを用いて
比較
インタフェース


tokenizer_t t = mk_tokenizer(char * filename);
void tok_next(tokenizer_t t);
• 次の1字句を読み込んで現在の字句に設定




token_kind_t tok_cur_token_kind(tokenizer_t t);
int
tok_cur_token_int_val(tokenizer_t t);
double
tok_cur_token_float_val(tokenizer_t t);
char *
tok_cur_token_str_val(tokenizer_t t);
• 現在の字句に関する情報を返す
インタフェース(2)
正しくエラーメッセージを表示するためのイン
タフェース
 char * tok_cur_token_string(tokenizer_t t);

• 現在構築中の字句の文字列表現

char * tok_cur_line_string(tokenizer_t t);
• 現在の行の文字列表現(現在の字句まで)

そのほか2, 3 (資料参照)
字句解析器のテストプログラム
 int
tokenizer_test(char * filename) {
tokenizer_t t = mk_tokenizer(filename);
while (tok_cur_token_kind(t) != TOK_EOF) {
print_cur_token(t);
tok_next(t);
}
return 0;
}

void print_cur_token(tokenizer_t t) {
char * C_name = tok_cur_token_kind_string(t);
switch(tok_cur_token_kind(t)) {
case TOK_ID:
case TOK_LITERAL_INT:
case TOK_LITERAL_FLOAT:
case TOK_LITERAL_STRING:
printf("%s (%s)\n", C_name, tok_cur_token_string(t));
break;
default:
printf("%s\n", C_name);
break;
}
}

int main(int argc, char ** argv) {
if (argc != 2) {
fprintf(stderr,
"usage : %s filename\n", argv[0]);
exit(1);
} else {
tokenizer_test(argv[1]);
exit(0);
}
}
字句の種類








テキスト，HP参照
or, and, is, not, in, =, ==, !=, >, >=, <, <=, +, -,
*, /, %, ~, <<, >>, ^, &, |,
None,
break, continue, pass, return, del, print,
global, if, elif, else, for, while, def,
(, ), {, }, [, ], ., ,, :,
integer, floatnumber, stringliteral,
identifier
newline, indent, dedent, end_of_file
少し複雑な字句

integer
• 0 | (1|…|9)(0|…|9)*

floatnumber
• (0|…|9)+.(0|…|9)* | .(0|…|9)+

string literal (エスケープ文字の扱い)
• ”(x | \y)*”

identifier
• (a|_)(a|d|_)*

テキストおよびmini-Pythonの文法を参照
注意の必要な字句
end_of_file : 入力終端に達すると生成される
 newline : 改行に対して生成される(無視しない)
 字下げ:

• indent : 字下げを1レベル深くする字句
• dedent : 字下げを1レベル浅くする字句

コメント
字下げ/改行字句生成の例


 
def fib(n):
 if n < 2:
 return 1
else:
 return fib(n-1) + fib(n-2)
def another_fun(…)
…
改行

字下げ(indent)

逆字下げ(dedent)
コメント
基本: #から改行手前までを無視
 行が空白とコメントのみの場合，改行も無視
 例:

• x = y + z # calc x
• id(x), =, id(y), +, id(z), newline
• # calc x first
x=y
# then p
p=q
• id(x), =, id(y), newline, id(p), =, id(q), newline
字句の種類のCプログラムでの定義

typedef enum {
TOK_OR,
/* or */
TOK_AND,
/* and */
…,
…,
TOK_ID,
TOK_NEWLINE,
TOK_INDENT,
TOK_DEDENT,
TOK_EOF
} token_kind_t;
字句のCプログラム内での定義

typedef struct token
{
token_kind_t k;
union {
char * s_val; /* id, 文字列リテラル */
double f_val; /* 浮動小数点数リテラル */
int i_val;
/* 整数リテラル */
} v;
} token, * token_t;
字句解析器の基本的な仕組み

「現在の文字」に基づく場合わけ
• tok_next(tokenizer_t t) {
…
switch (現在の文字) {
case ’%’ : t->tok.k = …; break;
case ’0’..’9’ : t->tok.k = …; break;
}
…
}
いくつかややこしいところ
各種literalとidentifier (正規表現)
 コメントの読み飛ばし
 indent/dedent字句の生成
 現在構築中の行，字句の保持(エラーメッ
セージ用)


いきなりだとどうしていいか悩んでしまう人は，
• newline/indent/dedent 字句を後回しにする
• エラーメッセージ表示(そのための状態管理)を後
回しにする

tok_nextの主要部分(次の文字で場合わけを
しながら，字句の切れ目まで読んでいく．読ん
だtokenをtokにセットする)に集中
有用な下請け部品

char_stream_t
先週からの拡張
• 文字を読み出すための下請け部品
• ファイル名，行番号，列番号，現在行(現在の文字まで)を
維持

char_buf_t
• 文字をためるバッファ(append)
• cur_line, cur_token_string, string literalの読み込み用

int_stack_t
• 整数のスタック
• indent/dedent用
デバッグの心構え

いけないこと
• 平常心を失うこと(「なぜ動かないんだっっ!!」)
• バグが消えてほしいと思うこと
• プログラムをむやみにいじること(うまく動けばラッ
キー，という考え方)

よい心構え
• 目の前の(バグ入り)プログラムの動作を理解・観
察・追跡する
実践的心構え

極力小さな入力でバグを再現する
• どんな入力なら動いて，どんな入力は動かない
か?

(できるだけ小さな入力で)，どこまでまともに
動作し，どこから狂いだすかを追跡する
• printfで変数の値を表示
• デバッガ
「デバッガ」の使い方よりも大切な
「デバッグ」の方法

平常心
• プログラムを直そうとやっきにならない

大切な心構え
• 目の前にあるプログラムの挙動の調査
• どこで「本来の挙動」を逸脱したかの調査
本来の挙動
異常観測地点
プログラム開始時点
実際の挙動
デバッガ
プログラムを実行
 実行途中で停止

• 関数先頭，行番号
• ステップ(１行ずつ)実行

停止した状態で，変数，その他の「状態を観
察」
• 変数の値
• 関数呼び出しの履歴(なぜ今ここにいるか)
起動方法
gcc –g …
 (shell)% gdb プログラム名
 (emacs) M-x gdb

まめ知識: gdbの良く使うコマンド










r コマンドライン引数…
p
bt
b 関数名
b ファイル名:行番号 (Emacs: C-x SPACE)
c
n
s
disp
<RET>で最後のコマンドの繰り返し
メモリ割り当てについて

よく分からない人はmalloc (C++ではnew)が
基本と思っておく
• 関数呼び出し後も生き延びてほしい(使われる)領
域は必ずmallocで割り当てる
tokenizer_t mk_tokenizer()
tokenizer_t mk_tokenizer()
{
tokenizer_t t
{
= (tokenizer_t)malloc(sizeof(tokenizer));
tokenizer t[1];
if (t == 0) { … exit(1); }
t->… = …;
t-> … = …;
…
…
return t;
return t;
}
}
M-x info
 Cut & paste (コピペ)

• C-SPACE … C-w
• C-y
M-x query-replace
 M-x replace-string
 キーボードマクロ


Download Report