B演習(言語処理系演習)第3回 字句解析 田浦

今日の予定 字句解析インタフェース 字句の定義 字句解析器の仕組み(概要) まめ知識: デバッガ デバッグに関する若干の抽象論 今週の課題 下請け部品 char_buf, char_stream, int_stack まめ知識: デバッガ デバッグに関する若干の抽象論

字句解析器とは 字句解析器 ‘d’ ‘e’ ‘f’ ‘ ’ ‘f’ ‘i’ ‘b’ ‘(’ ‘n’ ‘)’ ‘:’ (tokenizer) Identifier (n) ( identifier (fib) def

今週の課題 字句解析器の作成とそのテスト テストプログラム: ファイルから字句を読み出して，読み出された字句をその順に表示 表示の仕方 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 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 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 floatnumber string literal (エスケープ文字の扱い) identifier 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 int_stack_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)が基本と思っておく tokenizer_t mk_tokenizer() { tokenizer_t t 　　= (tokenizer_t)malloc(sizeof(tokenizer)); if (t == 0) { … exit(1); } t-> … = …; … return t; } tokenizer_t mk_tokenizer() { tokenizer t[1]; t->… = …; … return t; }

M-x info Cut & paste (コピペ) M-x query-replace M-x replace-string C-SPACE … C-w C-y M-x query-replace M-x replace-string キーボードマクロ