Compiler: Assignment 2
Seung-Hoon Na May 27, 2018
1 Decaf에 대한 syntax-directed translation
Decaf 은toy 객체지향 언어로, 강 타입, 상속성 및 캡슐화를 지원 등 특징을 가지며 c++/java와 많은 유사성이 있는 언어이다.
본 과제에서는Decaf으로 작성된 소스코드를 TAC (Three address code) 중간 코드로 번역하는 Syntax-directed translation을 구현하는 것으로, 핵심 구현 내용은1) Decaf 어휘 분석기, 2) Decaf 구문분석기, 3) TAC 중간 코드 생성기의 세 parts로 나뉜다. 여기서 Decaf 구문분석기는 Assignment 1의 LALR 구문분석 기를 이용하여 구현되어야 한다.
아래 절부터Decaf의 핵심 및 예제 코드를 소개한다.
Decaf문법과 관련된 보다 상세한 내용은 다음 URL을 참조하도록 하라.
https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/
handouts/030%20Decaf%20Specification.pdf
1.1 Decaf: 문법과 어휘
1.1.1 Decaf: Grammar
Decaf의 문법을 extended BNF형식으로 기술하면 다음과 같다.
P rogram ::= Decl+
Decl ::= V ariableDecl | F unctionDecl | ClassDecl | Interf aceDecl V ariableDecl ::= V ariable ;
V ariable ::= T ype id
T ype ::= int | double | bool | string | id | T ype []
F unctionDecl ::= T ype id ( F ormals ) StmtBlock | void id (F ormals ) StmtBlock
F ormals ::= V ariable+,|
ClassDecl ::= class id hextends idi himplements id+,i { F ield∗} F ield ::= V ariableDecl | F unctionDecl
Interf aceDecl ::= interface id { P rototype∗ }
P roptotype ::= T ype id ( F ormals ) ; | void id ( F ormals ) ; StmtBlock ::= { V ariableDecl∗ Stmt∗ }
Stmt ::= hExpri ; | If Stmt | W hileStmt | F orStmt |
BreakStmt | ReturnStmt | P rintStmt | StmtBlock If Stmt ::= if ( Expr ) Stmt helse Stmti
W hileStmt ::= while ( Expr ) Stmt
F orStmt ::= for ( hExpri ; Expr ; hExpri ) Stmt ReturnStmt ::= return hExpri ;
BreakStmt ::= break ;
P rintStmt ::= Print ( Expr+, ) ;
Expr ::= LV alue = Expr | Constant | LV alue | this | Call | ( Expr ) | Expr + Expr | Expr - Expr | Expr * Expr | Expr / Expr | Expr % Expr | - Expr | Expr < Expr | Expr <= Expr | Expr > Expr | >= Expr | Expr == Expr | Expr != Expr | Expr && Expr | || Expr | ! Expr | ReadInteger ( ) | ReadLine ( )| new id | NewArray ( Expr , T ype ) LV alue ::= id | Expr . id | Expr [ Expr ]
Call ::= id ( Actuals ) | Expr . id ( Actuals ) Actuals ::= Expr+,|
Constant ::= intConstant | doubleConstant | boolConstant | stringConstant| null
다음은 위의BNF 문법에서 사용된 meta-notation들에 대한 설명이다.
1.1.2 Decaf: Tokens
Decaf의 토큰들의 종류는 다음과 같이 예약어, 식별자, 상수, 연산자, 구분자로 나뉜다.
• 예약어 (keywords): Decaf의 예약어는 다음과 같다.
void int double bool string class interface null this extends implements for while if else return break new true false NewArray Print ReadInteger ReadLine
여기서 NewArray, Print, ReadInteger, ReadLine은 미리 지정된 Decaf 내장함수의 이름으로 배열생성 및 입출력 기능을 수행한다.
• 식별자 (identifies): 식별자는 교과서 138페이지의 내용과 동일하며, letter(대 소문자), digit(숫자), underbar로 구성된 sequence이며, 대소문자를 구분하 고, 첫글자는 letter 또는 underbar로 시작한다.편의를 위해 식별자의 최대길 이는31로 둘 수도 있다 (그렇게 하지 않아도 무방함).
예를 들어, if는 예약어이며, IF나 iF는 식별자이다. binky와 Binky는 서로 다른 식별자이다.
• 상수 (constants): Boolean 상수는 true와 false의 2개 예약어로 구성된다.
정수형 상수는 교과서139페이지의 그림 4-4와 동일하게 10진수로 기술된다 (16진수는 본 과제에서 다루지 않아도 된다). 실수형 상수는 교과서 139페이 지의 그림4-5와 동일한 상태도에 따라 정의된다. (단, 본 과제에서는 실수형 상수는 구문 분석 테스트까지는 사용하고, 중간코드 생성단계에서는 사용하 지 않는다.) 문자열 상수의 경우 double quote (큰 따옴표)로 둘러싸인 임의의 문자열(new line 및 double quote를 제외)을 가리킨다 (공백도 포함). 문자열 상수는single line에서 정의가 되어야 하며 다중 lines에 걸쳐 있으면 안된다.
단순성을 위해, 문자열 상수에서 Escape Character를 다루지 않는다.
다음은 문자열 상수의 예이다.
"Hello." "Hello decaf" "abc def test"
• 연산자 (operators): 연산자들은 다음과 같다.
+ - * / %< <= > >= = == != && || !
• 구문자 (punctuation characters): 구분자들은 다음과 같다.
; , . [ ] ( ){ }
1.2 Decaf: Overview
1.2.1 Scope
Java와 마찬가지로 Decaf은 여러 단계에 걸쳐 scoping을 지원하며, top-level의 경 우 global scope, 각 class의 경우 class scope, 각 함수는 parameter부분과 body 부분 각각에 대해 별도의local scope을 갖는다.
다음은 식별자와 관련된scoping 규칙들이다.
1. 가시성 (visibility): 변수는 한번 선언되면 해당 scope내에서 visible, 즉 참조 가능해야 한다.
2. 유일성 (uniqueness): 하나의 scope내의 identifiers들은 유일해야 한다.
3. 변수 새도우 (variable shadowing): Nested scope상에서, inner scope은 outer scope을 가린다 (shadow). 예를 들어, function안에서 정의된 local 변수는, 동일한 이름을 갖는global variable를 참조하지 않고, 별도의 저장소를 독립 적으로 갖는다.
1.2.2 Types
Decaf의 types은 primitive type와 타입 생성자를 통한 named type으로 나뉜다.
1. Primitive type:
void int double bool string 2. Namedtype:
1) 객체/인터페이스 타입: class, interface의 생성식을 통해 프로그래머가 정의한 타입
2) 배열 (arrays): non-void type의 n개의 elements로 구성된 타입.
1.2.3 Variables
변수(Variables)는 non-void type으로 선언되어야 한다. 변수의 scope은 선언된 위치에 따라 크게 global scope, class scope, local scope으로 나뉠 수 있다.
1. Global scope: 모든 함수 외부에서 선언된 Global 변수의 scope
2. Class scope: 클래스 안에 있으나 특정 함수 외부에서 선언된 class 멤버 변수의scope
3. Local scope: 함수의 파라미터 또는 body에 선언된 지역 변수의 scope
1.2.4 Arrays
배열은 크기 정보가 없이 선언되며, 필요할 때 NewArray함수를 통해 heap상에서 동적으로 메모리 할당이 된다. 배열은 reference로 구현된다 (automatically deref- erenced pointers).
1. 배열 allocation: NewArray(N, type)을 통해 N개로 구성된 동일한 types 을 갖는 배열을 생성한다. N은 양수이다.
2. 배열 size: a.length()는 배열 a의 길이를 리턴한다.
3. 배열 indexing: 크기가 n인 배열의 index는 0부터 n − 1까지의 정수이다.
4. 배열 parameter: 배열은 임의의 함수에서 parameter로 전달되거나 return 타입이 될수도 있다.
5. 배열 copy: 배열이 다른 배열로 assign될때는 reference만 copy된다.
1.2.5 Strings
String은 reference로 구현된다.
1. String 입력: ReadLine함수는 사용자로부터 문자열을 입력받아 String con- stant를 만들어 리턴해주며, 이때 newline 문자는 포함하지 않는다.
2. String comparison: 문자열 비교 (==, !=)는 내용 비교 연산자로, 두 문자 열들의character sequences 비교한다.
3. String copy: 문자열이 다른 문자열로 assign될때는 reference만 copy된다.
1.2.6 Functions
1. 함수 scope: class밖에 선언되는 경우 global scope을 갖고, class안애 선언 되면 해당class scope을 갖는다.
2. 함수 오버로딩(overloading): 오버로딩은 허용되지 않는다.
3. 함수 return: void형의 return type을 제외한 모든 함수는, 해당 type으로 returnstatement가 존재해야 한다.
1.2.7 Classes
Field는 member variable또는 member function을 가리키고, 클래서 선언이란 곧 fields의 리스트이다. 다시 말해, class는 member variables 과 member functions 구성되는named type이다.
1. Encapsulation: 본 과제에서는 별도의 접근 제한없이, class의 모든 mem- ber variables과 member functions는 public이라고 가정한다.
1.2.8 Objects
Object는 임의의 named type(class또는 interface)의 instance로, 해당 named type 의 변수이다. 모든 객체는 heap 메모리상에서 new 함수를 통해 동적으로 allocated 된다.
1.2.9 Inheritance
Decaf은 상속을 위해 java에서 처럼 다음 구문을 따른다.
A extends B
여기서 B는 베이스 클래스 (base class)를, A는 파생 클래스 (derived class)를 의미한다. 파생 클래스에서는 베이스 클래스의 member functions을 오버라이딩 (overriding)하거나, 베이스 클래스의 fields에 더해 임의의 field (member vari- able/function)을 추가할 수 있다.
1.2.10 Interface
Java에서 처럼 interface 선언은 function prototype들로 구성된다. 주어진 in- terface를 implement한 class는 해당 interface에서 정의된 function prototype의 형식에 맞춰functions 들을 구현해야 한다.
1.3 Decaf: Example codes
다음은Decaf코드의 예들이다.
1. reference: https://github.com/manuzhang/decaf compiler 2. reference2: https://github.com/rupss/Decaf-compiler-CS143 3. reference3: https://github.com/mariobecerra/decaf compiler
1.3.1 Example codes: 문법 테스트
• helloworld.decaf: Hello world 메시지를 출력 void main() {
Print("hello world");
}
• array test.decaf: 배열 생성 및 assign 테스트 int Binky(int a, int[] b, int[] c)
{
return b[c[0]];
}
void main() {
int[] c;
int [][]d;
d = NewArray(5, int[]);
d[0] = NewArray(12, int);
c = NewArray(10, int);
c[0] = 4 + 5 * 3 / 4 % 2;
d[0][c[0]] = 55;
Print(c[0], " ", 2 * Binky(100, d[0], c));
}
• function test.decaf: 함수 call 테스트 void main() {
int c;
string s;
s = "hello";
c = test(4, 5);
Print(c);
Print(s);
}
int test(int a, int b) { return a + b;
}
• for test.decaf: 반복문 for 테스트 int i;
i = 0;
for (; i <10;) { Print(i);
i = i + 1;
}
Print("done\n");
}
• for test2.decaf: 반복문 for 테스트2 int main()
{
int i;
int j;
for (i = 2; i < 7; i = i + 1) { for (j = 2; j < 6; j = j + 1) {
if (i * j == 10) break;
Print(i, j, "\n");
} }
Print("done");
}
• if test.decaf: if 조건문 테스트 int main() {
if ( 1 == 1) { Print(1);
} else if (2 == 1) { Print(2);
} else { Print(3);
}
if ( 1 == 2) { Print(1);
} else if (2 == 2) { Print(2);
} else { Print(3);
}
if ( 1 == 2) { Print(1);
} else if (2 == 1) { Print(2);
} else { Print(3);
} }
• while test.decaf: while 조건문 테스트
void main() { int a;
a = 0;
while (a != 10) { Print(a, " ");
a = a + 1;
}
Print("\na now = ", a, " which is ");
if (a % 2 == 0) Print("even");
else
Print("odd");
a = 0;
while (true) break;
while (a != 10) { Print(a, " ");
a = a + 1;
if (a == 7) Print(a);
else break;
} a = 0;
while (a != 10) { Print(a, " ");
a = a + 1;
if (a > 7) if (a == 8)
if (a == 9) break;
} }
• class simple.decaf: class관련 테스트 class Cow {
int height;
int weight;
void Init(int w, int h) {
weight = w;
height = h;
}
void Moo() {
Print ( this.height, " ", this.weight, "\n" );
} }
void main() {
Cow betsy;
betsy = new Cow;
betsy.Init(100, 122);
betsy.Moo();
}
• class inheritance.decaf: class 상속 테스트 class Animal {
int height;
Animal mother;
void InitAnimal(int h, Animal mom) { height = h;
mother = mom;
}
int GetHeight() { return height;
}
Animal GetMom() { return mother;
} }
class Cow extends Animal { bool isSpotted;
void InitCow(int h, Animal m, bool spot) { isSpotted = spot;
InitAnimal(h,m);
}
bool IsSpottedCow() { return isSpotted;
} }
void main() { Cow betsy;
Animal b;
betsy = new Cow;
betsy.InitCow(5, null, true);
b = betsy;
b.GetMom();
}
• interface test.decaf: interface사용 예 interface Colorable {
Color GetColor();
void SetColor(Color c);
}
class Color {
void SetRGB(int red, int green, int blue) { this.red = red;
this.green = green;
this.blue = blue;
}
int red;
int green;
int blue;
}
class Shape implements Colorable { Color GetColor() { return myColor; } void SetColor(Color c) { myColor = c;}
Color myColor;
}
class Rectangle extends Shape { }
void main() { Colorable s;
Color green;
green = new Color;
green.SetRGB(0, 0, 255);
s = new Rectangle;
s.SetColor(green);
}
• class inheritance2.decaf: class상속 사용 다른 예 void Grow(int a) {
Print("mmm... veggies!\n");
}
class Seeds {
int size;
}
class Vegetable { int weight;
int color;
void Eat(Vegetable veg) {
Seeds[] s;
int [][]w;
color = 5 % 2;
Print("Yum! ", color, "\n");
veg.Grow(s, w);
return;
}
void Grow(Seeds []seeds, int [][]water) {
Print("Grow, little vegetables, grow!\n");
Eat(this);
} }
class Squash extends Vegetable {
void Grow(Seeds []seeds, int [][]water) {
Print("But I don't like squash\n");
Print(10 * 5);
} }
void main() {
Vegetable []veggies;
veggies = NewArray(2, Vegetable);
veggies[0] = new Squash;
veggies[1] = new Vegetable;
Grow(10);
veggies[1].Eat(veggies[0]);
}
1.3.2 Example codes: 자료구조 및 알고리즘
• queue.decaf: queue구현 class QueueItem {
int data;
QueueItem next;
QueueItem prev;
void Init(int data, QueueItem next, QueueItem prev) { this.data = data;
this.next = next;
next.prev = this;
this.prev = prev;
prev.next = this;
}
int GetData() { return this.data;
}
QueueItem GetNext() { return next;}
QueueItem GetPrev() { return prev;}
void SetNext(QueueItem n) { next = n;}
void SetPrev(QueueItem p) { prev = p;}
}
class Queue { QueueItem head;
void Init() {
this.head = new QueueItem;
this.head.Init(0, this.head, this.head);
}
void EnQueue(int i) { QueueItem temp;
temp = new QueueItem;
temp.Init(i, this.head.GetNext(), this.head);
}
int DeQueue() { int val;
if (this.head.GetPrev() == this.head) { Print("Queue Is Empty");
return 0;
} else {
QueueItem temp;
temp = this.head.GetPrev();
val = temp.GetData();
temp.GetPrev().SetNext(temp.GetNext());
temp.GetNext().SetPrev(temp.GetPrev());
}
return val;
} }
void main() { Queue q;
int i;
q = new Queue;
q.Init();
for (i = 0; i != 10; i = i + 1) q.EnQueue(i);
for (i = 0; i != 4; i = i + 1) Print(q.DeQueue(), " ");
Print("\n");
for (i = 0; i != 10; i = i + 1) q.EnQueue(i);
for (i = 0; i != 17; i = i +1) Print(q.DeQueue(), " ");
Print("\n");
}
• stack.decaf: stack 구현 class Stack {
int sp;
int[] elems;
void Init() {
elems = NewArray(100, int);
sp = 0;
Push(3);
}
void Push(int i) { elems[sp] = i;
sp = sp + 1;
}
int Pop() { int val;
val = elems[sp - 1];
sp = sp - 1;
return val;
}
int NumElems() { return sp;
} }
void main() { Stack s;
s = new Stack;
s.Init();
s.Push(3);
s.Push(7);
s.Push(4);
Print (s.NumElems(), " ", s.Pop(), " ", s.Pop(), " ", s.Pop(),
" ", s.NumElems());
}
• factorial.decaf: factorial 함수 (recursive function 테스트) int factorial(int n)
{
if (n <=1 ) return 1;
return n*factorial(n-1);
}
void main() {
int n;
for (n = 1; n <= 15; n = n + 1)
Print("Factorial(", n , ") = ", factorial(n), "\n");
}
• gcd.decaf: gcd 함수 (recursive function 테스트) int a = 10;
int b = 20;
int gcd(int a, int b) { if (b == 0) { return(a); }
else { return( gcd(b, a % b) ); } }
void main() { int x, y, z;
x = a;
y = b;
z = gcd(x, y);
Print("print_gcd", z);
}
• qsort.decaf: quick sort 클래스 (recursive function 테스트) class QuickSort {
int[] list;
void displayList(int start, int len) { int j;
Print("List:\n");
for (j = start; j < start + len; j = j + 1) {
Print(list[j], " ");
}
Print("\n");
}
void initList(int size) { int i;
list = NewArray(size, int);
for (i = 0; i < size; i = i + 1) { list[i] = (i * 2382983) % 100;
} }
void swap(int leftPtr, int rightPtr) { int temp;
temp = list[leftPtr];
list[leftPtr] = list[rightPtr];
list[rightPtr] = temp;
}
void quickSort(int left, int right) { if (right - left <= 0) {
return;
} else {
int pivot, part;
pivot = list[right];
part = partition(left, right, pivot);
quickSort(left, part - 1);
quickSort(part+1, right);
} }
int partition(int left, int right, int pivot) { int leftPtr;
int rightPtr;
leftPtr = left-1;
rightPtr = right;
while (true) { while (true) {
leftPtr = leftPtr + 1;
if (list[leftPtr] >= pivot) { break;
}
}
while (true) {
if (rightPtr <= 0) { break;
}
rightPtr = rightPtr - 1;
if (list[rightPtr] <= pivot) { break;
} }
if (leftPtr >= rightPtr) { break;
} else {
swap(leftPtr,rightPtr);
} }
swap(leftPtr, right);
return(leftPtr);
} }
int main() { int size;
size = 100;
QuickSort qs;
qs = new QuickSort;
qs.initList(size);
qs.displayList(0,size);
qs.quickSort(0,size-1);
Print("After sorting:\n");
qs.displayList(0,size);
}
• matrix.decaf: 행렬 연산 class Matrix {
void Init() {}
void Set(int x, int y, int value) {}
int Get(int x, int y) {}
void PrintMatrix() { int i;
int j;
for (i = 0; i < 10; i = i + 1) { for (j = 0; j < 10; j = j + 1)
Print(Get(i,j), "\t");
Print("\n");
} }
void SeedMatrix() { int i;
int j;
for (i = 0; i < 5; i = i + 1) for (j = 0; j < 5; j = j + 1)
Set(i,j, i+j);
Set(2,3,4);
Set(4,6,2);
Set(2,3,5);
Set(0,0,1);
Set(1,6,3);
Set(7,7,7);
} }
class DenseMatrix extends Matrix { int[][] m;
void Init() { int i;
int j;
m = NewArray(10, int[]);
for (i = 0; i < 10; i = i +1) m[i] = NewArray(10, int);
for (i = 0; i < 10; i = i + 1) for (j = 0; j < 10; j = j + 1)
m[i][j] = 0;
}
void Set(int x, int y, int value) { m[x][y] = value;
}
int Get(int x, int y) { return m[x][y];
} }
class SparseItem { int data;
int y;
SparseItem next;
void Init(int d, int y, SparseItem next) { this.data = d;
this.y = y;
this.next = next;
}
SparseItem GetNext() { return next;}
int GetY() { return y;}
int GetData() { return data;}
void SetData(int val) { data = val;}
}
class SparseMatrix extends Matrix { SparseItem[] m;
void Init() { int i;
m = NewArray(10, SparseItem);
for (i = 0; i < 10; i = i + 1) m[i] = null;
}
SparseItem Find(int x, int y) { SparseItem elem;
elem = m[x];
while (elem != null) { if (elem.GetY() == y) { return elem;
}
elem = elem.GetNext();
}
return null;
}
void Set(int x, int y, int value) { SparseItem elem;
elem = Find(x,y);
if (elem != null) { elem.SetData(value);
} else {
elem = new SparseItem;
elem.Init(value, y, m[x]);
m[x] = elem;
} }
int Get(int x, int y) { SparseItem elem;
elem = Find(x,y);
if (elem != null) { return elem.GetData();
} else {
return 0;
} } }
void main() { Matrix m;
Print("Dense Rep \n");
m = new DenseMatrix;
m.Init();
m.SeedMatrix();
m.PrintMatrix();
Print("Sparse Rep \n");
m = new SparseMatrix;
m.Init();
m.SeedMatrix();
m.PrintMatrix();
}
• blackjack.decaf: Blackjack 게임 class Random {
int seed;
void Init(int seedVal) { seed = seedVal;
}
int GenRandom() {
seed = (15625 * (seed % 10000) + 22221) % 65536;
return seed;
}
int RndInt(int max) {
return (GenRandom() % max);
} }
Random gRnd;
class Deck { int current;
int[] cards;
void Init() {
cards = NewArray(52, int);
}
void Shuffle() {
for (current = 0; current < 52; current = current + 1) { cards[current] = (current + 1) % 13;
}
gRnd = new Random;
while (current > 0) { int r;
int temp;
r = gRnd.RndInt(current);
current = current - 1;
temp = cards[current];
cards[current] = cards[r];
cards[r] = temp;
} }
int GetCard() { int result;
if (current >= 52) return 0;
result = cards[current];
current = current + 1;
return result;
} }
class BJDeck { Deck[] decks;
int numdealt;
void Init() { int i;
decks = NewArray(8, Deck);
for (i = 0; i < 8; i = i + 1) { decks[i] = new Deck;
decks[i].Init();
} }
int DealCard() { int c;
c = 0;
if (numdealt >= 8*52) return 11;
gRnd = new Random;
while (c == 0) { int d;
d = gRnd.RndInt(8);
c = decks[d].GetCard();
}
if (c > 10) c = 10;
else if (c == 1) c = 11;
numdealt = numdealt + 1;
return c;
}
void Shuffle() { int i;
Print("Shuffling...");
for (i = 0; i < 8; i = i + 1) decks[i].Shuffle();
numdealt = 0;
Print("done.\n");
}
int NumCardsRemaining() {
return 8*52 - numdealt;
} }
class Player { int total;
int aces;
int numcards;
int bet;
int money;
string name;
void Init(int num) { money = 1000;
Print("What is the name of player #", num, "? ");
name = ReadLine();
}
void PrintName() { Print(name);
}
void Hit(BJDeck deck) { int card;
card = deck.DealCard();
Print(name, " was dealt a ", card, ".\n");
total = total + card;
numcards = numcards + 1;
if (card == 11) aces = aces + 1;
while ((total > 21) && (aces > 0)) { total = total - 10;
aces = aces - 1;
} }
bool DoubleDown(BJDeck deck) { int result;
if ((total != 10) && (total != 11)) return false;
if (GetYesOrNo("Would you like to double down?")) { bet = bet * 2;
Hit(deck);
Print(name, ", your total is ", total, ".\n");
return true;
}
return false;
}
void TakeTurn(BJDeck deck) { bool stillGoing;
Print("\n", name, "'s turn.\n");
total = 0;
aces = 0;
numcards = 0;
Hit(deck);
Hit(deck);
if (!DoubleDown(deck)) { stillGoing = true;
while (total <= 21 && stillGoing) {
Print(name, ", your total is ", total, ".\n");
stillGoing = GetYesOrNo("Would you like a hit?");
if (stillGoing) Hit(deck);
} }
if (total > 21) Print(name, " busts with the big ", total,
"!\n");
else Print(name, " stays at ", total, ".\n");
}
bool HasMoney() { return money > 0; } void PrintMoney() {
Print(name, ", you have $", money, ".\n");
}
void PlaceBet() { bet = 0;
PrintMoney();
while ((bet <= 0) || (bet > money)) {
Print("How much would you like to bet? ");
bet = ReadInteger();
} }
int GetTotal() { return total;}
void Resolve(int dealer) { int win; int lose;
win = 0; lose = 0;
if ((total == 21) && (numcards == 2)) win = 2;
else if (total > 21) lose = 1;
else if (dealer > 21) win = 1;
else if (total > dealer) win = 1;
else if (dealer > total) lose = 1;
if (win >= 1) Print(name, ", you won $", bet, ".\n");
else if (lose >= 1) Print(name, ", you lost $", bet, ".\n");
else Print(name, ", you push!\n");
win = win * bet;
lose = lose * bet;
money = money + win - lose;
} }
class Dealer extends Player { void Init(int id) {
total = 0;
aces = 0;
numcards = 0;
name = "Dealer";
}
void TakeTurn(BJDeck deck) { Print("\n", name, "'s turn.\n");
while (total <= 16) { Hit(deck);
}
if (total > 21) Print(name, " busts with the big ", total,
"!\n");
else Print(name, " stays at ", total, ".\n");
} }
class House { Player[] players;
Player dealer;
BJDeck deck;
void SetupGame() {
Print("\nWelcome to CS143 BlackJack!\n");
Print("---\n");
gRnd = new Random;
Print("Please enter a random number seed: ");
gRnd.Init(ReadInteger());
deck = new BJDeck;
dealer = new Dealer;
deck.Init();
deck.Shuffle();
}
void SetupPlayers() { int i;
int numPlayers;
Print("How many players do we have today? ");
numPlayers = ReadInteger();
players = NewArray(numPlayers, Player);
for (i = 0; i < players.length(); i = i + 1) { players[i] = new Player;
players[i].Init(i+1);
} }
void TakeAllBets() { int i;
Print("\nFirst, let's take bets.\n");
for (i = 0; i < players.length(); i = i + 1)
if (players[i].HasMoney()) players[i].PlaceBet();
}
void TakeAllTurns() { int i;
for (i = 0; i < players.length(); i = i + 1)
if (players[i].HasMoney()) players[i].TakeTurn(deck);
}
void ResolveAllPlayers() { int i;
Print("\nTime to resolve bets.\n");
for (i = 0; i < players.length(); i = i + 1) if (players[i].HasMoney())
players[i].Resolve(dealer.GetTotal());
}
void PrintAllMoney() {
int i;
for (i = 0; i < players.length(); i = i + 1) players[i].PrintMoney();
}
void PlayOneGame() {
if (deck.NumCardsRemaining() < 26) deck.Shuffle();
TakeAllBets();
Print("\nDealer starts. ");
dealer.Init(0);
dealer.Hit(deck);
TakeAllTurns();
dealer.TakeTurn(deck);
ResolveAllPlayers();
} }
bool GetYesOrNo(string prompt) {
string answer;
Print(prompt, " (y/n) ");
answer = ReadLine();
return (answer == "y" || answer == "Y");
}
void main() { bool keepPlaying;
House house;
keepPlaying = true;
house = new House;
house.SetupGame();
house.SetupPlayers();
while (keepPlaying) { house.PlayOneGame();
keepPlaying = GetYesOrNo("\nDo you want to play another hand?");
}
house.PrintAllMoney();
Print("Thank you for playing...come again soon.\n");
Print("\nCS143 BlackJack Copyright (c) 1999 by Peter Mork.\n");
Print("(2001 mods by jdz)\n");
}
1.4 Symbol Table과 Constant Table
Symbol table (또는 environments)은 식별자 (identifier)에 해당되는 의미정보 (type, offset, 기타 속성)을 mapping한 테이블이다. Decaf은 nested scope을 허 용하기 때문에 동일한 식별자가 다른scope상에 두번 이상 참조될때 애매성이 발 생한다. 이러한 애매성을 효과적으로 해결하기 위해 하나의 large symbol table이 아닌, multiple symbol tables로 나누고 scopes들간의 변수 shadowing을 반영할 수 있도록symbol tables들을 계층적으로 구조화시킨다.
즉, scope의 계층 구조(hierarchy)를 반영하기 위해, 각 scope마다 하나의 sym- bol table을 두고 (symbol table per scope), 이들을 계층적으로 연결되는 hier- archical symbol tables형식으로 구현한다.
다음은Symbol table의 구현을 위한 클래스 구조도의 예이다 (java).
• SymbolTable: SymbolTable 클래스는 tree형태의 계층 구조상의 하나의 노드 에 대응되며, children은 자식 Symbol tables의 리스트를, parent는 부모 Symbol table을 참조한다.
class SymbolTable { public String name;
public HashMap<String,Symbol> symbols;
public LinkedList<SymbolTable> children;
public SymbolTable parent;
public SymbolTable(String name_){
name = name_;
symbols = new HashMap<String,Symbol>();
} ...
}
• Function, Class, Interface: Decaf의 식별자는 선언된 위치에 따라, global scope, class scope, interface scope, function scope, local scope 등을 갖는다. Func- tion scope, class scope, interface scope의 경우 symbol table상내에 특수한 독자 적인 자료구조나 함수를 포함할 필요가 있다. 이를 위해, SymbolTable의 파생클래 스로 Function, Class, Interface를 정의한다.
class Function extends SymbolTable {
public LinkedList<Symbol> params; //symbols중에서 parameter에 해당되는 symbol들의 모임
}
class Class extends SymbolTable {
public LinkedList<Symbol> members; //symbols중에서 member variables에 해당되는 symbol들의 모임
public LinkedList<Function> methods; //symbols중에서 member function에 해당되는 symbol의 reftable 들의 모임
...
}
class Interface extends SymbolTable {
public LinkedList<Function> methods; //symbols중에서 member function (추상형 function)에 해당되는 symbol의 reftable 들의 모임
...
}
• Symbol: Symbol은 해당 문자열, type정보, offset 등 정보를 포함한다. 아 래 구현에서는 symbol의 빠른 type참조를 위해 symtype을 별도로 정의하였으나, type만으로도 충분하다. reftable은 symbol이 1) 특정한 named type의 instance (object)일때 본래 type에 해당하는 SymbolTable, 2) class, interface, function type의 경우 해당 symbol의 named type의 Symbole Table을 참조한다.
public enum SymbolType {
STRING, INT, DOUBLE, BOOL, CLASS, INTERFACE, FUNCTION, NAMED }
public enum SymbolAttribute { PARAM, LOCAL
}
class Symbol {
public String name;
public String type; //int, double, bool ... or a class name public SymbolType symtype;
public SymbolTable reftable; // reference table public SymbolAttribute att; //attributes
public int offset;
public Symbol(String name_, String type_name_){
...
}
public Symbol(String name_, SymbolType type_){
...
} }
• Constant table: 한편, Symbol table외에 코드상에서 나타난 모든 상수 literal들은 Constant table에 저장한다. 다음은 Constant table을 위한 클래스 들이다.
class ConstantTable {
public HashMap<String,Constant> constants;
public ConstantTable(String name_){
constants = new HashMap<String,Constant>();
} ...
}
public enum ConstantType {
STRING, INT, DOUBLE, BOOL, NULL }
class Constant {
public String value; //constant string -- the value expressed as an ASCII string
public String type; //intConstant, doubleConstant, stringConstant,
public ConstantType const_type;
public int address;
}
1.4.1 Symbol Table: Examples
Hierarchal symbol tables의 예를 위해 다음 Decaf 코드를 살펴보자.
• symboltable test.decaf: Symbol table테스트 코드 int x, y;
class A { int a, b;
int foo(int a, int b){
int z;
z = a + b;
return z;
} } x = 10;
y = 20;
A a;
a = new A;
{
int c = a.foo(x,y)
}
위의 예제 코드에서 나타난 식별자들에 대한 계층형 symbol tables의 구조의 핵심적인 내용만 기술하면 다음과 같다.
1.5 TAC (Three Address Code) 중간코드
본 과제에서 중간코드 표현으로 3주소 코드 - TAC (Three Address Code)를 사 용한다. 단순성을 위해, 본 과제에서는 Decaf의 double자료형은 사용하지 않는다.
따라서 모든 자료형(주소가 값)은 4byte로 표현된다 (boolean의 경우에도 4byte 공간을 차지한다고 가정하자.)
편의상 생성된 TAC코드는 c/c++에서 동작될 수 있도록 하고, TAC코드는 다음과 같이inline 함수 또는 Macro 함수 형태로 구현하라.
#define _M(x) (x >= 0? *(STACK + x) : *(HEAP + x))
#define _pM(x) (x >= 0? (STACK + x) : (HEAP + x)) inline void ADD(int A,int B,int C){
*_pM(A) = _M(B) + _M(C);
}
inline void SUB(int A,int B,int C){
*_pM(A) = _M(B) - _M(C);
}
inline void MUL(int A,int B,int C){
*_pM(A) = _M(B) * _M(C);
} ...
여기서, HEAP과 STACK는 다음절에 상세히 설명한다.
TAC의 유형을 설명하기 전에 먼저 중간코드의 실행시간 환경 (가상 환경)에 대해서 정의하자.
1.5.1 실행시간 환경 (Run-time Environment): Memory Allocation 실행시간 환경 중 메모리 할당 방법은 스택 메모리 할당과 힙 메모리할당으로 나 뉜다.
• 스택 메모리 할당 (Stack storage allocation): Stack 공간에 상수, 지역변 수, 파라미터 등을 할당하는 과정이다. 또한, 실행시간에서 프로시저가 call 될때 필요한 각종 파라미터와 제어 요소를 포함하는 활성 레코드(activation record)가 스택 공간상에 할당된다.
• 힙 메모리 할당 (Heap storage allocation): 프로그램 실행시 필요할 때 마다 별도의heap공간상에서 동적으로 메모리를 할당하고 해제한다.
교과서 그림9-9와 같이 Stack과 Heap은 하나의 선형 메모리 구조를 공유한다 고 가정하고, 초기에 충분한 크기의 선형 memory를 다음과 같이 할당한다. (Heap 또한 단순성을 위해 선형성을 따른다고 가정한다.)
#define MAX_STACK_HEAP_MEMORY_SIZE 65536
int *STACK = new int[MAX_STACK_HEAP_MEMORY_SIZE];
int *HEAP = &STACK[MAX_STACK_HEAP_MEMORY_SIZE];
int TOP_SP = 0;
int HEAP_SIZE = 0;
int STACK_SIZE = 0;
이때, STACK과 HEAP은 각각 스택과 힙의 top을 가리키는 메모리 pointer들이 며, TOP SP와 현재 activation record상에서 지역변수가 시작되는 stack 상 주소를 가리키고 (교과서 그림 9-15참조), HEAP SIZE은 프로그램 시작부터 현재까지 할 당된 heap 메모리 크기를, STACK SIZE는 현재까지 할당된 stack 메모리 크기를 가라킨다.
이렇게 정의된Stack과 Heap 메모리와 변수들을 도식화하면 다음과 같다.
Heap은 선형 메모리상의 끝부터 감소하면서 할당되므로, 가장 최근에 할당된 heap의 주소는 HEAP - HEAP SIZE가 된다.
Memory overflow를 체크하는 함수는 다음과 같다.
bool is_memory_overflow(){
return HEAP_SIZE + STACK_SIZE >= MAX_STACK_HEAP_MEMORY_SIZE;
}
1.5.2 실행시간 환경 (Run-time Environment): 함수 호출 TAC생성시 프로시저 call 과정은 다음을 따르도록 하라.
1. caller는 인자들 (Parameter)을 스택에 추가한다.
2. caller는 procedure call을 한다.
3. callee는 caller의 TOP SP을 스택에 저장한다.
4. callee는 TOP SP를 스택의 마지막 주소를 설정한다.
5. callee는 procedure body를 실행한다.
6. callee는 body 실행후 저장된 caller의 TOP SP로 다시 복구한다.
7. callee는 활성레코드 및 스택에 할당된 메모리를 해제한다. (단 return값은 남아있음을 유의)
8. caller는 return값을 지역 변수에 카피한다.
위의 과정을 따르는 TAC 명령어로 PARAM과 CALL을 다음과 같이 정의하라.
(하나의 예이므로, 각자의 설계에 맞게 적절히 수정하거나 확장할 것.)
inline void PARAM(int A){
*(STACK +STACK_SIZE) = _M(A);
STACK_SIZE ++;
}
inline void CALL(void (*proc)(void), int PARAM_SIZE, int RETURN_SIZE){
//PARAM_SIZE parameter들의 스택 공간 크기 ( int단위 )
//RETURN_SIZE는 해당 함수의 return value를 위한 공간 크기 ( int단위 )
STACK_SIZE += RETURN_SIZE; //return value를 위한 공간을 할당한다 .
*(STACK +STACK_SIZE) = TOP_SP; //함수 호출후 반환될 주소를 저장한다 .
STACK_SIZE++;
int PREV_STACK_SIZE = STACK_SIZE; //TOP_SP의 이동전에 STACK_SIZE 저장
TOP_SP = STACK_SIZE; //TOP_SP를 이동한다 . proc(); // procedure 호출 (callee)
...
TOP_SP = STACK[TOP_SP - 1]; //TOP_SP를 caller의 원래 TOP_SP로 복귀한다 .
STACK_SIZE = PREV_STACK_SIZE - 1 - PARAM_SIZE - RETURN_SIZE;
// 스택에 할당된 공간 (parameter, return값, control영역) 을 해제한다 .
// 단 return 값은 곧바로 caller의 지역변수에 copy가 되어야 한다 .
// 보다 정확히 하기 위해 , return값이 카피된 이후에
해제하는 식으로 구현해도 된다 .
...
}
모든 프로시저마다 void foo(void)의 형식을 갖는 함수를 선언 및 정의하 고, procedure call을 할 때는, CALL의 첫번째 인자로 해당 함수 포인터 (function pointer)를 인자로 넘겨 호출한다.
다음은 프로시저가 호출되어 새로운 활성레코드가 추가된 이후의 스택 도식도 이다.
1.5.3 TAC: Summary
본 과제에서 중간코드생성에 필요한 TAC 종류를 정리하면 다음과 같다 (교과서 299페이지 참조).
• A = B op C형식의 치환문:
void ADD(int A,int B,int C);
void SUB(int A,int B,int C);
void MUL(int A,int B,int C);
...
• A = op B형식의 치환문:
void MINUS(int A,int B);
...
• A = B형식의 치환문:
void ASSIGN(int A,int B);
void ASSIGN_REF(int A,int i);
• A = B형식의 무조건 분기문:
#define GOTO(L) (goto L)
• A relop B GOTO L형식의 조건부 분기문:
#define EQ_GOTO(x,y,L) ...
#define LESS_GOTO(x,y,L) ...
#define GREATER_GOTO(x,y,L) ...
#define LESSEQ_GOTO(x,y,L) ...
...
• 프로시저 호출문:
void PARAM(int A);
void CALL(void (*f)(void), int N, int M);
• A = B[i], A[i] = B와 같은 첨자 치환문:
void ASSIGN_RINDEX(int A, int B, int i);
void ASSIGN_LINDEX(int A, int i, int B);
1.5.4 TAC: Examples
위에서 정의한TAC 체계에 따라 생성된 중간코드의 예를 살펴보자.
• TAC test.decaf: 예제 Decaf 코드는 다음과 같다.
int x, y;
class A { int a, b;
int foo(int a, int b){
int z;
z = a + b;
return z;
} } x = 10;
y = 20;
A a;
a = new A;
A b;
{
int c = a.foo(x,y);
int d = a.a + a.b;
b = a;
}
아래는 위Decaf코드에 대한 Symbol Table의 개략도이다.
위 Decaf코드에 대한 TAC 생성 결과의 예는 다음과 같다. (아래는 개략적인 예이므로 각자 설계에 따라 수정 및 확장할 것)
...
void A_foo(){
SUM(TOP_SP, TOP_SP-3,TOP_SP-2); //z= a+ b를 수행 ASSIGN(TOP_SP-1, TOP_SP); //return z수행 }
void main(){
STACK[STACK_SIZE++] = 10; //constant 초기화 STACK[STACK_SIZE++] = 20; //constant 초기화 TOP_SP = STACK_SIZE;
STACK_SIZE += 8; //local variable인 x,y,a,b,c,d 및 temporary variables t1, t2를 위한 stack 메모리 할당
//A a는 reference형이므로 int형 4byte 크기
ASSIGN(TOP_SP + 0, 0); // x = 10 ASSIGN(TOP_SP + 1, 1); // y = 20
HEAP_SIZE += 2; //new A 실행으로 HEAP상에 메모리 할당 . A가 총 8 byte이므로 2*4 byte만큼 증가
ASSIGN_REF(TOP_SP + 2, -HEAP_SIZE+1 ); //a = new A; HEAP상에 할당된 주소 카피,
//2 번째 인자의 offset은
구현 세부사항에 따라
달라질 수 있음
PARAM(TOP_SP+2); //a.foo(x,y)에서 class reference 파라미터 저장
PARAM(TOP_SP+0); //a.foo(x,y)에서 첫번째 파라미터 x저장
PARAM(TOP_SP+1); //a.foo(x,y)에서 두번째 파라미터 y저장
CALL(A_foo, 3, 1); //a.foo(x,y)실행, reference 크기 1, parameter크기는 8byte로 2, 리턴타입 4byte로 1 ASSIGN(TOP_SP+4, TOP_SP+STACK_SIZE+3); //int c =
a.foo(x,y)에서 리턴값 카피 ,
//TOP_SP+STACK_SIZE+3위치에 리턴값이
존재한다 .
STACK_SIZE += 2; //a.a와 a.b를 copy하기 위한 임시변수 t1, t2 생성
ASSIGN_RINDEX(TOP_SP+7,TOP_SP+2,0); //t1 = a.a수행 (t1은 임시변수 )
ASSIGN_RINDEX(TOP_SP+8,TOP_SP+2,-1); //t2 = a.b수행 (t2는 임시변수 ), 변수 a는 heap상에 있으므로 a.b의 offset에
음수를 취함
SUM(TOP_SP+5,TOP_SP+7,TOP_SP+8); //int d= a.a + a.b수행. 즉, d = t1 + t2
ASSIGN(TOP_SP+6,TOP_SP+2); //b = a 수행 . reference카피 }
참고로, 생성된 TAC 중간코드가 실행될때의 Stack및 Heap의 내용은 아래와 같을 것이다.
2 과제 내용
앞절의Decaf 및 TAC 설명을 참조하여, 중간코드생성을 위한 다음 모듈들을 구현 하라.
1. Decaf 어휘 분석기: 교과서 145페이지의 그림 4-13와 같이 Decaf 어휘 분석 을 위한 상태 전이도를 작성하고, 이를 구현하여 그림 4-14와 같이 출력되는 어휘 분석기를 작성하시오(java로 작성권장).
2. Decaf 구문분석기: Assignment 1의 문법 포맷에 따라 Decaf의 문법파일을 작성하시오. Assignment 1의 결과를 이용하여 작성된 문법파일에 따라 교 과서256페이지의 표 6-9와 같이 LALR파싱표를 얻어내고, Decaf의 LALR 구문분석기를 작성하시오(java로 작성권장).
결과 LALR파싱표가 shift-reduce 충돌이 발생하는 경우, 연산자 우선순위 등을 적용하여 충돌을 제거한 파싱표를 사용해야 한다. (이때, 원래 LALR 파싱표와, 충돌이 제거된 파싱표 각각을 파일로 구성하고 2개 모두 제출 결 과물에 포함할 것)
또는 원래Decaf문법을 모호성이 발생하기 않도록 변환해야 한다. (이경우, 원래 문법파일과 변환된 문법파일을 각각 구성하고2개 모두 제출 결과물에 포함할 것)
우선순위 적용이나 문법변환등으로 자동으로shift-reduce 충돌이 제거가 안 될경우, 해당 문제를 보고서에 기술하고 reduce우선 또는 shift우선 등 간단한 휴리스틱으로 처리할 것.
samples.zip에 있는 모든decaf 코드에 대해 파싱테스트를 해보고 결과파 일을 저장할 것. 단 bad로 시작하는 decaf파일은 구문분석기 test용도로 사 용하라.
3. TAC 중간 코드 생성기; Decaf코드를 읽어들어 앞의 TAC방식으로 중간 코드 파일인c++코드가 자동으로 생성되는 Syntax-directed translator (SDT) 을 작성하시오 (java로 작성 권장, 중간코드는 c++ 코드 파일). 생 성된c++코드는 g++로 컴파일되어 실행되어야 한다.
Print, ReadInteger, ReadLine 함수는 c++코드로 선언 및 구현하여 li- brary화 하고, 생성된 중간코드 파일에서 #include하여 실행파일 만들때 포함시키도록 하라.
보고서에는 앞Decaf 구문분석기로 파싱을 수행하는 중에 교과서 312-320페 이지의 그림8-13 또는 그림 8-15와 같이 각 문법 규칙별로 중간코드 생성을 위해 필요한 내용들의 핵심을 pseudo-code로 문서화하라. samples.zip 에 있는 모든decaf코드에 대해 중간코드를 생성하여 실행 결과를 저장하고, 구동 결과를 기술할 것.
2.1 제출 내용 및 평가 방식
코드는 java또는 c++로 작성하도록 하고, 본 과제 결과물로 필수적으로 제출해야 내용들은 다음과 같다.
• 코드 전체
• 테스트 결과: 각 내용별 테스트 코드 및 해당 로그 파일. samples.zip에 있 는 모든decaf코드에 대해 테스트 결과, 생성된 중간코드 및 실행 결과 로그 파일
• 결과보고서: 코드 설계(클래스 계층도 등),구현 방법 및 실행 결과를 요약한 보고서. 또한, 문법 규칙별로 중간코드 생성을 위해 필요한 내용에 대한 설계.
본 과제의 평가항목 및 배점은 다음과 같다.
• 각 세부내용의 구현 정확성 및 완결성 (80점)
• 코드의 Readability 및 쳬계성 (10점)
• 결과 보고서의 구체성 및 완결성 (10점)
