1 追補_1. 高階の述語と文脈自由文法 １.１ 文脈自由文法 次の文献に拠って，文脈自由文法の概略を記す：二宮 崇「数理言語情報論」 (http://www.r.dl.itc.u-tokyo.ac.jp/~ninomi/mistH19w/mistH19w-ninomi-3.ppt)． 文脈自由文法(context-free grammar)は， と定義される．ここに， は変数 (variable)または非終端記号(non-terminal symbols)，文法概念(syntactic category)と呼ばれる， 書き換えるべき記号の有限集合である． は終端記号(terminal symbols)と呼ばれる，目的と は生成規則(production rules)と呼ばれ する語を構成するアルファベットの有限集合である． る『非終端記号→非終端記号と終端記号の列』という書き換え規則の有限集合である． 始記号(start symbol)と呼ばれる特別の変数で，最初に出発する非終端記号である． 生成される終端記号の列を語といい，その語の集合 は開 によって を， によって表現される言語(文脈自 由言語－Context Free Language)という． 文脈自由文法は再帰的に定義される．例えば， から構成される式 は，次のように再帰的に定義される: 1. は式である． 2. が式なら、 や も式である． これを文脈自由文法で記述すれば，以下のようになる： ．また，同じ変数の生成規則の右辺を， “または” ただし， ． を表す“｜”を用いてまとめて， 文法と実際に与えられる語との間の関係については， 語＝終端記号列 (文字列)から開始記号(非終端記号)に至る－再帰的推論(Recursive inference) 開始記号(非終端記号)から語 (文字列) に至る－導出(Derivation) という 2 つの見方ができるが，どちらも本質的には同じである． ある非終端記号 に生成規則 導出(Derivation)といい， を適用して非終端記号 または終端記号 を生成することを または と記す．また， は， を関係として見た時 の閉包を表し， の右辺は最終的な導出結果である． Copyright © 2007－2011 IT Consulting Co., Ltd. All Rights Reserved 2 １.２ 文脈自由文法による高階の述語(入れ子記法)の定義 １.２.１ 高階の述語(統語論) 述語の体部のみを高階化する入れ子記法(ただし，併合は含まない1)は，以下のような文脈自 由文法から生成される言語として定式化できる： P1 P2 P3 P4 の元のリスト の元のリスト ここに， P5 P6 は，それぞれ，述語(コト)の名前，論議領域(UoD)におけるモノの名前， を元とする終端記号の集合を表す．生成規則は，コンマではなく改行文字で区切っている． 同じ変数の生成規則の右辺を， “または”を表す“｜”を用いてまとめると，上記の生成規則 は，下のようにも書かれる： また，生成規則 P5,P6 は，それぞれの集合の元を“｜”でつないだものとなる． 次の例は，入れ子記法の高階の述語記述が先頭記号から順次導出される様子の途中経過の一 部と最終結果を示したものである： なお，この例では，終端記号の集合は，次の通りである： 1 併合とハイパー述語（後述）は，データ操作を簡素化するためのもので，世界の記述にとっては本質的ではない． Copyright © 2007－2011 IT Consulting Co., Ltd. All Rights Reserved 3 １.２.２ 統語論と意味論の統合 述語の頭部と体部の双方を高階化して，述語抽出法の統語論と意味論を同時に満足する言語 を生成する文法を次に示す： の元のリスト の元のリスト の元のリスト ここに， は，それぞれ，述語(コト)の名前，論議領域(UoD)におけるモノの名 前，集合族の名前を元とする終端記号の集合を表す． なお，自分が書いた高階の述語が上記の文法に則っているか否かは，以下のサイトで公開さ れているツールを用いて確認できる： http://smlweb.cpsc.ucalgary.ca/start.html ただし，このツールでは， を終端記号として受け入れないので，別の文字で代用する 必要がある． 高階の述語を記述する文脈自由文法が与えられたということは，高階の述語で記述された概 念モデルを論理モデル（主なものは第２部で紹介する）に変換する処理系(コンパイラ)を作成で きるということを意味する．実際，その処理系の作成は，情報科学系学部学生にとって格好の 演習問題であろう．意欲ある読者は，是非，挑戦していただきたい． Copyright © 2007－2011 IT Consulting Co., Ltd. All Rights Reserved
© Copyright 2024 ExpyDoc
