JPH01116830A - Ｌｒ構文解析テーブル圧縮方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明は一般的にはデータ処理に関し、さらに詳しくは
パーサ（構文解析系）の圧縮法に関する。

Ｂ、従来技術およびその問題点 ＡＤＡ、Ｃ等の高級言語をマシン・リーダプルな形（マ
シン語）に変換するのに用いられるコンパイラは、しば
しば、丁度英語の学習者が文の正確さを確かめるために
文を主語、動詞、目的語に解析するのと同じように、１
行のソース・コードを構成要素に解析するパーサを含む
。パーサがその作業を終えると、コンパイラの他の部分
がソース・コードからマシン・コードへの実際の変換作
業を行なう。

過去数年の間に、新しい言語が完全な文法をもって開発
されたり、あるいは既存の言語が完全な文法をもって特
定されたりしてきた。コンビュー夕言語であれ人間の原
語であれ、任意の言語の文法の場合と同様に、文法とい
うものは１文法的に許容できる構造を決定する規則を備
える。コンピュータ言語文法に基づいて、マトリックス
形式のテーブルからなるＬＲ（左−右）パーサを生成す
ることができる。そこでは、行がパーサの状態を表わし
、列がパーサへの入力を表わす。行と列の交点は、パー
サの特定状態への所与の入力の結果化じる。アクション
（動作）を保持する。このようにマトリックスは、オー
トマトン、つまり例えば言語の文法規則に従う機械の特
徴を記憶するのに用いられる。

スピード性能の面で、マトリックスはＬＲオートマトン
を記憶するのに極めて効率のよい方法である。なぜなら
、プロセッサに対してルックアップ・テーブルの形で提
示できるからである。残念ながら、マトリックスが必要
とするスペース量は、マトリックスに含まれる有意（非
エラー）エントリの数ではなくて、行と列の数によって
決まる。

例えば、ＡＤＡ等の言語の場合、約５００の状態と約４
００の可能な入力があり得る。この結果。

マトリックスには２００，０００個のエントリが存在す
る。一般に、ＬＲ子テーブル含まれる有意エントリは極
めて少なく、典型的な場合にはマトリックスの２％を占
めるにすぎない。マトリックス・スペースの残り９８％
は非有意情報、つまりゼロである。時間の効率の点から
マトリックスに近い表現であって、テーブル中の有意エ
ントリの数に比例する量だけが必要になるものを選択す
るのが望ましい。

また、入力に従う可能状態の連係を主に示すグラフィッ
ク形式でオートマトンを表わすことも可能である。かか
る表現は、有意エントリの数と同じだけの大きさしか必
要としないから、コンパクトであるという利点を持つ。

しかしながら、希望する状態と入力が見つかるまで各鎖
のリンクを探査しなければならないので、かかる表現に
基づくオートマトンは極めて遅い。

ＬＲ解析テーブルの圧縮のためのいくつかの方法が知ら
れている。大抵のＬＲパーサ・ジュネレータは、解析テ
ーブルを圧縮して提供していた。

通常、圧縮はハツシングまたは線形リストを使って行わ
れる。これらのデータ構造は極めて一般的であり、それ
らの解析テーブル圧縮への応用は一般に文献に記されて
いない。

ハツシング法では、希薄なマトリックスを表現するのに
、ハツシュ・テーブルが用いられる。行と列のインデッ
クスが“ハツシュ”されて、シングル・テーブルへのイ
ンデックスを形成する。ハツシュ衝突とエラーをチエツ
クするために、テーブルは解析動作のみならず、行と列
のインデックスも含まなければならない。ハツシュ解析
テーブルで必要になるスペースは極めて多い。また、行
と列のインデックスをチエツクするので、解析時間が増
加する。本発明のテーブル圧縮によれば。

ハツシング・テーブルを使った場合のせいぜい１／２未
満のスペースしか必要としない解析テーブルが得られる
。

線形リストを使う方法では解析マトリックス・エントリ
が線形リストをなしで記憶されたときに相当のスペース
の節約をもたらす。しかしながら、。

解析動作が必要になると、リストを逐次的にサーチしな
ければならない。したがって、解析動作を決定するのに
要する時間は一定でなく、解析マトリックス・エントリ
の数に依存することになる。

かかる方法は、スペースの節約にはなるけれども、時間
の点で犠牲を払うことになる。この方法は、Ａｈｏ、５
ｅｔｈｉ、υｌ１ｍａｎ著”Ｃｏｍｐｉｌｅｒｓ：Ｐｒ
１ｎｃｉｐｌｅｓ。

Ｔｅｃｈｉｑｕｅｓ、ａｎｄ　Ｔｏｏｌｇ、”Ａｄｄｉ
ｓｏｎ−１ｉ１ｅｓｌｏｇ社、１９８６年発行の２４５
ページに記されている。

行変位（ｄｉｓｐｌａｃｅｍｅｎｔ）−を使う方法にお
いては、希薄な解析マトリックスの行が互いに”オーバ
ーレイ”されて１つの１次元テーブルとされる。オーバ
ーレイ・テーブルにおける各行の開始インデックスを検
索するために、補助テーブルが必要とされる。また、オ
ーバーレイ・テーブル中の各エントリには、インデック
スされた場所が有効エントリに対応することを確認する
“チエツク″エントリが関連していなければならない。

この方法はＺｉｅｇｌｅｒ、Ｓ、Ｆ、著”Ｓｍａｌｌｅ
ｒ　Ｆａｓｔｅｒ　Ｔａｂｌｅ　Ｄｒｉｖ、ｅｎ　Ｐａ
ｒｓｅｒ”、　（未公開Ｍ稿）　Ｍａｄｉｓｏｎ　Ａｃ
ａｄｅｍｉｃ　ｃｏｍｐｕｔｉｎｇ　Ｃｅｎｔｅｒ、Ｕ
ｎｉｖ、ｏｆ　Ｗｉｓｃｏｎｓｉｎ、Ｍａｄｉｓｏｎ　
　１９７７年にて提案されており、（他の方法とともに
）ＹＡＣＣパーサ・ジェネレータ、っまりＪｏｈｎｓｏ
ｎ　。

Ｓ、Ｃ，著、”Ｙ　Ａ　ＣＣ・・・Ｙｅｔ　ａｎｏｔｈ
ｅｒ　Ｃｏｍｐｉｌｅｒｃｏｍｐｉｌｅｒ”、Ｃ３ＴＲ
３２、Ｂｅ１ｌ　Ｌａｂｏｒａｔｏｒｉｅｓ。

Ｍｕｒｒａｙ　１ｌｉ１１．　Ｎ　Ｊ　１９７５年で使
用されている。

この方法は解析動作時間に関して成功しているけれども
、スペースの需要が過大なものになり得る。

この方法におけるスペース効率は、行がどのようにオー
バーレイされるかに非常に依存する。本発明の方法は、
ある程度行を変位させるけれども、行のオーバーレイに
関して新規な手法を用い、実際に１次元テーブルにおけ
る未使用エントリの数を最小にする。

Ｄｅｎｃｋｅｒ、　Ｐ　、　、　ＤｕｒｒｅｅＫ　Ｈｅ
ｕｆｔ、　Ｊ　、　、によって“Ｏｐｔｉｍｉｚａｔｆ
ｏｎ　ｏｆ　Ｐａｒｓｅｒ　Ｔａｂｌｅｓ　ｆｏｒ　Ｐ
ｏｒｔａｂｌｅＣｏｍｐｉｌｅｒｓ、”　ＰＰ、　５４
６−５７２、ＡＣＭ　Ｔ。

ＰＬＡＳ第６巻、ナンバー４．１９８４年１０月に提案
されているグラフ・カラリング法は、互換性のあるエン
トリを備えた行と列を認識することによって１元のマト
リックスのエントリ数を減らそうと努める。ブラフ・カ
ラリング・アルゴリズムは、解析マトリックスをより小
さな動作マトリックスとブーリアン・チエツク、マトリ
ックスとに簡約するのに用いられる。結果として、迅速
にアクセスすることのできる極めて小さな解析テーブル
が得られる。本発明も互換性のある行を識別することに
より終点動作エントリの数を減らすけれども、上記文献
のものとは異なる方法によってであり、ブーリアン・チ
エツク、テーブルは使われない。上記文献では、終点動
作毎にブーリアン・マトリックスをアクセスしなければ
ならない。

大抵のマシンにおいて、かかる形式のアクセスは、単純
なテーブル・インデックス型のものよりかなり遅い。

したがって、本発明の目的は、構文テーブル内の有意な
エントリの数に比例するメモリ・スペースに記憶するこ
とのできる。圧縮された解析テーブルを提供することに
ある。

本発明の別の目的は、コンパクトに記憶することができ
るけれども、対応する行列表現よりも高速に動作するこ
とのできる解析テーブル表現を提供することにある、。

本発明のさらに別の目的は、既存の方法を使う場合より
も小さく、顕著にアクセス時間の短い解析テーブルを与
えることにある。

Ｃ０問題点を解決するための手段 本発明は、コンピュータ言語をコイパイルするのに使わ
れるようなＬＲ解析テーブルを圧縮する方法を提供する
。この方法では、第１に、同じ、つまり互換性のある動
作を持つ状態を併合する。

続いて、マトリックス・テーブルの隣接する行同士をオ
ーバーレイさせてベクトル表現とし、有意性のないエン
トリを削除する。第３に、圧縮されたテーブルへのイン
デックスとして使うために、状態番号を符号化する。

Ｄ、実施例 コンピュータ言語用のＬＲ解析テーブルは、該言語の文
法を要約したものである。それはマトリックスとして記
述することができる。その行はスタック駆動・有限状態
オートマトンの状態を表わし、列は言語の記号（シンボ
ル）を表わし、「動作（アクション）」と呼ばれるマト
リックスの各要素の値はオートマトンの遷移（トランジ
ション）またはエラーの何れか一方を表わす。オートマ
トンはスタック駆動式である。・なぜなら、解析の際に
、初期状態から現在状態へ至るべくとられた、オートマ
トン中の経路（ｐａｔｈ）を追跡するのに、補助スタッ
クを使うからである。

最初、スタックは、オートマトンの初期状態だけを持つ
。解析の際の任意の時点において、パーサはスタックの
頂点（トップ）で示される状態にある。パーサは、入力
ストリーム中の最初のトークン・シンボルにアクセスす
る。２種類の遷移が起こり得る。

１）新しい状態への前向遷移。新しい状態がスタックに
ブツシュされることになる。

２）後退（ｒｅｇｒｅｓｓｉｏｎ　）スタックの頂点か
らゼロ以上の状態を取り去ることになる。

コンピュータ言語のシルポルは２つのカテゴリに分類で
きる。すなわち、１）終端（ターミナル）、２）非終端
（ノン・ターミナル）である。

終端とは実際の入カドークンとして使用され得る記号に
ことにである。つまり、例えば、プログラムを書く人間
によって与えられる。言語中の諸命令のことである。非
終端とは言語によって内部的に使用される。言語中のフ
レーズのことである。

記号をカテゴライズした結果、解析テーブルは論理的に
別々の２個のテーブルに分けることができる。つまり、
１）行として状態を、列として終端を、それぞれ持つ終
端動作テーブル、および２）行として状態を、列として
非終端を、それぞれ持つ非終端動作テーブルつまり先行
（ＧＯＴＯ）テーブルである。以下の説明で使う文法に
関する終端動作テーブルと非終端動作テーブルが、第１
図と第２図にそれぞれ示されている。

ＬＲパーサは、現在状態と現在記号から計算された動作
によって次の状態と次の記号が決定される。オートマト
ンであるので、マトリックスの直接アクセス性は維持さ
れなくてもよい。言い換えると、オートマトンが状態Ｓ
になるための唯一の方法は、前向遷移が状態をＳへ移す
か、あるいは前向遷移が先行して既にスタック中にＳを
置いていた場合に後退によってＳに戻ることである。そ
れゆえ、Ｓに至る前向遷移エントリだけがＳをアクセス
しなければならない。

上記解析テーブルの説明は、例を参照した方がよく理解
できる。以下の例は、本明細書の以後の部分において、
解析テーブルの一般論および本発明の詳細な説明するの
に用いられる。

選んだ例は、単純な数式、例えばａ＋ｂ、ａｍｂ、ある
いはａｍ（ａ＋ｂ）を生成するための文法である。該文
法には、以下のとおり、終端シンボル、非終端シンボル
、および１１個の規則（ルール）が含まれる。

終端記号　　　ｉｄ　（）＋＊ｅｏｆ 非終端記号　：　ＥＴＦＶＲ ルール １、Ｅ：：＝Ｔ ２、Ｅ：：＝＋Ｔ ３、　　　　　Ｅ　　　：：＝　　　Ｅ＋Ｔ４、Ｔ：：
＝Ｆ ５、　　　　　Ｔ　　　：：＝−ＴｍＦ３、Ｆ：：＝Ｖ ７、Ｆ：：＝Ｒ ８、Ｖ　　　：：＝　　　ｉｄ ９、　　　　　Ｖ　　　：：＝　　　１ｄＲ１０、Ｒ：
：＝　　　（Ｅ） １１、　　　Ｒ：：＝　　　（Ｅ）Ｒ 終端記号は通常ユーザが与えるものである。したがって
、ユーザがａ＋ｂというステートメントを与えたならば
、終端記号はａ、ｂ、および十である。

終端記号＃　ｉ　ｄ　ｊｌは識別子を表わし、この場合
では、ａ、ｂ、ｃあるいはｘ、ｙ、ｚといった変数であ
る。終端希望１１　ｅ　ｏ　ｆ”は、入力の終了を表わ
すという意味で特殊である。この文法により生成される
式の１例を下に挙げる°。

ｉｄ＋ｉｄ　（ｉｄ） この式は、″トークン″の例を入力と解することにより
、”解析″される。

ｉｄ＋ｉｄ　（ｉｄ）ｅｏｆ トークンは左から右へ“読まれ″、各トークンが読まれ
る毎に１以以の解析″動作″が取られる。

解析の際には、以前の解析動作の゛′結果″を覚えてお
くのに補助“スタック”が必要とされる。これらの結果
は状態と呼ばれ、結果を保持するスタックは“状態スタ
ック”と呼ばれる。解析の際の任意の瞬間において、あ
る程度の数の入カドークンは消費されており、そのよう
な行為した結果は状態スタックで記録されている。１１
　ｅｏｆＩＩトークンに達すると、入力は゛′受理され
た”状態にあると言え、解析は終了する。トークンの入
力シーケンスが文法により生成される言語に属さないな
ら（すなわち、入力が例としてあげた文法では許容され
ない式なら）、“エラー″が表示され、解析は終了する
（つまり、″ブロック”）。

非終端記号はユーザにとってトランスペアレントである
中間記号であり、実際その意味はルールに依存する。

工ないし１１の番号を付されたルールは、合法的に生じ
得る還元（リダクション）を確立する。

シンボル：：＝は、右辺から左辺への１方向の等優性を
表わす。例えば、ルール１によると、ステートメントＥ
：：＝Ｔは、ＴがＥと置換され得る（つまりＥに還元さ
れ得る）ことを意味する。

例のルール１〜１１は、標準的な演算階層、つまり演算
子の優先順位を維持している。したがって、式ａ＋ｂ　
＊　ｃでは１乗算ｂ＊Ｃが最初に行なわれ、加算＋はそ
の後に続く。このとこはルールの中で反映されている。

ルールの中で、可能性があるとするなら、最終りダクシ
ョン（還元）はルール１に対応する。加算演算子を含む
ルール２は。

乗算演算子を含むルール５よりも、ルー゛ル１による最
終りダクションに近い。

パーサの制御は、現在の入カドークンとスタックの頂部
の現在状態が与えられると取るべき活動を指定するテー
ブルによって行なわれる。これらテーブル（または行列
）は、特定文法についての動作を内容とする。かかる行
列の例が第１図および第２図に示されており、以下で詳
細に説明する。

解析時に起こり得る動作は合計７通である。そのうち終
端動作行列に従って起こり得る動作は５通りであり、非
終端動作行列に従うのは２通りである。終端動作テーブ
ルのエントリは、５通りの値のうちの１つを有すること
ができる。

シフトｎは″シフト″入力を意味しくつまり。

後続シンボルが現在シンボルになる）、ｎを現在状態と
して、ｎを状態スタックにブツシュする。

シフト動作は前進遷移であり、これに関連するテーブル
・エントリは、パーサが入るべき後続の状態である。一
般に、シフトにおいては、入力ストリーム中の後続の新
たなシンボルが受理されて解析に回される。

（２）ｐによる還−： 文法ルールＰを適用する。これは、ルールｐの右辺の各
記号につき１つの状態をスタックから除去し、（ポツプ
・オフ）、状態スタックの頂点になった状態を現在状態
とし、ルールｐの左辺の記号についての非終端動作を取
ることにより行なわれる。還元動作は後退であり、これ
に関連するテーブル・エントリはルール番号を表わす整
数である。スタックの頂部から除去する状態数には、右
辺の長さとして計算される。還元動作の実行後、還元さ
れたルールの左辺が現在入力記号となり。

残りのトークン・ストリームの前に置かれる。

３　シフト／　による゛　−： ルールｐによる還元がすぐに続く、シフト入力動作であ
る。シフト／還元動作は、還元動作に先立つ任意の状態
へのシフト動作と等価である。シフト／還元に関連する
テーブル・エントリはルール番号である。

口１２え雇じ− 人力の解析が成功したことを知らせる。解析は完了して
いる。どんな解析テーブルでも１つだけ受理動作がある
。

℃σ工孔う：二Ｌ エラー動作−一解析を停止して入力を拒絶する。

それから先の解析は不可能である。つまり入力はエラー
である。

非終端動作マトリックスは還元動作に続く非終端動作用
のものである。行先テーブルのエントリには、２通りの
値のうちの１つを有することができる。

状態ｎに状態スタックにブツシュし、状態ｎを現在状態
にする。ｇｏｔｏ動作は前向遷移であり、これに関連す
るテーブル・エントリはパーサが入るべき後続の状態で
ある。後続の動作は終端動作である。

（２）　ｇｏｔｏ／ｉ元ｐ 名前のない状態に対してｇｏｔｏ動作を実行し、直後に
還元ｐ動作を行なう。ｇｏｔｏ／還元動作は、還元動作
に先立つ任意の状態へのｇｏｔｏ動作と等価である。ｇ
ｏｔｏ／ｉ元動作に関連するテーブル・エントリは、ル
ール番号である。

非終端動作マトリックスは空（ｖｏｉｄ）のエントリを
持ち得るけれども、エラー・エントリは存在しない。

パ還元″動作は１文法ルールに従う入力の派生（ｄｅｒ
ｉｖａｔｉｏｎ）の再生成（ｒｅｃｏｎｓｔｒｕｃｔｉ
ｏｎ）を可能にするので、最も重要性が高い。例えば、
式ｉｄ＋ｉｄは、非終端記号Ｅから生成される。

派生は非終端記号から始まり、ここまで生成されたシー
ケンスの最も右にある非終端記号に対しであるルールが
適用される。適用されるルールの番号が、次の式におい
て記号１１　＝＞　１１の下に示されている。

Ｅ　＝　＞　Ｅ　＋　Ｔ　＝　＞　Ｅ　＋　Ｆ　＝　＞
　Ｅ　十Ｖ　＝　＞　Ｅ　＋　ｉ　ｄ”＞Ｔ＋ｉ　ｄ＝
＞Ｆ＋ｉ　ｄ＝＞Ｖ＋ｉ　ｄ＝＞ｉ　ｄｌ　　　　　４
　　　　　６　　　８ 十ｉｄ したがって、まずルール３を使ってＥが書き直されてＥ
＋Ｔが得られる。次にルール４を使ってＥ＋Ｆに書き直
される。次にルール６を使ってＦがＶに書き直される。

といった具合である。書き直すべき非終端記号がなくな
ると、派生は停止する。その結果、式ｉｄ＋ｉｄが生ま
れる。

入力シーケンスの解析によれば、還元動作に通して派生
の逆が生成される。上記例では。

ｉｄ＋ｉｄ＜＝Ｖ＋ｉｄ＜＝Ｆ＋ｉｄ＜：Ｔ十ｉｄ＜＝
Ｅ＋ｉ　ｄ＜＝Ｅ＋Ｖ＜＝Ｅ＋Ｆ＜＝Ｅ＋Ｔ＜＝Ｅ 解析動作は以下のとおりである。

Ｌ）Ｅを予期する状態でスタートする。

２）′ｖを予期する状態にシフトし、最も左にあるｉｄ
トークンを読み取る。

３）ルール８によって還元する。

４）ｇｏｔｏ／ルール６での還元。

５）ｇｏｔｏ／ルール４での電光。

６）Ｔが解析済であることを覚えている状態にシフトす
る。

７）ルール１による還元。

８）Ｅが解析済であることを覚えている状態にシフトす
る。

９）Ｔを予期する状態にシフトし、十トークンを読み取
る。

１０）Ｖを予期する状態にシフトし、最も左のｉｄトー
クンを読み取る。

１１）ルール８による還元。

１２　）　ｇｏｔｏ／ルール６での還元。

１３　）　ｇｏｔｏ／ルール４での還元。

１４）Ｔが解析済であることを覚えている状態にシフト
する。

１５）ルール３による還元。

１６）ｅｏｆトークンを受理する。

パーサの状態は、終端記号・非終端記号である番号とし
て符号化される。ルール番号はルールを表わすのに用い
られる。文法例に対応する終端記号・マトリックスおよ
び非終端記号・マトリックスの例が、第１図および第２
図にそれぞれ示されている。この例では状態が１から始
まる番号として示されている。しかし、わかりやすくす
るため、番号は記号に割り当てられているわけではない
。

マトリックスのエントリは上述した解析動作である。こ
れらの動作はマトリックスの中で次のように略記されて
いる。

Ｓｎ　　　　状態番号ｎへのシフト Ｇｎ　　　　状態記号ｎへ行＜　（ｇｏｔｏ）Ｒｋ　　
　　ルール番号ｋによる還元 ＳＲｋ　　　シフト／ルール番号による還元Ｇ　Ｒｋ　
　　ｇｏｔｏ／ルール番号ｋによる還元Ａｃｃ　　　受
理動作 Ｅｒｒ　　　エラー 非終端動作マトリックスはｇｏｔｏおよびｇｏｔｏ・還
元動作を含む。終端動作マトリックスはシフト、シフト
・還元、還元、および受理動作を含む。エラー動作は空
白のエントリによって示されている。

文法例についてのＬＲパーサの終端動作マトリックスが
第１図に示され、非終端動作マトリックス（行先、ｇｏ
ｔｏマトリックス）が第２図に示されている。−船釣に
行列も非常に希薄である。（つまり、はとんどのエント
リがエラー動作である。）この例では、終端動作マトリ
ックスは約半分しか詰まっておらず、非終端動作マトリ
ックスは約１／３しか詰まっていない。

これら２つの行列は多くの空白のエントリを含むけれど
も、そのままで使うことができる。本発明による圧縮法
の目標は、エントリをできるだけ多くの削減して、各マ
トリックスを単純線形（１次元）テーブルに圧縮するこ
とである。

入力シーケンスの解析は、これらの行列、およびその時
までに解析された入力の形を覚える５′状態スタツク”
によってコントロールされる。″状態″は動作マトリッ
クスの行インデックスとして符号化される。解析の始ま
る初期つまり開始状態があり、これは約束で状態１とさ
れる。構文解析は状態スタックで状態１から開始する。

さらに、入力シーケンスの終りに追加されて、入力が終
了したことを知らせる。特殊な入力記号″ｅＯｆｎがあ
る。

これらのマトリックスは次のようにして使用される。パ
現在状態″は常に状態スタックのトップにある状態であ
る。″現在人力″記号は現在読取中の記号である。現在
入力記号についての動作を獲得するために、現在状態と
現在入力記号が、それぞれ終端マトリックスの行インデ
ックスと例インデックスとして使用される。

シフト動作は後続の入力記号を獲得して、新たな現在状
態を状態スタックにブツシュする。還元動作は状態スタ
ックから状態を除去するとともに、還元中のルールの左
辺に相当する非終端記号について非終端動作を行なう。

以上のことは、”　Ａ　＋　Ｂ”を例にとって考えると
理解し易い。“Ａ　＋　Ｂ　”は“Ａ　＋　Ｂ　’　ｅ
ｏｆ”になる。ｅｏｆ記号は式の終りを表示するマーカ
ーの役を果たす。今の例では最初の入カドークンはＡ’
（ｉｄ終端記号）である。したがって、第１図によれば
、状態１の行とｉｄの列を参照することにより、最初の
動作が発見される。そこに配置されている動作は“Ｓ５
”であり、これは入力をシフトさせ、かつ状態５を状態
スタックにブツシュすることを意味する。入力ストリー
ムの次のトークン“＋”が現在入力記号になり、かつ状
態スタックのトップにある状態５が現在状態になる。し
たがって、とるべき終端動作は、行５において“＋”入
カドークンの下１手表示されているＲ８”である。これ
は、ルール８による還元を意味し、ｉｄをＶに還元する
。

還元動作の結果、状態スタックから１つの状態。

状態５が除かれる。なぜなら、ルール８の右辺には記号
が１つしかないからである。したがって。

今の現在状態は１である。■、つまりルール８の左辺に
ついての非終端動作が実行される。したがって１行１に
おいてＶと記された列の下を見ると。

次の動作が“ＧＲ６”であることがわかる。これは、ル
ール６を用いる還元が直後に続く無名の状態へのｇｏｔ
ｏである。ルール６の右辺の長さは１なので、スタック
にブツシュされる無名の状態は還元動作によって直ちに
除かれる。このため、無名の状態を任意に選んでよい。

結果として、現在状態は１のままである。ルール６はＶ
をＦに還元する。オートマトンはまだ状態１にあるから
、Ｆ列の下を見ると、そこには“Ｇ　Ｒ４”がある。こ
れは、”ｇｏｔｏ／ルール４による還元”を意味する。

ルール４の右辺には記号が１つしかないので、無名の状
態が状態スタックにブツシュされ、その後除去される。

ルール４はＦをＴに還元する。まだ状態１にあるので、
Ｔ列を見ると、“Ｇ４″が見つかる。これは状態４へ行
くことを意味する。状態４が状態スタックにブツシュさ
れ、シーケンス１．４がその内容になる。次の動作は終
端動作である。記号４１　＋　Ｉｔが依然として現在記
号であり。

状態４が現在状態である。次に終端動作マトリックスに
おいてトークン“＋”の下で状ｓ４を探すと、ルール１
による還元が見つかる。これは、ＴをＥを還元する。還
元動作の結果、スタックのトップから状態４が除かれ、
状態１が現在状態になる。続いてルール１の左辺である
記号Ｅを使って非終端動作が行なわれる。行１と列１の
交点における動作は “Ｇ２”である。つまり状態２へのｇｏｔｏである。

状態２が状態スタックにブツシュされる。このとき、状
態スタックは、現在状態を２として、シーケンス１．２
をその内容としている。現在入力記号は依然としてｉｔ
　＋　Ｉｔである。終端動作が求められる。

状態２において、１１　＋　１１に対応する終端動作は
１１　Ｓ　７１ｊである。これは、入力をシフトし、か
つ状態７を状態スタックにブツシュすることを意味する
。状態スタックは状態７を現在状態とし、１．２．７に
なる。後続の記号は＃　Ｂ　！＋であり、ｉｔ　ｉｄ　
Ｆｊが現在入力記号になる。終端動作がとられる。

状態７では、Ｉｔ　ｉ　ｄ　ｌｊについての終端動作は
ＺｒＳ２”である。これは入力をシフト、かつ状態５を
状態スタックにブツシュすることを意味する。状態スタ
ックは１，２．７，５になり、４１ｃｏｆ＃ｊが現在入
力記号になる。現在状態は５である。

状態において゛１ｅｏｆｊｌ対応する終端動作はＲ８で
ある。これは、ｉｄをＶに還元する。その結果、状態５
が状態スタックのトップかち除かれ、新しい状態７にお
いてＶに関する非終端動作が行なわれる。この動作はＧ
　Ｒ６であり、”ｇｏｔｏ／ルール６による還元（Ｆ＝
＞Ｖ）”である。ある無毛の状態が状態スタックにブツ
シュされた後そこからポツプされ、現在状態は７のまま
である。続いて。

状態７においてＦについての非終端動作が実行される。

この動作はＧｌｌ、つまり“ｇｏｔｏ　１１　”であり
、状態１１を状態スタックにブツシュする。

このとき、状態スタックは１．２．７．１１である。状
態１１が現在状態であり　１１ｅｏｆｌｊが現在入力記
号である。終端動作がとられる。状態１１において、ｔ
ｌｅｏｆｔＴについての終端動作はＲ３であり、ルール
３による還元、つまりＥ＝＞Ｅ＋Ｔである。このルール
の右辺の長さは３であるので、３個の状態が状態スタッ
クのトップから除去され、状態１だけが残ることになる
。状態１を現在状態とし、かつルール３の左辺であるＥ
を非終端記号として、非終端動作が行なわれる。非終端
動作マトリックスの与える動作はＧ２、つまり“Ｇｏｔ
ｏ　２　”であり、状態２を状態スタックにブツシュす
る。

状態スタックの内容は１と２になり、状態２を現在状態
としている。現在入力記号は依然としてＩＩｅＯｆｌｌ
である。次の動作は終端動作である。

状態２“ｅｏｆ”ではについての終端動作はＡｃＣ１つ
まり受理動作である。したがって、当該入力シーケンス
に関して構文解析が成功裡に終了した。

上述したタイプの動作マトリックスは一般に巨大であり
、マトリックス式アクセスは一般に高価なものとなる。

第１図と第２図の例では、合計１３２のエントリがあり
、そのうち６１が非エラー・エントリである。モダン・
プログラミング言語用の文法だとエントリの数は２００
０ｏＯ以上になるけれども、約４０００個（２％）以外
のエントリはエラー・エントリであることが普通である
。

マトリックスの行と列を並べ換え、かつそれに応じて前
向遷移エントリを変更することにより、オリジナルと同
形（ｉｓｏｍｏｒｐｈｉｃ）であって同一の８語を認識
する別のオートマトンを生成することができる。実際１
行の並べ換えは状態の再ラベル付けとなるし、列の並べ
換えは記号の再ラベル付けとなる。

このような１５１ｍが本発明に従うテーブル圧縮法の基
礎を形成する。パーサがＱ個の状態、Ｍ個の終端、Ｎ個
の非終端を備えていると仮定しよう。

動作テーブルは、終端記号が列位置１〜Ｍを占める状態
で、〔１・・・Ｑ、１・・・Ｍ〕なる次元を持つ。一方
、行先テーブルは、非終端記号が列位置１〜Ｎを占める
状態で、〔１・・・Ｑ、０・・・Ｎ〕なる次元を持つ。

行先テーブルに付加された０番目の列は、重要なエント
リだけを含むと仮定されるが、これについては後で詳し
く説明する。

普通、ＮＸＭマトリックスの１番目の行、５番目の列の
要素にアクセスするためには、加算１回、減算１回、そ
して乗算１回が必要とされる。本発明では、行先テーブ
ル（Ｇｏｔｏテーブル）がＢＡＳＥ　　ＡＣＴＩＯＮ　
（基底動作）と呼ばれる単純ベクトルに圧縮される。各
状態Ｓは、ＢＡＳＥ　　ＡＣＴＩＯＮにおける、状態Ｓ
に対応する行先マトリックスの行が置かれた場所のイン
デックスとして表わされる。したがって１行先マトリッ
クスの列インデックスによって表わされる非終端Ａが与
えられると、状態Ｓにおける記号Ａについての動作が、
ＢＡＳＥ　　ＡＣＴＩＯＮ　（ＳＥＡ）として、つま’
ＪＢＡＳＥ　　ＡＣＴＩＯＮテーブルをインデックスＳ
＋Ａでもって引くことにより、計算可能である。このた
め、本方法を用いる非終端動作の計算コストは１回の加
算と１回のインデックス動作であり、マトリックス表現
を用いる動作の計算コストより少ない。構文解析の際に
計算される動作の大部分は非終端動作である。ので、か
かる効果は顕著なものになる。

ＢＡＳＥ−ＡＣＴ工ｏＮベクトルにおける有意エントリ
の数は、行先テーブルの有意エントリの数にオートマト
ンの状態数を加えた数に等しい。

通常、ＢＡＳＥ　　ＡＣＴＩ○Ｎ要素の５％しか未使用
にならない。それにもかかわらず、時間を犠牲にして、
さらに２つのベクトルＢＡＳＥ　　ＣＨＥＣＫ　（基本
チエツク）とＧＯＴＯ−ＤＥＦＡＵＬ　Ｔ　（ｇｏｔｏ
デフォルト）を伴う本方法の変形を使うことにより、顕
著なスペース面での改善が図られる。

Ｂ　Ａ　Ｓ　Ｅ　　ＣＨＥ　ＣＫベクトルは、ＢＡＳＥ
−ＡＣＴＩＯＮベクトルとパラレルに用いられ、状態Ｓ
と非終端Ａのそれぞれについて、非終端アクションが状
態ＳのＡで規定されている場合にのみ。

ＢＡＳＥ　　ＣＨＥＣＫ　（ＳＥＡ）はＡに等しくなる
。ＧＯＴＯＤＥＦＡＵＬＴベク１−ルは、各非終端につ
いてのデフォルトの動作をその内容としている。非終端
Ａについてのデフォルト動作は、行先マトリックスで最
も頻繁い登場する動作である。

新しい表現と使うと、状態Ｓ、非終端Ａについて規定さ
れている動作は、以下のアルゴリズムを用いて計算でき
る。なお、ＩＩ　／　＊　ｕとＬｄ　、　／　ｌ″の間
にはコメントを記している。

ｉｆ　ＢＡＳＪＣＨＥＣＫ（ＳＥＡ）＝Ａ　ｔｈｅｎＹ
ｉｅｌｄ　ＢＡＳＩＥ−ＡＣＴＩＯＮ（ＳＥＡ）　；　
／　”動作はＢＡＳＪＡＣ丁ｌ０Ｎ（ＳＥＡ）　　であ
る亨／ ｅｌｓｅ　Ｙｉｅｌｄ　ＧＯＴＯ−ＤＥＦＡＵＬＴ（Ａ
）；／＊そうでない場合、 動作ＧＯＴＯ−ＤＥＦＡＵＬＴ（Ａ） である＊／ この新たな表現では、インデックス動作を１回、比較を
１回行なう。つまり詳しく言うと、ＲＡＳＥ　　ＣＨＥ
ＣＫベクトルをＳＥＡでもって引くとともに、ＢＡＳＥ
　　ＣＨＥＣＫ　（ＳＥＡ）とＡが等価であるか比較を
行なうので、時間コストは余分にかかる。しかしながら
、ＢＡＳＥ　　ＡＣＴＩＯＮが元々必要とするスペース
の５０％をも節約することができる。

動作テーブルは２つのパラレルなベクトルに圧縮される
。１つはＴＥＲＭ　　ＡＣＴＩＯＮ　（終端動作）であ
り、実際の終端動作エントリを含む。

もう１つはＴＥＲＭ　　ＣＨＥＣＫ　（終端チエツク）
であり、ＴＥＲＭ　　ＡＣＴＩＯＮ中の対応する要素の
有効性を確かめるのに使われる。これらのテーブル中の
有意エントリの数は、一般に動作テーブル中の有意エン
トリの数よりも少ない。このような節約が達成されるの
は、動作テーブルの多くの行がＴＥＲＭ　　ＡＣＴＩＯ
Ｎに配置される前に組み合わされるからである。状態Ｓ
と終端記号して規定される動作は、以下のアルゴリズム
を使って計算することができる。

ｓｓ　：　＝　５Ａｓｃ、、ｇＡｃｒ工ｏＮ（ｓ）　；
　／　率ＳＳ　ヲＢＡＳＥ−ＡＣＴＩＯＮ（Ｓ）にする
ネ／ ｉｆ　ＴＥＲＭ、、−ＣＨＥＣＫ（ＳＳ＋ｔ）　＝　ｔ
　ｔｈｅｎＹｉｅｌｄ　ＴＥＲＭＪＣＴＩＯＮ　（ＳＳ
十ｔ　）；／宰動作はＴＥＲＭＪＣＴＩＯＮ （ＳＳ＋ｔ）である。傘／ ｅｌｓｅ　Ｙｉｅｌｄ　ＴＥＲＭＪＣＴＯＮ（ＳＳ）；
７本そうでない場合、動 作はＴＥＲＭＪＣＴＯＮ　（ＳＳ　）である。＊／ ここでも、１回の終端動作の計算は、３回のインデック
ス動作、１回の加算、および１回の比較からなるので、
マトリックス要素のアクセス・コストに極めて近くなる
。

パーサは、各ルールの左辺の記号を内容に持つベクトル
と各ルールの右辺の長さを内容に持つぺクトルとを必要
とする。ＢＡＳＥ　　ＣＨＥＣＫベクトル（Ｇｏｔｏデ
フォルトが使われるとき）とこれらの２つの補助ベクト
ルに追加（アペンド）される。したがって、ベース・ベ
クトルの下限は、言語のルール数に１を加えた数である
。

Ｇｏｔｏデフォルトを使うと、各非終端について最も頻
轄に生じる動作が、登場位置がどこであれ、行先マトリ
ックスから除去される。Ｇｏｔｏデフォルト・ベクトル
は、非終端記号の各々をその“デフォルト″つまり、最
も頻繁に発生する動作と関連づけるのに用いられる。既
に述べたように、パーサに影響を与えることなく、行先
マトリックスの行と列を並べ換えることができる。行と
列が、そこに含む動作の数の順に並べ換えられる。すな
わち、動作が最も多い行が第１行となり、動作が最も多
い列が第１列となる。本発明のこのステップは重要であ
る。なぜなら、マトリックスの上玉角部に有意動作エン
トリを集中させることにつながるからである。その結果
、密度の比較的濃い行が最初に登場し、各行の行動は第
１列の近辺に群がる傾向が出ている。ゼロによって索引
づけられる特別の列が、並べ換えた後のマトリックスに
追加される。この列は、各行の本来のインデックスをそ
の内容としており、したがって行に施された並べ換えを
表わす。どのシフト動作ｇｏｔｏ動作も状態の並べ換え
に従って再番号づけしなければならないので、この列は
必要である。ＢＡＳＥ　　ＡＣＴＩＯＮベクトルを生成
する際にも、このベクトルは、対応する状態の終端動作
についてのインデックス位置を与えるのに用いられる。

続いて、並べ換えられた行先マトリックスはＢＡＳＥ　
　ＡＣＴＩＯＮベクトルを形成すべく圧縮される。圧縮
アルゴリズムは以下の通りである。

ＢＡＳＥ　　ＡＣ”ｊ’ＩＯＮベクトルのエントリの各
々は、最初、エントリがパ未定義″であることを示す特
別な値に設定される。次に、並べ換えられた行先マトリ
ックスの各行は、ＢＡＳＥ−ＡＣＴＩＯＮベクトルの未
使用部と“比較″される。比較はＢＡＳＥ　　ＡＣＴＩ
ＯＮベクトルの最初の使用可能・未定義エントリから始
められ、行先マトリックスの行の各有意エントリがＢＡ
ＳＥ　　ＡＣＴＩＯＮベクトルの未定義エントリと対応
すると判断されたら成功する。比較が不成功に終わると
。

ＢＡＳＥ　　ＡＣＴＩ○Ｎベクトルの次の使用可能・未
定義エントリが試みられ、処理が繰り返される。

最後には比較は成功しなければならない。比較が成功し
た点において、行先マトリックスの行はＢＡＳＥ　　Ａ
ＣＴＩＯＮベクトルにオーバーレイされる。このアルゴ
リズムは下記の擬似コードに要約される。

ＢＡＳＥ　　ＡＣＴＩ○Ｎ全エントリを未定義にセット
する。

並べ換えられた行先マトリックスの各行工について実行 ＢＡＳＥ　　ＡＣＴＩＯＮ　（Ｊ）が未定義に等しいよ
うな各Ｊについて実行。Ｇｏｔｏ　（Ｉ　、　Ｋ）が有
意であるようなすべてのＫについて ＢＡＳＥ　　ＡＣＴＩＯＮ　（Ｊ＋Ｋ）が未定義ならば
かかるすべてについてＢＡＳＥ−ＡＣＴＩＯＮ（Ｊ＋Ｋ
）をＧｏｔｏ　（Ｉ、Ｋ）にセットする。次に行１につ
いて継続する。

各行のＯ番目の要素は有意エントリとなるから。

各行がユニークな場所で開始することが保証される。上
述したような行と列の頻度ソートは、良好な圧縮を達成
するのに役立つ。最も高密度の行がＢＡＳＥ　　ＡＣＴ
ＩＯＮにまず置かれるので、作られたギャップは後で希
薄な行で満たされる。そのような希薄行の多くは１，２
個のエントリしかもたない。

状態は、ＢＡＳＥ　　ＡＣＴＩＯＮでの０番目要素のイ
ンデックスによって表現される。したがって、状態Ｓが
与えられたなら、Ｓにおいて記号Ｘについて規定された
動作を得るためには、ＸをＳに加算してＢＡＳＥ　　Ａ
ＣＴＩＯＮをその結果で引けばよい。

ＢＡＳＥ　　ＡＣＴＩＯＮ中のすべての前向遷移（ｇｏ
ｔｏ動作）は、状態の新しいラベル付けを反映するよう
に変えられる。５ＴＡＲＴ　　５ＴＡＴＥという特別な
変数は、オートマトンの開始状態の値を維持するのに用
いられる。受理動作（ＡＣＣＥＰＴ−ＡＣＴＩＯＮ）の
値は、ＢＡＳＥ　　ＡＣＴ、ＩＯＮにおいてＧｏｔｏ行
が用いる最高インデックスの値プラス１として符号化さ
れる。エラー動作（ＥＲＲＯＲＡＣＴＩＯＮ）の値は、
ＡＣＣＥＰＴ−ＡＣＴＩＯＮ＋１として符号化される。

ＢＡＳＥ　　ＡＣＴＩＯＮ内の未定義のま末であるすべ
ての位置（有意エントリを持つ最後のインデックスまテ
）ニはＥＲＲＯＲＡＣＴＩＯＮが割り当てられる。Ｇｏ
ｔｏデフォルトが用いられるときは所与の状態およびＢ
ＡＳＥ　　ＡＣＴＩＯＮテーブルから得られた入力記号
についての非終端動作は必ずしも正確でないので、パラ
レルなりＡＳＥ−ＣＨＥＣＫテーブルに照らしてチエツ
クされなければならない。各行はＢＡＳＥ　　ＡＣＴＩ
ＯＮの中のユニークな場所から始まるので、有意動作が
規定されている。行の中の各記号もユニークな場所を持
つ。したがって、ＢＡＳＥ　　ＡＣＴＩＯＮベクトルの
有意エントリに対応するＢＡＳＥ　　ＣＨＥＣＫベクト
ルは、有意エントリが規定されている記号を含む。ＢＡ
ＳＥ　　ＡＣＴＩＯＮのＥＲＲＯＲＡＣＴＩＯＮエント
リに対応する。ＢＡＳＥ’　　ＣＨＥＣＫの上限は、Ｂ
ＡＳＥ　　ＡＣＴＩＯＮにおけ最高のインデックスを獲
得したＧｏｔｏ行で規定される。最高の非終端動作に関
するチエツクを許容できるように、拡張されなければな
らない。

２つのベクトル、つまりＴＥＲＭＩＮＡＬ　　ＡＣＴＩ
ＯＮ　（終端動作）　とＴＥＲＭＩＮＡＬ　　ＣＨＥＣ
Ｋ、（終端チエツク）を使って、終端動作マトリックス
が表現される。ＴＥＲＭＩＮＡＬ−ＣＨＥＣＫベクトル
はＢＡＳＥ−ＣＨＥＣＫベクトルと同じ機能を持つ。す
なわち、所与の状態及び終端入力記号に関して、計算で
求められたＴＥＲＭＩＮＡＬ　　ＣＨＥＣＫベクトルの
エントリがＴＥＲＭＩＮＡＬ−ＡＣＴＩＯＮべ’）ト）
Ｌｉ中の対応エントリの有効性を検査する。ＴＥＲＭＩ
ＮＡＬＣＨＥＣＫベクトルが必要とされる理由は、入力
がエラーであるかもしれないこと、およびデフォルト還
元が使用されることにある。

終端動作マトリックスをベクトルに圧縮する前に、有意
エントリの数を減らすべく２つのステップが実行される
。それらは、互換性のある（ｏｍｐａｔｉｂｌｅ）状態
を併合（ｍｅｒｇｅ）すること、および各行の最も頻度
の高い還元動作をデフォルト還元と置換することである
。

以下の条件が満足されるとき、状態Ｓ２は他の状態Ｓ１
と互換性があると言う。

１．８１と８２は同じシフト、シフト／還元動作エント
リを有する。

２．８２の還元動作に関係するルール・セットと８１の
還元動作に関係するそれは同じである。

３、状態Ｓ１とＳ２の両方において規定されている還元
動作に関する終端記号ｔの各々について、還元動作が一
致する。

まずオートマトンの状態が区分され、それにより終端動
作マトリックスの行が互換性クラスに区分される。まず
上記条件１のみに基づいて粗い区分が行なわれる。条件
１は、シフトとシフト／還元の動作が一致するなら状態
同士の互換性ありとするものであった。所与のしようだ
いに関するシフト・エントリは、その状態の″シフト・
マツプ″によって表わされ得る。ここでシフト・マツプ
とは、終端記号と所与の状態で該記号についてなされる
べきシフトまたはシフト／還元動作とからなる対のセッ
トのことである。ある互換性クラス内の状態はすべて同
じシフト・マツプを有する。

所与の状態に関する還元エントリは、その″還元マツプ
″すなわち終端記号と該所与の状態で該記号についてな
されるべき還元動作とからなる対のセットによって表わ
される。シフト・マツプ互換性クラスの各々は、該クラ
スの状態の還元マツプに従ってさらに区分することがで
きる。この区分は上記条件２、条件３に基いて行なわれ
る。

区分が完了した後、各クラスの状態は以下のようにして
単一状態に併合される。シフト・エントリおよびシフト
／還元動作は共通している。所与のクラスの任意の状態
においである還元動作が生じるなら、それも含まれる。

併合後の状態に対応するべく、終端動作マトリックスの
行は再定義される。

次に、“デフォルト還元”動作が修正後の終端動作マト
リックスの各行について計算され、所与の行の０番目の
列に入れられる。デフォルト還元は、当該行において還
元動作があるなら単純に最も発生頻度の高い還元動作と
され、なければエラー動作とされる。

行が併合され、デフォルト還元列が付加された終端動作
行列は、行先マトリックスを圧縮するのに使ったのと同
じアルゴリズムを使って圧縮される。結果生じるのが、
ＴＥＲＭＩＮ　　ＡＣＴＩＯＮテーブルとＴＥＲＭＩＮ
　　ＣＨＥＣＫテーブルである。ＴＥＲＭＩＮ　　ＡＣ
，Ｔｌ０Ｎテーブル中のシフト動作（前向遷移）はすべ
て、ＢＡＳＥ−ＡＣＴＩＯＮで用いられたのと同じ状態
ラベルリングを反映するように変更される。各シフト／
還元動作ｒｒは、ルールｒｒに関する還元動作と区別さ
れるように、ＥＲＲＯＲＡＣＴＩＯＮ＋ｒｒとして符号
化される。最終的に、ＢＡＳＥ　　ＡＣＴＩＯＮ中の各
行先テーブル行の第Ｏエントリは、ＴＥＲＭＩＮＡＬ　
　ＡＣＴＩＯＮ中の対応する終端動作マトリックス行の
開始（第０）インデックスを使って更新される。ここで
、併合されたすべての行は、ＴＥＲＭＩＮＡＬ　　ＡＣ
ＴＩＯＮ内で同一の開始位置を有することに注意された
い。

動作新たな符号化により、その値がルールの数似下であ
るエントリは、還元またはｇｏｔｏ還元エントリである
。また、その値がルールの数より大きいけれどもＡＣＣ
ＥＰＴ　　ＡＣＴＩＯＮ未満であるエントリは、シフト
またはｇｏｔｏエントリである。

その値がＥＲＲＯＲＡＣＴＩＯＮより大きなエントリな
シフト／還元動作であり、還元されるルールはエントリ
値からＥＲＲＯＲＡＣＴＩＯＮを減することにより得ら
れる。

結果として得られる圧縮されたテーブルは、標準的なＬ
Ｒ解析のアルゴリズムとともに使用してよい。構文解析
の任意の時点において、保留動作。

現在状態、現在終端入力記号、および残っている入力の
シーケンスとともに状態を持つスタックが存在する。ス
タックは最初開始状態を内容としている。現在状態は常
に状態スタックのトップにある状態である。圧縮済テー
ブルを使うと、開始状態はＢＡＳＥ　　ＡＣＴＩＯＮテ
ーブルに対する所定のインデックスになる。最初このイ
ンデックスが状態スタックにブツシュされる。現在状態
と現在入力記号によって後続の解析動作が決定される。

この動作は常に終端記号動作である。このように。

現在状態インデックスでのＢＡＳＥ　　ＡＣＴＩＯＮテ
ーブルの値は、ＴＥＲＭＩＮＡＬ　　ＡＣＴＩＯＮにお
ける終端動作の見つかるインデックスを与える。したが
って、Ｃ８が現在状態を意味し、ＣＩが現在入力を意味
するとすると、解析動作は、ＴＥＲＭＩＮＡＬ　　ＣＨ
ＥＣＫ　（ＢＡＳＥ　　ＡｃＴｒｏＮ（Ｃｓ）＋ＣＩ）
がＣＩに等しいならば、ＴＥＲＭＩＮＡＬ　　ＡＣＴＩ
ＯＮ　（ＢＡＳＥＡＣＴＩＯＮ　（Ｃ８）＋ＣＩ）の値
になる。

そうでないならば、ＴＥＲＭＩＮＡＬ　　ＡＣＴＩＯＮ
　（ＢＡＳＥ　　ＡＣＴＩＯＮ　（Ｃ８））になる。

このようにして決まる終端記号動作は、還元動作である
かもしれないしく値がルール数以下の場合）、シフト動
作であるかもしれないしく値がルール数を超えるけれど
もＡＣＣＥＰＴ　　ＡＣＴＩＯＮ未満である場合）、シ
フト／還元動作であるカモシれないしく値がＥＲＲＯＲ
ＡＣＴＩＯＮを超える場合）、受理動作であるかもしれ
ないしく値がＡＣＣＥＰＴ　　ＡＣＴＩＯＮに等しい場
合）、あるいはエラーであるかもしれない、（値がＥＲ
ＲＯＲＡＣＴＩＯＮに等しい場合）。上述したようにし
て決まった動作がシフト動作である場合。

新たな状態が状態スタックにブツシュされ、後続の入力
記号が現在入力記号になる。また、還元動作に決まった
場合とは、還元されるルールの右辺の長さに等しい数の
状態がスタックからポツプされる。スタックのトップが
現在状態になり、現在状態と還元されるルールの左辺を
使って非終端動作が実行される。動作がシフト／還元動
作であるなら、還元動作が実行されるけれども、右辺の
長さは１減少される。動作が受理動作なら、解析は成功
裡に終了したことになる。動作がエラー動作なら、解析
は入力中のエラーよってブロックされたわけである。

非終端動作はＢＡＳＥ　　ＡＣＴＩＯＮテーブル、現在
Ｃ８、最後に還元されたルールの左辺記号りを使って行
なわれる。

ＢＡＳＥ　　ＡＣＴＩＯＮ　（Ｃ８＋Ｌ）がＬに等しい
なら、非終端動作はＢＡＳＥ　　ＡＣＴＩＯＮ（Ｃ３＋
Ｌ）の値となる。

その他の場合、ＤＥＦＡＵＬＴ　　ＧＯＴ○（Ｌ）が非
終端動作になる。

この動作はｇｏｔｏ動作またはｇｏｔｏ還元動作である
。

前者の場合、当該値が状態スタックにブツシュされ、現
在状態になる。現在状態と現在記号に関する終端動作が
生じる。後者の場合、還元動作が実行されるけれども、
右辺の長さは１だけ減る。

上記方法は、以下の例を参照すること比よって、より明
解に理解されるのであろう。

まず、非終端動作行列が簡約され、続いて圧縮される。

非終端動作の数の削減は、″デフォルト″ｇｏｔｏ動作
の使用によって達成される。すなわち、非終端マトリッ
クスの各列から、最も頻繁に発生する動作（ｇｏｔｏま
たはｇｏｔｏ／還元）が除かれる。

最も頻繁に発生する動作が２以上ある場合は、そのうち
の何れかを選択してもよい。結果は、非終端記号によっ
てインデックスされるｇｏｔｏデフォルト動作のベクト
ルである。今の例では、このベクトルは第３図で示され
るようなデフォルトｇｏｔｏ　（行先）テーブルである
。

このようなファクタライズの結果、非終端動作マトリッ
クスに最初あった２３エントリのうちの１７が削除され
る。マトリックスでは、デフォルト動作が°エラー（つ
まり空席）エントリと置換される。したがって、今の例
では、非終端動作マトリックスは第４図に示される如く
になる。

この簡約ステップにはコストがかかる。デフォルトｇｏ
　ｔｏ子テーブル非終端動作マトリックスの１行分のス
ペースを必要とする。非終端動作を獲得するのにもコス
トがかかる。行先をデフォルトにしない場合、解析時に
決定された非終端動作がエラー動作になることはあり得
ない。行先をデフォルトにすると、非終端エラー動作に
よって、所与の非終端記号につきデフォルト動作をとる
べきことが示される。これは解析時にしなければならな
い特別なチエツクである。非終端動作マトリックスが単
純ベクトルに圧縮されると、エラーのチエツクは余分な
チエツク・ベクトルを必要とする。

ｇｏｔｏデフォルト動作の使用は本圧縮方法の１部では
ないけれども、本方法とともに使われて通常はテーブル
・スペースの相当な節約をもたらす。

さて、節約化された非終端マトリックスは、単一の動作
テーブルとチエツク・テーブルとに圧縮される。チエツ
ク・テーブルが必要なのは、　ｇｏｔ。

デフォルト動作が使用される場合のみである。マトリッ
クスのテーブルへの圧縮は、大部分、行をシフトさせ互
いにオーバーレイすることによって行なわれる。

１つの方法は次のように進行する。第１行をレイ・ダウ
ンする。第２行を１位置分右ヘシフトさせ、第１行と″
オーバーレイ″できるか否かテストする。ある行の非エ
ラー・エントリを持つ位置の各々において、他の行がエ
ラー（ブランク）エントリを持つならば、前者は後者に
オーバーレイすることができる。第２行の第１行へのオ
ーバーレイは、第２行の非エラーエントリの各々を第１
行の対応位置に置くことにより達成される。オーバーレ
イが不可能なら、第２行はさらに１位置分右へシフトさ
れ、処理が繰り返される。最悪の場合には、第２行を第
１行の完全に右側ヘシフトさせなければならない。第１
行の右側と第２行の左側にエラー・エントリが来ること
を仮定する。

第２行かだい１行にオーバーレイされた場合、その結果
を第１行を考え、第３行を第２行であると考える。マト
リックスのすべての行がオーバーレイされ尽くすまで処
理は繰り返される。簡単にするため、最初に空白行はす
べて削除できるとしよう。今の例では、第５図に示され
る結果が得られる。

第５図は、対応するテーブル・エントリの下にインデッ
クス番号を付すことによって、各行の開始位置を示して
いる。したがって、行３は位置１で開始し、行５は位置
２で開示する。どいつた具合である。非終端動作マトリ
ックスの列インデックスに対応する非終端記号に番号を
付することにより、このテーブルを使って非終端動作を
見つける場合に必要とされるのは、状態番号を取り出し
てテーブルにおける動作行インデックスを見つけること
だけである。該インデックスに対して非終端記号を加え
た後にその和から１を引き算した結果は、テーブルを引
くのに使える。すなわち。

ＡＣＴＩ○Ｎ　　ＮＯ，＝ＰＯ８ＩＴＩＯＮ　　ＮＯ，
＋ＳＹＭＢＯＬ　　Ｎｏ、−１である。

したがって、（第５図の位置４から始まる）状態７にお
ける記号番号２（Ｔ）に対応する動作を見つけるために
は、位置４＋２−１　（＝５）に行き、動作Ｇｌｌを読
めばよい。

ｇｏｔｏデフォルトを使用中なので、チエツク、テーブ
ルが必要になる。このテーブルは第５図の圧縮済動作テ
ーブルと同じ長さであり、動作が規定されて゛いる。各
位置には非終端記号が含まれている。記号Ｅｒｒはエラ
ーつまり未使用チエツク、テーブルを示すのに使われて
いる。今の議論で使用するチエツク、テーブルを第６図
に示す。

状態７と記号番号２（Ｔ）についての動作を見つけるた
めには、インデックスが５として計算され、チエツク、
テーブル（第６図）の当該位置のエントリがＴであるか
否かのチエツクが行なわれる。今の例ではその通りなの
で、希望する動作が動作テーブルから獲得される。

状態３、記号番号３（Ｆ）に関する動作（つまり、第２
図に示されるＧＲ４）を希望する場合には、まずインデ
ックスが１＋３−１＝３として計算される。チエツク、
テーブルの位置３の値はＦではなくてＥであるので、Ｆ
についてデフォルトｇｏｔｏテーブル（第３図）を使っ
て動作Ｇ４を得なければならない。

上記のオーバーレイ手法によって線形ベクトルが生成さ
れる。しかし、なお多くのエントリが未使用であり、６
７％もの余分のスペースが必要とされている（つまり、
６個のエントリで済ませたいところ、合計１０個のエン
トリが存在している）。本発明による以下の方法を使う
と、オーバーレイされたテーブルをさらに簡約すること
ができる。

まず、行と列を並べ換え、含む動作の数の順に並ぶよう
にする。動作が最も多い行、列をそれぞれ第１行、第１
列にする。この結果、動作行列は“三角行列化″する傾
向にある。すなわち大抵の動作は対角線より上に登場し
、対角線の下には動作がほとんど登場しなくなる。第４
図の簡約された非終端動作マトリックスについてかかる
整理をした結果が、第７図に示され動作テーブルである
。

ここで、動作のない状態に対応する行とエントリのない
非終端に対応する列は、第４図のテーブルから削除され
ている。したがって、列Ｖ、そして行１．２．４．８．
１０．１１が削除されている。削除された非終端には、
他のものに続く番号が割り当てられる。

行また列のエントリの数が同じ場合には、それらの配置
は交換可能である。したがって、今の例では列ＲとＴが
最も多くのエントリ（どちらも２個）を持つから、これ
らの列が第７図の整理済マトリックスの最初の２行を形
成する。すべての行のエントリの数は同じなので、各行
は整理済マトリックスの任意の位置に置くことができる
。

行の動作が変更されているので、同様にｇｏｔｏデフォ
ルト・テーブルにも変更を加えなければならない。その
結果の新たなｇｏｔｏデフォルト・テーブルを第８図に
示す。

上記のオーバーレイ・アルゴリズムを使うと、第９図と
第１０図にそれぞれ示す非終端動作テーブルとチエツク
・テーブルが得られる。

ここで、未使用のエントリは２個だけである。

（余分に３３％のスペースが必要とされるだけである。

）チエツク・テーブルは最終行の長さ全体まで延ばされ
、インデックスを確実に収めている。

しかしながら、本発明では、テーブル７．９がさらに改
善される。本発明による改善は、動作テーブルのインデ
ックスによって状態番号を符号化することにより可能と
される。今の例では、状態６に番号１を付し、状態３に
番号２を付し、といった様なことが行なえる。続いて、
ｇｏｔｏ動作を状態番号を置き換えることできる。しか
しながら、非終端動作を持たない（つまりデフォルト動
作しか持たない）状態もある。したがって、テーブル・
インデックスは未使用状態の各々にも同様に割り当てら
れなければならない。さらに、終端動作テーブル（その
構成は後で説明する）中の所与の状態について、終端動
作の開始を突き止める必要がある。したがって、第７図
のマトリックスの非終端動作に、各状態に関するその終
端動作の開始インデックスを与える特別な列を付加する
のが好都合である。例えば、第１行（状態６）の特別な
左側列は、Ｔ６を含むであろう。マトリックスが完璧に
オーバーレイするなら、非終端動作テーブルの長さは、
簡約されたマトリックスのエントリの総数に状態数をプ
ラスしたものになる。

実際、終端動作がない、またはデフォルト動作だけしか
ない状態について必要とされる単独エントリは、他の行
とのオーバーレイの結果残る孔を埋めるので、結果とし
て完全なバッキングが実現される。説明中の例では、各
状態の終端動作についてのエントリを編入することによ
り、第７図の″三角行列化″された非終端動作マトリッ
クスに由来する。第１１図に示すような非終端動作テー
ブルがもたらされる。

対応するチエツク・テーブルもある。第１１図に示すチ
エツク・テーブルは、第９図のチエツク・テーブルと同
様にして生成されるけれども、第１０図の非終端動作テ
ーブルに対応させた形で示されている。ゼロまたは終端
エントリのすべてにはＥｒｒエントリが与えられ、　ｇ
ｏｔｏエントリには、第７図のｇｏｔｏエントリが現わ
れる列で決まる記号が与えられる。

状態ｋについての終端動作の開始はＴＫによって表示さ
れている。状態記号は動作テーブル中の開始インデック
スに符号化される。さらに、テーブルは、ルール番号よ
り１つ大きなインデックスで始まる。今の例ではルール
が１１個があるので、開始インデックスは１２である。

ｇｏｔｏ動作の場合、符号化された状態番号は、例えば
ＧＲ５を例にとると５である。一方、Ｇ８については番
号２７が用いられる。なぜなら、状態８は第１１図にお
いて１６にインデックスされており、かつルールの数は
１１なので、１１＋１６＝２７になる。　ｇｏｔ。

／還元動作の場合には、ルール番号が動作を表わす。最
終的に、２つのインデックスが取って置か九だ。

１つは受理動作番手ついてであり、もう１つはエラー動
作についてである。結果生じたテーブルは″基本動作テ
ーブル″と呼ばれ、第１３図に示されるような内容であ
る。

受理動作は３０として符号化され、エラー動作は３１と
して符号化される（図示していない）。

終端動作テーブルが（下記のようにして）作られるとき
、そのエントリは１から始まるようにインデックスされ
る。所与の状態ｋについての終端動作に関する開始イン
デックスが決まると、基本動作テーブル中のＴｋについ
てのエントリは当該インデックスにセットされる。

次に、終端動作行列の簡約・圧縮について考えよう。エ
ントリ数を減らすために、互換性のある行が識別される
。２つの行のシフトおよびシフト／還元動作が一致し、
かつ還元動作の組が、同じならば、２つの行は１′互換
性がある″。１方の状態と終端記号について一還元動作
が規定されるときは、必ず、他方の状態で当該終端記号
について、同じ還元動作が規定されているか、または動
作が何も規定されていないか、である。第１図の動作テ
ーブルを調べると、状態１．６が互換であり、状態３．
７．９が互換性をもつ。この結果、終端動作行列から行
が３つ除かれる。今の例での結果の行列が第１４図に示
されている。

互換性のある状態を合併することにより、今の例では７
動作（約２０％）が削除される。デフォルトの還元を取
り出すことにより、さらに多くの動作を削除することが
できる。すなわち、状態（行）毎に、頻度の最も高い還
元を抽出する。それがデフォルト還元である。所与の行
について還元がないならば、エラー動作をデフォルト還
元として使用する。今の例でデフォルト還元を取り出し
た結果が第１５図に示されている。そこで、第１例（ｄ
ｅｆ）がデフォルト動作を示している。

今の例ではデフォルト還元を取ると、８エントリ　（約
２０％）が節約される。したがって１元のマトリックス
の３８エントリのうち、１５が既に削除されたわけであ
る。

次に、上述した並べ換え方法を適用する。エントリの数
に従って行と列が並べ換えられるので、行の有効なオー
バーレイが保証される。説明中の例についての結果が第
１６図に示されている。上記のように、並べ換え法の使
用によって、マトリックスは三角行列化する傾向にある
。

次に、行のオーバーレイが実行されて、終端動作テーブ
ルが作られる。チエツク・テーブルも必要である。終端
記号がチエツク記号とマツチしないなら、該状態につい
てのデフォルト動作がとられる。今取り上げている例を
使ったオーバーレイの結果が、第１７図と第１８図にそ
れぞれ示す終端動作テーブルとチエツク・テーブルであ
る。

ここではバッキングが完璧であり、未使用のエントリは
ない。残っているのは、終端動作テーブルおよびチエツ
ク・テーブルにとっての適当な開始インデックスを割り
当て、すべての動作を符号化することだけである。シフ
ト動作は基本動作テーブル（第１３図）におけるシフト
された状態のインデックスにより表わされる。シフト／
還元動作は、基本動作テーブルのエラー・エントリのイ
ンデックスに還元されつつあるルールのルール番号を加
算することにより符号化される。受理動作は基本動作テ
ーブルにおける受理のインデックス（３０）により符号
化される。エラー動作は基本動作テーブルにおけるエラ
ーのインデックス（３１）により符号化される。これは
第１９図に示されている。

最終終端チエツク・テーブルに用いられる終端記号のイ
ンデックスは、整理された動作マトリックス（第１６図
）の列の順番づけに基いて割り当てられる。終端チエツ
ク・テーブルでは、ゼロはエラー・エントリのために用
いられる。今の例では、最終終端動作テーブルが第１９
図に、最終終端チエツク・テーブルが第２０図に、それ
ぞれ示されている。

第１９図の終端動作デープルの状態のインデックスを用
い盃と基本動作テーブルを完成させることが可能になる
。この例では、最終基本動作テーブルが第２１図に、最
終非終端チエツク・テーブルが第２２図に、そしてｇｏ
ｔｏデフォルト・テーブルが第２３図にそれぞれ示され
ている。

Ｅ０発明の効果 本発明によれば、ＬＲ構文解析テーブルを記憶するのに
要する記憶装置のスペースを大幅に節約することができ
る。

【図面の簡単な説明】

第１図は、サンプル文法についての終端動作マトリック
スである。 第２図は、サンプル文法についての非終端動作マトリッ
クスである。 第３図ないし第５図は、従来技術に従ってＬＲ子テーブ
ル圧縮する方法を示す図である。 第６図ないし第２３図は１本発明方法に従って、サンプ
ル文法に対応するＬＲ子テーブル圧縮する様子を示す図
である。 ＦＩＧ、１　　　　　　ｙｔａ゛動イ乍マトリ・ソクヌ
ＦＩＧ、２　　　非終瑞旬イ乍マトリックスＦＩＧ、３ テ°′フォルト・チーアノし

Claims (1)

1. 【特許請求の範囲】 構文解析時にとるべき動作が現在状態に対応する行と現
   在入力記号に対応する列の交点を参照することにより決
   定されるマトリックス状のＬＲ構文解析テーブルの圧縮
   方法であつて、 （ａ）上記テーブルの中の、同じ動作を持つ行を探し、 （ｂ）同じ動作を持つ複数の行が存在するならば、これ
   らの行に対応する状態を併合し、かつ上記テーブル中に
   はこれらの行を代表する行を１つだけ残して不要となつ
   た行は上記テーブルから削除し、 （ｃ）上記テーブル中の有意でないエントリが削除され
   るように、上記（ａ）、（ｂ）のステップを経たテーブ
   ル中の行を重ね合わせて上記テーブルをベクトル化し、 （ｄ）上記ベクトル化されたテーブルに対するインデッ
   クスとして使えるように上記状態を符号化する ことを特徴とする方法。