Page 1 州工業大学学術機関リポジトリ *kyutaca 『 Kyushulnstitute of

九州工業大学学術機関リポジトリ
Title
Author(s)
Issue Date
URL
オートマトン自動生成システムとそれを用いた言語処理
系の開発
山之上, 卓; 藤岡, 明美; 安在, 弘幸
1982-09-01T00:00:00Z
http://hdl.handle.net/10228/4268
Rights
Kyushu Institute of Technology Academic Repository
九州工業大学研究報告（工学）N◇．45 1982年9月 35
オートマトン自動生成システムとそれを用いた言語処理系の開発
（昭和57年5月31日 原稿受付〉
情幸肛学教室山之上卓
情報工学教室藤岡明美
情報工学教室 安 在 弘 幸
Automat皿Generation Systern and Its Applied
Development of Language Processors
by Takashi YAMANOUE
Akiy◎shi FUJIOKA
Hir◎yuki ANZAI
Ab8traεt
We have already reported the method to construct a symbol manipulation system or a
language processor which is composed from finite automata， action routines and their driver．
And there the a碇〔）mata are shown缶be constmcted fmm a g輌veどegular仕ansl就i◎n form（RTF）
This paper presents a system automaticaUy constructing the automata from the given PTF，
The automata here are deterministic and minimized． And the method using this system is
illustrated by practically constructing a micro BASIC processor，
1．まえがき 2．オートマトンの合成と変換
前報告三｝では，オートマトンモデルを用いることに 本記号処理系自動生成システムでは記号処理系の仕様
よって，言語処理系などの記号処理系が実現できること 書のなかのRTFを逆ポーランド記法に変換し，それを
を示した。このオートマトンモデルを自動的に生成でき ’ プッシュダウンスタックを用いてオートマトンに組立て
れば，より簡単に記号処理系を開発することができる。 る。そしてさらに，このオートマトンを簡約決定性に変
本報告では，記号処理系の仕様書の一部であるRTFを 換する。この章ではその方法を説明する。
入力し，オートマタを自動的に生成するシステムを与え
る。 2，1 RTFの逆ポーランド記法変換
このシステムは，まずRTFを入力して逆ポーランド 前報告2節で示した算術式の逆ポーランド記法変換の
記法に変換する。次にプッシュダウンスタックを用いて 場合と同じように，RTFも逆ポーランド記法に変換す
これをオートマトンに合成する。最後にこのオートマト ることができる。図一1にRTFを逆ポーランド記法に変
ンの簡約決定性変換を行って出力する。 換させる機能を，RTF自身で記述して示す。
本報告で示すシステムと，前報告で示したシステムを 本稿では，前報告で示した方法を用いて，このRTFか
用いることによって，言語処理系を簡単に作ることがで ら一般のRTFを読みとってその逆ポーランド記法に変
きる。これをmicr◎BASIC処理系の作成を例に示す。な 換する記号処理系を（オートマタシステムとして）作成
お，本システムは，前報告と同様にUCSD PASCALシ する。次節にそこで使用する活動ルーチンについて説明
ステム上で制作された。 する。
36
ロお エロ
＜TEXT＞ ロ［OPEN】＜HEAD＞＜AUTOMATA＞， 1★IENDIICLOSEI ；
＜HEAD＞ ＝l l★・BEGIN， ；
＜AUTOMATA＞一くRTF＞〈RTF＞★ ；
〈RTF＞ ＝IMARK】＜LEFT＞’＝，＜RIGHT＞ ，；1【OUT】 ；
＜1」EFT＞ エ1 ，★〈NS＞， ，★ ；
〈RIGHT＞ ＝｛RECO】＜EXPR＞． 1★ ；
＜EXPR＞ ＝＜TERH＞（．＋，〈TERM＞［＋】）★ ；
＜TERM＞ ＝〈FACTOR＞（〈FACTOR＞ICONCAT］）★ ；
＜FACTOR＞ ＝， ，★＜ELE岡ENT＞（，★，［★1＋1／・［OPT】）！ ；
＜ELEHENT＞ エ＜NS＞＋〈TS＞＋＜ACT＞＋〈PAREN＞ ；
〈PAREN＞ 己，（冒〈EXPR＞1）． ；
＜ACT＞ エ1【，（＜NAME＞＋〈SYMBOL＞）¶］1［ACTI ；
＜NS＞ ヱ1く‘〈NAME＞．〉，［NS】 ；
＜TS＞ ＝．ll（＜NAME＞◆〈SYHBOL＞），ll【TS】 ；
＜NAME＞ 宕【CLEAR】〈ALPHABET＞［CON】（（〈ALPHABET＞＋〈NUHBER＞）ICON】）★ ；
〈ALPHABET＞冨［ALPHABETI ；
＜NUHBER＞ ＝【NUMBER】 ；
〈SYMBOL＞ 8［CLEAR】【SYMBOL】【CON】 ；
END
図一1
2．2 オートマトンの合成 タックにプッシュする。（図一3）
2．1節で示したRTF（図一1）によって逆ポーランド記 ・などの単項演算子が入力されると，スタックを1回
法に変換された一般のRTFは，プッシュダウンスタッ ポップして1つのオートマトンを取り出し，その演算子
クを使ってオートマトンに組み上げることができる。実 に対応する演算（オートマトンの変換）を行って，得ら
際にはこの部分では，文献2）に示されている右線形方程 れたオートマトンをスタックにプッシュする。（図一4）
式を用いてオートマトンを表現している。
ンを作ってスタックにプッシュする（図一2）。
図一4 単項演算子＊を入力したとき
”一 一 ●一、
ノ ぱ へ
w’「易 鹸蕊欝鶯ll灘
する過程を示す。
図一2 被演算子aを入力したとき
’鍋6・ ．∼”＼、
わ
ゴ
じ
⇒
十
，’ @一 、、
’ 、
⊥上
‘ b ⑪
、 ’
、、一 一’
’
図一3 二項演算子十，・を入力したとき
仁
＋，・などの二項演算子が入力されると，スタックを
2回ポップして2つのオートマトンを取り出し，その演
算子に対応する演算（オートマトンの合成）を行ってス 図一5 abc・＊・に対応するオートマトンの合成
37
2．3．オートマトンの簡約決定性変換 3．オートマトンの逆転をとる。（図一10）
2．2，節までで作られたオートマトンは，決定性だとは 4．決定性変換を行う。（図ゴD
限らない。また，もっと小さなオートマトンになる可能 このようにして，与えられたオートマトンに対するそ
性がある。一般に，与えられたオートマトンを決定性の の簡約決定性オートマトンが得られる。なお，決定性変
簡約されたオートマトンに変換することを簡約決定性変 換，簡約決定性変換のアルゴリズムは文献3）のものを
換という。この節ではその方法を述べる。 使用した。
非決定性のオートマトンは，1つの状態から同一の入
力記号で複数の状態へ遷移する部分があるような種類の
b
オートマトンである。オートマトンの決定性変換は，一
般に，部分集合構成法を用いて行うことができる。その
例を図．6に示す。 c 4
図一7 オーマトンA
臼b
b
図一8 Aの逆転A1
α
3
図一9 A・の決定性変換A2
｛2・3｝ ｛1、2，3｝
◎
b ◎ b
α d→◎
図一10 A2の逆転A3
穣 ・ b
袴 0L 4
図一6 オートマトンの決定性変換
図一｛1A3の決定性変換A4
ここで与える簡約決定性変換は，オートマトンの決定
性変換を2回行うことによって行なわれる．これを図 3・本システムの鮪法
一7の例で説明する。 この節では，算術式の逆ポーランド記法変換を行う処
1．オートマトンの逆転をとる。（図一8） 理系の自動生成を例にとって，本システムの使用法を説
2．決定性変換を行う。（図一9） 明する。システム全体の構成を図一12で示す。
38
記号処理系
記号処理系自動生成システム （前報告で示した部分）
INTEXT，
TEXT
ACONST CODE
アクションルーチン
逆ポーランド
記法変換
RTF
一〇UTEXT．
RPOLA．TEXT
TEXT
一RPOL．CODE
DRIVER TEXT
オートマトンの合成
INTERPRET
PASCAL
ﾈ約決定性変換
OBJECT．
TEXT
bompiler
一RPOL．GRA，TEXT
図一12 システム構成図
ステップ1 処理系の仕様書の一部となるRTF（図一13） TEXTから逆ポーランド記法に変換されたRTFが
を，ファイルINTEXT． TEXTに書き込む。 入力され，そのRTFに等価なオートマトンの合成と，
その簡約決定性変換が行なわれる。完成されたそれぞ
BEGIN れのオートマトンは・ファイルOBJECT・TEXTに図
くE＞＝＜T＞（‘＋9＜T＞［＋D★ ； −15のような形で出力される。これは前報告で示した
〈T＞＝＜F＞（，★1＜F＞【★】）★ ； オートマトンの外部表現である。これと同時に，ファ
＜F＞＝lAl［A］＋1（1＜E＞，）， ； イルACTABLE． TEXTには，活動記号対応表（図
END ．16）が出力される。この表は，オ＿トマタとそれが呼
図一13 入力されるRTF び出すアクションルーチンとの結合表である。
ステップ2 プログラムRTFを実行する。このプログ BEGIN BCONST；
ラムの実行によって，入力されたRTFが逆ポーラン CONSTN（100，101，200）；
ド記法に変換される。逆ポーランド記法に変換された CONSTT（101，102，，＋1）；
結果（図．14）は，ファイルOUTEXT． TEXTに格納 C ONSTN（102・103・200）；
されている・
@ ＝1：891∼｝°1・1）；
DNT −〈T＞ CONSTN（200・201・300）；
DT＋ −1＋・ CONSTT（201・202・’★’）；
DNT −〈T＞ CONSTN（202・203・300）；
R7 −． CONSTA（203・201・2）；
：今＋ ：甲 1811鵠；1；・1，，Al）；
R8 −★ CONSTT（300・302・’（’）；
R7 −． CONSTA（301・303・3）；
CONSTN（302，304，100）；
図一14逆ポーランド記法に変換されたRTF CONSTT（304，303，，），）；
CONSTL（303）；
ステ。プ3プ。グラムINTERPRETを実行する．こ P：＝ECONST；EXECUTE END・
のプログラムの実行によって，ファイルOUTEXT． 図一15 完成されたそれぞれのオートマトン
39
4．本システムの応用
｛刈 一 1
｛★］ − 2 本システムの応用例として，癒cr◎BASIC処理系を
［A］ − 3 制作した。これは算術式のインタープリタである。
図＿16活動記号対応表 このBASICの実行には・代入文とプリント文がある・
その実行例を図づ9に示す。
ステップ4 前報告の3．3．節で示したようにしてタアタ
ションルーチンを書く（図一17）。このルーチンと，ス
て・プ3で完成し一マトン͡表現訓 1；＋7★（8−6）／2；
報告3・2・節で示したドライバールーチンや外部内部 X＝−1；Y＝2＋3；SUB＝X＋Y；
表現変換手続を加えることによって，記号処理系が完 ？SUM；？X−Y；？Y−X；
成される（図一18）。 4
−6
鍬◎cε抑織ぼ鎚UTε； 6
PROC8DびRE READS（VAX X‡LN）；
BEl認，、黄（、う 図一抱 頚icro BASICの実行倒
END；
PROCEDURE PLUS；
B鎚斑饗虹鷲uて1 ぺ）E助；
取911↑‖R；R全：1舎；い 。，）路D、 4．1．micro BASICの仕様
P鼠：lli‖9；R：㌫；（・ A・）EN。、 mi￠r◎BASICの仕様はRTFを用いて図一2◎のように
PR◎eEl）OR8 PACTIO川
眠抽 定めた。
￠ASE P＾．AX◎ ◎方 1二PL蓼§； 2：真§TAヌ 3：AAAA EN口；
EN；：・P＾・LL1蔚K micro BASIC処理系は，内部にプッシュダウンス
タックや変数表などの抽象データ型を持っている（図
図一17 アクションルーチン
ー21）。アクションルーチンは，これらの抽象データ型を
使って文の実行を行う。
（★＄S碑）
PROGRAH RPOL；
（★＄U ACONST．C◎DE ★） ． 工
X
USES ACONST； 2
（★61 RP◎L．A．丁芭XT ★） 3
5
Y
9
su碗
’4
（★＄工 DRIVER．丁芭XT r★） ・
s
●
●
（★＄1RPOLGRA．狸XT★） 1
；
◎
●
●
看
9
ファイル RPOLATEXTにアクションルーチン， 繕
ファイル RPOL．GRA．TEXTにオートマトンの外部表現
がそれぞれ格納されている。 プッシュダウンスタック 変数名欄 データ欄
変数表
函一雪8 完成された記号処鷺系 ・ 図一21抽象データ型
・6起G王N
＜MC食O叙S《C＞司eLS｝〈SENTENC菖〉＜S芭NT斑CE＞がENが；
〈§田HTENC起〉 宗〈1｝RINT＞手くA§SΣ奪N〉；
〈PRINT＞ 編1？，＜EXPR＞1；1｛？］ ；
＜“s三GN＞ 縮く蕪A寵〉）ξSA川〈EX鰍〉∵柄；
〈露x●R〉 嬬〈TE品〉い÷‘〈揺RU＞ひい㌔‘〈猟鮒〉｛刈）★；
〈T8RH＞ ・＜FACTOR＞（1★’＜FACTOR＞｛・】ヂ’／’＜FACTOR＞1／D・；
＜舗C題R＞ 嫁〈猟C＞＋㌔’＜FAC＞｛鰭工G川ベペ〈F蕊〉｛PSIG刈 ；
〈FAC＞ 昧くNAM鷹〉［PUSH1】・qNTεGER＞・’（’〈EXPR＞・）’；
＜NAME＞ 洪〔NEWll＜ALPHA＞〔CON11（（〈ALP日A＞・＜NUMBER＞）｛C。MD・撫C。］；
〈抽鷲醜R＞ 箒｛踵殿｝〈靱XB録〉口硲幻く＜紗酪寵〉｛co媛］）ヴ鱒S搬蚕；
〈ALPHA＞ 編｛ALPHA］ ；
〈NりH賊R＞ ゑ｛NU鰻品剖 ；
E討D
図一20斑cm BASIC処理系のRTF
40
各アクションルーチンは以下の動作を行う。 ［PUSH 2］ 整数をスタックにプッシュする。
［CLS］ スタックをクリアする。 ［ALPHA］ 英文字を1文字読み込む。
［？］ 結果（スタックのトップ）をプリントする。 ［NUMBER］ 数字を1文字読み込む。
［＝］ 変数表のデータ欄に結果を入れる。（代入す 4．2．micro BASICの制作
る） 記号処理系自動生成システムに，micro BASIC の
［SAVE］ 代入の準備をする。 RTF（図一20）を入力することによってオートマタ（の外
［＋］ スタックをポップして値を2つ取り出し，そ 部表現）と活動記号対応表（図一22）を出力させる。次に
の和をとってスタックにプッシュする。 アクションルーチンを準備して，これを活動記号対応表
［一］ スタックをポップして値を2つ取り出し，そ に従ってオートマトンに結合させる（図一23）。最後に記
の差をとってスタックにプッシュする。 号処理系に使うすべての手続をまとめ（図一24），これを
［＊］ スタックをポップして値を2つ取り出し，そ コンパイルする。
の積をとってスタ・クにプ・シュする・ 【CLS］−1
［／］ スタックをポップして値を2つ取り出し・そ ［？］ − 2
の商をとってスタックにプッショする。 ［SAVE】 − 3
［MSIGN］ スタックをポップして値の符号を換 ［＝］ − 4
え，スタ。クにプ。シュする。 ［＋］−5
［PSIGN］何もしない。 ［一］−6
［PUSH1］該当する変数の⊇表から取り出 1；1：；
し・スタックにプッシュする。 ［MSIGN］ − 9
［NEW1］ 変数名を読み込む準備をする。 ［PSIGN］ − 10
［CON1］ 変数名の1文字を読み込んだ後の処理 ［PUSH1】 − 11
をする（文字をつなぐ）。 ［NEW1］ − 12
［RECO］読み込んだ変数名を変数表の中力、ら探し ［CON1］−13
［RECO］ − 14
出す。もし変数表中にその変数が登録されて ［NEW2］ ＿ 15
いなければ・この変数を新しく登録する。 ［CON2】 − 16
［NEW2］ 整数を読み込む準備をする。 ［PUSH2］ − 17
［CON2］ 整数を1文字読み込んだ後の処理をす ［ALPHA］ − 18
る．（前に読み込んだ数を10倍して，新しく読 ［NUMBER］−19
んだ数を加える。） 図一22 活動記号対応表
PROCEDURE EXECUTE；
TYPE CELLエRECORD A：SYMBOL； BOX：INTEGER END；
VAR NAHE：SYMBOL；
NAMETAB：ARRAY【1．．201 0F CELL；
STACK：ARRAY｛1．．101 0F INTEGER；
X，Y，SP，NTP，NNUH，ITABLE，WORK：INTEGER；
PROCEDURE READS（VAR X：LN）；
BEGIN
IF EOLN（INPUT） THEN
BEGIN READLN； READ（X） END
ELSE READ（X）
END；
FUNCTION RECO（X：SYト｛BOL）：INTEGER；
VAR I：INTEGER；
BEGIN
NAMETAB［NTP1．A：−X； 1：＝0；
REPEAT I：エ1＋1 UNTIL NAMETAB【正】．A＝X；
IF I＝NTP THEN NTP：＝NTP＋1；
RECO：エI
END；
PROCEDURE PUSH（1：INTEGER）；
BEGIN STACK［SP】：呈1； SP：エSP＋l END；
41
PR◎CEI）URE P◎PζVAR I：1NT琶G欝頁）；
筋EGIN sp：繍SP−1； 1：襯STACK［SP〕 END；
FUNCTION EXGH（A：SYMBOL）：INTEG｝9R；
VAR 1：1NTEGER； AA：c｝IAR；
8已呑斑
AA：本A【1】；
奪AS鷺 AA ◎F タ◎‘：1：謬｛）； 唄1曇：〕［：−1； 42‘：箪；隷2； 婁3，‡玉：零3； 柔4’：ま：灘存；
聯5β：王▲之5； ’6妻：工：エξ」； 弁7事言工：＝7； き8’：竃：領8，．； 隅9，：董；高9
END；
葺xc｝1；エ1
芭ND；
蔓「R◇c慧1｝UIミg CLEAIミ；
BEGエN 》lTP：晶1； SP：＝l END；
PR◎Cξζ1｝ORε P￠乙S；
8EGIN CLEAR； P：ぼP＾．LLINK EN】）；
PR◎CEDURE PPR工N「r；
魏EGIN POP（X）； WRIT8LN（X）； P：媒P＾◆LLINX 霧ND；
PROCEDURE PASS工GN；
B鶴cΣN t》OP《x）； NAH茎「rAB茎NNUH］、息《）］ζ：認x； 摯：濡P＾．るも叢Nさζ 嵩葵鵬》’
PROCEDURE PPLUS；
懲EGI』《 POP（Y）； P◎P（x）； P登SH（x◆Y）； P：粛P＾．LLtNK琶欝D：
PR◎c舷DUR8 PHIN口s；
6起GIN POP（Y）； POP（X）； POSH（X猶Y）； P：鵠PA．LL工NK END；
鞭裏《多CEI）蓼R8 登枝OLT1；
6EGIN POP（￥）； P◎P（X）： PUSH（】《★Y）； P：■P＾．輻LIN杖 8N《｝ハ
PR◎C欝DUR8 PI）1V；
3起馨IN P〔きP（Y）； P〔＞P（】ζ）： pu§H（X D至V Y）； P；＝P＾み痴L1黄…ζ茎NI）；
PROC6DU鼠E PMSIGN；
B繕G1因 ●◎P（X）； Pミ）S……（−X）； P：＝P莇束LL1糠翼 慈討1）；
PROCEDURR PPSIGN；
登EGIN I｝：工P＾◆LL竃NIζ END；
PROC8DI∫R8 PSAVE；
86奪王N NNUき｛；：富ITABL呂； 警：堺互》＾可LLINK 8N］〉；
警Roc狂1＞u鼠窪 P2USH1；
BEGIN PuSH（NAH6TA6｛工TABLE］．BOX）； P：斎P＾．LLIHK E鱒1）；
皇R◎cEI｝URE P督8聾1；
3EGIN NAME：堺．・； P：エP＾．LI㎡1NK 6ND；
」PRoc罵奎｝9R芭 pc◎N1；
66（〕IN NAHE：嬬CONCAT（NAME，CH）； P：穗P＾、LLINK END；
藁｝〕ミ《）c麓1）奪Ri《 …｝1ミ8c《）；
BEGIN ITABL9：＝R鳳CO（NAHE）； P：㈱P＾．LLINK END；
董）ROC芭DURE PN鷺W2；
B鰯GIN WORK：零0； P；＝P夫，LLINK εHD；
PROCEDURE PCO‘N2；
、 6罵（〕ΣN PUSH〈W◎Rlζ）； P：編P＾θLL茎討ハζ 茸討1）；
PROCEDURE PPUSH2；
蕗8（≧1藩 P｛3SH〈響ORK）； P：篇P＾瞭LLIN藪ζ 建Nl）；
PR◎C芭DURE PAL〕》HA；
B鷺C斑
XF L工N琶｛1董 IN ｛＄Al．．・zジ】 『rHEN
Bε奪1艮 CH：文e◎PY《乙ΣN繊♪1，1）； D諺L霧丁総（LIN8，1鼻1）； P：奴P＾．LLξ醤1ζ 震ND
gLS芭 P：認P《・RI揚互w裟
END；
PRζ）C葛OURE PN目H8§R；
3怠GIN
lF LINE［11 1N ｛．0，，．’9’］ THEN
8奪GIN eH：涼￠OPY（L工翼鶴，1旙1）； 三）8LET｜§《L累Ne I，1）； 穿言涼P轟 LL董RK霧ND
兄乙s套 P：雪P＾・1ミL叉N裟
ENO；
夢RO◎別）UR8 PA￠τ，10N；
B鴛G王N
CAS8 Pハ，Aパ奪 OF 至：PCLS； 2：PP》ζ1NT； 3：PSAVE； 4：PA§SIGN； 5：PP乙US；
6：PHIN∬S； 75PMUTI； 8：PSIV； 9：PHSXGN； 10：PPSIGN；
皇1：P●USH1； 12：PN起響1； 芝3：PC◎N1； 14：PR8C◎； 15：P裏翌聾2；
16；PCON2； 17：PPuSH2； 18：PALPHA； 19；PNUHB8R
6ND
日蛸驕
図一23アクシ田ンルーチン
42
のに適した言語をこのRTFを用いて記述することであ
（★＄S＋★） る。こうすれば，この言語の処理系はこのシステムを用
ぞ購R会：。醤1↑i；86E★） いて自動生成できる・また・本稿で示したmi…BAsIc
USES ACONST； では・少数の簡単な文しか取扱っていない。現在までに
｛瑠鵠織二謬x雲）り 我々の研究室で｝1楡の言語の種々の文の多くに対し
（★＄I MBASIC．GRA．TEXT ★） て・RTFによる記述を試みている。今後は・これらを整
理し，更に多くを調べてRTF記述の一般的な方法を与
ファイル MBASICA．TEXTにアクションルーチン，
ファイル MBASICGRA．TEXTにオートマトンの外部表現 える必要がある。
がそれぞれ格納されている。
図一24 完成されたmicro BASIC処理系 参考文献
1）山之上他：“記号処理系のオートマタシステムによる実現”九工大
研究報告，No．44， pp．83−90，1982．
5．あとがき 2）安在・潮崎：“再帰降下順序変換機系とその生成機械”電子通信学
会論文誌，63−D，9，pp．771−778（Nov．1980）．
現在のシステムでは・アクシ・ンルーチン｝まPASC・3
G瓢l l漂襟1］1弩潔㌘『『㌢技術報告
ALを用いて記述している。次の段階はこれを記述する 4）Dr． Kenneth他著，越智他訳rUCSD PASCALシステム入門」，
に適した言語，すなわち意味や抽象データ型を記述する JBA，（1980）．