JPH03152626A - パターンマッチング処理方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔概　要〕 文字列で表される式等のパターンマツチング処理に関し
、 任意の構文規則と代入条件とを定義することにより、定
義に従う２文字列のパターンマツチングを、代入条件の
チエツクを含めて実行するパターンマツチング処理方式
を目的とし、 パーザ生成部とパターンマツチャとを有し、該パーザ生
成部は、所与の構文定義に従って、所定のパーザを生成
し、該パーザは、文字列を解析して、該文字列の構文を
表す所定の構造データに変換し、該パターンマツチャは
、該パーザが変換した２組の該構造データについて、該
両構造データ上で所定の対応をなす各要素間を比較し、
すべての該要素間について、両該要素が同一であるが、
又は両該要素が所与の代入条件定義に従って代入可能で
あることにより、該両構造データのマツチングを判定す
るように構成する。

〔産業上の利用分野〕

本発明は、文字列で表される式等のパターンマツチング
、特に代入条件チエツクを伴うパターンマツチング処理
方式に関する。

〔従来の技術と発明が解決しようとする課題〕プログラ
ムの実行、プロダクションシステム、或いは項書き換え
システム等の計算機の処理において、所要の構文規則に
基づく文字列からなる式や項同志の構文上の同一性を判
別する、いわゆるパターンマツチングが必要になる。

このようなパターンマツチングを実行するパターンマツ
チャは、所定の構文規則に従って入力文字列を構文解析
することにより、文字列の構文を決定することが必要な
ために、各構文規則ごとに設けられる。

しかし、利用者が個別に構文規則を定義できるシステム
の場合には、それらの構文規則に対応できる汎用パター
ンマツチャが望まれる。

又、通常パターンマツチングと共に、変数とその変数に
代入される対象の型との対応条件である代入条件を制限
したい場合があるが、従来そのような代入条件のチエツ
クは、パターンマツチングとは別に処理しなければなら
ない。

本発明は、前記のような従来の問題を解決して、任意の
構文規則と代入条件とを定義することにより、定義に従
う２文字列のパターンマツチングを、代入条件のチエツ
クを含めて実行するパターンマツチング処理方式を目的
とする。

〔課題を解決するための手段〕

第１図は、本発明の構成を示すブロック図である。

図はパターンマツチング処理方式の構成であって、パー
ザ生成部３とパターンマツチャ５とを有し、パーザ生成
部３は、所与の構文定義１に従って、所定のパーザ４を
生成し、パーザ４は、文字列６を解析して、文字列６の
構文を表す所定の構造データフに変換し、パターンマツ
チャ５は、パーザ４が変換した２組の構造データフにつ
いて、両構造データ７上で所定の対応をなす各要素間を
比較し、すべての該要素間について、両該要素が同一で
あるか、又は両該要素が所与の代入条件定義２に従って
代入可能であることにより、両構造データフのマツチン
グを判定する。

〔作　用〕

この処理方式により、所要の構文規則と代入条件の定義
を与えることによってパーザが生成され、パーザは文字
列を所与の構文規則に従って、文字列の構文を表す一定
の仕様の構造データに変換するので、その構造データを
処理対象とするパターンマツチャで、代入条件定義に従
う代入条件のチエツクを含めて、パターンマツチング処
理を行うようにすることにより、利用者が個別に与える
構文規則と代入条件の定義に対して、個別のパターンマ
ツチャを作らないでも、自動的にパターンマツチングに
応じ、且つ同時に代入条件をチエツクすることができる
。

〔実施例〕

第１図において例示するように、パーザ生成部３は例え
ば構文変換部１０及びパーザ組立部１１からなり、与え
られる構文定義ｌを構文変換部ｌＯが所定の構成の構造
データに対応した形式に変換し、パーザ組立部１１は変
換結果の構文定義１２に従って文字列６を構文解析結果
の解析木を表す構造データ７に変換するようにパーザ４
を構成する。

第２図（ａ）は構文定義１の一例であって、各行は矢印
の右辺の記号列を、左辺に示す記号で表される構文要素
とすることを定義する。なお、図において右辺の、引用
符で囲まれる記号は終端記号を示し、「１」は「又は」
を示す。

構文変換部１０はこのような構文定義１を、例えば第２
図（ｂ）に示すような形式に変換して、非終端記号に引
数を付加した形式によって、 構文要素名（解析した文字列の構成要素）の形で、木構
造を表現する構造データに対応するようにする。なお、
図で大括弧（［と］）は、括弧で囲まれる部分が、「、
」でつながれた記号列からなるリストであることを示す
。

パーザ組立部１１は、このように変換された構文定義１
２に基づいて、文字列を解析して第２図（ｂ）の右辺に
一致する構成要素を、左辺のように書き換える処理を、
書き換えができなくなるまで繰り返すようにパーザ４を
構成する。その結果パーザ４は、例えば第４図に示すよ
うに、白抜き矢印の左辺に例示する文字列を解析して、
右辺に示すような構造データに変換するように構成され
る。

次にパターンマツチャ５は、パーザ４が出力する２文字
列の解析結果の構造データを、代入条件定義２を参照し
ながら比較して、パターンマツチングを実行する。

第５図は代入条件定義の一例であって、図の例はｒ　ｍ
ｅｔａ−ｆｏｒｍｕｌａにはｂａｓｉｃ−ｆｏｒｍｕｌ
ａのみが代入可能である」ことを表す例である。

パターンマツチャ５は、第４図の例の右辺のような２構
造データを、例えば左から調べて両構造データの対応す
る構文要素が一敗するか、又一致しない場合は代入条件
定義２で定義された条件を満足するか判別し、何れかが
満足されれば、この処理を進めてすべて満足すれば、こ
の両構造データのマツチングが得られたと判別する。パ
ターンマツチャは以上のマツチング状況と共に、マツチ
ングした場合には代入関係を示す代入リストを処理結果
として出力する。

第３図は、パターンマツチャ５の処理の流れの一例を示
す図である。処理対象の両構造データの一方を構造デー
タ■、他方を■として、データの要素を左から順次処理
するものとし、先ず処理ステップ２０で構造データ■の
先頭の要素を見て、データがリストか否か識別する。

リストの場合には処理ステップ２１で、そのリストの要
素を先頭要素から順次処理するものとして、各要素につ
いては処理ステップ２０からの処理を再帰的に実行する
。

リストでない場合、即ち処理対象の部分が構文要素名（
−−−・−） の場合には、処理ステップ２２で構造データ■と■の対
応する構文要素名を比較し、両構文要素名が等しければ
処理ステップ２３で構造データ■の構文要素名に続く括
弧内が終端記号か識別し、終端記号でなければ処理ステ
ップ２４で括弧内のデータについて、処理ステップ２０
からの処理を再帰的に実行する。

又、括弧内が終端記号であれば、処理ステップ２５で、
構造データ■も同一の終端記号か識別し、同一終端記号
でなければマツチング失敗として終了する。

処理ステップ２２で両構文要素名が等しくない場合には
、処理ステップ２６で両構文要素の組合わせが代入条件
定義２の代入条件を満足するか識別する。その結果代入
不可と判定した場合にはマツチング失敗として処理を終
わる。

代入可能と判定した場合には処理ステップ２７でこの組
合わせについて代入リストに所定の代入関係を示す項を
追加する。

以上の結果、マツチング失敗にならない場合には処理ス
テップ２８で、構造データ■の全要素を処理したか識別
して、未処理があれば処理対象を次の要素に進めて処理
ステップ２０に戻る。処理済みなら、処理ステップ２９
で構造データ■が処理済みか識別し、■も処理済みなら
マツチング成功、■に未処理があればマツチング失敗と
して処理を終わる。

第６図は前記例の構文定義及び代入条件定義がある場合
に、（ａ）は文字列［Ａ→ＢＪと「ｐ−＋ｑ」、（ｂ）
は「〜Ａ」と「Ｐ−＋ｑ」について、各側突字列のパタ
ーンマツチングを以上のように処理した状況を説明する
図である、各２文字列から変換された構造データについ
て、図に矢印で対応付けた要素が左から順次比較され、
等しくない場合には代入条件がチエツクされて、（ａ）
の場合はマツチングに成功するが、（ｂ）の場合は最初
の構文要素名の比較で不一致のために、そこまででマツ
チング失敗となって処理を終了することになる。

〔発明の効果〕

以上の説明から明らかなように本発明によれば、文字列
で表される式等のパターンマツチングＭｌにおいて、任
意の構文規則と代入条件とを定義することにより、定義
に従う２文字列のパターンマツチングを、代入条件のチ
エツクを含めて実行することができるので、構文規則と
代入条件の定義ごとに、個別のパターンマツチャを作ら
ないでも、自動的にパターンマツチングに対処でき、且
つ同時に代入条件をチエツクすることができるという著
しい効果がある。

５はパターンマツチャ、６は文字列、 ７は構造データ、　　　１０は構文変換部、１１はパー
ザ組立部、 ２０〜２９は処理ステップ

【図面の簡単な説明】

第１図は本発明の構成を示すブロック図、第２図は構文
定義の例を示す図、 第３図は本発明の処理の流れ図、 第４図は構造データの例を示す図、 第５図は代入条件定義の例を示す図、 第６図は処理例の説明図 である。 図において、 ｌ、１２は構文定義、　　２は代入条件定義、３はパー
ザ生成部、　　４はパーザ、 本発明の構成を示すブロック図 第１図 ＤＩ 構文定義の例を示す図 第２図 本発明の処理の流れ図 第　３１２１

Claims (1)

1. 【特許請求の範囲】 パーザ生成部（３）とパターンマッチャ（５）とを有し
   、該パーザ生成部（３）は、所与の構文定義（１）に従
   って、所定のパーザ（４）を生成し、 該パーザ（４）は、文字列（６）を解析して、該文字列
   の構文を表す所定の構造データ（７）に変換し、該パタ
   ーンマッチャ（５）は、該パーザ（４）が変換した２組
   の該構造データ（７）について、該両構造データ上で所
   定の対応をなす各要素間を比較し、すべての該要素間に
   ついて、両該要素が同一であるか、又は両該要素が所与
   の代入条件定義（２）に従って代入可能であることによ
   り、該両構造データのマッチングを判定するように構成
   されていることを特徴とするパターンマッチング処理方
   式。