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

Slides:



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

プログラミング言語論 第3回 BNF 記法について(演習付き) 篠埜 功. 構文の記述 プログラミング言語の構文はどのように定式化できるか? 例1 : for ループの中に for ループが書ける。 for (i=0; i
システムソフトウェア 第3回:2007年10月17日(水)   . 2 本日学ぶこと 文法  文字と文字列  無限集合  文法とそのクラス  オートマトン.
和田俊和 資料保存場所 /2/26 文法と言語 ー正規表現とオートマトンー 和田俊和 資料保存場所
プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
基本情報技術概論 I 演習(第5回) 埼玉大学 理工学研究科 堀山 貴史
文法と言語 ー字句解析とオートマトンlexー
プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
計算の理論 I 文脈自由文法 月曜3校時 大月 美佳 平成15年6月30日 佐賀大学知能情報システム学科.
言語処理系(7) 金子敬一.
コンパイラ 2011年10月17日
επιστημη さん 提供の VB.NETプログラムを丸裸にする!?
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
言語処理系(6) 金子敬一.
5.チューリングマシンと計算.
5.チューリングマシンと計算.
文法と言語 ー文脈自由文法とLR構文解析2ー
文法と言語 ー文脈自由文法とLL構文解析ー
プログラミング言語論 第4回 式の構文、式の評価
計算の理論 II 文脈自由文法と プッシュダウンオートマトン
人工知能特論2011 資料No.6 東京工科大学大学院 担当教員 亀田弘之.
言語処理系(5) 金子敬一.
コンパイラ 2012年10月15日
コンパイラ 2012年10月22日
コンパイラ 2011年10月24日
形式言語とオートマトン2013 ー有限オートマトンー 第5日目
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
コンパイラ 第14回 上昇型構文解析(2) 38号館4階N-411 内線5459
東京工科大学 コンピュータサイエンス学部 担当 亀田弘之
言語プロセッサ 第7回目 平成27年11月16日.
プログラミング言語論 第3回 BNF記法について(演習付き)
正則言語 2011/6/27.
文法と言語 ー字句解析とオートマトンlexー
文法と言語 ー字句解析とオートマトンlexー
形式言語の理論 5. 文脈依存言語.
東京工科大学 コンピュータサイエンス学部 亀田弘之
コンパイラ 第13回 上昇型構文解析(1) 38号館4階N-411 内線5459
言語と文法 言語とは,ルールに従う記号列の無限集合である. 文法を与えることで言語が定義できる.
文法と言語 ー文脈自由文法とLR構文解析2ー
言語プロセッサ ー第9回目ー 構文解析(続き).
平成20年10月5日(月) 東京工科大学 コンピュータサイエンス学部 亀田弘之
文法と言語 ー文脈自由文法とLR構文解析3ー
計算の理論 II 前期の復習 -有限オートマトン-
計算の理論 I ε-動作を含むNFA 月曜3校時 大月 美佳.
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
2007年度 情報数理学.
プログラミング言語論 第9回 情報工学科 木村昌臣 篠埜 功.
コンパイラ 2011年10月20日
形式言語とオートマトン 中間試験解答例 2016年11月15実施 中島毅.
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分
東京工科大学 コンピュータサイエンス学部 亀田弘之
文法と言語 ー文脈自由文法とLR構文解析ー
5.チューリングマシンと計算.
形式言語とオートマトン 第14回 プッシュダウンオートマトンと全体のまとめ
文法と言語 ー字句解析とオートマトンlexー
東京工科大学 コンピュータサイエンス学部 亀田 弘之
4.プッシュダウンオートマトンと 文脈自由文法の等価性
情報処理Ⅱ 2005年10月28日(金).
計算の理論 I NFAとDFAの等価性 火曜3校時 大月 美佳 平成16年5月18日 佐賀大学理工学部知能情報システム学科.
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
コンパイラ 2012年10月11日
言語プロセッサ ー第9回目ー 構文解析(続き).
言語プロセッサ ー第7回目ー 構文解析(続き).
東京工科大学 コンピュータサイエンス学部 亀田 弘之
東京工科大学 コンピュータサイエンス学部 亀田 弘之
システムソフトウェア講義の概要 計算機システムの復習:中央演算処理装置(CPU),プログラムの実行,主記憶装置,補助記憶装置
文法と言語 ー文脈自由文法とLR構文解析2ー
4.2 再帰下降解析 (1)再帰下降解析とは ■再帰下降解析(Recursive Descent Parsing)
Presentation transcript:

文法と言語 ー文脈自由文法とLL構文解析ー 2019/4/21 文法と言語 ー文脈自由文法とLL構文解析ー 和田俊和 資料保存場所 http://vrl.sys.wakayama-u.ac.jp/SS/

2019/4/21 前回までの復習

言語と文法 言語とは,ルールに従う記号列の無限集合である. 文法を与えることで言語が定義できる. 2019/4/21 言語とは,ルールに従う記号列の無限集合である. 文法を与えることで言語が定義できる. 文法にはタイプ0からタイプ3までのレベルがあり, プログラム言語としてはタイプ2「文脈自由文法」 プログラム中の字句の表現にはタイプ3「正規文法」 が用いられる.

文脈自由文法 2019/4/21 文脈自由文法(Context Free Grammar:CFG)は,前後の記号に関係なく「非終端記号1つ」を「非終端記号と終端記号から成る記号列」に置き換えるという生成規則 A→t のみを持つ文法 出発記号に対して生成規則の要素を何度か適用して終端記号列を得ることを「導出」と呼ぶ. 終端記号列と文法が与えられたとき,生成規則がどのように適用されたのか,つまり,導出の過程を求めることを「構文解析」と呼び,その結果,導出木が得られる. 導出木からそれを簡略化した「構文木(演算子木)」が求められ,それを利用した式の計算などが可能である.

2019/4/21 正規文法 正規文法は,「非終端記号1つ」を「終端記号」もしくは「終端記号 非終端記号」に置き換えるという生成規則 A→a or B→bB  のみを持つ文法 正規文法で表現できるのは,「整数」「実数」「識別子(変数名)」「キーワード」など,比較的単純な記号の並びである. 正規文法によって規定される言語は,正規表現によって表現することができる. 正規表現から,それに唯一に対応付けられる「非決定性有限状態オートマトン(NFA)」が機械的に対応付けられる.

2019/4/21 字句解析オートマトンの生成 機械的に求められたNFAは,ε-closureによる新たな状態の導入により計算機で実行可能なDFAに変換することができ,さらに状態数の最適化などが行われ,字句解析に用いられる. このような字句解析オートマトンを生成するプログラムに lex がある. lex は拡張された正規文法と,C言語プログラムを与えることで,簡単にオートマトンが生成できる.

前回の演習課題 という正規表現を受理するオートマトンを, 個々の文字列を受理するオートマトンをε遷移で束ねたNFA 決定性に変換したDFA 2019/4/21 前回の演習課題 という正規表現を受理するオートマトンを, 個々の文字列を受理するオートマトンをε遷移で束ねたNFA 決定性に変換したDFA に分けて,それぞれ示しなさい.

解答例 w h a t t a g m s s f f a ε w h e r e r e b h n t v f v f ε e tu w c i o u w f g-k m-q f i i ε w h y h y d j p f f l ε w h o o e k q f o f ε h o w w f l r r f f

解答例 右の正規表現に対応するオートマトンが受理する記号列(すなわち言語)L(A)〜L(D)をVenn図で示しなさい L(A) ε L(B) A: a*b* B: aa*b* C: a*bb* D: aa*bb* L(B) L(D) L(C) L(A) ε

2019/4/21 文脈自由文法における導出

BNF:Backus-Naur Form 出発記号 S=算術式 生成規則 P={ 2019/4/21 BNF:Backus-Naur Form 出発記号 S=算術式 生成規則 P={    算術式 →項 加減演算子 算術式,    算術式→ 項 項 → 因子 乗除演算子 項 項 → 因子 因子→ 識別子 因子→ “(“ 算術式 “)” 識別子→変数   識別子→数値 数値→”1”, 数値→”2”, ... ,数値→”9” 変数→”A”, 変数→”B”, 変数→”C” 加減演算子→“+”,  加減演算子→“-” 乗除演算子→“×”,  乗除演算子→“÷”} 非終端記号 N= {算術式,項,因子,識別子,数値,変数,英数字,加減演算子,乗除演算子} 終端記号 T={“+”, “-”, “×”, “÷”, “0”,”1”,...,”9”, “A”,”B”,...,”Z”, “a”, “b”,...,”z”, “)”, “(“} BNFによる記述 <算術式> →<項><加減演算子><算術式>|<項> <項>→ <因子><乗除演算子><項>|<因子> <因子>→ <識別子>|(<算術式>) <識別子>→<変数>|<数値> <数値>→1|2|... |9 <変数>→A|B|C|...|Z <加減演算子>→+|- <乗除演算子>→×|÷

導出のタイプと文法 2019/4/21 文法1 <算術式> →<項><加減演算子><算術式>|<項> <項>→ <因子><乗除演算子><項>|<因子> <因子>→ <識別子>|<変数>|<数値>|(<算術式>) <数値>→1|2|... |9 <変数>→A|B|C|...|Z <加減演算子>→+|- <乗除演算子>→×|÷ 文法2 <算術式> →<算術式><加減演算子><項>|<項> <項>→ <項><乗除演算子><因子>|<因子> <因子>→<識別子>|<変数>|<数値>|(<算術式>) <数値>→1|2|... |9 <変数>→A|B|C|...|Z <加減演算子>→+|- <乗除演算子>→×|÷ 最左導出   非終端記号のうち,一番左側にあるものから生成規則を適用していく 最右導出   非終端記号のうちの,一番右側にあるものから生成規則を適用していく     文法によってはこれらの導出順序が無限ループを生み出すことがある.上の文法では文法1が最左導出を前提とした文法,文法2が最右導出を前提としている.

最右導出の例 <算術式> →<算術式><加減演算子><項>|<項> 2019/4/21 最右導出の例 <算術式> →<算術式><加減演算子><項>|<項> <項>→ <項><乗除演算子><因子>|<因子> <因子>→ <変数>|<数値>|(<算術式>) <数値>→1|2|... |9 <変数>→A|B|C|...|Z <加減演算子>→+|- <乗除演算子>→×|÷ 算術式 項 加減演算子 3 - 因子 数値 2 1 - 3 2 1

最左導出の例 <算術式> →<項><加減演算子><算術式>|<項> 2019/4/21 最左導出の例 <算術式> →<項><加減演算子><算術式>|<項> <項>→ <因子><乗除演算子><項>|<因子> <因子>→ <変数>|<数値>|(<算術式>) <数値>→1|2|... |9 <変数>→A|B|C|...|Z <加減演算子>→+|- <乗除演算子>→×|÷ 算術式 項 加減演算子 3 - 因子 数値 2 1 - 3 2 1

予備知識:スタックとは? データの格納と取出しが同じ側から行われる線形なデータ構造. push(x,S) x=pop(S) x ... 2019/4/21 予備知識:スタックとは? データの格納と取出しが同じ側から行われる線形なデータ構造. push(x,S) x=pop(S) x ... ... ... ... ...

逆ポーランド記法による数式の計算 321-- 32-1- - 3 2 1 - 3 2 1 逆ポーランド記法 2019/4/21 逆ポーランド記法による数式の計算 - 3 2 1 - 3 2 1 逆ポーランド記法   深さ優先探索の順序を表す破線の矢印が,節を下から上に横切るときに節の記号を出力することによって得られる          321-- 32-1- - 1 - - - 2 1 2 1 3 3 2 3 1 0

最左導出:LL構文解析 ( ) 1 + $ S 2 - F 3 文法: S→F S→(S+F) F→1 2019/4/21 ( ) 1 + $ S 2 - F 3 文法: S→F S→(S+F) F→1 スタック [S,$], 入力 (1+1) 入力から(,スタックからSを読み,ルール2を適用する [(,S,+,F,),$] 入力とスタックにある(を除去する.[S,+,F,),$] 入力から1,スタックからSを読みルール1を適用する.[F,+,F,),$] 入力1とスタックの先頭Fからルール3が適用される[1,+,F,),$] 1,+をスタックと入力から除去する.[F,),$]

最左導出:LL構文解析(続き) ( ) 1 + $ S 2 - F 3 文法: S→F S→(S+F) F→1 2019/4/21 ( ) 1 + $ S 2 - F 3 文法: S→F S→(S+F) F→1 スタック [F,),$], 入力 1) この場合,ルール3が適用される.[1,),$] 入力とスタックから1が取り除かれる. 入力とスタックから)が取り除かれる. スタック内が$だけになり終了 S→(S+F)→(F+F)→(1+F)→(1+1)

LL構文解析の手続き スタックのトップが終端記号の場合、非終端記号の場合、特殊記号 $ の場合の3種類のステップを以下のように実行する。 2019/4/21 LL構文解析の手続き S   スタックのトップが終端記号の場合、非終端記号の場合、特殊記号 $ の場合の3種類のステップを以下のように実行する。 トップが非終端記号の場合、入力バッファの記号を調べ、構文解析表を参照し、適用すべき文法規則を決定して実行する(スタックを書き換える)。構文解析表において、その非終端記号と入力バッファ上のトークンの組み合わせで適用すべき規則が記されていない場合、エラーを通知して停止する。 トップが終端記号の場合、入力バッファとスタックの記号を比較し、それらが同じである場合に取り除く。違っていた場合、エラーを通知して停止する。 トップが $ の場合、入力バッファも $ なら、構文解析成功を通知する。入力がまだある場合、エラーを通知する。いずれの場合も構文解析器は停止する。 S F F ( 1 + 1 )

構文解析表の作り方 First Setの求め方 2019/4/21 構文解析表の作り方 First Setの求め方 目的, スタックトップがAi,入力が’a’であるとき, Ai → wi の規則がマッチすることを調べる. wi の先頭に来る可能性のある終端記号の集合をFirst Setと言い, Fi(wi) で表わす. 各 Fi(wi) と Fi(Ai) を空集合で初期化する。 各規則 Ai → wi について、Fi(wi) を Fi(Ai) に追加する。ここで、Fi は以下のように定義される: Fi(a w' ) = { a }、a は終端記号。 Fi(A w' ) = Fi(A)、A は非終端記号で、Fi(A) には ε は含まれない。 Fi(A w' ) = Fi(A) \{ ε } ∪ Fi(w' )、A は非終端記号で、Fi(A) には ε が含まれる。 Fi(ε) = { ε } 各規則 Ai → wi について Fi(wi) を Fi(Ai) に追加する。 ステップ2と3を全 Fi 集合が変化しなくなるまで繰り返す。

構文解析表の作り方(例) ( ) 1 + $ S 2 - F 3 S→F S→(S+F) F→1 Fi(F)=φ , Fi(S)=φ 2019/4/21 構文解析表の作り方(例) ( ) 1 + $ S 2 - F 3 S→F S→(S+F) F→1 Fi(F)=φ , Fi(S)=φ Fi(S)={(}, Fi(F)={1}  S→FというルールからFi(S):=Fi(S)∪Fi(F)とする Fi(S)={(,1}, Fi(F)={1}

LL構文解析は,下降型構文解析 導出木は,上から下に作られる. 左側の部分から先に作られていく(最左導出のため) 2019/4/21 LL構文解析は,下降型構文解析 導出木は,上から下に作られる. 左側の部分から先に作られていく(最左導出のため) 下降型構文解析で,LL構文解析と本質的に同じ構文解析アルゴリズムに,再帰下降型構文解析というものがある.

LL構文解析問題 2019/4/21 S→F S→-F+S F→1  上記文法の元で,-1+1をLL構文解析で構文解析するとどうなるか?構文解析表を求め,導出木を示しなさい.