JPH0455944A - コンパイラの構文解析部の作成方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［概要］ コンパイラの構文解析部の一部をＬＲ（１）構文解析法
で作成する場合の作成方法に関し、複数の文法を単一の
ＬＲ（１）構文解析表を用いて解析できるようにするこ
とを目的とし、コンパイラの構文解析部の一部をＬＲ（
１）構文解析法で作成する場合において、ＬＲ（１）構
文解析サブルーチンを使用する部分で解析する文法が複
数存在する場合に、ＬＲ（１）構文解析サブルーチンを
作成するための文法に、解析する文法の種別を示すトー
クンを挿入することによって、複数の文法を解析するＬ
Ｒ（１）構文解析表を生成しておき（ステップ１）、こ
のＬＲ（１）構文解析表を含むＬＲ（１）構文解析サブ
ルーチンを呼出す際に、解析する文法の種別を挿入する
ことにより目的の文法を解析する（ステップ２）ように
構成する。

［産業上の利用分野］ 本発明はコンパイラの構文解析部の一部をＬＲ（１）構
文解析法で作成する場合の作成方法に関する。

［従来の技術］ ＬＲ（１）構文解析法は、コンパイラの構文解析部を計
算機等で自動生成する上で最も強力で実用的な方法であ
る。ここてＬＲ（１）構文解析法とは、ある文字列を左
から読込み、解釈は右から行い、次の動作を決める時に
は１つ先の語まで読込むという方法である。しかしなが
ら、強力なオブチマイザ（最適化ツール）がない場合に
は、構文解析部を全てＬＲ（１）構文解析法で作成する
と、構文の自動生成ツールとしてのＬＲ（１）　構文解
析表か膨大になってしまったり、解析速度が低下したり
する。

第５図はＬＲ（１）構文解析表の概念図である。

図に示すように「状態」と「語」より構成されており、
ある状態の下である語が来たらどういう処理を行うかが
記載されている。例えば、ある状態のある語とで決定さ
れる図の斜線で示される部分では、以下のような遷移が
行われる。

■１つ語を読んで、状態ｎに進む。

■１つ語を読んで、それをスタックに積んで状態ｎに進
む。

■還元処理；例えばＡ−Ａ＋Ｃという構文規則では、Ａ
＋Ｃを解析して、その結果をＡに還元し、同時に＋ａ、
ｃというコードを生成する。

ところで、ある言語の一部が全てＬＲ（１）文法でなけ
ればならないものではなく、文法によっては、制限が多
いが単純である演算子順位法や、ＬＬ　（１）構文解析
法で十分な場合もある。演算子順位法とは、＋、−、ｘ
、　　÷等の演算子に優先度をつけて構文解析を行うよ
うにするものである。

またＬＬ　（１）構文解析法は、ある文字列を左から読
込み、解釈も左から行い、次の動作を決める時には１つ
先の語まで読込むという方法である。

そのため、コンパイラを作成する上で、複数の構文解析
法を混在させることがある。コンパイラの一部をＬＲ（
１）構文解析法で作成する場合、異なる文法要素である
が、それらが互いに関連しあっているため、それらを１
つの構文解析ルーチンで解析するほうが都合がよい場合
がある。例えば、以下に示す３つの文法があるものとす
る。

■文法１（算術式ン Ｅ→Ｅ＋１１１　　　　　（１） ■文法２（条件式） ％式％（２） ここで、１は「又は」の意味である。−意名とはデータ
等の固定値を示す。これらの文法を用いて構文解析を行
う場合、それぞれの文法毎にＬＲ（１）構文解析表が必
要となる。ところが上式より明らかなように、算術式に
は一意名を用い、条件式にも算術式を用いている。また
、−意名には算術式を用いている。このように、文法が
相互に関連があることが多い。このような場合、３つの
文法も同一のＬＲ（１）構文解析表を用いた構文解析ル
ーチンで解析したほうが都合がよいことは明らかである
。

［発明が解決しようとする課題］ しかしながら、コンパイラの構文解析部の一部をサブル
ーチンとしてＬＲ（１）構文解析法で作成する場合には
、複数の文法を解析することができないという問題があ
った。このことを詳細に説明する。例えば、今、 ｉ−ｉ＋ｉ という文字列が前記文法を満足しているかどうかを調べ
る場合には、第６図に示すようなツリーを作成する。そ
して、最終的にＥで終われば前記文字列はＬＲ（１）構
文解析ができることになる。

このような構文解析を行う場合文法ＧはｆｖＮ。

Ｖ、、Ｐ、Ｓ＋　なる４つの要素から成り立っている。

ＶＮ　；　Ｅ、Ｔ、Ｆ等の途中に現れる文字列ＶＴ　　
：　ｌ　＋　−＋　十等の最終的に現れる文字列Ｐ；規
則 Ｓ、Ｅ等の開始記号 ある文法を解析するサブルーチンを作成した場合、最終
的には最初の記号に戻って（る。ところが、文法の種別
（算術式９条件式等）によって開始記号が異なっている
。コンパイラの処理は開始記号まで戻す処理であるから
、開始記号か異なると、単一のＬＲ（１）構文解析表で
複数の文法を解析することができなかった。

本発明はこのような課題に鑑みてなされたものであって
、複数の文法を単一のＬＲ（１）構文解析表を用いて解
析できるようにすることができるコンパイラの構文解析
部の作成方法を提供することを目的としている。

［課題を解決するための手段］ 第１図は本発明方法の原理を示すフローチャートである
。本発明は、 コンパイラの構文解析部の一部をＬＲ（１）構文解析法
で作成する場合において、 ＬＲ（１）構文解析サブルーチンを使用する部分で解析
する文法が複数存在する場合に、ＬＲ（１）構文解析サ
ブルーチンを作成するための文法に、解析する文法の種
別を示すトークンを挿入することによって、複数の文法
を解析するＬＲ（１）構文解析表を生成しておき（ステ
ップ１）、このＬＲ（１）構文解析表を含むＬＲ（１）
構文解析サブルーチンを呼出す際に、解析する文法の種
別を挿入することにより目的の文法を解析する（ステッ
プ２）ようにしたことを特徴としている。

［作用コ ＬＲ（１）構文解析サブルーチンを作成するための文法
に、解析する文法の種別を示すダミーのトークンを挿入
して複数の文法を共通に扱えるようにする。例えば、前
記した（１）〜（３）式に加えて、 ５−ａＥ　Ｉ　ｂＣｌ　ｃ　Ｉ　　　（４）なる文法を
付加するのである。ここで、ａ、ｂ。

Ｃがダミーのトークンである。これにより、算術式を示
すＥも条件式を示すＣも一意名を示す■も共に開始記号
Ｓに還元されるので、単一のＬＲ（１）構文解析表を用
いて構文解析が行えるようになる。

［実施例］ 以下、図面を参照して本発明の実施例を詳細に説明する
。

算術式１条件式及びデータ名（−意名）を解析するサブ
ルーチンの場合、算術子はデータ名を構成要素として含
み、条件式は算術式、データ名を構成要素して含み、デ
ータ名は添字等に算術式を含むというように、相互に関
連している。このようなサブルーチンを解析する文法を
Ｇとした場合、文法Ｇの定義を以下のようにする。

Ｐは、 Ｇ−（ＶＮ　、ＶＴ　、Ｐ、５） ＶＮ　＝　（Ｓ、　Ｅ、　Ｃ，１１ Ｖ↑−（（１＋　　１．−１ Ｃ＋　　）＋　　ａ＋　　ｂ＋　　０１Ｃがダミー〇ト
ークン Ｓ−→ａＥｌｂｃｌｃｌ Ｅ４Ｅ＋ＩＩ Ｃ→Ｅ−Ｅ ■→ｉ　　（Ｅ） ここで、上式のａ、　　ｂ。

で、それぞれの算術式９条件式、データ名の解析を示す
終端記号である。（５）〜（１１）に示す文法を基にＬ
Ｒ（１）構文解析表を作成すると、算術式１条件式及び
データ名を解析するサブルーチンを作成することができ
る。ここで、サブルーチンを作ってみる。

算術式ＥはＥという記号と十という記号とＩという記号
又は■という記号で表されるものとし、これを Ｅ−Ｅ＋Ｉ　Ｉ　Ｉ　　　　　　　　　　　（１２）と
表すものとする。以下、条件式〇、データ名Ｉについて
も同様に考え、 Ｃ４Ｅ−Ｅ（１３） Ｉ−ｉ　（Ｅ）　　　　　　　　　　　　（１４）と表
す。また、 Ｓ′からＳが生成されるものと考えて Ｓ′→Ｓ　　　　　　　　　　　　　　（１５）という
生成規則を追加する。これら文法において、Ｅから生成
されるものには例えば ｉ＋ｉ＋ｉ、ｉ があり、Ｃから生成されるものには例えばｉ−ｉ、ｉ＋
ｉ−ｉ があり、■から生成されるものには例えば、ｉｉ　　（
ｉ）がある。

何も読んでいない状態を■。、Ｉｏからａを読んだ状態
をＩ、、Ｉｏからｂを読んだ状態をＩ２■１からｉを読
んだ状態を１３とすると、第２図に示すような状態と行
き先を決めるＧＯＴＯ文（遷移先）が作成される。・は
トークンをどこまで読んだかを示している。これがＬＲ
（１）構文解析表となる。Ｉ３の状態で次のトークンが
Ｃてなければｉのオブジェクトコードを生成する。

なお、このサブルーチンを呼び出す場合には、先頭のト
ークンとして算術式２条件式、データ名の先頭のトーク
ンではなく、ａ、ｂ、ｃを示すトークンをサブルーチン
に渡すことによって、算術式１条件式、データ名を解析
することができる。

例えばａというトークンをサブルーチンに渡せば、算術
式だと思って解析を始める。またｂというトークンをサ
ブルーチンに渡せば条件式だと思って解析を始める。

第３図はサブルーチン内のトークンの読込み処理を示す
フローチャートである。先ず、文字列の読込みが１回目
であるかどうかチエツクする（Ｓｌ）。１回目である場
合には、本発明によるダミートークンの付加処理に入る
。つまり、文字列が条件式であるかどうかチエツクしく
Ｓ２）、そうであった場合には条件式を示すトークンの
ｃｎｄを返す（Ｓ３）。

次に、条件式でなかった場合には、算術式であるかどう
かチエツクしくＳ４）　、そうであった場合には、算術
式を示すトークンのａｒｔを返す（Ｓ５）。次に、算術
式でなかった場合にはデータ名しか残っていないから、
データを示すトークンのｄａｔａを返す（Ｓ６）。若し
、文字列の読込みが１回目でない場合にはダミートーク
ンを返す必要はないから、読込んだトークンをそのまま
返せばよい（Ｓ７）。

第４図は本発明で用いるコンパイラの構成例を示す図で
ある。図において、１は読み込んだ文字列を解析する字
句解析部、２は本発明を特徴づける構文解析部、３は意
味解析部、４は最適化部、５は目的コード生成部である
。構文解析部２は、構文解析本体２ａ、構文解析サブル
ーチン２ｂ及びダミートークン付加部２ｃより構成され
ている。

構文解析本体２ａには、ＬＲ（１）構文解析部は含まれ
ない。構文解析サブルーチン２ｂでＬＲ（１，）構文解
析が行われる。また、構文解析サブルーチン２ｂには、
前記したＬＲ（１）構文解析表が含まれる。

このように構成されたシステムにおいて、先ず文字列が
字句解析部１に読込まれる。読込まれた文字列は字句解
釈された後、構文解析部２に入力される。構文解析部２
では入力された文字列の先頭に算術式１条件式及びデー
タ名の種別に応じてその先頭にダミートクン付加部２ｃ
によりダミートクンが付加される。そして、ダミートー
クンが付加された文字列の解析は構文解析サブルーチン
２ｂで解析され、構文解析本体２ａに渡される。

この場合において、全ての文法が同一の開始記号に還元
されるので、共通のＬＲ（１）解析表を用いて解析する
ことができる。

構文解析部２で解析された結果は、次に意味解析部３に
渡され、意味の解析が行われる。その後、最適化部４で
最適化処理がなされた後、目的コード生成部５でオブジ
ェクトコードが生成される。

［発明の効果］ 以上、詳細に説明しプこように、本発明によればＬＲ（
１）構文解析サブルーチンを作成するための文法に、解
析する文法の種別を示すダミーのトークンを挿入して複
数の文法を共通に扱えるようにすることにより、算術式
を示すＥも条件式を示すＣも一意名を示すＩも共に開始
記号Ｓに戻るので、単一のＬＲ（１）構文解析表を用い
て構文解析を行うことができる。

【図面の簡単な説明】

第１図は本発明方法の原理を示すフローチャート、 第２図は状態図とコール文を示す図、 第３図はサブルーチン内のトークンの読込み処理を示す
フローチャート、 第４図は本発明に用いるコンパイラの構成例を示す図、 第５図はＬＲ（１）構文解析表の概念図、第６図は文字
列の解析法の説明図である。 第４図において、 １は字句解析部、 ２は構文解析部、 ２ａは構文解析本体、 ２ｂは構文解析サブルーチン、 ２ｃはダミートークン付加部、 ３は意味解析部、 ４は最適化部、 ５は目的コード生成部である。

Claims (1)

1. 【特許請求の範囲】 コンパイラの構文解析部の一部をＬＲ（１）構文解析法
   で作成する場合において、 ＬＲ（１）構文解析サブルーチンを使用する部分で解析
   する文法が複数存在する場合に、ＬＲ（１）構文解析サ
   ブルーチンを作成するための文法に、解析する文法の種
   別を示すトークンを挿入することによって、複数の文法
   を解析するＬＲ（１）構文解析表を生成しておき（ステ
   ップ１）、このＬＲ（１）構文解析表を含むＬＲ（１）
   構文解析サブルーチンを呼出す際に、解析する文法の種
   別を挿入することにより目的の文法を解析する（ステッ
   プ２）ようにしたことを特徴とするコンパイラの構文解
   析部の作成方法。