Principle and compilation of programming language
brief introduction
This is a compilation principle operation called microc, which is mainly completed based on microc and Yuby. Through the code improvement and development of interpreter and compiler, the syntax of some C language is realized (and some parts are improved). The main functions are as follows:
Project description
structure
-
CLex.fsl generated clex FS lexical analyzer.
-
The basic keywords, identifiers, constants and upper case letters are defined in CLex
When the program reads this symbol, it will convert it into the capital letter we define, and then give it to CPar for processing
-
-
CPar. CPAR generated by fsy FS parser.
-
The CPar file is divided into two parts, each separated by%%
-
The first part declares the variables (morphemes) to be used. After declaring the variables, you also need to declare the priority
-
The second part defines grammar rules (grammar)
These basic elements include: statement, expression, function, main, vardeclare, variabledescribe, type and const
Indicates how to deal with these rules after recognizing the symbol string composed of these capital letters defined above
-
-
Absyn.fs defines an abstract syntax tree
The construction methods of variable description, function and type are defined
-
Comp. Transform stack syntax into virtual machine
-
interp.fs semantic analysis of abstract syntax tree
-
Machine.fs virtual machine instruction definition
-
Machine.java executes virtual machine instructions
- Machine.java generates machine Class virtual machine and machinetrace Class stack trace
Test set: the test program is placed in the example folder
usage method
compiler
Generate assembly instruction digital file out (select one of the following two files)
dotnet restore microc.fsproj // Optional dotnet clean microc.fsproj // Optional dotnet build microc.fsproj // Build/ bin/Debug/net5.0/microc.exe dotnet run -p microc.fsproj example/ex1.c // Execute the compiler and compile EX1 c. And output EX1 Out file dotnet run -p microc.fsproj -g example/ex1.c // -g view debugging information
Construction and operation of virtual machine
javac -encoding UTF-8 Machine.java java Machine ex9.out 3//Display results directly java Machinetrace ex9.out 0//View the details of each step of the stack virtual machine
In actual use, it is found that if - encoding UTF-8 is not added, the editing prompt error will be caused.
interpreter
**Run the compiler interpreter interpc exe **
dotnet restore interpc.fsproj // Optional dotnet clean interpc.fsproj // Optional dotnet build -v n interpc.fsproj // Build/ bin/Debug/net5.0/interpc.exe ```http://www.biyezuopin.vip **Execution interpreter**
./bin/Debug/net5.0/interpc.exe ex_all.c
dotnet run -p interpc.fsproj ex_all.c
dotnet run -p interpc.fsproj ex_all.c //-g displays debugging information such as token AST
## Function realization
#### 1. Variable initialization
- brief introduction: After the variable is declared, the value of the variable can be initialized at the same time
- Grammar analysis:
```F#
| Vardec ASSIGN Expr SEMI StmtOrDecSeq { DecAndAssign (fst $1, snd $1, $3) :: $5 }
-
Abstract syntax tree:
| DecAndAssign of typ * string * expr
-
Semantic analysis (interpreter):
and stmtordec stmtordec locEnv gloEnv store = match stmtordec with | Stmt stmt -> (locEnv, exec stmt locEnv gloEnv store) | Dec (typ, x) -> allocate (typ, x, None) locEnv store | DecAndAssign (typ, name, expr) -> allocate (typ, name, Some(fst (eval expr locEnv gloEnv store))) locEnv store -
compiler:
and cStmtOrDec stmtOrDec (varEnv: VarEnv) (funEnv: FunEnv) : VarEnv * instr list = match stmtOrDec with | Stmt stmt -> (varEnv, cStmt stmt varEnv funEnv) | Dec (typ, x) -> allocateWithMsg Locvar (typ, x) varEnv | DecAndAssign (typ, x, e) -> //Assignment on definition let (varEnv, code) = allocate Locvar (typ, x) varEnv (varEnv, code @ (cExpr (Assign((AccVar x), e)) varEnv funEnv) @ [ INCSP -1 ]) -
example:
void main(){ int a = 3; print a; } -
Stack diagram
2.float|double type (interpreter)
-
Introduction:
float: single precision floating-point type, with recognition format of 'number' + '+‘ The number '+' f(F) 'occupies an address unit in the stack
Double: double precision floating-point type, with recognition format of 'number' + '+‘ Number 'is converted into 64 bit binary through iee754, split into two 32-bit binary numbers, and then converted into two decimal systems, accounting for two address units in the stack
-
Parsing:
http://www.biyezuopin.cc| ConstFloat { CstF $1 } | ConstDouble { CstD $1 } ConstFloat: CSTFLOAT { $1 } | MINUS CSTFLOAT { - $2 } ; ConstDouble: CSTDOUBLE { $1 } | MINUS CSTDOUBLE { - $2 } ; | FLOAT { TypF } | DOUBLE { TypD } -
Abstract syntax tree:
| TypF | TypD | CstF of float | CstD of double
-
Semantic analysis (interpreter):
// memData | FLOAT of float | DOUBLE of double member this.float = match this with | FLOAT i -> i | INT i -> float i | DOUBLE i -> float i | STRING i -> float i | _ -> failwith ("wrong float") member this.double = match this with | DOUBLE i -> i | INT i -> double i | _ -> failwith ("wrong double") | CstF i -> (FLOAT(i), store) | CstD i -> (DOUBLE(i), store) -
example:
void main() { double i = 2.21; print i; float j = 3.21; print j; }
3.float|double|long|char (compiler)
-
Introduction:
float: single precision floating-point type, with recognition format of 'number' + '+‘ Number '+' f(F) ', via ieeer32 24 is converted to 32-bit binary and occupies an address unit in the stack
Double: double precision floating-point type, with recognition format of 'number' + '+‘ Digital ', through IEEE R64 53 is converted into 64 bit binary, split into two 32-bit binary numbers, and then converted into two decimal systems, accounting for two address units in the stack
Long: long integer. The recognition format is' number '+' l(L) '. It is divided into two 32 bits through byte operation and handed over to the virtual machine for processing. It occupies two address units in the stack
char: character type. The recognition format is' + 'character' + 'and occupies an address unit in the stack
-
example:
//ex4.c void main() { long a = 100000L; print(a); float b = 2.55F; print(b); char c = 's'; print(c); double d = 3.666; print(d); }(improved by referring to int type)
Add a new type in machine Add the corresponding assembly instruction, machine code, get the address of the label in the machine code, get the function of the address of the label, decompile and so on.
In virtual machine. java Add corresponding instructions to java.
In machine In Java, according to the instruction type, the data type is supplemented with stack pressing, addition, subtraction, multiplication and division, size judgment and so on.
-
Stack diagram
float: 1076048691, converted to binary, which is ieeer32 of 2.55 24 (IEEE 754) binary code
double: 1074030182 1717986918. The former number and the latter number are converted into 32-bit binary respectively. When spliced together, it is IEEE R64 of 2.55 53 binary code
4.boolean (compiler)
-
Introduction: boolean type. true is 1 and false is 0
-
Lexical definition:
| "boolean" -> BOOLEAN | "true" -> CSTBOOL 1 | "false" -> CSTBOOL 0
-
Parsing:
| BOOLEAN { TypB } //= -
Abstract syntax tree:
| TypB (*boolean*) Const: CSTINT { $1 } | CSTBOOL { $1 } -
example
void main() { boolean flag=true; if (flag) { print(1); } if (!flag) { print(0); } } -
Stack diagram
5.string type (interpreter)
-
Introduction: string type, which is limited to 64 bit string in this project
-
Parsing:
| ConstString { CstS $1 } ConstString: CSTSTRING { $1 } ; | STRING { TypS } -
Abstract syntax tree:
| TypS | CstS of string
-
Semantic analysis (interpreter):
// memData | STRING of string member this.string = match this with | STRING i -> i | INT i -> string i | CHAR i -> string i | POINTER i -> string i | FLOAT i -> string i | DOUBLE i -> string i | CstS i -> (STRING(i), store) -
example:
void main() { string i = "Compilation principle"; print i; }
6.print
-
Introduction: it expands the function of print and can output three new types (string float double)
-
Semantic analysis:
| Prim1 (ope, e1) -> let (i1, store1) = eval e1 locEnv gloEnv store let res = match ope with | "!" -> if i1.int = 0 then INT(1) else INT(0) | "printi" -> if i1 = STRING(i1.string) then printf "%s " i1.string i1 else if i1.float = float(i1.int) then printf "%d " i1.int i1 else printf "%.2f " i1.float i1 | "printc" -> printf "%c " i1.char i1 | _ -> failwith ("unknown primitive " + ope) -
example:
Same as above float double string Examples of
7.for
-
Introduction: A for loop similar to C
-
Parsing:
| FOR Access IN RANGE LPAR Expr COMMA Expr COMMA Expr RPAR StmtM {ForIn($2, $6, $8, $10, $12)} -
Abstract syntax tree:
| For of expr * expr * expr * stmt
-
Semantic analysis (interpreter):
| For(e1,e2,e3,body) -> let (v, store1) = eval e1 locEnv gloEnv store let rec loop store1 = let (v,store2) = eval e2 locEnv gloEnv store1 if v<>INT(0) then loop(snd(eval e3 locEnv gloEnv (exec body locEnv gloEnv store2))) else store2 loop store1 -
Semantic analysis (compiler):
Compile e1 assignment first, release the space occupied during calculation after assignment, and then judge the condition e2. If IFNZRO=1, execute the body statement, on the contrary, end the for loop.
| For(e1, e2, e3, body) -> let labbegin = newLabel() let labtest = newLabel() cExpr e1 varEnv funEnv @ [INCSP -1] @ [GOTO labtest; Label labbegin] @ cStmt body varEnv funEnv @ cExpr e3 varEnv funEnv @ [INCSP -1] @ [Label labtest] @ cExpr e2 varEnv funEnv @ [IFNZRO labbegin] -
example:
void main() { int i; for (i = 0; i < 5; i = i + 1) { print i; } } -
Runtime stack:
8.do while|do until
-
Introduction:
Do while: execute the statement in the body once first, and jump out of the loop if it does not meet the conditions.
dountil: execute the statement in the body once, and jump out of the loop if it meets the conditions
-
Parsing:
| DO StmtM WHILE LPAR Expr RPAR SEMI { DoWhile($2, $5) } | DO StmtM UNTIL LPAR Expr RPAR SEMI { DoUntil($2, $5) } -
Abstract syntax tree:
| DoWhile of stmt * expr | DoUntil of stmt * expr
-
Semantic analysis (interpreter):
| DoWhile (body, e) -> let rec loop store1 = let (v, store2) = eval e locEnv gloEnv store1 if v <> INT(0) then loop (exec body locEnv gloEnv store2) else store2 loop (exec body locEnv gloEnv store) | DoUntil (body, e) -> let rec loop store1 = let (v, store2) = eval e locEnv gloEnv store1 if v = INT(0) then loop (exec body locEnv gloEnv store2) else store2 loop (exec body locEnv gloEnv store) -
Semantic analysis (compiler):
Do while: similar to while, you only need to execute the body statement for the first time
Dountil: the difference between dountil and dowile is that dowile continues when the condition is 1, while dountil exits the loop when the condition is 1
| DoWhile (body, e) -> let labbegin = newLabel () let labtest = newLabel () cStmt body varEnv funEnv @[ GOTO labtest] @[Label labbegin ] @ cStmt body varEnv funEnv @ [ Label labtest ] @ cExpr e varEnv funEnv @ [ IFNZRO labbegin ] | DoUntil (body, e) -> let labbegin = newLabel () let labtest = newLabel () cStmt body varEnv funEnv @[ GOTO labtest] @[Label labbegin ] @ cStmt body varEnv funEnv @ [ Label labtest ] @ cExpr e varEnv funEnv @ [ IFZERO labbegin ] -
example:
//ex7.c void main() { int i=3; do{ i+=1; }while(i<3); print(i); do{ i-=1; }until(i<3); print(i); } -
Runtime stack:
9. Ternary operator:
-
Introduction: similar to C's ternary operator: a > b? a : b
-
Parsing:
| Expr QUEST Expr COLON Expr { Prim3($1,$3,$5) } -
Abstract syntax tree:
| Prim3 of expr * expr * expr
-
Semantic analysis (interpreter):
| Prim3(e1, e2, e3) -> let (v, store1) = eval e1 locEnv gloEnv store if v <> INT(0) then eval e2 locEnv gloEnv store1 else eval e3 locEnv gloEnv store1 -
Semantic analysis (compiler):
Compile the R-value expression e first and judge the condition. If it is 0, execute e2; If it is 1, execute e1.
| Prim3 (e, e1, e2) -> let labelse = newLabel () let labend = newLabel () cExpr e varEnv funEnv @ [ IFZERO labelse ] @ cExpr e1 varEnv funEnv @ [ GOTO labend ] @ [ Label labelse ] @ cExpr e2 varEnv funEnv @ [ Label labend ] -
example:
void main() { int i=3; i > 5 ? i=0 : i=5; print(i); } -
Runtime stack:
10.+= -= *= /= %=
-
Introduction: similar to C. variables perform four operations on themselves
-
Parsing:
| Access PLUSASSIGN Expr { AssignPrim("+=", $1, $3) } | Access MINUSASSIGN Expr { AssignPrim("-=", $1, $3) } | Access TIMESASSIGN Expr { AssignPrim("*=", $1, $3) } | Access DIVASSIGN Expr { AssignPrim("/=", $1, $3) } | Access MODASSIGN Expr { AssignPrim("%=", $1, $3) } -
Abstract syntax tree:
| AssignPrim of string * access * expr
-
Semantic analysis (interpreter):
| AssignPrim(ope, acc, e) -> let (loc,store1) = access acc locEnv gloEnv store let tmp = getSto store1 loc.pointer let (res,store2) = eval e locEnv gloEnv store1 let num = match ope with | "+=" -> match (tmp) with | INT i -> INT(tmp.int + res.int) | FLOAT i -> FLOAT(tmp.float + res.float) | _ -> failwith ("wrong calu") | "-=" -> match (tmp) with | INT i -> INT(tmp.int - res.int) | FLOAT i -> FLOAT(tmp.float - res.float) | _ -> failwith ("wrong calu") | "*=" -> match (tmp) with | INT i -> INT(tmp.int / res.int) | FLOAT i -> FLOAT(tmp.float / res.float) | _ -> failwith ("wrong calu") | "/=" -> match (tmp) with | INT i -> INT(tmp.int / res.int) | FLOAT i -> FLOAT(tmp.float / res.float) | _ -> failwith ("wrong calu") | "%=" -> match (tmp) with | INT i -> INT(tmp.int % res.int) | FLOAT i -> FLOAT(tmp.float % res.float) | _ -> failwith ("wrong calu") | _ -> failwith("unkown primitive " + ope) (num, setSto store2 loc.pointer num) -
Semantic analysis (compiler):
First obtain the position of the variable e1, take a value after DUP, then compile the right value expression e2, and finally assign a value after addition, subtraction, multiplication and division by match operation.
| AssignPrim (ope, e1, e2) -> cAccess e1 varEnv funEnv @[DUP;LDI] @ cExpr e2 varEnv funEnv @ (match ope with | "+=" -> [ ADD;STI ] | "-=" -> [ SUB;STI ] | "*=" -> [ MUL;STI ] | "/=" -> [ DIV;STI ] | _ -> raise (Failure "unknown AssignPrim")) -
example:
void main() { int i = 3; i += 1; print(i); i -= 1; print(i); i *= 2; print(i); i = i/2; print(i); } -
Runtime stack:
11.switch-case-default
-
Introduction: similar to C. find the same case value according to the variable expression in switch. If none of them match, execute the expression in default, and the default expression must be written at the end
-
Parsing:
| FOR LPAR Expr SEMI Expr SEMI Expr RPAR StmtU { For($3, $5, $7, $9) } CaseList: { [] } | CaseDec { [$1] } | CaseDec CaseList { $1 :: $2 } | DEFAULT COLON StmtM { [Default($3)] } CaseDec: CASE Expr COLON Stmt { Case($2,$4) } -
Abstract syntax tree:
| Switch of expr * stmt list | Case of expr * stmt | Default of stmt
-
Semantic analysis (interpreter):
| Switch(e, body) -> let (v, store0) = eval e locEnv gloEnv store let rec carry list = match list with | Case(e1, body1) :: next -> let (v1, store1) = eval e1 locEnv gloEnv store0 if v1 = v then exec body1 locEnv gloEnv store1 else carry next | Default(body) :: over -> exec body locEnv gloEnv store0 | [] -> store0 | _ -> store0 (carry body) | Case (e, body) -> exec body locEnv gloEnv store | Default(body) -> exec body locEnv gloEnv store -
Semantic analysis (compiler):
Define the recursive function serchcases, which is used to match the list of cases. It is divided into three cases: empty set, case and default. Case needs to judge the condition and execute the body statement only when EQ is equal. Otherwise, call the function again to find the next one. Default ends after the statement is executed directly.
| Switch (e, cases) -> let rec searchcases c = match c with | Case (e, body) :: tail -> let labend = newLabel () let labfin = newLabel () [DUP] @ cExpr e varEnv funEnv @ [EQ] @ [ IFZERO labend ] @ cStmt body varEnv funEnv @ [ GOTO labfin ] @ [ Label labend ] @ searchcases tail @ [ Label labfin ] | Default body :: [] -> cStmt body varEnv funEnv | [] -> [] cExpr e varEnv funEnv @ searchcases cases @[INCSP -1] -
example:
void main() { switch(5){ case 1:print(1); case 2:print(2); case 3:print(3); default:print(4); } } -
Runtime stack:
12. Self increase and self decrease
-
Parsing:
| Access PREINC { Prim4("I++", $1) } | Access PREDEC { Prim4("I--", $1) } | PREINC Access { Prim4("++I", $2) } | PREDEC Access { Prim4("--I", $2) } -
Abstract syntax tree:
| Prim4 of string * access
-
Semantic analysis (interpreter):
| Prim4(ope, acc) -> let (loc, store1) = access acc locEnv gloEnv store let (i1) = getSto store1 loc.pointer match ope with | "I++" -> match (i1) with | INT i -> let res = INT(i1.int + 1) (i1, setSto store1 loc.pointer res) | FLOAT i -> let res = FLOAT(i1.float + 1.0) (i1, setSto store1 loc.pointer res) | _ -> failwith ("wrong calu") | "I--" -> match (i1) with | INT i -> let res = INT(i1.int - 1) (i1, setSto store1 loc.pointer res) | FLOAT i -> let res = FLOAT(i1.float - 1.0) (i1, setSto store1 loc.pointer res) | _ -> failwith ("wrong calu") | "++I"-> match (i1) with | INT i -> let res = INT(i1.int + 1) (res, setSto store1 loc.pointer res) | FLOAT i -> let res = FLOAT(i1.float + 1.0) (res, setSto store1 loc.pointer res) | _ -> failwith ("wrong calu") | "--I"-> match (i1) with | INT i -> let res = INT(i1.int - 1) (res, setSto store1 loc.pointer res) | FLOAT i -> let res = FLOAT(i1.float - 1.0) (res, setSto store1 loc.pointer res) | _ -> failwith ("wrong calu") | _ -> failwith ("unknown primitive " + ope) -
Semantic analysis (compiler):
i + +: first find the variable address, copy a copy and then take the value, exchange the original value with the address (save the original value), and then the same as + + i. finally, clear the calculation result after assignment to save space
++i: After finding the variable address, dup a copy, take the value, add constant 1, add operation, and assign the calculation result
| Prim4 (ope, e1) -> (match ope with | "I++" -> cAccess e1 varEnv funEnv @[ DUP;LDI;SWAP;DUP;LDI;CSTI 1; ADD;STI;INCSP -1 ] | "I--" -> cAccess e1 varEnv funEnv @ [ DUP;LDI;SWAP;DUP;LDI;CSTI -1; ADD;STI;INCSP -1 ] | "++I" -> cAccess e1 varEnv funEnv @[ DUP;LDI;CSTI 1; ADD;STI ] | "--I" -> cAccess (e1) varEnv funEnv @ [ DUP;LDI;CSTI -1; ADD;STI ] | _ -> raise (Failure "unknown primitive 4")) -
example:
void main(){ int i = 1; print i++; print i; print i--; print i; print ++i; print i; print --i; print i; } -
Runtime stack:
In ex2, a is 1, and the output result of 8 print s should be 1 2 2 1 2 1 1. The stack display operation is shown in the figure.
Take i + + as an example, first find the location of i (GETBP+CSTI 0+ADD), take LDI value after DUP, and SWAP saves the original value. After that, a copy of DUP is changed to the address of i at the top of the stack for value taking, and then the constant 1 is added. After adding, STI is assigned. INCSP -1 will take the calculated value out of the stack and leave the backup i value for print.
[ 4 -999 1 1 2 1 1 ]{27: ADD} i The value of is backed up i value i Address of i Value constant 1 mutually plus
13.for-in-range
-
Introduction: similar to C. find the same case value according to the variable expression in switch. If none of them match, execute the expression in default, and the default expression must be written at the end
-
Parsing:
| FOR Access IN RANGE LPAR Expr COMMA Expr COMMA Expr RPAR StmtM {ForIn($2, $6, $8, $10, $12)} -
Abstract syntax tree:
| ForIn of access * expr * expr * expr * stmt
-
Semantic analysis (interpreter):
| ForIn (var, e1, e2, e3, body) -> let (local_var, store1) = access var locEnv gloEnv store let (start_num, store2) = eval e1 locEnv gloEnv store1 let (end_num, store3) = eval e2 locEnv gloEnv store2 let (step, store4) = eval e3 locEnv gloEnv store3 let rec loop temp store5 = let store_local = exec body locEnv gloEnv (setSto store5 local_var.pointer temp) if temp.int + step.int < end_num.int then let nextValue = INT(temp.int + step.int) loop nextValue store_local else store_local if start_num.int < end_num.int then let intValue = INT(start_num.int) loop intValue store4 else store4 -
example:
void main() { int i; for i in range (2,10,3) { print i; } }
Technical evaluation
-
example
function Corresponding test documents excellent good in Variable initialization Assign.c √ Self increasing and self decreasing Pre.c √ for loop for.c √ ternary operator prim3.c √ switch-case switch.c √ float, double, char, long types (compiler) type.c √ dowhile,dountil dowhileuntil.c √ += -= *= /= %= Add.c √ boolean boolean.c √
Reference documents
http://sigcc.gitee.io/plc2021/#/07/microc.compiler Learning instruction
