yacc - みる会図書館


検索対象: 月刊 C MAGAZINE 1989年12月号
16件見つかりました。

1. 月刊 C MAGAZINE 1989年12月号

ティスク内 - 、 , お知らせ 創刊第 3 号特別付録 ( 5 〃 2 H D ) には , 次のプログラムがそれぞれのサプディレク トリに含まれています。 ①ディスク版『 QuickC プログラミング』 YQCPRGYPCPRG. EXE ② Turbo シリーズ修正差分ファイル YTUPDATEY く TurboC, Turbo PascaI , Turbo Assembler 別のディレクトリ〉 ③サービスューティリティ YCOSMOYADIR. EXE YCOSMOYADEL. EXE TOKU2 : 第 2 特集 ④掲載全ソースプログラム OUYOU : 応用 C 言語 YCMAGAY く各記事のディレクトリ〉 なお , このディスクには MS-DOS のシス テムが含まれていませんのて、 , 実行するに は MS-DOS のシステムディスクが必要とな ります。また , ディスクの容量の関係て、 , ①および④の「 COMPUTER LANGUAGE 提携記事』と ryacc による C コンパイラブ ログラミング』はプログラムを圧縮して載 せてあります。圧縮は前号付録の LHarc を 使い自動解凍てきるように指定しました。 各サプディレクトリに README をつけま したのて、そちらも参照してください ティスク版 『 QuickC プログラミング』 日本ソフトバンクより出版されている fQuickC プログラミング』 ( 定価 2 , 680 円 [ 本 体価格 2 , 602 円 ] ) に掲載されているプログ ラムの実行形式ファイルとその簡単な説明 , * . doc ファイルを圧縮した自動解凍プログ ラムて、す。 QCPRG. EXE を 900K バイト以 上の空き容量があるディスクにコヒ。ーし , QCPRG を実行します。 142 CMAGAZINE 1989 12 qcprg これて、解凍されたファイルがて、きます。 各プログラムには * . doc ファイルが用意さ れていますのて、参照してください。なお , プログラムの詳しい内容を知りたい方は 『 QuickC プログラミング』をご覧ください Turbo シリーズの修正差分ファイルと C マガジン 11 月号の付録ディスクに入れた TSR のバージョンアップ版て、す。差分ファイル は , それぞれ TCUPDATE (TurboC 2.0 用 ) , TPUPDATE(Turbo Pascal 5 . 0 用 ) , TDUPDATE(Turbo Assembler& Debugger 1.0 用 ) というディレクトリに入 っています。修正の方法は , それぞれのデ ィレクトリにあるドキュメントファイル (T x UPDATE. DOC ) に記載されています。差分 ファイルは圧縮してあり , Turbo のマスタ ーディスクにある UNPACK.COM を使っ て展開します。ファイルを展開した後は , 一括して修正を行うプログラムが用意され ていますのて、 , そちらをご使用ください サービスユーティリティ MS-DOS オペレーティング支援ユーティ リティとして拡張 DIR 命令 ( オールディレ クトリ表示 ) と拡張 DEL 命令 ( オールファ イル削除 ) を入れてあります。 2 本のプロ グラムは MS-DOS 3.1 以降て、ご利用くださ い。使い方については README を参照し なお , 本プログラムを運用し てください た結果については , 一切責任を負いかねま すのてご了承ください とくにオールディ レクトリ削除プログラムは十分注意してご Tu 「 bo シリーズ 修正差分ファイル サプデイクトリ CMAGA の下に記事別 のディレクトリをつくり , それぞれの記事 に関するプログラムを収めてあります。 使用ください 掲載全ソースプログラム DWO TOKUI OPPK 講座 : ワンポイントプログラミング STAR"II) : 初級 C 言語講座 YACCP : C コンパイラブログラミンク CMSIXE : MS-DOS プログラミング入門 : 第 1 特集 提携記事 : COMPUTER LANGUAGE りましたら , 編集部まて、ご連絡ください 各プログラムに関するご意見ご希望があ けてください リがあるのて、 / x ( 小文字 ) を忘れないて、つ このファイルのみ解凍後にサプディレクト yacc /x 固 し , 次のように実行します。 の空き容量があります。ディスクにコビー の方法は , YACC. EXE を 220K バイト以上 C コンパイラブログラミング関連の解凍 poker 固 次のように実行します。 以上の空き容量があるディスクにコヒ。ーし , 凍の方法は , POKER.COM を 350K バイト PUTER LANGUAGE 提携記事関連の解 ログラムを圧縮して載せてあります。 COM 携記事と C コンパイラブログラミングはプ 先のとおり COMPUTER LANGUAGE 提 の記事と README を参照してください 各々のプログラムの使い方は , それぞれ

2. 月刊 C MAGAZINE 1989年12月号

Cm コンパイラは , LSIC-86(Ver.3.10), TurboC(Ver. 2.0), MS-C(Ver. 5.1) の各 コンパイラて、動作を確認ずみて、す。それぞ れのコンパイラ用の MAKEFILE もディス クに入れてあります。また , 標準的な機能 のみを使用していますのて、 , ほかの OS やコ ンパイラに移植するのも容易て、しよう ( ただ し , プロトタイプを使っていますのて、 , ANSI C 準拠て、なければ , つらいかもしれませ 遅れてしまいましたが , Cm コンパイラの 最後の仕上げは ( 株 ) 工ル・エス・アイジャ パンの乗松保智氏に協力していただきまし た。生成するアセンプラコードに MASM 疑 似命令を埋め込み , さらにスタートアップ ルーチンや「標準ライプラリ関数」 ( ! ) を整 備するなど , Cm を実際に動く言語になるよ うに生命を吹き込んて、くれました。この場 を借りて感謝の意を表します。 出鼻をくじく話 それて、は , いよいよ Cm コンパイラの作 成に入りましよう。まずはじめに , 文法の 定義を行います。 yacc て、は , 文法を文脈自 由文法に従って定義します。ここて、冒頭か ら士気をそぐようなことをいうのは気がひ けるのて、すが , プログラミング言語の文法 を厳密に定義するのはたいへん難しく , 文 脈自由文法の深い知識を必要とします。ま た , 文法を「デバッグ」するには , yacc の動 作原理も理解していなければなりません。 この連載はパーサをつくるのが目的て、はな いのて、 , 文法の定義については簡単な解説 程度にとどめさせていただきます。て、すか ら , まったくオリジナルに言語を設計した い方は , 第 2 回て、あげた参考文献て、文脈自由 文法を勉強してください しよっぱなから厳しいことをいってしま いましたが , 「渡る世間に鬼はなし」とか「人 生楽ありゃ苦もあるさ」ともいいます。まっ たく新規に言語を設計するならともかく , 既存の言語のパーサをつくるのなら楽をす る方法もあります。今どきのプログラミン グ言語は文脈自由文法に基づいて定義され ていて , 仕様書に文脈自由文法ふう ( あるい は , BNF ) の定義が与えられているのが普通 て、す。て、すから , 仕様書の文法定義を機械 的に yacc ソースプログラムに変換すればよ いわけて、す。幸い , Cm は C の機能を削っ たサプセット仕様て、すのて、 , 文法の定義は 基本的に C のものを流用することがて、きま す。 C の文法は , カーニハンとリッチーの名著 「プログラミング言語 C 』 ( 以下 K & R ) の付 録て、定義されています。文脈自由文法ふう に定義されているのて、 , これをほばそのま ま yacc ソースプログラムに変換すればよい わけて、す。しかし , 落とし穴もあります。 K & R の文法の定義は , あくまて、も文脈自由 文法「ふう」て、 , 厳密に定義されているわけ て、はなく , いい加減なところもありますの て、 , これをそのまま yacc に食わせても , は じかれてしまいます。そこて、 , yacc が文句 をいわないように手直しする必要がありま す。このように , 既存の言語のパーサをつ くる場合て、も , 文脈自由文法の知識がまっ たくいらないわけて、はありません。 というわけて、 , なんの代償なしに yacc の 恩恵にあずかれるわけて、はありません。し かし , パーサを人手て、作成するというのは , コンパイラ開発のうちて、も , かなり手間が かかり退屈なものて、す。て、すから , 少々の 前準備が必要て、も , トータルて、見れば yacc を使うだけの価値はあります。個人的な体 験て、すが , 筆者は今まて、 C のパーサを 2 回書 いたことがあります。 1 回目は , 式の部分を 演算子順位パーサ ( 自動生成 ) て、 , そのほか の部分を再帰下向き法 ( 手書き ) て、作成しま した。 2 回目は , yacc を使い全面的に自動生 成にしましたが , 実感としてかかった手間 は 5 分の 1 から 6 分の 1 程度だと思います。「自 動生成なのだから手間はもっと減るのて、は ないか」と当初予想していたのて、すが , 実 際は文法のデバッグ法などのノウハウを確 立するのに , 時間をとられてしまいました。 コンノヾイラ yacc による C コンバイラブログラミング 71 * 型か int 型を積むことがて、きます。アクシ としておけば , 必要に応じてスタックに char # define YYSTYPE yystype } yystype ; int value ; Char *name typedef struct { たとえば , けばいいわけて、す。 必要なデータ型の union として宣言してお もちろん , こういう場合には YYSTYPE を ろな種類のデータを積む必要があります。 コンパイラなどて、は , スタック上にいろい タのみをスタックに積むとはかぎりません。 define していましたが , いつも 1 種類のデー プログラムて、は , STYPE を long に # ータの型は YYSTYPE 型て、す。前回の電卓 ることがて、きます。スタックに積まれるデ として , スタックの内容を参照 , セットす クと呼びます ) 。アクション中て、 $ $ や $ n スタックを利用します ( 以下 , たんにスタッ 報の受け渡しをするのに , セマンティック ましよう。 yacc て、はアクションどうして、情 ティックスタックの使い方について説明し たが , 文法の定義に入る前に , まずセマン 前回 , yacc の使い方について説明しまし に分けられます。 優先順位の定義 , ④文法の定義の 4 つの部分 ックスタック定義 , ②トークンの定義 , ③ 説明をしましよう。 List2 は , ①セマンティ します。このリストに基づいて文法定義の 定義部分だけを取り出したものを List2 に示 が , アクションを取り除いて , 純粋に文法 Cm 言語の定義は cm. Y て、行っています セマンティックスタック 断は正しかったと考えています。 う , と判断したからて、す。今て、も , この判 の保守のことも含めると結果的に楽て、あろ するよりも yacc て、書き換えたほうが , 今後 書き直した理由は , 手書きのパーサを改造 しかし , そもそも 2 回目に yacc て、全面的に の内部を詳解

3. 月刊 C MAGAZINE 1989年12月号

語に依存しますが , 文の区切り記号 , 閉じ カッコなどを採用します。 Cm パーサて、は , 今説明した ' } ' ' ; ' が「つつかかり」とな るわけて、す。 式の定義 式の定義は List2 の 229 から 280 行目まてて、 す。 nc expr, expr, primary, expr list の 4 つのノンターミナルが定義されています が , このうち , 実際に式を表す『メインエ ントリ』は , expr て、す ( ノンターミナルと は , 形式言語理論の用語て、 , yacc て、は文法 規則の左辺にあたります ) 。残りの 3 つは , expr を定義するための補助的なものて、す。 先ほど簡単に触れましたが , いちばん弱 い ( 優先順位が低い ) コンマ演算子を扱うた めに , nc_expr というノンターミナルを導 入しています。 nc expr とは , non-comma expression のつもりて、名づけたものて、 , コ ンマより強い演算子を含む式を定義してい ます。そして , expr て、は nc expr を使っ てコンマ式を定義しています。 こて、「コンマ式 (comma expression) 」と いう呼び方をしましたが , これはコンマ演 算子て、結合された式のことて、す。ただし , コンマがいちばん弱い演算子て、なければな りません。たとえば , 「 a = 2 , b = 5 」はコン マ式て、すが , 「 a = ( 2 , b = 5 ) 」はコンマ式て、 はありません。なぜなら , コンマはカッコ の中に現れるのて、 , この式て、のいちばん弱 い演算子て、はないからて、す。 一般に , ある演算子がもっとも弱い演 算子として現れる式を降式」と呼びます。 四則演算程度て、すと , 「式」 , 「項」 , 「因子」 と優先順位ごとにユニークな名前をつけら れますが , C のように優先順位が多くなると そうもいきません。そこて、 , このように機 械的に名前をつけるのて、す。また , C て、はい ちばん弱い演算子はコンマなのて、 , コンマ式 = ( いわゆる ) 式 となります。この規則に従うと「 a = ( 2 , b= 5 ) 」は代入式て、あることになります。また , 76 CMAGAZINE 1989 12 non ー comma expression も , 正式には assignment expression ( 代入式 ) と呼ぶべ きて、しよう。 なぜ Cm ( と C ) て、はコンマ演算子だけを特 別扱いしなければならないのて、しようか ? これは , C の文法て、はコンマ式が使えない場 所があるからなのて、す ()m についても同 様 ) 。関数呼び出しのパラメータと初期化式 がそれて、す ( Cm て、は , 初期化はて、きません が ) 。たとえば , は , 正しい解釈て、は「 a 」 , 「 b 」というふたつの パラメータをもっ関数呼び出して、す。しか し , かりにパラメータにコンマ式を書く とがて、きるとすると , これは「 a , b 」という ひとつのコンマ式をパラメータとする関数 呼び出して、ある , と解釈されてしまいます。 初期化式についても同様なことがいえます。 たとえば , int a = 2 , b = 5 ; という宣言て、は , 初期化式としてコンマ式 を許した場合 , a という変数を「 2 , b = 5 」と いう値て、初期化することになってしまいま す。 これは , 区切りと演算子に , コンマとい う同じ記号を割り当ててしまったからて、す。 この衝突を避けるために , パラメータと初 期化式て、は , コンマ式を書けないことにし ているのて、す。ちなみに , どうしてもコン マ演算子を使いたい場合は , カッコて、くく ります。つまり とすれば , 「 (), b) 」というひとつのパラメー タをもった関数呼び出しと解釈されますし , int a = ( 2 , b = 5 ) ; とすれば , 変数 a を宣言してから「 ( 2 , b = 5 ) 」という値て、初期化することになります。 カッコて、くくることによって , コンマ演算 子が外から直接見えなくなり , コンマ式て、 はなくなるからて、す。 expr ( 255 ~ 261 行 ) は , 今説明したように nc expr をひとつ以上 , 間にコンマをはさ んて、並べたものて、す。前回 , 文脈自由文法 の説明のところて、紹介した繰り返しの定石 を使って定義します。また , yacc を使う場 合には , 適当なところに error を含む規則 を入れてエラーリカバリをしなければなり ません。 工ラーリカバリ用のアクションは , Fig. 1 のようにするのが定石て、す。しかし , Fig. 1 のとおりにすれば必すうまくいく , という わけて、はありません。トライ & 工ラーを繰 り返して , 実際のエラーて、適当なリカバリ が行われることを確認する必要があります。 また , 正常なケースについて矛盾なしに文 法が定義て、きていても , error トークンを 含む規則を追加すると , 文法がおかしいと yacc に文句をいわれることもあります。 ういった場合には , よく文法を吟味して処 置を講じますが , そのためには文脈自由文 法の知識が必要て、す。 expr の定義も定石に くらべて少し異なっていますが , これもト ライ & 工ラーをしたためて、す。ェラーリカ バリは , 実用的なコンパイラを作成するう えて、大切なポイントて、あり , コンパイラの 使いこちを左右します。しかし , 本論か ら外れることて、すのて、 , あまり追及しすぎ ても不毛て、しようから , この程度にとどめ ましよう。工ラーリカバリの方法を含め , yacc を使った文法の設計については参考文 献 [ 1 ] をお勧めします。 こて、話が前後しますが , yacc が指摘す るエラーについて説明しましよう。 yacc 使用時のエラーは , 入力ファイルの 文法工ラーと , 定義した文法自身のエラー の 2 種類に大別て、きます ( たいへんまぎらし くて申し訳ありません ) 。前者は yacc ソー スプログラムの文法工ラーて、 , たとえばセ ミコロンを忘れた , などのエラーて、す。 種のエラーは本質とは関係ありませんのて、 , これ以上説明しません。一方 , 後者は入力 した文法自体に矛盾があり , パーサを生成 て、きない , というエラーて、 , 「 shift/reduce conflict 」と「 reduce/reduce conflict 」 という 2 種類のものがあります。 yacc は , パースの過程て、パーサがとりう

4. 月刊 C MAGAZINE 1989年12月号

extern int a [IO) は OK て、すが , int extern a [ 10 ] はダメて、す。 ⑤は , 式のコード生成をするのに , 数値 型の種類が増えすぎると組み合わせのパタ ーンが多くなってしまうために設けた制限 て、す。 char は符号つきとして扱われます。 なお , signed char と書くことはて、きませ ん。 int と char をもとに , ポインタや配列 を任意に組み合わせて宣言て、きます。 ⑥も , コンパイラ簡素化のために設けた 制限て、す。 Cm て、は , 関数はプロトタイプ風 main(int argc, char * *argv) は不可て、す。ただし , 「プロトタイプ風」と お断りしたように , 構文がプロトタイプに なっているだけて、 , パラメータの型チェッ クをしないのはご愛敬て、す。 また , Cm コンパイラにはプリプロセッサ は含まれていません。 C コンパイラ用のプリ プロセッサを流用することにします。具体 的には , 創刊号付録の LSIC ー 86 試食版のプ リプロセッサ CCP を使うことにしましよ , こまて、に説明した相違点以外て、は , Cm は , C とまったく同じ仕様になっています。 キャストや sizeof などもちゃんとサポート しています。有名なべンチマークテストの 「エラトステネスのふるい」もそのままて、コ ンパイル実行することがて、きます (List1)0 LSIC て、 9 秒 , TurboC て、 12 秒 , MS-C て、 10 秒かかるところを , Cm は 24 秒て、す ( PC286 70 CMAGAZINE 1989 12 と定義します。従来の main (argc, argv) int argc ; char **argv ; V 10MHz) 。まあ , 予想していたほどは悪 くはないな , というのが開発者の感想てす。 Cm コンバイラの構成 [ 表 1 ] Cm コンノヾイラのソースファイル名一覧 するわけにはいきません。て、すから , ディ 残念ながら紙面の都合上 , 全リストを掲載 って話を進めることにしましよう。また , けて、すが , 実際に筆者が開発した順序に従 これから , Cm コンパイラの作成に入るわ ものが , 人手て、作成したファイルて、す。 って自動生成したものて、す。これら以外の トタイプて、 , ストリームエデイタ sed を使 のマクロ定義て、す。 function. れは関数プロ ョンによって自動的に生成されるトークン す。また , cm. h は , KM-yacc の -d オプシ の本体 ( 関数 y arse ) が定義されていま ケージに付属しているファイルて、 , パーサ c は , 前回説明したように , KM-yacc'€ッ ヒ。ーに収録されています。このうち ,yaccpar. これらのファイルは今月号の付録のフロッ ログラム全体て、約 4500 行ほどの長さて、す。 イルから構成されています ( 表 1 ) 。ソースプ ソースファイル (. y ) が 1 個の , 計 16 個のファ が 12 個 , C ヘッダファイル ( 上 ) が 3 個 , yacc Cm コンパイラは , C ソースファイル (. c) スクて、配付するソースプログラムを適宜参 照しながら読み進んて、いただくことになり ます。必要に応じて要所を抜粋したリスト を掲載します。 Cm コンパイラの開発はだいたい次の順序 て、行いました。 ①文法を定義する (cm. y) ②レキシカルアナライザをつくる (lex. c, lexstr. c)o この時点て、 , レキシカルア ナライザとパーサ ( 構文解析部 ) が完成。 とりあえず , プログラムをパースする ことがて、きる ( もっとも , 文法工ラーが なければウンともスンともいいません ③ヒープ領域ハンドラ ( heap. c ) , シンポ ルテープル処理ノレーチン (table. c) , オ プジェクトコード出力ルーチン (gen code. c) などの , ハウスキーヒ。ング部分 をつくる ④宣言の処理 ( declare. c ) をつくる ⑤式の意味解析 (exp. c) , 式のコード生成 (genexp. c) をつくる ⑥文の処理 ( stmt. c ) をつくる 今回 ( 第 3 回 ) は① , 第 4 回は② ~ ④ , 第 5 回 は⑤の前半 , 第 6 回て、⑤の後半と⑥ , という ペースて、今後の連載を進めていく予定て、す。 ファイル名 declare. C exp. C gencode. C genexp ・ c heap. c lex. C lexstr. c maln . C msc . C stmt. C table. c yaccpar. C cm. h cmder. h function. h cm ・ Y 内容 宣言と定義を処理する Cm 言語の文法定義 関数プロトタイプ (sedc 作成 ) 型 , マクロの定義 トークンのマクロ定義 ( cm. y をもとに yacc が生成 ) バーサ本体 ( KM ー yacc バッケージのもの ) シンボルテープル処理ルーチン 文のコードを生成する 工ラー処理 , 型合わせ , 型チェック , 定数式の畳み込みなど 下請けルーチン群 Cm コンバイラメインルーチン 厄 x. c の下請けで , 文字列の処理を行う レキシカルアナライザ ( 文字列 ) レキシカルアナライザ ( 本体 ) 宣言と式を表現する木構造を扱うルーチン ヒープ領域八ンドラ exp. c がつくった木構造をたどりながらオプジェクトコードを生成する 式のコード生成を行う オプジェクトコード生成ルーチン 構文木を作り出す このファイルのルーチンは , cm. y の中の式のアクションから呼び出され , 式の意味解析ルーチン すべての宣言 / 定義を処理する 外部宣言 , 関数定義 , バラメタ宣言 , ローカル宣言など

5. 月刊 C MAGAZINE 1989年12月号

C の直言・書き方と読み方 学 本ロ 0 五ロ 乗松保智 前回はがどのようにメモリ上に配置されるかをしました。鉅は や関数の館について考えてみましよう。 C の韮 int i : のように簡戦よものならわかりやすくていいのですか , のように複雑になると , 亠オは困難になります。そこで , 鉅は C の 館の方を考えます。的にできないのなら , してすれば いいのです。 まずいろいろナについて月し , 続いて C 讎訒館のを月しま す。「よくわからんそー」という声カ墹こえてきそうですが , まあ , なんとなく そうかなあくらいにしていただければです。取の言謎には yacc の を使います。 yacc につい召ー載の「 yacc による C コンヾイラブロ グラミング」をしてくださし最後に亟をわかりやすく書き直訪法とそ の方を月します。 C て、は基本的な算術型として , 次のものが 8 ビット Char 用意されています。 16 ビット short C の型について int short 32 ビット char int unsigned signed long 32 ビット long VOid float double まずは型についてざっと復習しましよう。 となっていることが多いようて、す。 こて、はハードウェアによって直接処理す 列挙型 また , signed, unsigned という , 変数 ることがて、きる基本型と , すて、に存在する 列挙型は がとる値を指定するものもあります。 signed 型を修飾してつくられる派生型に分けて考 enum { BLACK, WH 工 TE } : を指定すると「符号付き」の数となり , un えます。 C の基本的な型といえば , すぐに思 のように宣言される記号定数の一種て、 , 内 signed だと「符号なし」になります。 8 ビッ いつくのは int , char, float などて、しよう。 部的には int て、表現されます。そのため , 基 トの数値が符号付きの場合 , その値は一 128 これらは「基本的な算術型」と呼ばれ , ハー 本的な型に含めてあります。 から十 127 まて、となります。符号なしの場合 ドウェアが直接サポートて、きます。また , また , C の文法は unsigned int のように には 0 から 255 まて、て、す。これらの型はハー これらの型の大きさ ( ビット長 ) は各コンパ これらを自由に組み合わせることがて、きる ドウェアが直接サポートされますが , float , イラ , 実行するハードウェアによって , 異 ようになっています。ただし , char int の double, long double といった浮動小数 なっていてもいいことになっています。 ようなわけのわからない組み合わせは意味 点型のデータの演算は , ソフトウェアて、ェ たとえば , 多くの 16 ビットマシン上て、は 的に禁止されています。 ミュレートされることもあります。 void は特別な意味をもっ型て、 , 関数が値 8086 や , 68000 などのマイクロプロセッサ を返さないことやパラメータをとらない は , CPU 本体だけて、は浮動小数点数の演算 とを示すとき , ポインタがどんな型を指し はて、きません。ハードウェアて、演算を実行 てもいいことを示すときに使われます。 するためには「コプロセッサ」が必要て、す。 浮動小数点演算用のコプロセッサを搭載し 派生型 となっていますが , ていないシステムては , ランタイムライプ ションな ワークステー 派生型というのは「すてに定義された型を どの 32 ビットマシンて、は ラリの中に用意されている浮動小数点演算 使って新しい型をつくる」という意味て , 基 サプルーチンが呼び出されます。 C 言語雑学講座 123 16 ビット 16 ビット 32 ビット Char short int long

6. 月刊 C MAGAZINE 1989年12月号

コンノヾイラ の内部を詳解 しかし , 何となく気持ちが悪いのて、いちお う宣言しておきましよう。 演算子の優先順位に関してはこれて、すべ てて、す。後は yacc が自動的にめんどうをみ てくれます。 文法の定義 List2 の 65 行目以降が文法の定義て、す。文 法の定義は大きく分けて①プログラム ( いち ばん外側のレベル ) , ②宣言 , ③文 , ④式の 4 つのレベルから構成されます。 List2 て、は , 上位レベルから下位レベルに向かって順に 定義しています ( つまり , トップダウンて、す ) が , 説明するのには反対にポトムアップに したほうがわかりやすいと思います。なぜ なら , あるものを定義するのに , その元に なるものがすて、に定義されていたほうが , イメージがっかみやすいからて、す。て、すか ら , ④から①に向かって順番に説明してい きましよう。 , こて、 , 式の定義を説明する前に rb, rp, sc の 3 つのノンターミナルを説明しま しよう。これらの定義は 283 ~ 288 行目にあ ります。 rb は ' } ' rp は ,),, sc は ' ; ' に定 義されています。また , それぞれのアクシ ョンとして yyerrok が指定されています。 ェラー処理の途中て、 yyerrok を実行する と , リカバリ処理が完了したことを指示し ます。つまり , 文法工ラーが発生した後に , ' } ' , ' ) ' , ' ; ' のいずれかを読み込むとリカバリが 完了することになります。 これは , yacc て、つくるパーサに限った話 て、はありませんが , 文法工ラーを見つけた とき , パーサはリカバリモードに入ります。 そして , トークンを読み捨てる ( または , 補 う ) などして , 正常な状態に復帰しようと努 めます。しかし , 文法工ラーがひどいとき には , この方法て、はリカバリて、きない があります。こういったケースて、は , パー サはパニックモードに入り , ある「つつかか り」が見つかるまて、トークンを読み捨て続け ます。「つつかかり」は , プログラミング言 yacc による C コンバイラブログラミング 75 0 凵 ST ・ 2 SWITCH error 217 : 218 : 219 : 220 : 221 : 222 : 223 : 224 : 225 : 226 : / * * * * express ions 227 : 228 : 229 : nc_expr pr lmary 230 : ' * ・ nc_expr %prec unop 231 : ・ & ' nc_expr %prec unop 232 : addop nc_expr %prec unop 233 : unop nc_expr 234 : incdecop nc_expr 235 : incdecop nc_expr 236 : mu 10P nc_expr nc_expr 237 : * ' nc_expr nc_expr 238 : addop nc_expr nc_expr 239 : sh i ftop nc_expr nc_expr 240 : nc_expr compop nc_expr 241 : eqop nc-expr nc_expr 242 : ' & ' nc_expr nc_expr 243 : nc_expr nc_expr ' ド nc_expr 244 : nc_expr 245 : logand nc_expr nc_expr 246 : 10g0r nc_expr nc_expr 247 : ' ? ' nc_expr expr 248 : nc_expr aSS lgnop nc_expr 249 : nc_expr nc_expr 250 : SIZEOF nc_expr %prec unop SI ZEOF ' ( ' type_name rp %prec unop 251 : ' ( ' type_name rp nc_expr %prec unop 252 : 253 : 254 : 255 : expr 256 : 257 : 258 : 259 : 260 : 261 : 262 : 263 : 264 : 265 : 266 : 267 : 268 : 269 : 270 : 271 : 272 : expr_list 273 : 274 : 275 : 276 : 277 : 278 : 279 : 280 : 281 : 282 : 283 : 284 : 285 : 286 : 287 : 288 : 289 : 290 : { yyerrok; } stmt list rb compound stmt ニ etc. 十ニ nc_expr nc_expr expr nc_expt { yyerrok; } expr error expr error nc_expr expr error a. a. X a. X 0 Z い 0 E E 【じ Z 第 ハし , a. a. a. , prl mary nc_expr expr_list nc_expr { yyerrok; } error expr_list error expr_list error nc_expr { yyerrok; } expr_l ist error { yyerrok { yyerrok ・ { yyerrok ・ -.O a. O

7. 月刊 C MAGAZINE 1989年12月号

定することがて、きます 01DENTIF 工 ER を ョンて、スタックの内容を参照するときには %token く symbol> IDENTIFIER とします。スタックの定義は List2 の 3 ~ 11 メンバ名 symbol として参照するには , % expr : expr ' 十 ' expr { $ $. value 行目にあります。各メンバの役割を表 2 に示 token 文て、 , $ 1. value 十 $ 5. value Cm の文法定義 ( yacc ソースプログラム ) のように「 . メンバ名」を $ n や $ $ の後につ 1 : semantic stack 2 : けます。しかし , いちいちメンバ名を指定 3 : %un ion C ONST 4 : するのはめんどうて、すし , まちがったメン 5 : TREE 6 : TYPE バ名を指定する恐れもあります。 7 : Char 8 : EXPR スタックの内容を簡潔に指定するために 9 : Char i nt yacc には , %union と %type という便利な 機能があります。 %union は , スタックに積 13 : terminal symbols むデータの型を指定するものて、す。たとえ 14 : %token く symbO I > ば今の例は %to ken く _const> 17 : %to ken %union 18 : %to ken char * name ; 20 : %token 21 : %token value ・ int 22 : 23 : %token く OP 〉 24 : %to ken く OP 〉 25 : %to ken 26 : 28 : nonterminal symbo 1 s 29 : 30 : %ty pe く type> type_spec type_name 31 : %ty pe declaration く tree> 32 : %ty pe declarator 1 ist declarator declarator2 く tree> 33 : %ty pe param_l ist param decl く tree> 34 : %ty pe abst_declarator abst_declarator2 く tree > 35 : %ty pe expr_ 1 i st く tree> 36 : %ty pe pr imary nc_expr expr expr_opt く expr> 37 : %ty pe i f head <label> 38 : %type く label 〉 whi le_head 39 : %type <label> for_head 40 : %ty pe <label> sw i tch_head 42 : procedence table 43 : 44 : %left comma 45 : %ri ght / * assignment 46 : %right / * conditional 47 : %left logical or 48 : %left / * logical and 49 : %left bitwise or 50 : %left bitwise xor 51 : %left / * bitwise and 52 : / * equal ity %left 53 : %left く , 〉 , くニ compamson 54 : %left / * shift くく 55 : %left / * add, sub 56 : / * mu l, d i v %left %right unary 58 : %nonassoc inc, dec 十十 , 59 : 60 : 62 : 63 : 64 : 65 : 66 : 67 : 68 : 凵 ST ・ 2 _const; *tree : *type ; *symbol : *expr : I abe l; IDENTIFIER CONSTANT I F ELSE WHILE FOR DO BREAK CONTINUE SWITCH CASE DEFAU し T RETURN GOTO SIZEOF INT CHAR EXTERN addop shiftop mulop compop eqop assignop i ncdecop unop 10g0r logand となり , YYSTYPE 型は char * と int の union て、あると宣言したことになります。次 に % type 文を使って , データの型を宣言し ます。この例て、は , %type く value> expr とします。これは , アクション中て、 expr が スタックに積む値は , value というメンバと して参照しなさい ということを示してい ます。アクションは次のように記述します。 expr : expr ' 十 ' expr yacc は % union の宣言をおばえていて , expr についてはスタックに積む値をメンバ value として参照するコードを出力します。 先ほどの例と較べて , value とメンバを指定 しないて、すむのて、 , すっきりしています。 トークンについても , データ型を指 [ 表 2 ] セマンティックスタックの内容 内容 メンノヾ CONST const; 定数の値 TREE 言の木へのポインタ * tree, TYPE 型テープルへのポインタ * type; Char * sym bO し 識別子 EXPR 式の構文木へのポインタ * expr; Char 演算子のトークンの値 OP ′ ( 表 3 参照 ) i nt label; 制御構造のラベル etc. aSS I gnop 10g0r logand eqop COVOP shift 叩 addop mu I op ' * ' unop incdecop f i 1 e : extern def ー file eitern_def { yyerrok; } ー error 72 CMAGAZINE 1989 12

8. 月刊 C MAGAZINE 1989年12月号

1989 年 12 月 1 日発行 ( 毎月 1 回 1 日発行 ) 第 1 巻第 3 号通巻 3 号 C マガジン 提携・米国「ハー」誌 / 監修・石田晴久 すへての C 言語プロクラマのための技術情報誌 0 日本ソフト八ンク 創刊 3 号 日 K SOFT 定価 980Y 。。 1989 DEC. Vo い No. 3 く特別付録〉 5"2HD ラスク ・ Quick C ユーティリティ集 ・和 rbo シリース修正差分ファイル ・ MS - DOS ユーティリティ ( 拡張 DEL ・ D 旧コマント ) ・掲載全ソースコート 提携記事・ Designing with Objects>yacc による C コン、イラフロクラミンク >C 言語入門講座・はしめて学ぶ C プロクラミンク く第 2 特集〉 QuickC Ver.2 0 徹底チェック巻頭インタヒュー NHK 人体を生んた C 言語新連載応用 c 言語・ファ弔レ操作編 く第 1 特集〉最新 MS - DOS 考察緊急レポート \/e に 4 の実 { 象ーこ迫るマイクロソフト・富士通・エプソン・日本旧 M に聞く

9. 月刊 C MAGAZINE 1989年12月号

Fig. 1 繰り返しの定石 ( 工ラーリカバリを含む ) ( 1 ) y を 0 個以上並べたもの x : / * empty * / ー X error ー error { yyerrok; x : Y ( 2 ) y を 1 個以上並べたもの ー X error { yyerrok; ※この規則からは , y, yzy, yzyzy, yzyz ・・・が生成される。 ー X 名 error ー yyerrok; } ー X error ー X error ー error 「 { yyerrok; } lx 広 y x : Y ( 3 ) z を区切りとして , y を 1 個以上並べたもの るすべての内部状態を計算します。そして , 計算したすべての内部状態ひとつひとつに ついて , 次に読み込むトークンに応じた動 作を決定して , 表 ( パーステープル ) を作成 します。生成されたパーサは , パースプロ グラムがトークンを読み込み , ノヾーステー プルを引きながらスタックを操作する仕組 みになっています。ノヾースプログラムが行 う動作には shift, reduce, accept, error の 4 つがあります。このうち , 後のふたつは 特殊な動作て、 , accept はパースが終了した ことを , error は入力に文法工ラーが見つ とを表しています。 shift は , 読み かったこ 込んだトークンをスタックに積みます。 reduce は , ある文法規則が認識されたこと を示し , 対応するアクション ( { $ $ = $ 1 + $ 2 } など ) が実行されます。 題はありません。もうひとつはエラーリカ else のある / なしによるものて、 , まったく問 flict 工ラーがありますが , ひとつは if 文の す。 cm. y にもふたつの shift/reduce con flict のほうが「軽症」だということがて、きま どちらかといえば , shift/reduce con ーて、す。 というエラ あって一意的に決定て、きない はたしかて、すが , 従うべき文法規則が複数 おいてとるべき動作が , reduce て、あること reduce/reduce conflict は , ある状態に うに矛盾している , というエラーて、す。 shift, 別の規則からは reduce, というよ においてとるべき動作が , ある規則からは shift/reduce conflict とは , ある状態 コンヾイラ のとして定義してあります。 をひとつ以上 , コンマをはさんて、並べたも expr て、す。て、すから ,expr list は nc expr として許されるのは (expr て、はなく ) nc のて、す。先ほど説明したとおり , パラメタ しのパラメータリストを記述するためのも expr list ( 272 ~ 280 行目 ) は , 関数呼び出 expr になっていることに注意してくださ はさまれるものは ()c expr て、はなくて ) コによるくくりだし ( 265 行 ) て、は , カッコに くりだし , を含んて、います。とくに , カッ 参照 , 関数呼び出し , カッコによる式のく 行目て、定義されており , 変数 , 定数 , 配列 ターミナルが現れています。これは , 263 ~ 270 229 行目て、は primary ( 一次子 ) というノン ャスト「 ( 型 ) 式」を定義しています。 式」 , 251 行目は「 sizeof ( 型 ) 」 , 252 行目はキ きおろしているだけて、す。 250 行目は「 sizeof て、 , ここて、は演算子の使い方をそのまま書 優先順位は , 44 ~ 58 行て、宣言していますの マ以外の演算子を含む式を定義しています。 nc expr の定義 ( 229 ~ 253 行 ) て、は , コン スて、もうまくいきます。 プルをつくり出しますのて、 , いずれのケー 起きた場合 , shift を優先させてパーステー せん。 yacc は , shift/reduce conflict が バリに関するものて、 , これも実害はありま の内部を詳解 文の定義 yacc による C コンバイラブログラミング 77 は , else があるもの ( 174 ~ 176 行 ) とないも 式文て、す。 173 ~ 176 行目は if 文て、す。 if 文 ています。 172 行目は , 「式十セミコロン」の きません。複合文は , 220 ~ 224 行て、定義し カル変数を宣言てきるのて、すが , Cm てはて、 だもの ) て、す。 C て、は , 複合文の先頭て、ロー ment : ' { ' と ' } ' の間に複数の文をはさん まず , 171 行目は複合文 (compound state 語の各種の文を , 順に定義しています。 て、 , 171 ~ 198 行目て、定義されています。 C 言 (statement) を表すノンターミナルは stmt 165 行目から 224 行目が文の定義て、す。文

10. 月刊 C MAGAZINE 1989年12月号

も彼のプログラムて、す。ばくはデータコン 伊藤 CG の場合は , 工程を説明すると , ま バージョンプログラムをつくったり , VTR ずスケッチみたいなものがあります。こう コントロールプログラムをつくったりしま いうものをつくりたいという個々の場面の した。誰もやってくれないから , 全部自分 スケッチて、す。それから , こう動いて , て、やるわけて、す ( 笑 ) 。 うなってこうなってというカット割りがあ それは必要から生まれるわけですか。 ります。ますそういう手描きの絵から入り 伊藤そうて、す。 ます。手描きの絵がて、きたら , 今度はモデ ディレクタがプログラムをつくるなん リングの過程があります。モデリングとい てすこ・いですよね。 うのは , 各物体の形づくりて、す。内臓なら 伊藤て、もそれほどたいしたことはないと 内臓 , バクテリアならバクテリアの形づく みんなが思えば , みんなっくれるようにな りて、す。 ります。考え方として UNIX の環境がそうい それはどうやってやるかというと , 昔は うものなのて、す。大きなシステムをつくる それこそⅵという UNIX のエデイタを使って 必要はないわけて、す。 OS をつくるわけて、は 数値を入れていたのて、すが , 今はほとんど ない。ツールという考え方が UNIX にはあり マウスて直観的に入れていきます。 ます。ツールを組み合わせる , あるいはツ その後アニメーションをデザインする場 ールをつくって使う。 合に , さきほどお話ししたようにわれわれ アニメーションプログラムをつくったのて、 たとえばばくたちがやっていてすごく多 すが , ばくのつくったアニメーションプロ が使っていたレイトレーシングのソフトウ かったのは , 1 回しか使わない使い捨てのプ グラムて、は yacc, awk, sed を全部使ってみ ェアにアニメーションツールがついていな ログラムがいつばい出ることて、す。たとえ ようという使い方て、構築して , c shell だけ かったのて、 , 自分たちて、つくらざるをえな ば数十行て、つくって , コンパイルして , 使 て、アニメーションプログラムをつくりまし かった。いろいろな文献を探して自然スプ って , そのとき便利なだけて、後はいらない ラインて、運動はこう表現するとかそこらに あれがツールなのですね。プログラム シェルプログラミングもけっこうやら あったプログラムをもってきて改良をして , を書くというのではなくて , これをしたい れるんですね。それでは実際ここではすべ さらにいろいろ付加していって自分なりの からという表現がたまたまプログラムの形 ものをつくっていく。それはもちろん vi て、つ て UN Ⅸで開発されているのですか。 式をとっているみたいな感じですね。 伊藤そうて、す。すべて UNIX て、開発してい くって , コンパイルして実行して , うまく 伊藤だから UNIX の上には sed とか awk と ます。 いかない場合は繰り返してやっていく。 かいろいろツールがありますがそれらの使 シンポリックスは別ですか。 「人体」制作のときもプログラムをつく い方を知らなくても , C を知っていれば , ち 伊藤ノンポリックスの言語は Lisp て、す。 ったりしているのですか。 ょっと時間をかければある程度何て、も書け シンポリックスは Lisp なのだけれども , シ 伊藤してました。人間が歩くアニメーシ てしまう。もちろん awk とか yacc とか sed と ンポリックスの場合はあまりプログラムの ョンがありましたね。あれはさきほどの金 か lex を知っていたほうが便利て、す。ばくも ことを考えなくてもいいようにて、きている。 子君というプログラムなどほとんど経験し たことのない , 工学部て、もない美大の学生 非常に Mac ライクて、す。ほとんどマウスだ さんが , いろいろなプログラムを見て , そ けて、事足りるシステムになっています。 れを自分て組み合わせたり , 改良したりし 実際にアニメみたいな動きを指示する てつくった映像て、す。て、すから技術者の人 ようなことがあれば , シェルスクリプトを は , 本当は彼の 10 倍はいいプログラムをつ 組むわけですね。 くらなければいけないはずなのて、す ( 笑 ) 。 伊藤そうて、す。各フレームのデータをシ 実際に番組のなかでもそれは使われた ェルスクリプトの形て、生成するツールをつ っくています。「人体』の CG のプロジェクト のですか。 伊藤人間の歩いたのがそうて、すし , 心臟 のなかて、は , アニメーションをつくる場合 , デザイナーだが C 言語も使う 金子徳明君。美大の院生。 バクテリアと白血球の戦いを「スターウォーズ」ふうにイメー 1 ロ月リ NHK 仄内を生んだ ロロ