UNIXとコンパイラー・コンパイラーの世界
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
[[FrontPage]]
#contents
2010/08/17からのアクセス回数 &counter;
** 大型コンピュータの世界 [#t9e16a31]
私は、1983年に科学技術計算を得意とする独立系ソフトハウス...
ツール作成や研究開発の支援を主な仕事としていました。
まだ、SunからLight weight processが発表される前に同等のラ...
同時に複数の人が絵を描くツールとか新しいものを作ったこと...
*** 私の入社した当時 [#s08dcff4]
私の入社した当時は、PCはありましたが実務では大型コンピュ...
数少ない端末を共有しながらの仕事では、プログラミングも端...
なく、コーディング用紙と呼ばれる紙にプログラムを書き、そ...
入力専門の人に依頼して入力していました。大型コンピュータ...
コンピュータの利用効率を高めることが第1の目標となっている...
環境は2の次でした。ですからUNIXの産みの親であるトンプソン...
が自由に使えるコンピュータ環境が欲しいと思いUNIXを作った...
*** 既にあるものは2度作らない [#ycea07d3]
勉強したアルゴリズムを自分でプログラムしてみたいと思うの...
先輩からは既にあるプログラムと同じものは作ってはいけない...
当時は、IMSLという科学計算ライブラリを使っており、計算精...
IMSLを使うことは当然のことでした。
今で言うと新しくプログラムを作る前に、同じものがオープン...
調べてみるのと似てますね。
** 「ソフトウェア作法」 [#p2e4cc4b]
カーニハン氏、ブローガー氏の「ソフトウェア作法」（木村泉...
以来30年も読み継がれている名著です。
*** UNIXコマンドの作り方 [#e8e261b4]
「ソフトウェア作法」では、Ratforという言語を使ってUNIXの...
（cp, wc, 種々のフィルター、 sort, ed, roff, m4等）の簡...
トップダウンの構造化プログラミング手法を分かりやすく説明...
もう一つ「ソフトウェア作法」ではRatforの中に日常語を混在...
構造を分かりやすく組み立てています。
例）標準入力を標準出力にコピーする例(P13から引用)
#pre{{
while (getc(c)が入力の終わりでない)
call putc(c)
stop
}}
*** トップダウンの問題点 [#kd71fad1]
とても有益なトップダウンの構造化プログラミングにも弱点が...
それは一番下位のルーチンに設計のしわ寄せが来て、処理が複...
それでもトップダウンで設計することで得るプログラムの読み...
を考慮すると十分価値があると言えるのです。
*** ratforコンパイラー・コンパイラー [#z590d612]
巻末には、RatforからFortranへの翻訳プログラムも収録され、...
を体験できるように工夫されていました。当時は今のようにC言...
一般には普及していませんでした。
私もCP/MのFortranコンパイラーでRatforの翻訳プログラムを実...
を楽しみました。これが私が構文解析に興味をもった最初の出...
** 英語は苦手 [#iec2e28f]
現在もオープンソースのドキュメントは、ほとんどが英語で書...
私は英語が苦手なので、他の人のようにさくさくドキュメント...
しかしソフトウェアのドキュメントの場合、ソースコードなど...
中身を類推しながら、読み進めることで返ってそのプログラム...
*** UNIXの情報源は、ほとんどが英語 [#u0edf4f7]
UNIXに関わった時には、日本語の解説書などはまったくありま...
情報のほとんどがmanと英語の解説書という状況では、英語のド...
選択肢がありません。
*** 「The UNIX System」はすごい [#ted489e1]
「The UNIX System」は、shの開発者であるボーン氏が書いたUN...
これ一冊あれば、シェルスクリプトからUNIXコマンド、システ...
一通りのことが分かる優れものです。私は「The UNIX System」...
英語は苦手という意識から何とか英語との本とも付き合える自...
特にコンピュータ関連のドキュメントは、記述パターンが多く...
本も読めるようになると思います。
** 「Lions' Commentary on UNIX」 [#dc09adf3]
UNIXカーネルについて書かれた書籍はたくさんありますが、「L...
本物のUNIXソースとその解説から構成されている点が大きな特...
元々この本は、著者のJ. Lions氏がニューサウスウェールズ大...
「UNIXオペレーティングシステムコメンタリー」と呼ばれるノ...
経歴の本です。UNIXのカーネルがどのようにできたのかを知る...
*** simhでUNIXのソースを読む [#d815ba0f]
「The Computer History Simulation Project」http://simh.tr...
simhというシミュレータを使って過去の貴重なコンピュータを...
「Lions' Commentary on UNIX」で紹介されているPDP-11のsimh...
と共にディスクイメージが提供されているので、UNIXコマンド...
私の印象に残ったは、UNIXコマンドのソースが簡潔で美しいこ...
いるイニシャルブートのシーケンス通りに動いていることでし...
** yaccの勉強 [#c8d26d36]
UNIXのすごいところは、OSの他に多くのコマンドとコンパイラ...
提供していることです。なかでもコンパイラーを作るためのツ...
yaccは、使いこなしてみたいツールの一つでした。
「Introduction to Compiler Constrction with UNIX」は、yac...
Cのサブセットを例に字句解析、構文解析、インタプリタ、コン...
この本の例題を動かすことでコンパイラー・コンパイラーの使...
著書の一つです。
特にyaccで文法を記述しエラーが出たときの対応や、構文解析...
いるので、初心者にも安心してyaccが使えるようになっていま...
*** バイナリファイルの構文解析もできる [#dba9f8b7]
yaccは、字句解析を自前で作成することによってバイナリファ...
私は、CADのバイナリファイルの変換プログラムでyaccを使いま...
プログラムも簡単にできるので、デバッグやテストで重宝しま...
*** 逆転の発想（Light Speed Cの世界） [#o112f17c]
一般に構文解析のエラーリカバリ処理は難しく、大変な部分で...
箇所をエディタで表示し、すぐに修正できるようにし、コンパ...
高めたのが、MacintoshのコンパイラーLight Speed Cでした。...
時間のかかる処理が驚くほど改善されたのを今でも覚えていま...
** 「Javaによるパーサ構築技法」 [#h5afc320]
手続き型の言語の場合yaccで十分ですが、Prologのような論理...
よいのでしょうか。その答えが、「Javaによるパーサ構築技法...
前半の構文解析も分かりやすく、簡潔に説明されており、後半...
による論理構造の表現方法と単一化がポイントです。この推論...
論理型言語パーサーの作り方を習得できたと感じるとても不思...
** Antlr [#n31d6f3d]
最後に紹介するAntlrは、ちょっと変わったコンパイラー・コン...
yaccとは違い、LL(k)と呼ばれるトップダウンの構文解析を使っ...
ANTLRWorksというワークベンチを提供しており、ユーザの作っ...
簡単にできます。
言語の定義は、拡張BNFに似た形式となっていますので、はじめ...
また、サポートしている言語が、C、C++、Java、Python、C#、A...
ANTLRを解説した日本語の本はありませんが、私は「The Defini...
***ANTLRWorksを使う [#t60e49e0]
次の図が、ANTLRWorksを使ってユーザの作った文法（E1）に1+2...
このように文法を記述するだけで、テストが行え、文法のチェ...
&ref(ANTLRWorks.jpg);
*** 構文木のサポート [#t672ac12]
ANTLRの大きな特徴に、構文木をサポートしていることが挙げら...
構文木を使うことによって、構文解析後の変数テーブル、関数...
構文木を使うには、文法の最初にoptionsとtokensを追加します。
#pre{{
options{
output = AST;
ASTLabelType = CommonTree;
}
tokens{
ASSIGN; ALU_ADD; ALU_SUB; ALU_MUL; ALU_DIV;
}
}}
構文木の生成には、部分木を生成する^オペレータとノードを生...
次のstatementを例に簡単にオペレータの使い方を説明します。
#pre{{
statement
: expression NEWLINE!
| IDENTIFIER '=' expression NEWLINE
-> ^(ASSIGN IDENTIFIER expression)
| NEWLINE!
;
}}
NEWLINE!は、改行をノードに追加しません。
#pre{{
-> ^(ASSIGN IDENTIFIER expression)
}}
は、ASSIGNノードの下に、IDENTIFIERとexpressionからなる部...
*** Debuggerで動作を確認 [#hbe7d965]
ANTLRWorksのデバッガを使って、以下の入力をしたときの構文...
#pre{{
a=1
a+2*3
}}
&ref(debugger.jpg);
ASSIGNの下にa, 1がぶら下がる代入部分とALU_ADDの下にaとALU...
構文木は解析したプログラムを別の言語に変換するトランスレ...
** 自分だけの言語を作ってオリジナルのマシンを動かしてみる...
もう過去の技術だと思われていたコンパイラー・コンパイラー...
最後に、学研の「大人の科学」Vol.24の付録の4ビットマイコン...
例）１５秒カウンタプログラム
#pre{{
int a;
a = 15;
while (a > 0) {
out(a);
shts();
a = a - 1;
timer(10);
}
}}
生成されたアセンブラは、以下のようになります。
#pre{{
TIA f
TIY 0
AM
L1: TIY 0
TIA 0
AIA 1
M-
JUMP L2
TIY 0
MA
AO
CAL SHTS
TIY 0
TIA 1
M-
TIY 0
AM
TIA a
CAL TIMR
JUMP L1
L2: CAL ENDS
L3: JUMP L3
}}
*** アセンブラ [#y17216b6]
アセンブラから命令コードへの変換には、
http://www.musashinodenpa.com/misc/GMC4/
のアセンブラを使わせてもらいました。
*** シミュレータ [#ha97bc14]
GMC-4の元になった「FX-マイコン」のシミュレータが以下のURL...
http://homepage2.nifty.com/kocha_web/fxms/fxms.html
シミュレータを使うことによって、コンパイラーのバグ等問題...
とても助かりました。
&ref(simulator.jpg);
*** 実機での実行 [#y978c4fb]
生成された命令セットをGMC-4で動作しているときの画像です。
&ref(GMC-4.jpg);
終了行:
[[FrontPage]]
#contents
2010/08/17からのアクセス回数 &counter;
** 大型コンピュータの世界 [#t9e16a31]
私は、1983年に科学技術計算を得意とする独立系ソフトハウス...
ツール作成や研究開発の支援を主な仕事としていました。
まだ、SunからLight weight processが発表される前に同等のラ...
同時に複数の人が絵を描くツールとか新しいものを作ったこと...
*** 私の入社した当時 [#s08dcff4]
私の入社した当時は、PCはありましたが実務では大型コンピュ...
数少ない端末を共有しながらの仕事では、プログラミングも端...
なく、コーディング用紙と呼ばれる紙にプログラムを書き、そ...
入力専門の人に依頼して入力していました。大型コンピュータ...
コンピュータの利用効率を高めることが第1の目標となっている...
環境は2の次でした。ですからUNIXの産みの親であるトンプソン...
が自由に使えるコンピュータ環境が欲しいと思いUNIXを作った...
*** 既にあるものは2度作らない [#ycea07d3]
勉強したアルゴリズムを自分でプログラムしてみたいと思うの...
先輩からは既にあるプログラムと同じものは作ってはいけない...
当時は、IMSLという科学計算ライブラリを使っており、計算精...
IMSLを使うことは当然のことでした。
今で言うと新しくプログラムを作る前に、同じものがオープン...
調べてみるのと似てますね。
** 「ソフトウェア作法」 [#p2e4cc4b]
カーニハン氏、ブローガー氏の「ソフトウェア作法」（木村泉...
以来30年も読み継がれている名著です。
*** UNIXコマンドの作り方 [#e8e261b4]
「ソフトウェア作法」では、Ratforという言語を使ってUNIXの...
（cp, wc, 種々のフィルター、 sort, ed, roff, m4等）の簡...
トップダウンの構造化プログラミング手法を分かりやすく説明...
もう一つ「ソフトウェア作法」ではRatforの中に日常語を混在...
構造を分かりやすく組み立てています。
例）標準入力を標準出力にコピーする例(P13から引用)
#pre{{
while (getc(c)が入力の終わりでない)
call putc(c)
stop
}}
*** トップダウンの問題点 [#kd71fad1]
とても有益なトップダウンの構造化プログラミングにも弱点が...
それは一番下位のルーチンに設計のしわ寄せが来て、処理が複...
それでもトップダウンで設計することで得るプログラムの読み...
を考慮すると十分価値があると言えるのです。
*** ratforコンパイラー・コンパイラー [#z590d612]
巻末には、RatforからFortranへの翻訳プログラムも収録され、...
を体験できるように工夫されていました。当時は今のようにC言...
一般には普及していませんでした。
私もCP/MのFortranコンパイラーでRatforの翻訳プログラムを実...
を楽しみました。これが私が構文解析に興味をもった最初の出...
** 英語は苦手 [#iec2e28f]
現在もオープンソースのドキュメントは、ほとんどが英語で書...
私は英語が苦手なので、他の人のようにさくさくドキュメント...
しかしソフトウェアのドキュメントの場合、ソースコードなど...
中身を類推しながら、読み進めることで返ってそのプログラム...
*** UNIXの情報源は、ほとんどが英語 [#u0edf4f7]
UNIXに関わった時には、日本語の解説書などはまったくありま...
情報のほとんどがmanと英語の解説書という状況では、英語のド...
選択肢がありません。
*** 「The UNIX System」はすごい [#ted489e1]
「The UNIX System」は、shの開発者であるボーン氏が書いたUN...
これ一冊あれば、シェルスクリプトからUNIXコマンド、システ...
一通りのことが分かる優れものです。私は「The UNIX System」...
英語は苦手という意識から何とか英語との本とも付き合える自...
特にコンピュータ関連のドキュメントは、記述パターンが多く...
本も読めるようになると思います。
** 「Lions' Commentary on UNIX」 [#dc09adf3]
UNIXカーネルについて書かれた書籍はたくさんありますが、「L...
本物のUNIXソースとその解説から構成されている点が大きな特...
元々この本は、著者のJ. Lions氏がニューサウスウェールズ大...
「UNIXオペレーティングシステムコメンタリー」と呼ばれるノ...
経歴の本です。UNIXのカーネルがどのようにできたのかを知る...
*** simhでUNIXのソースを読む [#d815ba0f]
「The Computer History Simulation Project」http://simh.tr...
simhというシミュレータを使って過去の貴重なコンピュータを...
「Lions' Commentary on UNIX」で紹介されているPDP-11のsimh...
と共にディスクイメージが提供されているので、UNIXコマンド...
私の印象に残ったは、UNIXコマンドのソースが簡潔で美しいこ...
いるイニシャルブートのシーケンス通りに動いていることでし...
** yaccの勉強 [#c8d26d36]
UNIXのすごいところは、OSの他に多くのコマンドとコンパイラ...
提供していることです。なかでもコンパイラーを作るためのツ...
yaccは、使いこなしてみたいツールの一つでした。
「Introduction to Compiler Constrction with UNIX」は、yac...
Cのサブセットを例に字句解析、構文解析、インタプリタ、コン...
この本の例題を動かすことでコンパイラー・コンパイラーの使...
著書の一つです。
特にyaccで文法を記述しエラーが出たときの対応や、構文解析...
いるので、初心者にも安心してyaccが使えるようになっていま...
*** バイナリファイルの構文解析もできる [#dba9f8b7]
yaccは、字句解析を自前で作成することによってバイナリファ...
私は、CADのバイナリファイルの変換プログラムでyaccを使いま...
プログラムも簡単にできるので、デバッグやテストで重宝しま...
*** 逆転の発想（Light Speed Cの世界） [#o112f17c]
一般に構文解析のエラーリカバリ処理は難しく、大変な部分で...
箇所をエディタで表示し、すぐに修正できるようにし、コンパ...
高めたのが、MacintoshのコンパイラーLight Speed Cでした。...
時間のかかる処理が驚くほど改善されたのを今でも覚えていま...
** 「Javaによるパーサ構築技法」 [#h5afc320]
手続き型の言語の場合yaccで十分ですが、Prologのような論理...
よいのでしょうか。その答えが、「Javaによるパーサ構築技法...
前半の構文解析も分かりやすく、簡潔に説明されており、後半...
による論理構造の表現方法と単一化がポイントです。この推論...
論理型言語パーサーの作り方を習得できたと感じるとても不思...
** Antlr [#n31d6f3d]
最後に紹介するAntlrは、ちょっと変わったコンパイラー・コン...
yaccとは違い、LL(k)と呼ばれるトップダウンの構文解析を使っ...
ANTLRWorksというワークベンチを提供しており、ユーザの作っ...
簡単にできます。
言語の定義は、拡張BNFに似た形式となっていますので、はじめ...
また、サポートしている言語が、C、C++、Java、Python、C#、A...
ANTLRを解説した日本語の本はありませんが、私は「The Defini...
***ANTLRWorksを使う [#t60e49e0]
次の図が、ANTLRWorksを使ってユーザの作った文法（E1）に1+2...
このように文法を記述するだけで、テストが行え、文法のチェ...
&ref(ANTLRWorks.jpg);
*** 構文木のサポート [#t672ac12]
ANTLRの大きな特徴に、構文木をサポートしていることが挙げら...
構文木を使うことによって、構文解析後の変数テーブル、関数...
構文木を使うには、文法の最初にoptionsとtokensを追加します。
#pre{{
options{
output = AST;
ASTLabelType = CommonTree;
}
tokens{
ASSIGN; ALU_ADD; ALU_SUB; ALU_MUL; ALU_DIV;
}
}}
構文木の生成には、部分木を生成する^オペレータとノードを生...
次のstatementを例に簡単にオペレータの使い方を説明します。
#pre{{
statement
: expression NEWLINE!
| IDENTIFIER '=' expression NEWLINE
-> ^(ASSIGN IDENTIFIER expression)
| NEWLINE!
;
}}
NEWLINE!は、改行をノードに追加しません。
#pre{{
-> ^(ASSIGN IDENTIFIER expression)
}}
は、ASSIGNノードの下に、IDENTIFIERとexpressionからなる部...
*** Debuggerで動作を確認 [#hbe7d965]
ANTLRWorksのデバッガを使って、以下の入力をしたときの構文...
#pre{{
a=1
a+2*3
}}
&ref(debugger.jpg);
ASSIGNの下にa, 1がぶら下がる代入部分とALU_ADDの下にaとALU...
構文木は解析したプログラムを別の言語に変換するトランスレ...
** 自分だけの言語を作ってオリジナルのマシンを動かしてみる...
もう過去の技術だと思われていたコンパイラー・コンパイラー...
最後に、学研の「大人の科学」Vol.24の付録の4ビットマイコン...
例）１５秒カウンタプログラム
#pre{{
int a;
a = 15;
while (a > 0) {
out(a);
shts();
a = a - 1;
timer(10);
}
}}
生成されたアセンブラは、以下のようになります。
#pre{{
TIA f
TIY 0
AM
L1: TIY 0
TIA 0
AIA 1
M-
JUMP L2
TIY 0
MA
AO
CAL SHTS
TIY 0
TIA 1
M-
TIY 0
AM
TIA a
CAL TIMR
JUMP L1
L2: CAL ENDS
L3: JUMP L3
}}
*** アセンブラ [#y17216b6]
アセンブラから命令コードへの変換には、
http://www.musashinodenpa.com/misc/GMC4/
のアセンブラを使わせてもらいました。
*** シミュレータ [#ha97bc14]
GMC-4の元になった「FX-マイコン」のシミュレータが以下のURL...
http://homepage2.nifty.com/kocha_web/fxms/fxms.html
シミュレータを使うことによって、コンパイラーのバグ等問題...
とても助かりました。
&ref(simulator.jpg);
*** 実機での実行 [#y978c4fb]
生成された命令セットをGMC-4で動作しているときの画像です。
&ref(GMC-4.jpg);
ページ名:
SmartDoc
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
