ppt

B演習(言語処理系演習)第4回
田浦
構文解析器
def fib ( n ):
if n < 2:
return 1
else:
return …
構文解析器
字句列(token stream)
構文木
“fib”
def
n
if
<
n
…
2
全体像

データ型定義
• 各構文の種類(変数, 演算式, 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
…
tの現在の字句 A?
(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)
例 : リスト

整数のリスト
• 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

Download Report