手写C语言编译器，学习编译原理，写编译器（第六天)

学习编译原理，写编译器（第六天）

现在已经学会了Bison和Flex部分（没学会的看，学编译器第一天和第二天），那么我们开始实战吧！要求做一个编译器
PS::存稿发错了，将错就错吧， 看第五天和第四天的会简单点，都是偏实战的系列。 这个会复杂一丢丢

目录

• 1.基本要求
• 2.拓展功能
• 3.步骤大概分析
• 4.开始写flex和bison文件

1.基本要求：

• 变量类型：int
• 语句：注释，声明，赋值，循环（while和for），判断（if），输入输出
• 算术运算：+，-，*，/，%，^
• 关系运算：==，<，>，<=，>=，!=
• 逻辑运算：&&（与），||（或），!（非）

2.拓展功能

• 支持过程和函数调用
• 支持数组运算
• 支持指针运算
• 支持结构体

3. 步骤大概分析：

- [x]  词法分析
- [x]  语法分析
- [ ]  类型检查
- [ ]  代码优化
- [ ]  生成目标代码

4. 开始写flex和bison文件

• 读前须知

在这段Flex代码中，包含"yacc.tab.h"头文件是出于以下的考虑：
通信：Flex与Yacc通过yylval变量进行通信，Flex代码中的规则动作部分通常将识别到的符号的相关信息（比如文本，类型，行号等）存储在yylval中，然后返回给Yacc的解析程序。"yacc.tab.h"文件中定义了yylval变量的类型YYSTYPE，因此需要在Flex代码中包含这个文件。
解析："yacc.tab.h"文件中还定义了Yacc生成的语法单元的枚举值。Flex代码中的规则部分需要返回这些枚举值给Yacc解析，因此也需要包含这个头文件。
综上，包含"yacc.tab.h"头文件是为了让Flex词法分析器能正确识别并返回给Yacc语法分析器所需的信息。

Yacc（Yet Another Compiler-Compiler）是一个计算机程序，用于为 Unix 操作系统编写编译器和解析器。Yacc 是由 Stephen C. Johnson 于 AT&T 电话实验室开发的，它使用 LALR 解析的方式生成一个 LALR(1) 的解析器。
基本来说，Yacc 是一个工具，它接受一个上下文无关语法作为输入，然后产生一个C语言编写的语法分析器作为输出。这个输出的程序在给定输入时，可以确定是否该输入遵循了制定的语法。
使用Yacc生成解析器的主要步骤如下：
提供上下文无关语法：这是描述目标语言语法结构的规则，通常以 Backus-Naur Form（BNF）或 Extended Backus-Naur Form（EBNF）的形式提供。
描述语法规则的动作：每条语法规则后面通常会跟一个在成功匹配该规则后要执行的 C 代码块。
Yacc 与其配套使用的词法分析器生成工具通常是 Lex 或者 Flex。Lex/Flex 负责将输入文本分解为一系列的标记或称为词素（token），然后由 Yacc 产生的解析器根据这些 token 和给定的语法规则进行语法解析。

a.词法分析文件lea.l

%{
    #include "yacc.tab.h" //包含 yacc生成的头文件
    void comment(void); //声明处理注释的函数
    struct Tree* terminator(char* name, int number, ...); //声明建立AST(抽象语法树)节点的函数
%}
%option yylineno //这个选项会开启行号记录
delim   [ \\\\t\\\\n] //定义界定符，包括空格、制表符和换行符
whitespace  {delim}+ //定义空白字符，即一个或多个界定符
digit   [0-9] //定义数字，即0-9//定义整数常量
int8    (0([0-7])+)
int10   ([1-9]|1-9+|0)
int16   (0xX+)//定义字符串
string  "?["]
letter  [A-Za-z_] //定义字母，即A-Z、a-z和_
id  {letter}({digit}|{letter}) //定义标识符，即字母开头后接字母或数字//规则部分
void	{ yylval.tree = terminator("VOID", yylineno); return VOID;} //当识别到"void"关键字时，调用terminator函数并返回VOID，下同
main    { yylval.tree = terminator("MAIN", yylineno); return MAIN;}
//……略{whitespace}    {} //对于空白字符不做处理
{int8}  	{ yylval.tree = terminator("INT8", yylineno); return INT8;} //当识别到8进制整数常量时，调用terminator函数并返回INT8，下同
{int10}   	{ yylval.tree = terminator("INT10", yylineno); return INT10;}
{int16} 	{ yylval.tree = terminator("INT16", yylineno); return INT16;}//识别操作符
"("     { yylval.tree = terminator("LP", yylineno); return '(';} //当识别到"("时，调用terminator函数并返回字符'('，下同
")"     { yylval.tree = terminator("RP", yylineno); return ')';}//……略void comment(void)  // 定义函数来处理识别到的注释
{
    // 此函数会跳过注释部分，并检查注释是否正确结束
}int yywrap()  // 定义yywrap函数，当输入为空时，yylex函数将终止，此时yywrap函数返回1
{
    return 1;
}

这段代码具体做的事情如下：

识别关键词、变量、常量和运算符等：例如，void, main, return, const, static等C语言的关键字，以及识别C语言的运算符（+, -, , /等）。这种识别是通过正则表达式规则进行的。

处理注释：识别并剔除单行注释（//），以及跨行注释（/ …*/）。对这部分内容不进行进一步的处理。

生成抽象语法树：每当识别到一个关键字，变量，或者运算符等，它会调用名为terminator的函数，创建一个对应的抽象语法树（AST）节点。在这个过程中，它会把识别到的元素类型和位置信息（行数）等信息传递给terminator函数。

这样，通过这个Flex代码，输入的源程序字符流被转换为了一系列的词法单元，同时相应的词法信息被记录在AST中。这是编译器处理源程序的第一步，为后续的语法分析，语义分析等阶段提供了基础数据。

b. 语法分析器

读前须知:

在这段Flex代码中，包含"yacc.tab.h"头文件是出于以下的考虑：
通信：Flex与Yacc通过yylval变量进行通信，Flex代码中的规则动作部分通常将识别到的符号的相关信息（比如文本，类型，行号等）存储在yylval中，然后返回给Yacc的解析程序。"yacc.tab.h"文件中定义了yylval变量的类型YYSTYPE，因此需要在Flex代码中包含这个文件。
解析："yacc.tab.h"文件中还定义了Yacc生成的语法单元的枚举值。Flex代码中的规则部分需要返回这些枚举值给Yacc解析，因此也需要包含这个头文件。
综上，包含"yacc.tab.h"头文件是为了让Flex词法分析器能正确识别并返回给Yacc语法分析器所需的信息。

Yacc（Yet Another Compiler-Compiler）是一个计算机程序，用于为 Unix 操作系统编写编译器和解析器。Yacc 是由 Stephen C. Johnson 于 AT&T 电话实验室开发的，它使用 LALR 解析的方式生成一个 LALR(1) 的解析器。
基本来说，Yacc 是一个工具，它接受一个上下文无关语法作为输入，然后产生一个C语言编写的语法分析器作为输出。这个输出的程序在给定输入时，可以确定是否该输入遵循了制定的语法。
使用Yacc生成解析器的主要步骤如下：
提供上下文无关语法：这是描述目标语言语法结构的规则，通常以 Backus-Naur Form（BNF）或 Extended Backus-Naur Form（EBNF）的形式提供。
描述语法规则的动作：每条语法规则后面通常会跟一个在成功匹配该规则后要执行的 C 代码块。
Yacc 与其配套使用的词法分析器生成工具通常是 Lex 或者 Flex。Lex/Flex 负责将输入文本分解为一系列的标记或称为词素（token），然后由 Yacc 产生的解析器根据这些 token 和给定的语法规则进行语法解析。
语法分析器有点长， 但是读它是一个学习bison还有编译器比较好的方式，如果前面的一二三天都看了，就看下去吧，我放在最后，一行一行加注释的版本

;%{
    // 包含头文件和声明外部函数
    #include "tree.h"       // 处理抽象语法树的结构
    #include "hashMap.h"    // 提供哈希表功能，用于符号表
    #include "inner.h"      // 可能包含一些内部定义
    #include <stdio.h>
    #include <string.h>

    // 函数声明
    void output();          // 输出用的
    int yylex();            // 由 Lex/Flex 生成的词法分析器函数
    void yyerror(const char *s);  // 错误处理函数
    extern int yylineno;    // 行号
    extern FILE* yyout;     // 输出文件指针

    // 全局变量
    FILE *out,*outInner;
    HashMap* hashMap = NULL;       // 符号表
    int scope = 0;                 // 作用域计数器
    struct Declator* declator;     // 变量声明相关的数据结构
    int type, preType;             // 类型相关变量

    Tree* root;                    // 指向抽象语法树根节点的指针
    Node *head;                    // 用于链表结构
    int line_count=1;              // 行计数器，用于中间代码生成
%}

%union{
    struct Tree* tree;
}
%token <tree> INT8 INT10 INT16
%token <tree> ID
%token <tree> INT
%token <tree> VOID MAIN RET CONST STATIC AUTO IF ELSE WHILE DO BREAK CONTINUE SWITCH CASE
%token <tree> DEFAULT SIZEOF TYPEDEF VOLATILE GOTO INPUT OUTPUT
%token <tree> LE GE AND OR ADD_ASSIGN SUB_ASSIGN MUL_ASSIGN DIV_ASSIGN MOD_ASSIGN
%token <tree> INC DEC EQUAL NE PTR FOR STR
%token <tree> '(' ')' '[' ']' '{' '}' '!' '^' '&' '*' '-' '+' '=' '/' '%' ',' ';' '<' '>'
%type <tree> type
%type <tree> constant primary_expression postfix_expression unary_expression cast_expression
multiplicative_expression additive_expression relational_expression equality_expression
logical_and_expression logical_or_expression assignment_expression operate_expression declare_expression
nullable_expression while_expression for_expression funcion_expression if_expression if_identifier return_expression null unary_operator
main_function sentence statement assignment_operator single_expression

%precedence ')'
%precedence ELSE

%%

project:
    main_function
    {
        root = createTree("Project", 1, $1);

        //重新赋值行号
        int seek=1;
        line_count=1;
        if(root->code){
            while(seek){
                seek = swap(root->code,"#",lineToString(line_count++));
            }
            fprintf(outInner,"%s",root->code);
        }
    }
;

main_function
    : VOID MAIN '(' ')' '{' sentence '}'
    {
        $$ = createTree("Main Func", 7, $1, $2, $3, $4, $5, $6, $7);
    }
    | type MAIN '(' ')' '{' sentence '}'
    {
        $$ = createTree("Main Func", 7, $1, $2, $3, $4, $5, $6, $7);
    }
;

sentence
    : statement sentence
    {
        $$ = createTree("sentence", 2, $1, $2);
    }
    | statement

;
constant
    : INT8
    | INT10
    | INT16
;

primary_expression
    : ID
    {
        if(type == 0){
            Data* data = toData(type, $1->content, NULL, scope);
            HashNode* hashNode = get(hashMap, data);
            if(hashNode == NULL){
                char* error = (char*)malloc(50);
                sprintf(error, "\\\\"%s\\\\" is undefined", $1->content);
                yyerror(error);
                free(error);
            }
        }
    }
    | constant
    | '(' operate_expression ')'
    {
        $$ = createTree("primary_expression", 3, $1, $2, $3);
    }
;

postfix_expression
    : primary_expression
    | postfix_expression '[' operate_expression ']'
    {
        $$ = addDeclator("Array", $1, $3);
        //$$->code ti = $1-> inner * $3->inner + $3->inner
    }
    | postfix_expression INC
    {
        $$ = createTree("postfix_expression", 2, $1, $2);
    }
    | postfix_expression DEC
    {
        $$ = createTree("postfix_expression", 2, $1, $2);
    }
;

unary_operator
    : '+'
    | '-'
    | '*' {  type = preType; }
    | '&'
    | '!'
;

unary_expression
    : postfix_expression
    | INC postfix_expression
    {
        $$ = unaryOpr("unary_expression", $1, $2);
    }
    | DEC postfix_expression
    {
        $$ = unaryOpr("unary_expression", $1, $2);
    }
    | unary_operator cast_expression
    {
        if(!strcmp($1->content, "*")){
            $$ = addDeclator("Pointer", $2, $1);
        }else{
            $$ = unaryOpr("unary_expression", $1, $2);
        }
    }
;

cast_expression
    : unary_expression

;

multiplicative_expression
    : cast_expression
    | multiplicative_expression '*' cast_expression
    {
        $$ = binaryOpr("multiplicative_expression", $1, $2, $3);
    }
    | multiplicative_expression '/' cast_expression
    {
        $$ = binaryOpr("multiplicative_expression", $1, $2, $3);
    }
    | multiplicative_expression '%' cast_expression
    {
        $$ = binaryOpr("multiplicative_expression", $1, $2, $3);
    }
    | multiplicative_expression '^' cast_expression
    {
        $$ = binaryOpr("multiplicative_expression", $1, $2, $3);
    }
;

additive_expression
    : multiplicative_expression

    | additive_expression '+' multiplicative_expression
    {
        $$ = binaryOpr("additive_expression", $1, $2, $3);
    }
    | additive_expression '-' multiplicative_expression
    {
        $$ = binaryOpr("additive_expression", $1, $2, $3);
    }
;

relational_expression
    : additive_expression
    | relational_expression '<' additive_expression
    {
        $$ = binaryOpr("relational_expression", $1, $2, $3);
    }
    | relational_expression '>' additive_expression
    {
        $$ = binaryOpr("relational_expression", $1, $2, $3);
    }
    | relational_expression LE additive_expression
    {
        $$ = binaryOpr("relational_expression", $1, $2, $3);
    }
    | relational_expression GE additive_expression
    {
        $$ = binaryOpr("relational_expression", $1, $2, $3);
    }
;

equality_expression
    : relational_expression
    | equality_expression EQUAL relational_expression
    {
        $$ = binaryOpr("equality_expression", $1, $2, $3);
    }
    | equality_expression NE relational_expression
    {
        $$ = binaryOpr("equality_expression", $1, $2, $3);
    }
;

logical_and_expression
    : equality_expression
    | logical_and_expression AND equality_expression
    {
        $$ = binaryOpr("logical_and_expression", $1, $2, $3);
    }
;

logical_or_expression
    : logical_and_expression
    | logical_or_expression OR logical_and_expression
    {
        $$ = binaryOpr("logical_or_expression", $1, $2, $3);
    }
;

assignment_operator
    : '='
    | MUL_ASSIGN
    | DIV_ASSIGN
    | MOD_ASSIGN
    | ADD_ASSIGN
    | SUB_ASSIGN
;

assignment_expression
    : logical_or_expression
    | unary_expression assignment_operator assignment_expression
    {
        $$ = assignOpr("assignment_expression", $1, $2, $3);
    }
;

operate_expression
    : assignment_expression
    | operate_expression ',' assignment_expression
    {
        $$ = createTree("operate_expression", 3, $1, $2, $3);
    }
;

null:{$$ = createTree("null", 0, yylineno);};

nullable_expression
    : null
    | operate_expression
;

declare_expression
    : type operate_expression
    {
        $$ = createTree("declare_expression", 2, $1, $2);
        if($2){
            putTree(hashMap, $2);
            preType = type = 0;
        }
    }
;

single_expression
    : operate_expression ';'
    | declare_expression ';'
    | if_expression
    | while_expression
    | for_expression
    | funcion_expression ';'
    | return_expression ';'
    | ';'
;

if_expression
    : if_identifier ')' statement
    {
        int headline = $1->headline;
        int nextline = line_count;
        $$ = ifOpr("if_expression",headline,nextline, $1, $3);
    }
    | if_identifier ')' statement ELSE {$1->nextline = line_count++;} statement
    {
        int headline = $1->headline;
        int next1 = $1->nextline;
        int next2 = line_count;
        $$ = ifelseOpr("if_else_expression",headline,next1,next2, $1, $3, $6);
    }
;
if_identifier
    : IF  '(' operate_expression
    {
        $$ = $3;
        $$->headline = line_count;
        line_count += 2;
    }
;

statement
    : '{' sentence '}'
    {
        $$ = createTree("statement", 3, $1, $2, $3);
    }
    | '{' '}'
    {
        $$ = createTree("statement", 2, $1, $2);
    }
    | single_expression  {head = NULL;}
;

for_expression
    : FOR '(' nullable_expression {
        $1->headline = line_count;
    } ';'  nullable_expression ';' {
        $6->headline = line_count;
    } nullable_expression ')' {

    } statement
    {
        line_count += 2;
        int head1 = $1->headline;
        int head2 = $6->headline;
        int nextline = line_count++;
        $$ = forOpr("for_expression",head1, head2, nextline, $3, $6, $9, $12);
    }
;

while_expression
    : WHILE {
        $1->headline = line_count;
    }'(' operate_expression ')' {
        $4->headline = line_count;
        line_count += 2;
    } statement{
        int head1 = $1->headline;
        int head2 = $4->headline;
        int nextline = line_count++;
        $$ = whileOpr("while_expression",head1, head2, nextline, $4, $7);
    }
;

funcion_expression
    : INPUT '(' operate_expression ')'
    {
        $$ = unaryFunc("input", $1, $3);
        line_count+=2;
    }
    | OUTPUT '(' operate_expression ')'
    {
        $$ = unaryFunc("output", $1, $3);
        line_count+=2;
    }
;

return_expression
    : RET
    {
        $$ = retNull("return_expression", $1);
    }
    | RET operate_expression
    {
        $$ = retOpr("return_expression", $1, $2);
    }
;

type
    : INT {
        // $$ = createTree("type", 1, $1);
        type = INT;
    }
%%

void yyerror(const char* s){
    printf("Error: %s\\\\tline: %d\\\\n", s, yylineno);
}

int main(int argc, char* argv[]){
    const char* outFile="Lexical";
    const char* outFile2="Grammatical";
    const char* outFile3="Innercode";
    extern FILE* yyin, *yyout;	//yyin和yyout都是FILE*类型
    type = 0;
    hashMap = createHashMap(2);
	yyin = fopen(argv[1], "r");
    yyout = fopen(outFile, "w");
    out = fopen(outFile2,"w");
    outInner = fopen(outFile3,"w");
    int i = 0;
    fprintf(yyout, "%-15s\\\\t%-15s\\\\t%s\\\\n", "单词", "词素", "属性");
	if(!yyparse()){
        //正常解读文件
        printf("read successfully\\\\n");
        printTree(root);
    }
	else{
        printf("something error\\\\n");
    }
    fclose(out);
    fclose(outInner);
	fclose(yyin);
    fclose(yyout);
    destoryHashMap(hashMap);
	return 0;
}

这段代码具体做的事情如下：

• 识别关键词、变量、常量和运算符等：例如，void, main, return, const, static等C语言的关键字，以及识别C语言的运算符（+, -, , /等）。这种识别是通过正则表达式规则进行的。
• 处理注释：识别并剔除单行注释（//），以及跨行注释（/ …*/）。对这部分内容不进行进一步的处理。
• 生成抽象语法树：每当识别到一个关键字，变量，或者运算符等，它会调用名为terminator的函数，创建一个对应的抽象语法树（AST）节点。在这个过程中，它会把识别到的元素类型和位置信息（行数）等信息传递给terminator函数。
• 这样，通过这个Flex代码，输入的源程序字符流被转换为了一系列的词法单元，同时相应的词法信息被记录在AST中。这是编译器处理源程序的第一步，为后续的语法分析，语义分析等阶段提供了基础数据。

文件头部 (%)

• 头文件和外部函数声明 ：引入了与语法分析器相关的自定义头文件，如 "tree.h", "hashMap.h", 和 "inner.h"。同时声明了外部函数和变量，如 yylex()（词法分析函数），yyerror()（错误处理函数），以及行号变量 yylineno。
• 全局变量 ：定义了多个全局变量，例如 hashMap（用作符号表），scope（跟踪当前作用域），以及 root和 head（用于构建和管理抽象语法树）。

符号和类型声明

• %union{} ：定义了一个共用体，其成员 tree是一个指向 Tree结构的指针。这用于在不同的规则之间传递复杂的数据结构。
• %token <tree> 和 %type <tree> ：定义了一系列的标记（token）和类型。<tree>指明这些标记和非终结符将使用 %union定义的 tree类型。

语法规则和动作

• project 规则：定义了整个程序的最高层结构。它指定了程序由一个 main_function组成。匹配到此规则时，将执行大括号中的代码，用于构建抽象语法树的根节点。
• main_function 规则：定义了主函数的语法结构。它匹配 VOID MAIN '(' ')' '{' sentence '}'这样的模式，并构建一个表示主函数的语法树节点。

具体的规则和动作

• sentence 和 statement 规则：定义了程序中的句子和语句的结构。这些规则负责匹配更小的代码块，如变量声明、表达式和控制流语句，并将它们组合成更大的结构。
• expression 规则：定义了各种表达式的语法，包括算术表达式、关系表达式和逻辑表达式。每个表达式规则都会构建相应的语法树节点。

错误处理和主函数

• yyerror 函数：在解析过程中遇到错误时被调用，打印出错误信息和发生错误的行号。
• main 函数：设置输入输出文件，初始化全局变量，启动解析过程，并在解析完成后进行清理。

总结

这个 Bison 文件定义了一个编程语言（可能是类似C语言的某种语言）的语法规则和结构。它利用 Bison 的语法定义语言的结构，并在符合特定规则时构建抽象语法树（AST）。这个 AST 是进一步进行语义分析和代码生成的基础。整个文件涵盖了从最基本的元素（如变量、表达式）到高级结构（如函数和控制流语句）的构建过程。