文法と言語 ー文脈自由文法とLR構文解析2ー

Slides:



Advertisements
Similar presentations
プログラミング言語論 プログラミング言語の構 文 水野嘉明. 目次 1. プログラミング言語の構文 2. BNF 3. 文脈自由文法 4. 構文図式 2.
Advertisements

プログラミング言語論 第3回 BNF 記法について(演習付き) 篠埜 功. 構文の記述 プログラミング言語の構文はどのように定式化できるか? 例1 : for ループの中に for ループが書ける。 for (i=0; i
和田俊和 資料保存場所 /2/26 文法と言語 ー正規表現とオートマトンー 和田俊和 資料保存場所
プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
コンピュータープログラミング(C言語)(2) 1.文字列出力と四則演算 (復習) 2.関数と分割コンパイル
文法と言語 ー字句解析とオートマトンlexー
プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
Problem by D. Mikurube Slides by Y. Izumi
東京工科大学 コンピュータサイエンス学部 亀田弘之
言語処理系(7) 金子敬一.
コンパイラ 2011年10月17日
言語処理系(6) 金子敬一.
文法と言語 ー文脈自由文法とLR構文解析2ー
文法と言語 ー文脈自由文法とLL構文解析ー
プログラミング言語論 第4回 式の構文、式の評価
言語処理系(5) 金子敬一.
プログラミング演習Ⅰ 課題2 10進数と2進数 2回目.
コンパイラ 2012年10月15日
コンパイラ 2012年10月22日
東京工科大学 コンピュータサイエンス学部 亀田弘之
コンパイラ 2011年10月24日
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
コンパイラ 第14回 上昇型構文解析(2) 38号館4階N-411 内線5459
ちょっとした練習問題① 配列iroを['R', 'W', 'R', 'R', 'W' , 'W' , 'W']を宣言して、「W」のときの配列の番号をprintfで表示するようなプログラムを記述しなさい。
東京工科大学 コンピュータサイエンス学部 担当 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
プログラミング言語論 第3回 BNF記法について(演習付き)
文法と言語 ー字句解析とオートマトンlexー
文法と言語 ー字句解析とオートマトンlexー
FlexとBison+アルファ -実習編-
暗黙的に型付けされる構造体の Java言語への導入
形式言語の理論 5. 文脈依存言語.
前回の練習問題.
第7回 プログラミングⅡ 第7回
コンパイラ 第13回 上昇型構文解析(1) 38号館4階N-411 内線5459
言語と文法 言語とは,ルールに従う記号列の無限集合である. 文法を与えることで言語が定義できる.
文法と言語 ー文脈自由文法とLR構文解析2ー
東京工科大学 コンピュータサイエンス学部 亀田弘之
言語プロセッサ ー第9回目ー 構文解析(続き).
文法と言語 ー文脈自由文法とLR構文解析3ー
整数データと浮動小数データ.
東京工科大学 コンピュータサイエンス学部 亀田弘之
プログラミング言語論 第9回 情報工学科 木村昌臣 篠埜 功.
文法と言語 ー文脈自由文法とLL構文解析ー
コンパイラ 2011年10月20日
東京工科大学 コンピュータサイエンス学部 担当 亀田弘之
B演習(言語処理系演習)第2回 田浦.
C言語 はじめに 2016年 吉田研究室.
統計ソフトウエアRの基礎.
C++ 構文解析 構文解析器の状態保存と復元
地域情報学 C言語プログラミング 第2回 変数・配列、型変換、入力 2017年10月20日
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 担当 亀田弘之
文法と言語 ー文脈自由文法とLR構文解析ー
コンパイラ 2012年10月29日
計算の理論 I -プッシュダウンオートマトン-
文法と言語 ー字句解析とオートマトンlexー
4.プッシュダウンオートマトンと 文脈自由文法の等価性
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
コンパイラ 2012年10月11日
言語プロセッサ ー第9回目ー 構文解析(続き).
言語プロセッサ ー第7回目ー 構文解析(続き).
東京工科大学 コンピュータサイエンス学部 亀田 弘之
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
:: の扱い 長谷川啓.
プログラミング入門2 第5回 配列 変数宣言、初期化について
情報処理Ⅱ 小テスト 2005年2月1日(火).
岩村雅一 知能情報工学演習I 第7回(後半第1回) 岩村雅一
第1章 文字の表示と計算 printfと演算子をやります.
4.2 再帰下降解析 (1)再帰下降解析とは ■再帰下降解析(Recursive Descent Parsing)
Presentation transcript:

文法と言語 ー文脈自由文法とLR構文解析2ー 2019/8/26 文法と言語 ー文脈自由文法とLR構文解析2ー 和田俊和 資料保存場所 http://vrl.sys.wakayama-u.ac.jp/~twada/syspro/

2019/8/26 前回までの復習

最右導出と上昇型構文解析 最右導出を前提とした場合,上昇型の構文解析がしばしば用いられる. 上昇型構文解析では生成規則の右辺にマッチする部分を見つけ,それを左辺の非終端記号に置き換える「還元(reduction)」という操作を繰り返し,出発記号に到達するという 導出 還元

還元操作を行うには手がかりが必要 <算術式>→<算術式><加減演算子><項>   という生成規則の右辺にマッチする部分を  1-2-3-4  という記号列から見つける問題を考える. 明らかに”1-2-3”が右辺の<算術式>に,次の”ー”が<加減演算子>に,そして”4”が<項>に対応付けられる. これをどうやって見つけるかが問題

LR法例題 アクション * + 1 $ E B s1 s2 3 4 r4 2 r5 s5 s6 r3 5 7 6 8 r1 r2 文法の例 2019/8/26 アクション GOTO 状態 * + 1 $ E B s1 s2 3 4 r4 2 r5 s5 s6 acc r3 5 7 6 8 r1 r2 文法の例 (1) <E> →<E>*<B> (2) <E> →<E>+<B> (3) <E> →<B> (4) <B> → 0 (5) <B> → 1

アクション表と,GOTO表 2019/8/26 アクション表は状態と終端記号でインデックス付けされている(終端記号 $ は入力の終わりを示す)。各マスには以下のようなアクションが記述されている: shift(sn): 次の状態遷移先を n とする. reduce(rm): m番の文法規則を実行する. accept(acc): 入力バッファにある文字列を受理する. GOTO表は状態と非終端記号でインデックス付けされており、各マスには非終端記号を解釈し終えた次に遷移する状態を示す.

LR法のアルゴリズム スタックを [0] と初期化する.(現在の状態は常にスタックトップの数字で表される) 2019/8/26 スタックを [0] と初期化する.(現在の状態は常にスタックトップの数字で表される) 現在の状態と入力にある記号からアクション表を参照する。ここで以下の4つのケースがある. sn に従って状態遷移する. (これは,還元を行う文字列を一つ右に伸ばす) 現在の終端記号を入力バッファから取り除く. 状態 n をスタックにプッシュする. rm に従って文法規則を適用する。 (これは還元操作) m 番の規則の右側にある各記号についてスタックから状態を削除する(例えば E * B なら3個ポップする)。 その時点のスタックのトップを状態とし、それと m 番の文法規則の左側からGOTO表を参照し、そこにある状態をスタックにプッシュして新たな状態とする. 受理(acc)の場合、文字列の構文解析が完了。 アクションが指定されていない場合、文法エラーとなる. 上のステップを「受容」となるか「文法エラー」となるまで繰り返す。

前回の課題:0+1*1 の構文解析 入力 意味 状態 スタック 0+1*1$ [0] s1 ‘0’を還元の候補にする (0)+1*1 1 前回の課題:0+1*1 の構文解析 2019/8/26 状態 入力 スタック アクション 意味 0+1*1$ [0] s1 ‘0’を還元の候補にする (0)+1*1 1 +1*1$ [1,0] r4 ‘0’を<B>に還元する <B>+1*1 4 [4,0] r3 <B>を<E>に還元する <E>+1*1 3 [3,0] s6 ‘+’を還元の候補にする <E>(+)1*1 6 1*1$ [6,3,0] s2 ‘1’を還元の候補にする <E>(+)(1)*1 2 *1$ [2,6,3,0] r5 ‘1’を<B>に還元する <E>(+)<B>*1 8 [8,6,3,0] r2 <E>+<B>を<E>に還元する <E>*1 s5 ‘*’を還元の候補にする <E>(*)1 5 1$ [5,3,0] <E>(*)(1) $ [2,5,3,0] <E>(*)<B> 7 [7,5,3,0] r1 <E>*<B>を<E>に還元する <E> acc 受理

LR法例題 アクション * + 1 $ E B s1 s2 3 4 r4 2 r5 s5 s6 r3 5 7 6 8 r1 r2 文法の例 2019/8/26 アクション GOTO 状態 * + 1 $ E B s1 s2 3 4 r4 2 r5 s5 s6 acc r3 5 7 6 8 r1 r2 文法の例 (1) <E> →<E>*<B> (2) <E> →<E>+<B> (3) <E> →<B> (4) <B> → 0 (5) <B> → 1

前回の課題:0+1*1の導出木 上下逆転 <E> <E>*<B> <E> * 1 0 + 1 * 1 (0)+1*1 <B>+1*1 <E>+1*1 <E>(+)1*1 <E>(+)(1)*1 <E>(+)<B>*1 <E>*1 <E>(*)1 <E>(*)(1) <E>(*)<B> <E> 1 * <E> <B> +

今日の講義内容 アクション表・GOTO表の作り方

表の作成 アイテム表記(構文解析の段階を表す表記法) アイテムの集合を状態として表を作る. E → • E + B E → E • + B  E → E • + B は、E を認識した状態で,次に ‘+’ とB に対応する文字列がそれに続くことを期待していることを表している. アイテムの集合を状態として表を作る.

アイテム集合の作り方:1 E → E • * B とアイテム E → E • + B は共に非終端記号 E を読んだ後で適用可能である.従ってこれらのアイテムは1つの集合にまとめることができる. E → E + • B のように非終端記号の前にドットのあるアイテム がある場合,B 自体の構文解析を表すアイテム集合 B → • 1 や B → • 0 を 集合に加える必要がある.つまり, A → v•Bw という形式のアイテムが集合内にあり、文法に B → w' という規則がある場合、アイテム B → • w' をアイテム集合に含めなければならない。

アイテム集合の作り方:2 文法の拡張(新たな出発記号の導入)を行う (0) <S> →<E> (1) <E> →<E>*<B> (2) <E> →<E>+<B> (3) <E> →<B> (4) <B> → 0 (5) <B> → 1

アイテム集合 アイテム集合1(‘0’) アイテム集合 0 B → 0 • S → • E + E → • E * B アイテム集合2(‘1’) B → 1 • アイテム集合3(‘E ’) S → E • E → E • * B E → E • + B

アイテム集合 アイテム集合6(‘+’) アイテム集合 4(‘B’) E → E + • B E → B • + B → • 0 アイテム集合5(‘*’) E → E * • B + B → • 0 + B → • 1 アイテム集合7(‘B’) E → E * B • アイテム集合8(‘B’) E → E + B •

アイテム集合から状態遷移表 アイテム集合 * + 1 E B 2 3 4 5 6 7 8

状態遷移表から構文解析表,GOTO表へ 非終端記号に関する列はGOTO表に転記する. 終端記号に関する列はアクション表の shift アクションに転記する. 入力の終わりを示す ‘$’ の列をアクション表に追加し、アイテム S → E • を含むアイテム集合に対応するマスに acc を書く. アイテム集合 i が A → w • という形式を含み,対応する文法規則 A → w の番号 m が m > 0 なら,状態 i に対応するアクション表の行には全て reduce アクション rm を書く.

生成された アクション表 とGOTO表 アクション * + 1 $ E B s1 s2 3 4 r4 2 r5 s5 s6 r3 5 7 6 状態 * + 1 $ E B s1 s2 3 4 r4 2 r5 s5 s6 acc r3 5 7 6 8 r1 r2

Yet Another Compiler Compiler 文法を与えて,上昇型構文解析を行う構文解析器を生成するツール このソフトウエアが発表された当時,類似したソフトが多数あったため,皮肉でつけられた名前. lexによって生成した字句解析オートマトンを利用するように作られている.

yacc と lexを使ったプログラミング コンパイルの流れ yaccのソースファイル.y (生成規則の定義) yacc y.tab.c (LALR構文解析表) (コンパイル) cc lex.yy.c (字句解析 オートマトン) lex lexのソースファイル.l (字句の定義) a.out

yaccソースファイルの例 %{ #include <stdio.h> #include <ctype.h> int yylex(); main() { yyparse(); } %} %token NUMBER %left '+' '-' %left '*' '/' %right UMINUS %% lines : lines expr ‘\n’ {printf("%d\n",$2);} | lines '\n' | /* empty */ ; expr : expr '+' expr {$$ = $1 + $3;} |expr '-' expr {$$ = $1 - $3;} |expr '*' expr {$$ = $1 * $3;} |expr '/' expr {$$ = $1 / $3;} |'(' expr ')' {$$ = $2;} |'-' expr %prec UMINUS {$$ = - $2;} |NUMBER ; %% #include "lex.yy.c" yyerror(mes) char *mes; { fprintf(stderr,"%s\n",mes); } %token はトークン,%leftは左結合的であること,%rightは右結合的であること, $$は戻り値,$nは生成規則n番目の非終端記号の値を示す.

lexソースファイルの例・実行例 %% [ ] {} [0-9]+ {sscanf(yytext,"%d",&yylval); return NUMBER;} \n {return yytext[0];} . {return yytext[0];} 空白 は読み飛ばす 数字の列 10進数に変換し、値をyylvalに代入し、戻り値としてはNUMBERを返す 改行文字はそのまま返す その他の文字(ピリオドは任意の文字を表す) もそのまま返す [twada@host]$ ls lex.l syntax.y [twada@host]$ yacc syntax.y lex.l syntax.y y.tab.c [twada@host]$ lex lex.l lex.l lex.yy.c syntax.y y.tab.c [twada@host]$ cc y.tab.c -lfl [twada@host]$ ls a.out lex.l lex.yy.c syntax.y y.tab.c [twada@host]$ ./a.out 9/3/3-(8-4-3) 1+2+3+4+5+6+7+8+9+10 55 1+2 4+5 syntax error

下記文法の構文解析表とGOTO表を求めると,矛盾が生じることを示しなさい. (1) <E> →<E>+<B> (2) <E> →<B> (3) <B> →<B>*<T> (4) <B> →<T> (5) <T> → 0 (6) <T> → 1