記号処理系のオートマタシステムによる実現
（昭和56年10月31日 原稿受付）
情報工学教室 山之上 卓
〃 金 子 浩 一一 〃 藤 岡 明 美 〃 安 在 弘 幸
An Implementation of Symbol Mapipulation System
by An Automata System
by Takashi YAMANOUE
Kouichi KANEKO Akiyoshi FUJIOKA Hiroyuki ANZAI
This p⑳er prese産s a meth◎d c◎nstmc恒ng a kind（）f fmite a碇◎m［aね§ysteml as a symb◎茎 manipulation system from given regular translation form and action routines which describe behavior of the automata＄ystem In this method， the automata system is concretely imple・，
me批ed and really executed in comρ碇eτas a UCSD PASCAL program．
And finally， a lexical analyzer is shown as an example of its practical applications．
逆ポーランド記法は単純な操作で式を評価できるため
L註がき よく鮪れる。・A＋B。C、と司算術式髄牛ラン
記号処理システムはオートマトンモデルで実現するこ ド記法で表すと「ABC楽＋」となる。この逆ポーラン とができる。我々はオートマトンを計算機内部で実現し， ド記法変換の規則はRTF（Regular Transla乞ion F◇m）1）
これを実行させるシステムをUCSD PASCALシステ という記述方法で次のように表すことができる。
ム上で制作した。そしてこのシステムを用いることによ 〈算術式〉＝〈項〉ぐ＋▼〈項〉 ［＋］）＊
り，コンパイラの宇句解析を行う機械を簡単に作ること 〈 項 〉＝〈因子〉（▼※▼〈因子〉 ［東］）＊
ができた。 〈因 子〉＝▼文字・［文字］＋▼（▼〈算術式〉▼）▼
本稿では2章でオートマトンモデルによる記号処理シ ここで，「・▼」でかこまれた部分は入力される文字を ステム作成の原理について説明を行い，3章でこの原理 表し「端記号」という。「〈 〉」でかこまれた部分は「非 に基いて，我々の作った記号処理システムについて述べ 端記号」といい，左辺の非端記号を右辺の式で定義付け る。4章ではこのシステムの具体的な応用例としての字 する。「［］」でかこまれた部分は動作を示し，「アク 句解析を行う機械について述べる。 ション」という。ここでは［］内の文字を出力する。
2．記号処理システムのオートマトンによる実現法 最初の式と次の式の左の右肩にある「※」は゜回を含む 繰返を表し第3番目の亨▼でくくられていない「十」は 本章ではまず記号処理システムをオートマトンモデル 「または」っまりorを表す。
で実現する方法についての原理的説明を，算術式の逆 このRTFに対して，上述した解釈は，図一1に示す3 ポーランド記法変換を例に述べ，次にオートマトンが式 つのオートマトンの解釈と全く等価である。オートマト の直接実行も可能であることを示す。 ンは，ある状態から矢印の上に書いてある文字を入力し
84
て次の状態に遷移するという状態遷移図で表される。→○
は開始状態を示し，・は終状態を示す．ヲF端記号で遷移 Eつ⊥≡
している部分は，非端記号に対応する状態遷移図がここ
に挿入されると考えればよい．アクシ・ンのある遷移は TO』『
このアクシ・ンに対応した・すなわちこのアクシ・ンと ・文字・［文字］
して定義された動作を行う。上述の例では，アクション F』 （）
に対応づけられた定義は，そのアクション記号をそのま ・（・ E ・）・ ． ま出力するものであった。図一2に「A＋B※C」を入力
したときこのオートマトンの動作を示す。 鷺：慧雲CP「合祠 オートマトンは式を直接に実行（interprete）すること Fは〈因子〉（Fact°「）の省略である・
も可能である。例として前の逆ポーランド記法変換を行 図一1 逆ポーランド変換を行う うオートマトンのアクションとして次の動作を定義づけ 3つのオートマトン てみる。
ω・H＋］ ・…d＝
；悉Fぽ鷲編 T管 テ
▼（ E ）
（9）T◎上◆＿◇．＿
、：踏Fの実行を醜
（2）Eρエ◇＿
・治』「の実行蹴 、1。蝉・文字・
文字ワB▼を読んでBを出力。
㏄91㌶虻綱゜
（3）T』
6ピ ［文字］Fの実行を 、1、。。・＊・F
F ， Tに戻って次の状態から開始。
（4） ・文字・［文字］文字・A・を読んで・・肋。 CS
㏄；℃㌘へ F （121・♂ザ・・＿。＿＿
CS 入力A＋B＊
出力AB
…。・VF （13）・滅⊥
・一・csi難i難罐F鴨…ノFの
㈲誌一一：：遼、藷轡㌶
Tに戻って次の状態へ行く，
F ＿． このとき・を出力。
CS 出力ABC＊＋
これですべての動作を終る。
図一2 オートマトンによる逆ポーランド変換の実行
［記号］：スタックに記号をプッシュする。 入ヵ A A、 A，B A，B， A，B，c A、B，c
［蠕藁㌘惣蒜その和を勒L当山自自螢曙
［崇］1スタックから記号を2つポップしてその積を とり結果をスタックにプッシュする。
スカ ハキ 入力「A＋B楽C」に対して，このオートマトンは図 出ヵ［A］〔，］〔、ユ［．〕［、〕
賜鷲巖；作力綱ときその結果がス コ
このようにアクションを作りかえること，すなわちそ 図一3 図2のアクションを入れかえたとき
の定義（解釈）を変えることによって式の直接の実行も の動き ゜ 可能である。以上のようにオートマトンとアクションを
作ることにより様々な変換や，動作を行う機械を作るこ とができる。
3・記号処理システムの実際 回
本章では我々の作ったオートマトンによる記号処理シ
ス㌶㌶鑛；糎することができ＿マ（ 繍錫 （丙』錨
トンの外部表現を計算機が解釈，実行できる内部の表現 〜完治芸 に変換する部分と，オートマトンを実行する部分よりで
きている。（図一4） （a）オートマトンの作成 この章では3．1．節でオートマトンの外部表現につい
て・3・2・節でオートマトンの内部表現について・3・3・節 入力 でアクションルーチンについてそれぞれ述べたのち，3．
4．節で本システムの使用法を与える。
3．1． オートマトンの外部表現
オートマトンの外部表現はPASCALプログラムの手 （b）オートマトンの実行 続の例で表現することにした。
オートマトンの外部表現は人間が直接に理解でき，し 図一4 本システムの構成 かも計算機の内部表現に変換しやすいように，抽象的
データ構造である有向グラフによる表現と具体的データ ここで右辺の右肩の「＋」は1回以上の繰返を示す。
構造である計算機内部のリンク表現との中間的な形を 〈symbo1＞は端記号を示し，その型（たとえばcharな とっている。この表現を規定する文法をRTFで表すと ど）はユーザーが定義する。〈integer＞は整数である。
次のようになる。 〈automata＞はオートマトン（automaton）の複数型で 〈automata＞＝ ある。〈bconst＞はbegin construction， econstはend ▼bc◎nst；▼〈automat◎n＞÷▼P：＝ec。nst；▼ c◎nstruc乞ion， co憾丁はc◎nstruct Terminal（端記号），
〈automaton＞＝ constNはconstruct Nontermina1（非端記号），constA （▼c◎n§tT（▼〈conneet＞〈symbol＞つ；亨 はc◎nstmct Acti◎n（アクション），const Lはconstwct ＋▼constN（▼〈connect＞〈integer＞ワ）； Lambda（終状態）の略である。〈connect＞の2つの整 ＋▼con§tA（▼〈connect＞〈i就eger＞▼）；）＋ 数は遷移する前の状態と遷移した後の状態を示す。
（▼const L（〈integer＞▼）；▼）＋ 外部表現を用いたオートマトンは状態遷移図から次の 〈c◎nnect＞＝〈lnteger＞▼，▼〈i就eger＞▼，▼ ようにして作る。
・ラ・・
86
（1）ｵ：㌫㌫欝をアクションと鵬 （｝坦〈）（｝当｝旦○
（2）すべての状態に重複しないように番号をつける。
（図一6）
（3）非端記号を各オートマトンの開始状態の番号で置 （｝二当○ （〉⊥〈）上LO
換える。（図一7）
図一5 （4）アクションを適当な番号で置換える。（アクショ
ニrプ゜グラムを作るときに対応づける゜）（図・〔・⌒
㎡（5）すべての遷移をオートマトンの外部表現の蜘、 ・◇琶一
従って書き換える。（図一9） F ▼A▼ ［A］ F・▼A 1・［A］
ここで終状態は各オートマトンの最後に書く。 ツ E つ▼ ▼（▼1E13 ）▼
（6）すべてのオートマトンの最初にbconst；，最後に 図一6 P：＝econst；を加える。
bconst； ・A▼ ［A］ ▼A▼ A1 ヨロ
const N（1，2，5）；constT（2，3，▼十▼）；const N（3，4，5）； ・（・ 1 ・）・ ▼（・ 1 ・）・
12 13
12 13
const A（4，2，2）；const L（2）；
図一7 図一8
const N（5，6，9）；const T（6，7，▼※▼）；const N（7，8，9）；
以上の作業を図一1の逆ポーランド変換を行うオート 〔 ｛
マトンに対して行うと次のようになる・
c°nstA（8，6β）；c°nstL（6）； ②工③ ・・n・・T（脇・＋・）、
UCSD PASCALシステムでのオートマトンモデル 〔 ：1 ：；：；：1：：1；：：1：：： ：；21r・
は，次の各要素を用いて1つのプログラムとして実現さ c°nstL（2）
図一9
れる。
（1）オートマトンの外部表現（3．1．節参照） 3．2．オートマトンの内部表現
（2）アクションルーチン（3．3，節参照） 一般にオートマトンは，抽象的データ構造として，図 （3）（1）から内部表現への変換手続き（3．2．節参照） −1に示したように有向グラフで表現される。本システム （4）オートマトンの内部表現をシミュレートするドラ では，これを図一10に示すようなリンク表現による具体 イバールーチン 的データ構造として計算機内に実現する。
（5）端記号入力手続きとその判定関数 この内部表現の各要素としてのセル＝レコードは，1 ここで（1），（2），（5）はユーザーが与えねばならない。（3） 個の情報欄と2個のリンク欄すなわちL欄と RLINK と（4）はPASCALシステム上のファイルに登録されてい 欄から構成され，情報欄には遷移記号が書かれ，リンク る。 欄には次の遷移を示すポインタが書かれる。遷移記号と 上述したシステムは，まず（3）を用いて（1）を内部表現に 入力が一致すれば状態を示すポインタはLをたどり一致 変換する。内部表現が完成した後，EXECUTEという手 しないときはRLINKをたどる。そしてここでは状態を 続きによって（4）が起動され，オートマトンのシミュレー 示す特別な情報欄はなく，強いて言えばある遷移記号と ションを行う。 次の遷移記号の間に「状態」があると想定している。図
−11は図一1の逆ポーランド変換を行うオートマトンの有 うファイルに書かれた手続によって行なわれる。
向グラフ表現を計算機内部のリンク表現で表したもので 計算機内に実現されたオートマトンの内部表現上でこ ある。 のオートマトンを実行（すなわちシミュレート）させる 3．1．節で示したオートマトンの外部表現からこの内 手続きをドライバーと呼ぶ。図一12にこのドライバーの 部表現への変換は本システム上1こあるACP・GROUP・ プログラムを示す。この手続きは本システムの DRI．
TEXT（Automat皿Construct Procedure Group）とい VER TEXTというファイルに書かれている。
端記号遷移 非端記号遷移
アクション遷移
終 状 態
（ラムダ遷移）
グラフの分岐
上のすべてを含 んだ オートマトンの 例
グラフ表現
ワ マ
ゲ袷 ヂ℃
◎
ぎδ氾
▼A亨 N A1 ，B▼
内部表現
＝
▼A▼ ，B▼ ▼C▼
▼A▼ ▼駆
A1
｛杜蝕杜杜禽⇔含督食託杜☆⇔ 費鱈 枝軸紡禽銭 Ω 含軸⇔鱈品垂｝
｝：・恩堺・舶…… ………一…・・…・一口帥 ．：l
PROCεDUR芭 READT（VAR CH‡SYM80L： FLA《茎2：BOOLEAN）ハ BEGIN
工P PLAG2 THEN 88G‡N READS｛CH）ム W±ユCH ￡NO 口LSεζ翼‡存w
認功 PR㏄EDUR芭 駕NISYS
BEG工N P 讐TRUE3 83百TRUε END：
P頁㏄日o織o只Σ∨ε蓑｛T‡雑◎砕：草ぷ8，靹￠おBOOL顕習）ξ VAR ACP38◎◎LEAN5 UIHOLP？
PR㏄EDUR鷺 PTERH，
B￡GIN 票εADT｛CH．B，：
ΣP冗8wCH，P＾・§m灘G｝誓麗ロB8ぷ9亮＝ダ．Lぱ堺：8；エ？賢㈱§NO 江Sε8嵩翁ΣN唐ヰ㌔RぱNX：B2胃治品灘ぴDEND3
PROCEDUR聡 ！》NONTERH，
B￡GIN
UcエPξ DR工VER（P＾令LINKFB，ACP）3 P；駆U：
口ACP恒εN熱首ダ、Lロwx￡LS霧P；＝P＾．頁L斑K εN民
PROCEDURぽ PLAMBDAξ BEGIN Aζ：欝‡3TRUE： P NIL END5
8EGIN （・㈱GIN DRIVεR・）
ACP±属FALS窪：裳宝？：
衰εPεA？
CAS￡〆語㌘？OP
T宏RH：PTERH7 寵ONTERH；PNONT松RHハ ACTION c PACT工ON， LM8DAξPLAH8DA εND UNTIL P縁N文Lε
PAepフ魯ACP SND∫
8εG抽｛舎8斑ΣN￡XEごU恒脅）
IN工SYS♪ ORIVER（P，Fψ自｝
END：
図一12 ドライバールーチン
図一10オートマトンのグラフ表現と
計算機内部でのリンク表現 姻碑￡綱田；
ま鋼sn侶o島宕d1硯3
外部→内部変換手続 （3）
卿C￠凶匹々￠ εXεCμTε
λ μσcε血尾ε賢εA参s書汲尾ξ鐸・5タ纏妬
beg 由 （5）
un己￠4σn 了εs了lx．y；sγ鋪80L），
6eg《提 頷d，
ゐをヨば ロむ
λ 「 脚蹴ε〜2 ・碕 （2）
；P亀σ寘ｾ二￠卯1vε灼 ￠n㎡、 （4）
6蟹栖 ⑳由 λ 6，9｛同
i （1）
Pξ・稔cぴふ萄
図一董董図1の内部表現 図一穏 本システムのプログラムの構造
88
3．3． アクションルーチン ｛…………・……・…・帥………⇒
くカ ヨ ムけ しロユ カバ オートマトンの外部表現におけるアクションを定義す （……台…★★音……★…………★★ 杜含…… … ドおウリ
ヨ ロへ おスハば しぽエハるプログラムをアクションルーチンと呼ぶ。このアク 丁漂1：：漂蒜昔：、。り←＿②
シ。ンは，実際には3．1節で述べたようにそれぞ嬬号 竃漂蹴・亨己＝⑨
ロじむ ヤハづけられている。 ：8‖1翌ii；i 5） c° S⑰｛2・3 ＋ ｝ c°NS烈13 5） c°NST 2 2）
CONSTN｛S，6，9）， CONSTT｛6，？，，★．，ハ CONSTN（7ワ8，9）： CONSTA｛8，6．3）7 むハ しくる ハ
アクションルーチンは次のようにして書かれる。（今 ε朧蒜i；：｛》：：？：；；ε蒜瑞呈：｝；：｝1；，。。S。。、、、，n，甲，、
くハ ぼしくエユハハ まで扱ってきた逆ポーランド記法変換のオートマトンを ，。：： EC°NST EXECUTE
例にとる。） （a）
（1）各アクションに対応する手続きを書く。 ・………・………・……・………・
くの ハ エエむ むド ロゆば しロエ ぽハ procedure A1； （° ⇔ の脅 脅… ★ 台 台舎食゜舎⇔° ★ 台舳｝
PROCEDURE EXECUTE：
begin writeln（▼ A▼）end； PR 鷲2呈；Eよ部？1㌍｝…H；認：言『呂）。。D、
procedure A2； FuN；認鶉：器：i三i迄蔚MI言出38°°LE＾N begin writeln（▼ 十▼）end； PR（詰￥嵩E譲｝↓…（・ パ［ε・D、
ロほ ぽ ロロロ ムユロ
procedure A3； BeGm エTELN（ ◇ ）END ドほ ぽロリ ロ ハヨま
begin writeln（▼ ＊▼）end； 8部IN蝋TEL剛 ° ）END PR㏄EDURE PACTION：
ロロ エド
（2）（1）で作った手続きを呼出す手続を書く。 ：？㌃・『：L搬゜F18＾1 2 A2 3 A3 END ボロロフ
procedure PACTION； （b）
begin 図一14 case P↑．ANO of 1：A1；2：A2；3：A3 end；
P：＝P↑．LLINK
end； 4．字句解析系の作成
我々は3章で説明した記号処理システムの応用例とし ここでPACTIONはProcedure Actionの略でドラ て字句解析系を作成した。この章では字句解析について
イバルーチンはこの手続きを呼出す。P↑．ANOに動作 説明し，次に字句解析系の実際の作成例を紹介する。
を行うアクションの番号が入る。P：ニP↑．LLINKで 4．1．字句解析
次の遷移をたどる。 字句解析はコンパイラにおいて入力テキストを解析し 3．4．本システムの使用法 て入力テキストを構文要素（トークン）に分けることを この節では以上述べてきたオートマトンモデルの 行う。
UCSD PASCALシステムによる実現と，このモデルの 我々の作成した字句解析系では次のことを行ってい 動かし方について述べる。 る。
図一14に全体のプログラムの例（逆ポーランド記法変 （1）入力テキストを空白や▼，▼，▼＋▼，▼一▼などの「区 換）を示す。ユーザーは（a）と（b）を別のファイルに書き， 切記号」と区切記号にはさまれた文字列に分解し，
（a）のコンパイルと実行を行う。ここで（b）は（a）の①の場所 これを1つの要素（トークン）とする。
に挿入される。（b）は3．3．節で作ったアクションルーチン （2）入力されたテキストの1つのトークンに対して1 に，手続きEXECUTEの宣言，入力手続きREADSお つの固定長の記号すなわち不偏記号（uniform よび判定関数TESTを加えたものである。（a）の②の場 symbol）を出力する。（これを不偏記号表という。）
所にはオートマトンの変換手続きが挿入される。③の所 （3）すべての不偏記号が出力された後，不偏記号と にはドライバールーチンと手続きEXCUTEのbegin トークンの対応表である端記号表を出力する。
からendまでが挿入される。なお，（b）はEXAMPLE1・ この字句解析系は，入力テキストを不偏記号表と端記 A・TESTというファイルに入っていなければならな 号表に変換する記号処理システムと考えることができ い。 る。
この変換規則はRTFで次のように規定できる。 記号を出力する。［A3］は区切記号でない文字をつない
〈Lexica1＞＝［AOコ〈text＞ ＃ ［A4〕 でいく。［A4］は端記号表を出力する。［AO］は作業の
〈text＞＝〈break＞＊十（〈terminal＞〈break＞）＊ 準備を行う。
〈break＞＝（〈blank＞＋〈break symbol＞）［A1］ 4．2．字句解析系の実際
〈teminal＞＝（〈termsymb◎1＞つ ［A2］ 4．L節で述べた字句解析を定義するRTFから，オー
〈blank＞＝▼L」▼＋ トマトンの外部表現とアクシヨンに対応するプログラム
〈bre故§ymbol＞＝▼＋Ψ＋▼一亨＋▼騨＋．．．． を作り，これを3章で述べたようにして，1っのプログ 〈termsymbol＞＝ ラムにまとめる。このプログラムを図一15で示す。この字 （ A ＋1B ＋…＋1Z 一ピ◎ 牛11 Ψ…）［A3］ 句解析系を動作させた結果を図一16に示す。（a）が入力テ ここで［A1］は区切記号に対する不偏語号を出力し， キストであり，（b）が不偏記号表，（c）が端記号表である。
［A2］は区切記号にかこまれた文字列に対応する不偏 なお不偏記号は整数としている。
（ ★★★★口 口★★杜★冑口 繰 口★帥★禽 ★⇔★ ★★★ ★禽軸★★★）
｛：★ξ書昔告・ξ殼§ξ・★輔杜… 鱈始・★・口⇔蝋・ 舳・鍾・・杜⇔ね・… ．繰：｛
｛合SS＋舎｝
PROGRAH LEXICAL 3 TYPE SYMBOL〈㎜：
｛禽＄X ACP．GROUP．「rEXT ★）
｛吉S工 る培XΣC品．A．「PgX「ξ ★｝
｛糞sl I＞R工v2R．「P芭x㌘ ★）
BEGIN BCONST3
CON＄「PA（20021，0）3CONSIrN（21，22，1，｝3CONS「西｛22．23，1書り3CON5「rA｛23，24，4）；
c◎NS「PΣ虜｛24｝き
CONS「魏9｛1，1，3）∫CONS「罰悼｛】L，2ρ4）；CONS「rN｛2，又，3｝3 CONS「rL（5）5
CONSΨN（3，5，10）3CONSTN（3ワ5，12）‡
CON＄「rL（5）7
c◎N＄烈《4ぴ？，14）3c◎NS「灘｛ヲま了，14）：c◎NS「TA｛？，8ま2きξ CONS響L｛8）7
CONS㊥r（10，11，・ り7CONSTT｛11，11，， り；
CONS『PL（11｝3 CON8㌘A（13，6，1），
C◎NS「PT｛12 ユ3 ・＝．｝：CONS「PT｛12，駕3，・〈・｝：CONS「惚｛12，13択台〉．｝3C◎NS「T「夢｛12タ133・｛・）3 C◎NS望哩｛12■13 ・｝田）；CONS「P㌘｛12i，33，・÷台｝3C◇NS蛭｛12，13，8★蓼｝3￠（）NS手璽｛12タ13，自一目）＃
CONS「P「r（12 13ρパリ；CONSTT（12，13パ】・》3CONSTT｛12，13，・．り3C◎NSTT｛12，13，・，り3 CONS㌘T（12，13， ？．）3CONSTT（12，13，㌧・），CONSTT（12，13，・，り；CONSTT（12，13，・1りp CON8㍗r（12 13 S 1；CONS冊（12，13， も ）3CONSTT（12，13，・＆り，CONSTT（12，13，・＾り7 C◎NS三！「r｛12 139・e・）：C◎NS「惚｛12，13，・／・）；C◎Nsrrr【「（12 ユ．3才 8・・）5
c◎NS「PL｛6ハ：
CONS￠A｛15．16，3｝，
CONS娩（14，15ワ・A．）3CONSTT｛14，15，・B・，；CONSTT⊂14γ15，・Cり5CONSTrr｛14．15σ・D．｝3 CON＄「rT（14，15，・E．）3CON＄TT（14，15，・P・），CONSTT（14，15，．G．｝，CONSTT（14〆15，・Hリラ CONSIPT（14，15，，1，）3CONS惚哩｛14，15，．」・，3CONSTrP（14，15，・Xり3CONS！PT｛14，15謬 L・｝タ
． C◎繋S「惚｛1も152苗材・）；e◎NS賛｛14ひ］．5虜9Nま）きC◇NS「惚｛14汐又§夕浪Oつ3CON§「惚｛ユ4タ15，曽Pき）き CONS「r㌘｛14 15 ・Q曇｝；C◎NsrΣrr｛14，15，タR含｝3C◎NsrP㌘（14，3．5，°S漠｝3C◎Nsr惚（］．4，15．・rlr．｝ヲ CON8「rT（14，15， U・｝3CON＄TT｛14ワ15，・V．）；COSSTT（14，15，．Wl｝，CONSTT（14ρ15，・Xり3 CON8「P「P（14，15，IY．）3COWl＄う門P｛14，16，．Z．，3
CON＄唖（14，15，．0．）3CONSTT（14，15，・1り；CONSTT（14，15，．2り；CONSTT（14〃15汐・3・）3 CONS惚｛14 15汐84s海CONS「樫縫44Sθカ5 ）ξC◇艮S蛭｛3．4タコ．三〜，き6つ3￠ζボS「鯉α4タ15，97カ）7 C◎Nsr鯉｛14，15，蓼8．）zCONsr躍｛14PIS，・9ま｝；
CONS「rL（16｝3 P言繍BCONST5EX8CUTE END．
・ 図一15①
90
艦；；；＝＝；；：；ご…一………・一一…一一含：； 瓢ξSSI°N＞：〔：1器き1；｛：許㌫；・ζ・・，
（● ★禽金★ 金 宥 ★ 禽★ ★ ・⇔ ⇔★ ★ ★ ★⇔★ ⇔金 ★ 禽★ ★｝ ＜FACTOR＞ ＝・A・＋・（，＜EXPRESSION＞1）1 7 e ・
PR㏄EDURεEX㏄UTE @ （a）入力テキスト
TYPE TOKEN＝ARRAY【1．．311 0P CHAR r PTABLE＝＾TABLE：
TABLE ロRECORD LETTER ，TOKEN；
NUHBER ：INTEG巳R； 2 NEXT 3 PTABL8 3 4 END：
5 14
VARエNTEXT，usT，TERMT‡TEXT， 2 B1
§＝ε：；9鷺 一 ・・…，一，−N−A…， 1 ：。，R。SS、。N 呈；
PR㏄EDuRE R8ADs（vハR cHεsYHBoL）， 7 ＞ B4 B呂GIN 8 ＝ B5
1F：2T，5霊漂器㍑認8部IN 9 TERM ・ ・6
B㏄エNR脚LNIINT蜘）3R顕D｛INTEXT，CH）εND 8 ＜ B7
ELSE READ｛INTEXT，C川， 2 1 B8 脚RITELN（C田 6 ＋ Bg
EN；ワD 4 ｝ B10
10 ★ ・Bll FuNcTloN TEs「「（x Y；sYHBoLhBooLEAN5 11 「 B12
B㏄1N TEsT・＝（x−Y l宮NDピ 12 FACTOR I13
PRocEDuRE ExPAND（A‡ToKEN）3 ． 2 A 114 VAR NH31NTEGER 8 6
B爾1器HN：：≡；1‖；： ：9H§盟主；7N酬TEXP＾ND，， 4 （C）端記号表
LETTER 害A7 ・ NUMBERcエNH3 NEXT；＝NIL： ・ END， TEND＾．NEXT 3ヨTEXPAND ° ENDハ ．
FU P呈OI；彊欝 ：：；塁盟；；！°OL助N； 』 （b）不偏記号表
『；：：：：王R：言，31D。。，．T AND（A【、】。Bl、D、 図一16
1」TES「rc＝NOT T END
FUNCTION SEARCH｛A：TOKEN）31NT8GER∫
B㌢1：AND｛A），TS隙CH，＝TB㏄、N， 5．あとがき
隠HILE LTEST（A．TSEARCH＾．LETTER｝ DO TSεUCH：治TSEARCH＾．NEXT；
SEARCH‡冒TSEARCH＾．NUMBER：
，。；：でS蹴CH〈＞TEXPA D THEN T『XPAND 字TEND ELSE TEND 3覗XPA D 本システムではオートマトンをプログラムの一部とし
PR°YU監蒜畿1； て組み込んだが，本来ならば外部から入力されるべきも
BEGIN POR I‡牢1 TO 31 DO STRING【113ヨ． ・F SPOINT‡＝1 END5
PR㏄肋戚ぬ。。， ． のである。現在，オートマトンの外部表現を外部から読
V禄 X‡INTEGER，
B㏄IN X 字SEARCH（STRING、 脈1TRtN 「肌x）TF「 陀＾ c削n み込んで内部表現に変換して読み込む手続きを開発中で PROCEDURE AO，
，㌫NI31NTEGER ある。
RESET（INTEXT， I YAMA2：工NTEXT．TEXT I｝3
；；蒜；：（US．，・，楓、，UST．。，、，，）、 今後は本システムを使用して，字句解析の次の段階で
CLEARS STRUNG【1】3・， 1， STRINGl31】：エIB㌧
N翌1：器鰹↓橿1；2、丁眠IN＾D°B㏄IN ある構文解析系を作成し，最終的にはRTFを入力し，そ 1
NUMBER 3エ13
，ぽ驚識き1 の動作を行う機械を出力させる言語自動生成系を作成す
TEND 2■TBEGIN；
卵D る予定である。
POCEDURE A1，
B斑XN@CLEARS3 STRエNG【11 べH STRINGI31】・ B ，甑RK END・ なお本稿で与えたオートマトンモデル，すなわち順序
PR㏄EDURE J、23 噛
B㏄IN@STRING【311・3 1 ・ぬ・・E・D・ 機械の多重システムは，我々の研究室で与えた再帰降下
PR㏄8DURE A31
眠IN@STRING【SP°INT】cヰH・SP°INT・ヨSP°INT＋1 END・ 順序変換機系1｝に当たる。
PROCEDURE A47 V瓦R LJ．K‡1NTEGER：
BEGIN
晶謡摺纈㍑湾㍊1：：識：i㌫壬㌣ぴ 参 考 文 献
蒜：：：：：；≡：㌫：鷺：TS脚CH，。TBEG、N、 1）安在，潮崎： 再帰降下順序変換機系とその生成機械 ． FOR K言■1「rO J DO BEGIN
㌫。1；；≧｝ID°．擦認ε黙61：部・・…ER・・… 電子通信学会論趣63−D・9・PP・771−778（N°v・1980）・
EN；1隙cH；＝TsEucH＾・NExT 2）Lewi・J・・et al・tぐA Programming Methodology in ㌫：：漂号器6L器隻1↓Al合篇；llり Compiler Construction， North−Holland（1979）．
囲D @ ・ 3）安在他：． 半線形代数フ 第1報〜第8報，信学技法
PROCEDURE PACTION：
B㏄xN 、 AL801−60，61，62， AI．81−4，5，38，39，74（1981）
，，il三5＝°F°：A° 13A1 2ξA2 A3 4‡｛ 4）D・． K・nn・・h他⊇智他訳・UCSD PASCA・・Mシス
テム入門J，JBA，（1980）
5）米田，疋田「PASCALプログラミング」，サイエンス社，
図一15② （1979）6）中田育男「コンパイラ」，産業図書，（1981）
7）Donovan著，池田訳「システム・プログラムII」，日本 コンピュータ協会，（1976）．
