# Clite-compiler

**Repository Path**: bobhan/clite-compiler

## Basic Information

- **Project Name**: Clite-compiler
- **Description**: A toy compiler for Clite
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-12-03
- **Last Updated**: 2021-12-04

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## Compiler for Clite

词法分析器(Lexer)+语法分析器(Parser)+静态类型检查(StaticTypeChecking)+静态类型转换(TypeTransformer)+基于AST运行(Semantic)



### Lexer+Parser

Lexer将源码转化为Token流，Parser根据生成的Token流构建AST。

```cpp
//fibonacci.cpp
int fibonacci (int n) {
	int fib0, fib1, temp, k;
	fib0 = 0; fib1 = 1; k = n;
	while (k > 0) {
		temp = fib0;
		fib0 = fib1;
		fib1 = fib0 + temp;
		k = k - 1;
	}
	return fib0;
}
int main () {
	int answer;
	answer = fibonacci(8);
}
```



```cpp
//fibonacci.output
Begin parsing... programs/out/production/compiler-final/Examples/fib.cpp

Program (abstract syntax): 
  Globals: 
    {}
  Functions:
    Function = fibonacci; Return Type = int
      params = 
        {<n, int>}
      locals = 
        {<fib0, int>, <fib1, int>, <temp, int>, <k, int>}
      Block: 
        Assignment: 
          Variable: fib0
          IntValue: 0
        Assignment: 
          Variable: fib1
          IntValue: 1
        Assignment: 
          Variable: k
          Variable: n
        Loop: 
          Binary: 
            Operator: >
            Variable: k
            IntValue: 0
          Block: 
            Assignment: 
              Variable: temp
              Variable: fib0
            Assignment: 
              Variable: fib0
              Variable: fib1
            Assignment: 
              Variable: fib1
              Binary: 
                Operator: +
                Variable: fib0
                Variable: temp
            Assignment: 
              Variable: k
              Binary: 
                Operator: -
                Variable: k
                IntValue: 1
        Return:
          Variable: fibonacci
          Variable: fib0

    Function = main; Return Type = int
      params = 
        {}
      locals = 
        {<answer, int>}
      Block: 
        Assignment: 
          Variable: answer
          Call: fibonacci
            args = 
              IntValue: 8
```





```cpp
//recFib.cpp
int fibonacci (int n) {
   if (n < 2) return n;
   else return fibonacci(n-1) + fibonacci(n-2);
}
int main () {
	int answer;
	answer = fibonacci(8);
}
```

```cpp
//recFib.output
Begin parsing... programs/out/production/compiler-final/Examples/recFib.cpp

Program (abstract syntax): 
  Globals: 
    {}
  Functions:
    Function = fibonacci; Return Type = int
      params = 
        {<n, int>}
      locals = 
        {}
      Block: 
        Conditional: 
          Binary: 
            Operator: <
            Variable: n
            IntValue: 2
          Return:
            Variable: fibonacci
            Variable: n
          Return:
            Variable: fibonacci
            Binary: 
              Operator: +
              Call: fibonacci
                args = 
                  Binary: 
                    Operator: -
                    Variable: n
                    IntValue: 1
              Call: fibonacci
                args = 
                  Binary: 
                    Operator: -
                    Variable: n
                    IntValue: 2

    Function = main; Return Type = int
      params = 
        {}
      locals = 
        {<answer, int>}
      Block: 
        Assignment: 
          Variable: answer
          Call: fibonacci
            args = 
              IntValue: 8
```





### StaticTypeChecking+TypeTransformer

StaticTypeChecking会检查所有运算中类型的正确性和隐式类型转换的正确性，以便下一步可以正确进行。同时还会检查调用函数的实参是否与形参相匹配。

TypeTransformer会确定所有算术运算符的类型，进行隐式类型转换然后输出新的AST。

```cpp
//convert.cpp
int main ( ) {
    float f;
    int i;
    char c;
    c = 'a';
    i = 77;
    f = i - int(c);
}
```

```cpp
//convert.output
Begin parsing... programs/out/production/compiler-final/Examples/convert.cpp

Program (abstract syntax): 
  Globals: 
    {}
  Functions:
    Function = main; Return Type = int
      params = 
        {}
      locals = 
        {<f, float>, <i, int>, <c, char>}
      Block: 
        Assignment: 
          Variable: c
          CharValue: a
        Assignment: 
          Variable: i
          IntValue: 77
        Assignment: 
          Variable: f
          Binary: 
            Operator: -
            Variable: i
            Unary: 
              Operator: int
              Variable: c


Begin type checking...programs/out/production/compiler-final/Examples/convert.cpp

Type map:
Globals={}
Function main = 
{ 
    <c, char>, 
    <f, float>, 
    <i, int>,
    <main, int, {}>
}
No type errors

Transformed Abstract Syntax Tree

Program (abstract syntax): 
  Globals: 
    {}
  Functions:
    Function = main; Return Type = int
      params = 
        {}
      locals = 
        {<f, float>, <i, int>, <c, char>}
      Block: 
        Assignment: 
          Variable: c
          CharValue: a
        Assignment: 
          Variable: i
          IntValue: 77
        Assignment: 
          Variable: f
          Unary: 
            Operator: I2F
            Binary: 
              Operator: INT-
              Variable: i
              Unary: 
                Operator: C2I
                Variable: c
```



### Semantic

Semantic在最终的AST上运行程序。当调用一个函数`f(...)`时，他首先会创建一个新的活跃帧并将`f`的参数与局部变量添加进去，然后他将在上一个活跃帧的环境下依次解析(evaluate)`f`的参数，并将这些值依次赋值给相应的函数参数，如果`f`有返回值，再添加一个类型为返回值，和函数同名的变量。之后，将创建的活跃帧添加进运行栈(run-time stack)中，然后运行`f`的函数体，之后弹出运行时栈栈顶的活跃帧。如果`f`有返回值，则则取出该返回值，并将其赋值给相应的变量上。

```cpp
//newton.cpp
int main() {
	float a, x, result;
	a = 4.0;
	x = 1.0;
	while (x*x > a+0.0001 || x*x < a-0.0001 )
		x = (x + a/x)/2.0;
	result = x;
}
```

```cpp
//newton.output
Begin parsing... programs/out/production/compiler-final/Examples/newton.cpp

Program (abstract syntax): 
  Globals: 
    {}
  Functions:
    Function = main; Return Type = int
      params = 
        {}
      locals = 
        {<a, float>, <x, float>, <result, float>}
      Block: 
        Assignment: 
          Variable: a
          FloatValue: 4.0
        Assignment: 
          Variable: x
          FloatValue: 1.0
        Loop: 
          Binary: 
            Operator: ||
            Binary: 
              Operator: >
              Binary: 
                Operator: *
                Variable: x
                Variable: x
              Binary: 
                Operator: +
                Variable: a
                FloatValue: 1.0E-4
            Binary: 
              Operator: <
              Binary: 
                Operator: *
                Variable: x
                Variable: x
              Binary: 
                Operator: -
                Variable: a
                FloatValue: 1.0E-4
          Assignment: 
            Variable: x
            Binary: 
              Operator: /
              Binary: 
                Operator: +
                Variable: x
                Binary: 
                  Operator: /
                  Variable: a
                  Variable: x
              FloatValue: 2.0
        Assignment: 
          Variable: result
          Variable: x


Begin type checking...programs/out/production/compiler-final/Examples/newton.cpp

Type map:
Globals={}
Function main = 
{ 
    <result, float>, 
    <a, float>, 
    <x, float>,
    <main, int, {}>
}
No type errors

Transformed Abstract Syntax Tree

Program (abstract syntax): 
  Globals: 
    {}
  Functions:
    Function = main; Return Type = int
      params = 
        {}
      locals = 
        {<a, float>, <x, float>, <result, float>}
      Block: 
        Assignment: 
          Variable: a
          FloatValue: 4.0
        Assignment: 
          Variable: x
          FloatValue: 1.0
        Loop: 
          Binary: 
            Operator: ||
            Binary: 
              Operator: FLOAT>
              Binary: 
                Operator: FLOAT*
                Variable: x
                Variable: x
              Binary: 
                Operator: FLOAT+
                Variable: a
                FloatValue: 1.0E-4
            Binary: 
              Operator: FLOAT<
              Binary: 
                Operator: FLOAT*
                Variable: x
                Variable: x
              Binary: 
                Operator: FLOAT-
                Variable: a
                FloatValue: 1.0E-4
          Assignment: 
            Variable: x
            Binary: 
              Operator: FLOAT/
              Binary: 
                Operator: FLOAT+
                Variable: x
                Binary: 
                  Operator: FLOAT/
                  Variable: a
                  Variable: x
              FloatValue: 2.0
        Assignment: 
          Variable: result
          Variable: x


Begin interpreting...programs/out/production/compiler-final/Examples/newton.cpp

Entering main:
  Globals and top frame:
    ----------
    <result, undef>
    <a, undef>
    <x, undef>
    ----------
Leaving main:
  Globals and top frame:
    ----------
    <result, 2.0>
    <a, 4.0>
    <x, 2.0>
    ----------
Final State
  Globals and top frame:
    ----------
    ----------
```







```cpp
//gcd.cpp
int rem (int x, int y){
   return x - x/y * y;
}

int gcd (int x, int y){
   int z;
   if (y == 0) return x;
   else if (x == 0) return y;
   else {
    z = rem(x, y);
	return gcd(y, z);
   }
}

int main () {
   int answer;
   answer = gcd(24,10);
}
```

```cpp
//gcd.output
Begin parsing... programs/out/production/compiler-final/Examples/gcd.cpp

Program (abstract syntax): 
  Globals: 
    {}
  Functions:
    Function = rem; Return Type = int
      params = 
        {<x, int>, <y, int>}
      locals = 
        {}
      Block: 
        Return:
          Variable: rem
          Binary: 
            Operator: -
            Variable: x
            Binary: 
              Operator: *
              Binary: 
                Operator: /
                Variable: x
                Variable: y
              Variable: y

    Function = gcd; Return Type = int
      params = 
        {<x, int>, <y, int>}
      locals = 
        {<z, int>}
      Block: 
        Conditional: 
          Binary: 
            Operator: ==
            Variable: y
            IntValue: 0
          Return:
            Variable: gcd
            Variable: x
          Conditional: 
            Binary: 
              Operator: ==
              Variable: x
              IntValue: 0
            Return:
              Variable: gcd
              Variable: y
            Block: 
              Assignment: 
                Variable: z
                Call: rem
                  args = 
                    Variable: x
                    Variable: y
              Return:
                Variable: gcd
                Call: gcd
                  args = 
                    Variable: y
                    Variable: z

    Function = main; Return Type = int
      params = 
        {}
      locals = 
        {<answer, int>}
      Block: 
        Assignment: 
          Variable: answer
          Call: gcd
            args = 
              IntValue: 24
              IntValue: 10


Begin type checking...programs/out/production/compiler-final/Examples/gcd.cpp

Type map:
Globals={}
Function rem = 
{ 
    <x, int>, 
    <y, int>,
    <gcd, int, {<x, int>, <y, int>}>,
    <main, int, {}>,
    <rem, int, {<x, int>, <y, int>}>
}
Function gcd = 
{ 
    <x, int>, 
    <y, int>, 
    <z, int>,
    <gcd, int, {<x, int>, <y, int>}>,
    <main, int, {}>,
    <rem, int, {<x, int>, <y, int>}>
}
Function main = 
{ 
    <answer, int>,
    <gcd, int, {<x, int>, <y, int>}>,
    <main, int, {}>,
    <rem, int, {<x, int>, <y, int>}>
}
No type errors

Transformed Abstract Syntax Tree

Program (abstract syntax): 
  Globals: 
    {}
  Functions:
    Function = rem; Return Type = int
      params = 
        {<x, int>, <y, int>}
      locals = 
        {}
      Block: 
        Return:
          Variable: rem
          Binary: 
            Operator: INT-
            Variable: x
            Binary: 
              Operator: INT*
              Binary: 
                Operator: INT/
                Variable: x
                Variable: y
              Variable: y

    Function = gcd; Return Type = int
      params = 
        {<x, int>, <y, int>}
      locals = 
        {<z, int>}
      Block: 
        Conditional: 
          Binary: 
            Operator: INT==
            Variable: y
            IntValue: 0
          Return:
            Variable: gcd
            Variable: x
          Conditional: 
            Binary: 
              Operator: INT==
              Variable: x
              IntValue: 0
            Return:
              Variable: gcd
              Variable: y
            Block: 
              Assignment: 
                Variable: z
                Call: rem
                  args = 
                    Variable: x
                    Variable: y
              Return:
                Variable: gcd
                Call: gcd
                  args = 
                    Variable: y
                    Variable: z

    Function = main; Return Type = int
      params = 
        {}
      locals = 
        {<answer, int>}
      Block: 
        Assignment: 
          Variable: answer
          Call: gcd
            args = 
              IntValue: 24
              IntValue: 10


Begin interpreting...programs/out/production/compiler-final/Examples/gcd.cpp

Entering main:
  Globals and top frame:
    ----------
    <answer, undef>
    ----------
Calling gcd
  Globals and top frame:
    ----------
    <x, 24>
    <y, 10>
    <gcd, undef>
    <z, undef>
    ----------
Calling rem
  Globals and top frame:
    ----------
    <x, 24>
    <y, 10>
    <rem, undef>
    ----------
Leaving rem
  Globals and top frame:
    ----------
    <x, 24>
    <y, 10>
    <rem, 4>
    ----------
Calling gcd
  Globals and top frame:
    ----------
    <x, 10>
    <y, 4>
    <gcd, undef>
    <z, undef>
    ----------
Calling rem
  Globals and top frame:
    ----------
    <x, 10>
    <y, 4>
    <rem, undef>
    ----------
Leaving rem
  Globals and top frame:
    ----------
    <x, 10>
    <y, 4>
    <rem, 2>
    ----------
Calling gcd
  Globals and top frame:
    ----------
    <x, 4>
    <y, 2>
    <gcd, undef>
    <z, undef>
    ----------
Calling rem
  Globals and top frame:
    ----------
    <x, 4>
    <y, 2>
    <rem, undef>
    ----------
Leaving rem
  Globals and top frame:
    ----------
    <x, 4>
    <y, 2>
    <rem, 0>
    ----------
Calling gcd
  Globals and top frame:
    ----------
    <x, 2>
    <y, 0>
    <gcd, undef>
    <z, undef>
    ----------
Leaving gcd
  Globals and top frame:
    ----------
    <x, 2>
    <y, 0>
    <gcd, 2>
    <z, undef>
    ----------
Leaving gcd
  Globals and top frame:
    ----------
    <x, 4>
    <y, 2>
    <gcd, 2>
    <z, 0>
    ----------
Leaving gcd
  Globals and top frame:
    ----------
    <x, 10>
    <y, 4>
    <gcd, 2>
    <z, 2>
    ----------
Leaving gcd
  Globals and top frame:
    ----------
    <x, 24>
    <y, 10>
    <gcd, 2>
    <z, 4>
    ----------
Leaving main:
  Globals and top frame:
    ----------
    <answer, 2>
    ----------
Final State
  Globals and top frame:
    ----------
    ----------

```





```cpp
//functions.cpp
int h, i;
void A(int x, int y) {
	bool i,  j;
	B(h);
}
void B(int w) {
	int j, k;
	i = 2*w;
	w = w + 1;  
}
int main () {
	int a, b;
	h = 5; a = 3; b = 2;
	A(a, b);
}
```

```cpp
//funcsions.output
Begin parsing... programs/out/production/compiler-final/Examples/functions.cpp

Program (abstract syntax): 
  Globals: 
    {<h, int>, <i, int>}
  Functions:
    Function = A; Return Type = void
      params = 
        {<x, int>, <y, int>}
      locals = 
        {<i, bool>, <j, bool>}
      Block: 
        Call: B
          args = 
            Variable: h

    Function = B; Return Type = void
      params = 
        {<w, int>}
      locals = 
        {<j, int>, <k, int>}
      Block: 
        Assignment: 
          Variable: i
          Binary: 
            Operator: *
            IntValue: 2
            Variable: w
        Assignment: 
          Variable: w
          Binary: 
            Operator: +
            Variable: w
            IntValue: 1

    Function = main; Return Type = int
      params = 
        {}
      locals = 
        {<a, int>, <b, int>}
      Block: 
        Assignment: 
          Variable: h
          IntValue: 5
        Assignment: 
          Variable: a
          IntValue: 3
        Assignment: 
          Variable: b
          IntValue: 2
        Call: A
          args = 
            Variable: a
            Variable: b


Begin type checking...programs/out/production/compiler-final/Examples/functions.cpp

Type map:
Globals={<h, int>, <i, int>}
Function A = 
{ 
    <h, int>, 
    <x, int>, 
    <i, bool>, 
    <y, int>, 
    <j, bool>,
    <A, void, {<x, int>, <y, int>}>,
    <B, void, {<w, int>}>,
    <main, int, {}>
}
Function B = 
{ 
    <w, int>, 
    <h, int>, 
    <i, int>, 
    <j, int>, 
    <k, int>,
    <A, void, {<x, int>, <y, int>}>,
    <B, void, {<w, int>}>,
    <main, int, {}>
}
Function main = 
{ 
    <a, int>, 
    <b, int>, 
    <h, int>, 
    <i, int>,
    <A, void, {<x, int>, <y, int>}>,
    <B, void, {<w, int>}>,
    <main, int, {}>
}
No type errors

Transformed Abstract Syntax Tree

Program (abstract syntax): 
  Globals: 
    {<h, int>, <i, int>}
  Functions:
    Function = A; Return Type = void
      params = 
        {<x, int>, <y, int>}
      locals = 
        {<i, bool>, <j, bool>}
      Block: 
        Call: B
          args = 
            Variable: h

    Function = B; Return Type = void
      params = 
        {<w, int>}
      locals = 
        {<j, int>, <k, int>}
      Block: 
        Assignment: 
          Variable: i
          Binary: 
            Operator: INT*
            IntValue: 2
            Variable: w
        Assignment: 
          Variable: w
          Binary: 
            Operator: INT+
            Variable: w
            IntValue: 1

    Function = main; Return Type = int
      params = 
        {}
      locals = 
        {<a, int>, <b, int>}
      Block: 
        Assignment: 
          Variable: h
          IntValue: 5
        Assignment: 
          Variable: a
          IntValue: 3
        Assignment: 
          Variable: b
          IntValue: 2
        Call: A
          args = 
            Variable: a
            Variable: b


Begin interpreting...programs/out/production/compiler-final/Examples/functions.cpp

Entering main:
  Globals and top frame:
    ----------
    <a, undef>
    <b, undef>
    <h, undef>
    <i, undef>
    ----------
Calling A
  Globals and top frame:
    ----------
    <x, 3>
    <y, 2>
    <i, undef>
    <j, undef>
    <h, 5>
    ----------
Calling B
  Globals and top frame:
    ----------
    <w, 5>
    <j, undef>
    <k, undef>
    <h, 5>
    <i, undef>
    ----------
Leaving B
  Globals and top frame:
    ----------
    <w, 6>
    <j, undef>
    <k, undef>
    <h, 5>
    <i, 10>
    ----------
Leaving A
  Globals and top frame:
    ----------
    <x, 3>
    <y, 2>
    <i, undef>
    <j, undef>
    <h, 5>
    ----------
Leaving main:
  Globals and top frame:
    ----------
    <a, 3>
    <b, 2>
    <h, 5>
    <i, 10>
    ----------
Final State
  Globals and top frame:
    ----------
    <h, 5>
    <i, 10>
    ----------
```