Microsoft PowerPoint - 11Syntax.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - 11Syntax.ppt"

ちかこにいだ
4 years ago
Views:

1 言語理論 : 知的情報処理 (11) 構文論慶應義塾大学理工学部櫻井彰人言語を定義する方法 ( いくつかある ): 文法 ( 生成規則 ) オートマトン既知の言語間の演算これらの間には対応関係がある自然言語の記述だけでなく例えばコンパイラの設計に使用言語の定義方法プログラム言語の構文を簡単にどうやって定義するか定義方法は使いやすくあるべし, i..: 定義は有限の長さ与えられた文字列がその言語に属するか否かを調べるアルゴリズムが存在する必要があるさらにその意味が一意に抽出できるアルゴリズムが必要広く使われている方法は ( 生成規則を用いた ) 文法記述形式的な言語ではこれでほぼ十分しかし自然言語の記述には更なる工夫が必要文法 ::= n + n ::= d nd d ::= 式 + n n+n nd d+d dd d+d 文法は言語を定める式は生成規則を順に適用することによって導出されるご存じですね? 言語記号を有限個並べて得られる系列記号列言語制約 : 文法というチョムスキーによる自然言語研究が始まり文法の定義方法文は主部と述部からなる主部は名詞句とがからなる名詞句は名詞か修飾句を一個以上並べたものに名詞をつけたもの < 文 > = < 主部 > < 述部 > 種類が異なることに注意 < 主部 > = < 名詞句 > が < 名詞句 > = < 名詞 > < 修飾句並び > < 修飾句並び > = < 修飾句 > < 修飾句並び > < 修飾句 >

2 形式的には : 生成規則 production rul : 終端記号 trminal ymbol, またはアルファベット alphabt 非終端記号 nontrminal ymbol 文法を記述するための記号 NP VP. NP N A NP. 文法の書き方 ( 生成方向 ) A X 1 X 2... X m 書き換え規則生成規則 BNF (Backu Naur form, Backu normal form) 文法の書き方 ( 解析方向 ) A X 1 X 2... X m 同一記号の書換え A X 1 X 2... X m A Z 1 Z 2... Z m 解析方向 : 使用することはまれ A X 1 X 2... X m Z 1 Z 2... Z m と記述文法例 1 文法例 2 字字字非終端記号字字字字終端記号非終端記号項因子式項因子式 3 * 式式 + 項項項項 * 因子因子因子 ( 式 ) 項因子式足し算項かけ算終端記号

3 文法例 3 文 n 名詞 v 動詞 p 助詞 pp 後置詞句動詞句 pp n p v pp pp n p n p v 一郎が公園を走る pp pp v n p 一郎公園がを走る非終端記号終端記号チョムスキー階層 3 型正規文法受理 : 有限状態オートマトン A a A a B 2 型文脈自由文法受理 : プッシュダウンオートマトン A X 1 X 2...X m 1 型文脈依存文法受理 : 線型有界オートマトン Z 1 Z 2...Z n X 1 X 2...X m n m 0 型句構造文法受理 : チューリング機械右辺左辺とも任意 a 終端記号 A,B 非終端記号 X,Z どちらか有限状態オートマトン A cad ab a,a 非終端記号 a,b,c,d 終端記号決定性プッシュダウンオートマトン cd cd,a 非終端記号 c,d 終端記号 c A d : A: a b a : 0 c 1 d 2 c d 3 c c c c c d c d c 後で d との対応させるために c をとっておく ( 一般には ) スタック正規文法で記述できない言語の例 () ε 文脈自由文法では記述可とか () ε 文脈自由文法では記述可 ((( ))) ( (( )) ( ((((( ))))) () ) ) 文脈自由文法で記述できない言語の例 L = { a n b m c n d m n,m 1} u k uのk 回並び aa bbbb cc dddd L={ wcw w は (a b)* } aabbcaabb aacaa

4 構文解析の手法下向き v. 上向き文法項目をまとめてより上位の項目にあらゆる纏め方を考える実際に生成して同じものができるか? 深さ優先 v. 広さ優先候補生成の順番 : 縦方向横方向最左 v. 最右左端 ( 初め ) からか右端からか左から2 番目ということも考えられるが下向き解析例 1 文法 cad A ab a 入力 cad,a 非終端記号 a,b,c,d 終端記号 cad cabd 失敗バックトラック cad 成功解析例 2 下向き + 縦 + 最左入力一郎が公園を走る pp n p v pp pp v n p 一郎公園がを走る pp 一郎が一郎 p n p 一郎が公園 p 一郎 p 一郎が公園が一郎が一郎が公園を一郎が pp... 一郎が n p 一郎が公園を走る上向き型 A B aab Abc b d 入力 abbcd aabcd aad aab 最右 + 深さ優先解析例 2 深さ優先 + 最右 pp n p v 一郎が公園を走る pp pp 走る nが公園を走る pp pp v n p 公園を走る pp pp pp 公園を走る pp 失敗 pp n を走る pp 成功 pp n p 走る pp pp v n p 一郎公園がを走る構文解析木導出過程を表現した木 + n n+n nd d+d dd d+d 木は括弧付けされた式を表すと考えられる + 4 3

5 構文解析式が与えられたとき構文木を作成すること曖昧性があることもある式に二通りの構文解析方法がありうる問題となるのは : 27 (4 + 3) (27 4) + 3 曖昧性を解消する方法手順で纏める順序は * が + より先 3*4 + 2 は (3*4) + 2 と解析結合性 (aociativity) 等しい優先順序の演算は左 ( または右 ) から括弧でくくるは (3 4) + 5 と解析詳細はコンパイラの本等を文法の性質文法は多くの場合生成規則で記述される文法が異なっても生成する言語は同じときがある同一の言語を生成する文法は等価 quivalnt であるというある文法では生成規則の適用順序や適用規則が異なるにも関わらず同じ文が生成されることがある曖昧 ambiguou な文曖昧 ambiguou な文法という Chomky 階層認識機械との対応 Chomky 階層 ( 文法規則のパターンに対する制限の強弱 typ-0: 弱い ~typ-3: 強い ): typ-0 typ-1: 文脈依存 contxt dpndnt grammar typ-2: 文脈自由 contxt-fr grammar typ-2: 正規 rgular grammar 文法規則のパターンに対する制限が弱いほど文法的に正しい文と正しくない文の違いが微妙になる文の認識機械 ( 与えられた文字列が文か文でないかを判定する機械 ) の複雑さは文法の階層によって異なる : typ-0 の言語を認識するには Turing 機械が必要 ( なこともある ) 文脈依存言語を認識するには線形有界オートマトン linarly boundd automata が十分必要 ( なこともある ) 文脈自由言語を認識するにはプッシュダウンオートマトン puhdown automata が十分必要 ( なこともある ) 正規言語を認識するには有限オートマトン finit automata で十分有限オートマトン finit automata 有限オートマトンは, 5つ組 M = (Q, Σ, δ, q 0, F), ただし 1. Q : 状態 tat の有限集合 2. Σ: ( 許される ) 入力記号 accptabl input ymbol の有限集合 3. δ: 遷移関 tranition function 4. q 0 Q : 初期状態 initial tat 5. F : 終了状態 final tat の集合正規文法と有限オートマトン正規文法で定義できる言語と有限オートマトンで定義できる言語とは一致するすなわちこの 2 つの定式化は等価である以下に述べる正規文法で定義される言語の性質はいずれもテストすることができる : 2 言語の等価性定義した言語が空かどうか所与の文字列が所与の言語の要素かどうか残念なことに正規文法で定義できる言語というのは非常に限られた言語だけである

6 文脈自由文法の性質コンパイラ言語の構文解析は所与の文字列が文脈自由言語 contxt-fr grammar, or cfg に従っているかどうかをチェックすることと考えられる以下のような ( 他にもたくさん ) 話題がある曖昧性の問題演算子の優先順位文法の変換文法の変換 tranformation 文脈自由文法を任意の形式に変換するような一般的アルゴリズムは存在しないしかし任意の文脈自由文法は Chomky 標準形に変換することができる A BC (A, B, C N) A a (A N, a T) グライバッハ Gribach 標準形もよく知られている Backu-Naur form ::= 左辺は右辺で定義される < > 範疇の名称は角括弧 angl brackt で囲む例 : <program> ::= program <dclaration_qunc> bgin <tatmnt_qunc> nd ; Extndd Backu-Naur form N. Wirth が Pacal と Modula-2 を定義するのに使用 1981 年 Britih tandard Intitut が標準化記号の追加または * Kln の星印 ( ) メタレベルの括弧比較 BNF と EBNF の比較図式表現 BNF digit 0 digit 1 digit 9 unignd_intgr digit unignd_intgr digit unignd_intgr Idntifir Lttr Lttr Digit EBNF digit unignd_intgr digit digit *

Microsoft PowerPoint - 02LanguageTheory.ppt [互換モード]

Microsoft PowerPoint - 02LanguageTheory.ppt [互換モード] 言語理論 : コンパイラ理論 2 言語理論櫻井彰人言語を定義する方法 ( いくつかある ): 文法 ( 生成規則 ) オートマトン既知の言語間の演算これらの間には対応関係があるコンパイラの設計に使用言語の定義方法どうやって定義するか定義方法は使いやすくあるべし, i.. 定義は有限の長さ与えられた文字列がその言語に属するか否かを調べるアルゴリズムが存在する必要があるさらにその意味が一意に抽出できるアルゴリズムが必要広く使われている方法は