B演習(言語処理系演習)第3回
字句解析
今日の予定
字句解析インタフェース
• 今週の課題
字句の定義
字句解析器の仕組み(概要)
• 下請け部品 char_buf, char_stream, int_stack
まめ知識: デバッガ
字句解析器とは
字句解析器 (tokenizer) ‘d’ ‘e’ ‘f’ ‘ ’ ‘f’ ‘i’ ‘b’ ‘(’ ‘n’ ‘)’ ‘:’ def identifier (fib) ( Identifier (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
少し複雑な字句
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
字句の種類の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;
字句解析器の基本的な仕組み
「現在の文字」に基づく場合わけ
• 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[1]; t->… = …; … return t; } tokenizer_t mk_tokenizer() { tokenizer_t t = (tokenizer_t)malloc(sizeof(tokenizer)); if (t == 0) { … exit(1); } t-> … = …; … return t; }
M-x info
Cut & paste (コピペ)
• C-SPACE … C-w
• C-y
