ソフトウェアの最近のブログ記事

コンパイラ入門 C#で学ぶ理論と実践 (ソフトウェア実践講座)

posted with amazlet at 09.05.01

冨沢 高明
ソフトバンククリエイティブ
売り上げランキング: 352701

おすすめ度の平均:

ハイヒールで冬山登山するようなもの
クオリティの低い本
解答のない問題集

Amazon.co.jp で詳細を見る

はじめてコンパイラというものを実装しました。以下メモなど。

コンパイラを構成する要素

• スキャナ：一文字ずつif文で判定しながらトークン(単語)に分ける。
• パーサ：トークンの並びが文法的に正しいか判定する。
• シンボールテーブル：変数の一覧表。型をチェックする。
• コードジェネレータ：アセンブラコードを吐く。

Java実装

• 本ではC#だけど，Javaで読み替えながらコードを書いた。
• 自分の分かる範囲の知識で置き換えて書いたので，若干やってることが違うかも。
• 18章のポストモーテム(事後検証)は未実装。
• Primitive言語(Java実装)

所感

• この本は誤植も多いし突っ込みどころ満載だけど，やり遂げたら何とも言えない達成感がある。
• コンパイラを実際に実装してみると単なる文字列処理だってことが分かった。
• コンパイラの雰囲気は分かったけど，じゃあ有名なドラゴンブックとかには何が書いてあるんだろう？

今後読んでみたい本

• コンパイラ―原理・技法・ツール〈1〉 (Information & Computing)
• スモールコンパイラ の制作で学ぶ プログラムのしくみ
• Rubyで作る奇妙なプログラミング言語 ~Esoteric Language~
• やさしいインタープリタの作り方入門―オリジナルなインタープリタを作成する

コレの件。

自分で作ったコンパイラで，やっとプロンプトにHello Worldを出力できた。

まだHello Worldに必要な部分しか実装していないので，GW中に残りのコードジェネレータを完成させたい。

がんがるお！

SICP問題1.41をまじめに展開してみる。

doubleの定義：(define (double f) (lambda (x) (f (f x))))
incの定義：(define (inc x) (+ x 1))

(((double (double double)) inc) 5)
↓
(((double (lambda (x) (double (double x)))) inc) 5)
↓
(((lambda (x) (double (double (double (double x))))) inc) 5)
↓
((lambda (x) (double (double (double (double inc))))) 5)
↓
((lambda (x) (double (double (double (lambda (x) (inc (inc x))))))) 5)
↓
((lambda (x) (double (double (lambda (x) (inc (inc (inc (inc x)))))))) 5)
↓
((lambda (x) (double (lambda (x) (inc (inc (inc (inc (inc (inc (inc (inc x))))))))))) 5)
↓
((lambda (x) (lambda (x) (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc x)))))))))))))))))) 5)
↓
((lambda (x) (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc x))))))))))))))))) 5)
↓
((lambda (x) (+ x 16)) 5)

で，結局5+16=21になるというオチ。合ってるかなぁ？？

Rubyチップ実装に向けた取り組み，とかそんな感じ。

せめてRubyチップの入口くらいまでは行きたい。

• まずはRubyの勉強をする　←2〜3ヶ月くらい
• コレをRuby実装する　←2〜3ヶ月くらい
• 上記＋RHG1.9(S/Wライン)＋パタヘネ読書会(H/Wライン)＝Rubyチップが出来るはず！　←？ヶ月くらい

やっとパーサが出来た気がする。

頑張って3月中には全部完成させたい。

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
	
//ParserCls
public class ParserCls{
	ScannerCls scan = new ScannerCls();
	TokenCls token = new TokenCls();
	String s_work = "";
	String s_all = "";
	
	//コンストラクタ
	public ParserCls(){
		//ファイル読込み
		BufferedReader br;
		try{
			br = new BufferedReader(new FileReader("D:\\Java\\compiler\\Change.txt"));
			while((s_work = br.readLine()) != null){
				if(s_work.equals("")){
					continue;
				}
				s_all = s_all + s_work + " ";
			}
			br.close();
		}catch(FileNotFoundException e){
			System.out.println("ファイルが見つかりません");
		}catch(IOException e){
			System.out.println("致命的な入出力エラー");
		}
	}
	
	public void Entry(){
		this.strmsg("Parser");
		token = scan.getToken(token, s_all);
		this.program();
		this.xmatch("EOF");
		this.endmsg("Parser");
	}
	
	private void program(){
		this.xmatch("MODULE");
		this.xmatch("IDENT");
		this.xmatch("SEMICOLON");
		this.program1();
		this.xmatch("BEGIN");
		this.statlist();
		this.xmatch("END");
		this.xmatch("IDENT");
		this.xmatch("PERIOD");
	}
	
	private void program1(){
		if(this.match("BEGIN")){
			return;
		}
		else if(this.match("VAR")){
			this.decllist();
		}
		else{
			System.out.println("Parse Error! - program1");
			this.msg();
			this.stop();
		}
	}
	
	private void decllist(){
		this.xmatch("VAR");
		this.decllist1();
	}
	
	private void decllist1(){
		this.identlist();
		this.xmatch("COLON");
		this.type();
		this.xmatch("SEMICOLON");
		this.decllist2();
	}
	
	private void decllist2(){
		if(this.match("BEGIN")){
			return;
		}
		else if(this.match("IDENT")){
			this.decllist1();
		}
		else{
			System.out.println("Parse Error! - decllist2");
			this.msg();
			this.stop();
		}
	}
	
	private void statlist(){
		this.statement();
		this.statlist1();
	}
	
	private void statlist1(){
		if(this.match("END") || this.match("ELSE")){
			return;
		}
		else if(this.match("SEMICOLON")){
			this.xmatch("SEMICOLON");
			this.statement();
			this.statlist1();
		}
		else{
			System.out.println("Parse Error! - statlist1");
			this.msg();
			this.stop();
		}
	}
	
	private void identlist(){
		this.xmatch("IDENT");
		this.identlist1();
	}
	
	private void identlist1(){
		if(this.match("COLON")){
			return;
		}
		else if(this.match("COMMA")){
			this.xmatch("COMMA");
			this.xmatch("IDENT");
			this.identlist1();
		}
		else{
			System.out.println("Parse Error! - identlist1");
			this.msg();
			this.stop();
		}
	}
	
	private void type(){
		if(this.match("INTEGER")){
			this.xmatch("INTEGER");
		}
		else if(this.match("STRING")){
			this.xmatch("STRING");
		}
		else{
			System.out.println("Parse Error! - type");
			this.msg();
			this.stop();
		}
	}
	
	private void statement(){
		if(this.match("IDENT")){
			this.xmatch("IDENT");
			this.statement1();
		}
		else if(this.match("IF")){
			this.xmatch("IF");
			this.relation();
			this.xmatch("THEN");
			this.statlist();
			this.if1();
			this.xmatch("END");
		}
		else if(this.match("WHILE")){
			this.xmatch("WHILE");
			this.relation();
			this.xmatch("DO");
			this.statlist();
			this.xmatch("END");
		}
		else{
			System.out.println("Parse Error! - statement");
			this.msg();
			this.stop();
		}
	}
	
	private void statement1(){
		if(this.match("ASSIGN")){
			this.xmatch("ASSIGN");
			this.expression();
		}
		else if(this.match("OPEN")){
			this.xmatch("OPEN");
			this.literal();
			this.xmatch("CLOSE");
		}
		else{
			System.out.println("Parse Error! - statement1!");
			this.msg();
			this.stop();
		}
	}
	
	private void if1(){
		if(this.match("END")){
			return;
		}
		else if(this.match("ELSE")){
			this.xmatch("ELSE");
			this.statlist();
		}
		else{
			System.out.println("Parse Error! - if1!");
			this.msg();
			this.stop();
		}
	}
	
	private void relation(){
		this.expression();
		this.relop();
		this.expression();
	}
	
	private void expression(){
		this.expression1();
		this.term();
		this.expression2();
	}
	
	private void expression1(){
		if(this.match("OPEN") || this.match("IDENT") || this.match("NUMBER") || this.match("STR")){
			return;
		}
		else if(this.match("PLUS") || this.match("MINUS")){
			this.unaryop();
		}
		else{
			System.out.println("Parse Error! - expression1!");
			this.msg();
			this.stop();
		}
	}
	
	private void expression2(){
		if(this.match("SEMICOLON") || this.match("END") || this.match("NE") || this.match("LE")
		|| this.match("LT") || this.match("EQ") ||this.match("GT") || this.match("GE")
		|| this.match("THEN") ||this.match("DO") || this.match("CLOSE") || this.match("ELSE")){
			return;
		}
		else if(this.match("PLUS") || this.match("MINUS")){
			this.addop();
			this.expression3();
			this.term();
			this.expression2();
		}
		else{
			System.out.println("Parse Error! - expression2!");
			this.msg();
			this.stop();
		}
	}
	
	private void expression3(){
		if(this.match("OPEN") || this.match("IDENT") || this.match("NUMBER") || this.match("STR")){
			return;
		}
		else if(this.match("PLUS") || this.match("MINUS")){
			unaryop();
		}
		else{
			System.out.println("Parse Error! - expression3!");
			this.msg();
			this.stop();
		}
	}
	
	private void term(){
		this.factor();
		this.term1();
	}
	
	private void term1(){
		if(this.match("PLUS") || this.match("MINUS") || this.match("SEMICOLON") || this.match("END")
		|| this.match("NE") || this.match("LE") || this.match("LT") ||this.match("EQ") || this.match("GT")
		|| this.match("GE") || this.match("THEN") || this.match("DO") || this.match("CLOSE") || this.match("ELSE")){
			return;
		}
		else if(this.match("MULT") || this.match("DIV")){
			this.mulop();
			this.factor();
			this.term1();
		}
		else{
			System.out.println("Parse Error! - term1!");
			this.msg();
			this.stop();
		}
	}
	
	private void factor(){
		if(this.match("IDENT") || this.match("NUMBER") || this.match("STR")){
			this.literal();
		}
		else if(this.match("OPEN")){
			this.xmatch("OPEN");
			this.expression();
			this.xmatch("CLOSE");
		}
		else{
			System.out.println("Parse Error! - factor!");
			this.msg();
			this.stop();
		}
	}
	
	private void literal(){
		if(this.match("STR")){
			this.xmatch("STR");
		}
		else if(this.match("IDENT")){
			this.xmatch("IDENT");
		}
		else if(this.match("NUMBER")){
			this.xmatch("NUMBER");
		}
		else{
			System.out.println("Parse Error! - literal");
			this.msg();
			this.stop();
		}
	}
	
	private void relop(){
		if(this.match("NE")){
			this.xmatch("NE");
		}
		else if(this.match("LE")){
			this.xmatch("LE");
		}
		else if(this.match("LT")){
			this.xmatch("LT");
		}
		else if(this.match("EQ")){
			this.xmatch("EQ");
		}
		else if(this.match("GT")){
			this.xmatch("GT");
		}
		else if(this.match("GE")){
			this.xmatch("GE");
		}
		else{
			System.out.println("Parse Error! - relop");
			this.msg();
			this.stop();
		}
	}
	
	private void unaryop(){
		if(this.match("PLUS")){
			this.xmatch("PLUS");
		}
		else if(this.match("MINUS")){
			this.xmatch("MINUS");
		}
		else{
			System.out.println("Parse Error! - unaryop");
			this.msg();
			this.stop();
		}
	}
	
	private void addop(){
		if(this.match("PLUS")){
			this.xmatch("PLUS");
		}
		else if(this.match("MINUS")){
			this.xmatch("MINUS");
		}
		else{
			System.out.println("Parse Error! - addop");
			this.msg();
			this.stop();
		}
	}
	
	private void mulop(){
		if(this.match("MULT")){
			this.xmatch("MULT");
		}
		else if(this.match("DIV")){
			this.xmatch("DIV");
		}
		else{
			System.out.println("Parse Error! - mulop");
			this.msg();
			this.stop();
		}
	}
	
	private void xmatch(String s){
		msg();
		if(s.equals(token.def)){
			this.nextToken();
		}
		else{
			System.out.println("Parse Error! - xmatch");
			this.msg();
			this.stop();
		}
	}
	
	private boolean match(String s){
		if(s.equals(token.def)){
			return true;
		}
		else{
			return false;
		}
	}
	
	private void nextToken(){
		if(token.def != "EOF"){
			s_all = s_all.substring(token.str.length());
			scan.getToken(token,s_all);
			while(token.def == "WHITESPACE"){
				s_all = s_all.substring(token.str.length());
				scan.getToken(token,s_all);
			}
		}
	}
	
	//テスト用メソッド
	private void strmsg(String msg){
		System.out.println("-------------------- " + msg + " started! --------------------");
	}
	
	private void endmsg(String msg){
		System.out.println("-------------------- " + msg + " ended! ----------------------");
	}
	
	private void msg(){
		System.out.println("Token.str=" + token.str + " Token.def=" + token.def);
	}
	
	private void stop(){
		System.exit(0);
	}
}