B演習(言語処理系演習)第4回 田浦

構文解析器 def fib ( n ): if n < 2: return 1 else: return … 字句列(token stream) 構文解析器 構文木 “fib” n 2 … def if <

全体像 データ型定義 コンストラクタ 構文解析器本体 各構文の種類(変数, 演算式, def, for, etc.)ごとに, その種類の構文木の定義 (typedef struct …) 式すべて, 文すべてを表す構文木の定義 コンストラクタ 各種類の構文木を作る関数 構文解析器本体 各構文の種類ごとに, 字句解析器から字句の列を受け取り, その構文木を作る関数

構文木の定義(文の例) typedef struct stmt_while { /* while文 */ … } stmt_while, * stmt_while_t; typedef struct stmt_for { /* for文 */ … } stmt_for, * stmt_for_t; typedef struct stmt_fundef { /* def文 */ … } stmt_fundef, * stmt_fundef_t; … typedef struct stmt { /* 文全体 */ stmt_kind_t k; /* 種類 */ union { … } } stmt, * stmt_t;

while文の例 typedef struct stmt_while { /* while文 */ expr_t e; /* 条件部分 */ stmt_vec_t body; /* 繰り返し本体 */ } stmt_while, * stmt_while_t このように, 個々の構文の種類に対し, その構成要素(while文であれば条件式と本体)をフィールドに持つような構造体を作る 文法定義を眺めれば, 個々の構造体がどのようなフィールドを持たねばならないかがわかる

コンストラクタ 個々の構文の種類ごとに, その種類の構文木を作るような関数を作る stmt_t mk_stmt_while(expr_t e, stmt_t s, …) { … } stmt_t mk_stmt_for(char * x, expr_t e, stmt_t s, …) { … } 注: …のところには, ソースコード上の位置情報など, 必要な情報を適宜追加することだろう

構文解析器の作成 以上の「準備」ができていると仮定して, 実際の構文解析(字句の列から構文木を作る)処理について考える

文法定義の読み方(1) 単純な連結 例 (while文): while_stmt ::= "while" expression ":" suite 読み方: while_stmt (とみなされる字句の列)とは， “while” (というただひとつの字句からなる列) expression (とみなされる字句の列), “:” (というただひとつの字句からなる列) suite (とみなされる字句の列) をこの順に並べたものである

文法定義の読み方(2) 複数選択肢 例 (文全体) statement ::= expression_stmt NEWLINE | assignment_stmt NEWLINE | … | while_stmt | for_stmt | funcdef statement (とみなされる字句の列)とは, assignment_stmt とみなされる字句の列とNEWLINEというただひとつの字句からなる列をこの順で連結したもの, または, …, または funcdefとみなされる字句の列, のいずれかである

構文解析器の仕組み概要(1) LL(1)文法用再帰下向き構文解析法 文法記号Aに対し，関数 parse_A(tokenizer_t t, …) を定義 渡されたtから生成されるいくつかの字句列がA(とみなされる字句列)であれば，そこまで字句列を読み込んで，Aを表す構造体を作って返す さもなければエラー(行番号など)を表示して終了(exit)

… … 構文解析器の仕組み概要(2) parse_A(t, …)開始時 t A? parse_A(t, …)終了時 t tの現在の字句(tok_cur_token_XXX(t)) parse_A(t, …)終了時 … t tの現在の字句(tok_cur_token_XXX(t))

各記号ごとの構文解析器の導出 文法規則から(機械的に)導く 基本アイデア A -> B C D に対し， parse_A(tokenizer_t t) { parse_B(t); parse_C(t); parse_D(t); } 注: 構文木を組み立てる部分は省略

複数の選択肢がある場合 例 : A -> B C D | E F G 現在の字句によってどちらをとるべきかを選択する parse_A(tokenizer_t t) { if (現在のtokenがB C Dの先頭になりうる) { parse_B(t); parse_C(t); parse_D(t); … } else if (E F Gの先頭になりうる) { parse_E(t); parse_F(t); parse_G(t); … } else parse_err(t); }

構文解析器の課題 プログラムを読み込み，構文木を作って，またそれをprintする main() { tree = parse_program(…); print_program(tree, …); } (空白やコメント以外は)まったく同じプログラムが出力されるはず 出力された文字列をもう一度同じプログラムに入れてみる．今度はまったく同一の文字列が出てくるはず

./parser a.py > b.py ./parser b.py > c.py diff b.py c.py 注: a.py と b.py はコメントや空白を除き同一 b.py と c.py は同一の文字列

自然なソースコードの構成 syntree.h : 構文木のtypedefおよびコンストラクタの宣言 syntree.c : 多数のコンストラクタ(mk_A)の定義 parser.h : トップレベルの構文解析器(parse_file_input)の宣言 parser.c : 多数の構文解析器(parse_A)の定義(syntree.hを#include)

いくつかのヘルプ 原理がわかっていても実際にたくさんの構造体定義や関数を書くのは大変なので少しテンプレートを提供する syntree.h almost_empty_parser.c parser.c において, 少数の解析木だけを説明用に残し, あとはほとんど空にしたもの 使うと作業の道筋がわかりやすくなるとは思うが, これの「解読」に明けくれないように注意(基本アイデアは説明したとおり)

プリント修正(HP上のPDFは修正済み) 資料(3) 字句解析器 p20. 4.4節 最後の行 cs_cur_lineを実現するために…  cs_cur_line_stringを実現するために… p21. 4.5節 tokenizer の定義内 char_buf_t str_buf; /* 現在の行の先頭の空白の数 */  char_buf_t str_buf; /* 現在の行(先頭から現在の文字まで)を保持 */ int_vec_t indents;  int_stack_t indents;

ここまでを前半の課題とする 締め切り … 詳しくはHPにアナウンスする(まだしてない) 「できました」報告は別途メール subversionに”parser”という名前のモジュールを登録 ソース&Makefile checkoutして “make” で“parser”という名前のプログラムができるようにしておく ./parser プログラムファイル名 でプログラムの構文解析を行い，その構文木をまたプログラムに戻して表示 「できました」報告は別途メール 班番号，checkoutすべきモジュール名を報告

C言語雑学 汎用コンテナ コンテナ(入れ物) 頻出(多くのプログラミング言語で，ライブラリとして提供，または組み込み) リスト，ハッシュ表，探索木，etc. 頻出(多くのプログラミング言語で，ライブラリとして提供，または組み込み) C++ STL Javaクラスライブラリ Python 辞書，リスト，タプル

コンテナの何が問題か コンテナ実装のロジックは，入れるものが何であってもほとんど同じ にもかかわらず，intの入れ物と，char *の入れ物を別々に定義しなくてはならない 例 : リスト of T (Tを入れるリスト) typedef struct T_list { … } * T_list_t; T_list_t mk_T_list(); void list_append(T_list_t l, T x); T list_get(T_list_t l, int i)

例 : リスト 整数のリスト char * のリスト int_list_t mk_int_list(); void int_list_append(int_list_t l, int x); int int_list_get(int_list_t l, int i); char * のリスト string_list_t mk_string_list(); void string_list_append(string_list_t l, char * x); char * string_list_get(string_list_t l, int i);

選択肢? [その1]: あきらめて似たコードを何度も書く [その2]: int_listだけを定義する．そして思い切って(笑), int_listにchar *を入れてみる int_list_t l = mk_int_list(); int_list_append(l, “hello”); char * x = int_list_get(l, 0); 実は，ある場合には[その2]が機能する

そもそも[その2]が(一般には)まずい根本的なの原因は，int型の領域(変数, 配列/構造体の要素)にchar *の値を代入するところにある 例: int_list_append(l, “hello”); しかし実際には，char *もintも32 bit整数であるので，実はこの代入によって情報が失われているわけではない char * p = “hello”; int x = p; char * y = x; /* y == p */

C言語における危険だが合法な代入 C言語ではこのような，「機械語上では可能」な代入を(自己責任で)合法としている コンパイラは警告を出すがエラーとはしない char * x = 1000; /* ポインタ := 整数 */ int a[10]; char * p = a; /* char* := int* */ f(int x) { … } f(“hello”); void* はgenericポインタとよばれ，「不明な型」へのポインタを保持するのに慣習的に用いられる

つまり，以下は合法 int_list_t l = mk_int_list(); int_list_append(l, “hello”); char * x = int_list_get(l, 0);

キャストを用いて黙らせることも可能 int_list_t l = mk_int_list(); int_list_append(l, (int)“hello”); char* x =(char*)int_list_get(l, 0); しかし， 無様 間違いを犯す元(一般に，リストに何(int? char*?)が入っているのかを区別する手段がない

ベターな慣習 “汎用版”を一度だけ定義 それらを用いて個々の型に対するコンテナを定義 中身はvoid*としておくのが良い generic_list_t mk_generic_list(); generic_list_append(generic_list_t l, void * x); generic_list_get(generic_list_t l, int i); それらを用いて個々の型に対するコンテナを定義

例 int_list の定義 typedef struct int_list * int_list_t; int_list_t mk_int_list() { return (int_list_t)mk_generic_list(); } int int_list_append(int_list_t l, int x) { generic_list_append((generic_list_t)l, (void *)x); } int int_list_get(int_list_t l, int i) { return (int)generic_list_get((generic_list_t)l, i); }

注: 要するにどんな代入も合法か? もちろん否 ポインタ := 浮動小数点数 ポインタ := 構造体 整数 := 構造体 注: 「構造体へのポインタ」ではなく 構造体A := 構造体B