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

2024-01-01 11:51:13

学习编译原理,写编译器(第六天)

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

目录

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(跟踪当前作用域),以及 roothead(用于构建和管理抽象语法树)。

符号和类型声明

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

语法规则和动作

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

具体的规则和动作

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

错误处理和主函数

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

总结

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

文章来源:https://blog.csdn.net/lixiemang8887/article/details/135275601
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。