JPS6022245A - ブロツク構造を持つ言語における構文チエツク方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔発明の技術分野〕 本発明は、ブロック構造を持っＰＡＳＣＡＬのような言
語で書かれたソース・プログラムの何れの部分が入力さ
れても、その入力部分が構文的に正しいか否かをチェッ
クできるようになったブロック構造を持つ言語における
構文チェック方法に関するものである。

〔従来技術と問題点〕

端末から入力されるソース・プログラムラ、ソの場で構
文チェックするには、一般に、−回の入力を一つの文又
は行というような単位に規制しなければならないが、Ｐ
ＡＳＣＡＬのようなブロック構造を持つ言語では、文が
文を含むことがある等の理由により、−回で入力可能な
単位に分割することができない。以下にその理由につい
て説明する。

ＰＡＳＣＡＬ言語の構文定義の一部を取出すと、下記の
ようになる。

開始記号＝Ｓ 終端記号＝（げ、ｔｈｅｎ、ｂｅｇｉｎ、ｅｎｄＨ、単
純文９式）非終端記号＝（Ｓ０文の列９文９条件文、複
合文） 生成規則＝（Ｓ−一文の列。

文の列−文〔；文の列〕。

文−単純文１条件文１複合文。

条件文−ｉｆ式ｔｈｅｎ文。

複合文−ｈｑｉｎ文の列ｅｎｄ）・・・■ここでは、単
純文、式を終端記号とみなし、その内部の構文解析に対
する言及を省略している。この構文によシ生成されるプ
ログラムの一例は次のとお）である。

１１式ｔｈａｎ −ｆ式ｔｈａｎ ｂ＃！７Ｌｎ 単純文； 単純文 ｅｎｄｊ−１・・・―・・１・・…・ｌ・・・・・拳・
・・・・ｅ・ｊＩＴ−・・・・■■の形式で書かれた入
力を構文チェックするだけならば、次に示す中のすで行
を区切れるものとすればよい。

Ｓ　−文の列 ↑ 文の列一文〔；文の列〕 ↑ 条件文→ｉｆ式ｔＡ＃ル文 ↑ しかし、この制限はきびしすぎ、一般的でない上に、構
文全体にわたって統一的に決めることがむずかしい。■
の例は、人により次のように書くかもしれない。

ｌ１式 ｔｈｇｎ　ｉｆ式 （式が２行にわたる） ｔｈｅｎ　ｂｅｇｉｎ 単純文； 単純文 ａｎｄ・・・・・・・・・・・・・・・・・・・・・・
・・・・・・・・・・・・・・・・・・・・・・・■こ
のように、ＰＡＳ　ＣＡＬ言語に対する従来の構文定義
では、行に分割するための制限を妥当な範囲で作ること
が出来ない。したが９て、任意の入力行を構文チェック
するためには、プログラムの任意の一部分に対して構文
チェックできる必要があるＯ 〔発明の目的〕 本発明は、上記の考察に基づくものであって、ブロック
構造を持つＰＡＳＣＡＬのような言語で書かれたソース
・プログラムの何れの部分が入力されても、その入力部
分が構文的に正しいか否かをチェックできるようになっ
たブロック構造を持った言語における構文チェック方法
を提供することを目的としている。

〔発明の構成〕

そしてそのため、本発明のブロック構造を持つ言語にお
ける構文チェック方法は、構文表上の全ての終端記号と
非終端記号に対し、その記号のあとに来る記号列を表す
非終端記号を新たに追加し、当該追加された非終端記号
を左辺とする生成規則を、 Ａ−αＸβ Ｘ’＝βＡ′ （ただし、人は非終端記号、αとβは記号列、Ｘは記号
、Ｘ′とには新たに追加した非終端記号）なる式に従っ
て新たに作成し、さらに１開始記号からの生成規則を Ｓ→αα′ （ただし、Ｓは開始記号、αは終端記号、α′はαに対
応する非終端記号）で表わし、上記新しく追加された非
終端記号、新しく追加された非終端記号を左辺とする生
成規則および上記開始記号からの生成規則を含んだ拡大
された構文表を作成し、尚該拡大された構文表に基づい
て入力文のチェックを行うことを特徴とするものである
。

〔発明の実施例〕

以下、本発明を実施例を参照しつつ説明する。

任意の入力行の構文チェックを通常の構文解析の手法を
用いて行うために、非終端記号の追加、生成規則の追加
、開始記号からの生成規則の作成および生成規則の整理
統合を行って、構文を書換える。先ず非終端記号の追加
について説明する。

全ての終端記号と非終端記号に対し、「その記号のあと
にくる記号列」を表す非終端記号を追加する。ここでは
、もとの記号にダラシ：Ｌ（′　）を付けて表す。

非終端記号＝（Ｓ１文の列１文１条件文、複合文。

８２９文の列′１文′０条件文′、複合丈。

げ’、　ｔｈｅｎ’　、　ｈｇｉｎ’　、　ｇｎｒｌ’
、　；’　。

単純弐′、弐′　） 非終端記号を追加した後、生成規則の追加を行う。以下
に生成規則の追加について説明する◇もとの生成規則の
右辺に現れるすべての終端記号及び非終端記号に対応し
て、上述の追加した非終端記号を左辺とする生成規則を
作る。生成規則Ａ−αＸβ に対して に一βＡ′ を作る。ここで Ａ　：非終端記号 Ｘ　：終端記号又は非終端記号 α、β：終端記号及び非終端記号の列（字列を含む） とする。これに従い、■の生成規則に対するものを作る
と 文の列′−８′ 文′−〔；文の列〕文の列′ ；′　−文の列、文の列′ 文の列′−文の列′ 単純文−文′ 条件文′−文′ 複合文′−文′ ｔｆｌ　→式ｔｈｅル文条件文Ｉ 弐′−ｔｋｇｔＬ文条件文′ ｔｈｅル′→文一文文′ 文′　−条件文′ ｂｅｑｉｎ’−文の列ａｎｄ複合文′ 文の列′→−ｎｄ複合文′ ｅｎｄ’　→複合文′・・・・・・・・・・・・・・・
・・・・・・・・・・・・・・・・・・・・・■となる
。

生成規則の追加を行った後、開始記号からの生成規則の
作成を行う。以下に開始記号からの生成規則の作成につ
いて説明する０ 構文チェックは任意の終端記号から開始するのであるか
ら、開始記号からの生成規則は、すべての終端記号を指
す。

Ｓ−αα′　Ｓ：開始記号 α：終端記号 α′：αに対応する非終端記号 ■の文法においては、 Ｓ−げげ’　ｌ　ｔｈａｎ　ｔｈｅｎ’　ｌ　ｂｅｇｉ
ｎ　ｂｅｇｉｎ’　ｌ　ｅｎｄｇ３ｄＪ　；　；’　Ｉ
単純文　単純文′１式　釘・・・・・・・・・・・・・
・・・・・■となる。

開始記号からの生成規則の作成を行った後、生成規則の
整理統合を行う０以下に生成規則の整理統合について説
明する。

無意味な生成規則、すなわち Ａ　与Ａ　Ａ：非終端記号 となるものを削除し、共通の左辺のものを統合する。ま
た、Ｓ′は「開始記号のあとにくる文字列」を表してい
るものであるから、空で置きかえる。

■を書きかえ、■を含んで新しい文法全体を記述すると
、次のように橙る。

開始記号＝Ｓ 終端記号＝　（ｉｆ、ｔｈｅｎ、ｈすｉｎ、ｅｎｃＬ、
；＋単純文。

式） 非終端記号＝（Ｓ１文の列１文９条件文、複合文 文の列′９文′９条件文′、複合文′ げ’、ｔｈａｎ’、ｂｅｇｉｎ’、ａｒＬｄ’弓’、単
純文′。

弐′　） 生成規則＝　（Ｓ、ｉｆ　ｉｆ’　ｌ　ｔｈｅｎ　ｔｈ
ｇｎ’　ｌ　ｂｇｇｉｎｂｇｙｉｎ’ｌ　ａｎｄ　ａｎ
ｄ′１；　；’　ｌ単純文　単純文′１式　Ｋ。

文の列−文〔；文の列〕 文　−単純文１条件文１複合文 条件文−乙ｆ式ｔｈｅｎ文。

複合文−２ｑｉｎ文の列ｇｇｄ。

文の列’−１−ＣｇＢｄ複合文′〕 文′−〔：文の列〕文の列′ 条件文、４文・。

複合文′−文′。

ｔｆ′　一式　ｔｈｅｎ文条件デ。

ｔ　ｈ　ｇ　Ｂ’−文条件文′ ６すｔｒＬ′−文の列−ｎｄ複合文′。

ｅｎｄ’　−複合文′。

；′　−文の構文の列′。

学純文′−文′。

式’　−ｈｔｈｔｎ文条件文′）　・旧・・・・−１・
・川■■の文法に基づいて解析を行えば、解析結果がひ
ととおシ定まらずあいまいながらも、構文に合っている
か否かの検査ができ、目的を果たす。

■に示すとおり、開始記号からの生成規則は、すべての
終端記号を指し、その終端記号に対応する非終端記号が
続くので、入力されたテキストの先頭の記号からいきな
り、対応する非終端記号を得ることが可能である。すな
わち 開始記号”’　（ｌｆ’＊　ｔ　Ａ　ｇ　ｎ’＊　Ａ　
ｇ　ｊ７　Ｌ　ｒＬ’＠　ｇ　ｒＬｄ’ｅ　ｉ’＊単純
単純文武１式し、開始記号としてどの記号を選ぶかは、
入力されたテキストの先頭の記号で決まる。

■の例で明らかなとおシ、生成規則中でダッシュ付きの
非終端記号は右端にしか現われない。したがって、その
位置には戻ってくる必要が無く、他の非終端記号のよう
に前の状態を保存してから次の処理へ移るとと々く、単
なるＧＯＴｏで良い。

実際の解析処理に近い形、リストを用いて構文を表現す
ると、下記のようになる。第１図は■の構文をリストで
表現したものである。こ＼で、太線は本来の構文で、細
線は他の非終端記号の呼出し、点線は呼出された非終端
記号からの戻りの動きを示すものであって、リンクでは
ない。

第２図は拡大した■の構文をリストで表現したものであ
る。これは、第１図の点線の矢印をリンクとして生かし
たものである。太線の終点、すなわち点線の起点がダッ
シュ付き非終端記号に相当する。開始記号は、それぞれ
太線中に現われる対応する終端記号の次である。

いま、第３図のような構文があったとする。

αξδという入力があれば通常の構文解析の手法どおり
■■■■■と進んでαξが解析され、次にδとβが一致
しないのでエラーである。ξδという入力ならば■から
Ｃ′に進む。こ＼でリンクは二手に分かれ仮に■を選べ
ば■へ進んでξとβを比較する。こ＼ではたとえ一致し
なくてもエラーとはならず、Ｃ′のところにあったもう
一つの候補［相］から■へ進み、δが一致して終了する
。

第４図は本発明を実施するための手段を示す図である。

第４図において、１は構文表、２はエディタ、３は変換
処理部、４は内部テーブルをそれぞれ示している。構文
表とは、構文検査を行なおうとする言語の構文を一定の
規約に従って書いたものである。変換処理部３は、元の
構文表（例えば■の構文表）から拡大した構文表（例え
ば■の構文表）を作成するシステムである。エディタ２
は、利用者の入力に従ってデータを編集する機能をもつ
システムであり、従来機能とシンタックス・チェック機
能を有している。内部テーブル４は構文表をシンタック
ス・チェック機能が使い得る形に変換したものである。

〔発明の効果〕

以上の説明から明らかなように、本発明によれば、ブロ
ック構造を持ち、切れ目のはっきりしない言語で書かれ
た文に対し、一部分が入力されても、構文的に正しいか
否かをチェックすることが出来る。また、拡大した構文
を表現するには、元の構文を表現するリストにリンクを
追加するだけでよく、負担は大きくならない。

【図面の簡単な説明】

第１図は元の構文をリストで表現した図、第２図は本発
明による拡大した構文をリストで表現した図、第３図は
構文解析の１例を説明するための図、第４図は本発明を
実施するための手段の１例を示す図である。 １・・・構文表、２・・・エディタ、３・・・変換処理
部、４・・・内部テーブル。 特許出願人　富士通株式会社 代理人弁理士　京　谷　四　部

Claims (1)

1. 【特許請求の範囲】 構文表上の全ての終端記号と非終端記号に対し、その記
   号のあとに来る記号列を表す非終端記号を新たに追加し
   、当該追加された非終端記号を左辺とする生成規則を、 Ａ−αＸβ Ｘ′＝βＡ′ （ただし、Ａは非終端記号、αとβは記号列、Ｘは記号
   、Ｘ′とには新たに追加した非終端記号）なる式に従っ
   て新たに作成し、さらに、開始記号からの生成規則を Ｓ→αｌ （ただし、Ｓは開始記号、αは終端記号、α′はαに対
   応する非終端記号）で表わし、上記新しく追加された非
   終端記号、新しく追加された非終端記号を左辺とする生
   成規則および上記開始記号からの生成規則を含んだ拡大
   された構文表を作成し、当該拡大された構文表に基づい
   て入力文のチェックを行うことを特徴とするブロック構
   造を持つ言語における構文チェック方法。