现在已经学会了Bison和Flex部分（没学会的看，学编译器第一天和第二天），那么我们开始实战吧！要求做一个编译器
PS::存稿发错了，将错就错吧， 看第五天和第四天的会简单点，都是偏实战的系列。 这个会复杂一丢丢
- [x] 词法分析
- [x] 语法分析
- [ ] 类型检查
- [ ] 代码优化
- [ ] 生成目标代码
在这段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 和给定的语法规则进行语法解析。
%{
#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中。这是编译器处理源程序的第一步，为后续的语法分析，语义分析等阶段提供了基础数据。
读前须知:
在这段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;
}
"tree.h", "hashMap.h", 和 "inner.h"。同时声明了外部函数和变量，如 yylex()（词法分析函数），yyerror()（错误处理函数），以及行号变量 yylineno。hashMap（用作符号表），scope（跟踪当前作用域），以及 root和 head（用于构建和管理抽象语法树）。tree是一个指向 Tree结构的指针。这用于在不同的规则之间传递复杂的数据结构。<tree> 和 %type <tree> ：定义了一系列的标记（token）和类型。<tree>指明这些标记和非终结符将使用 %union定义的 tree类型。main_function组成。匹配到此规则时，将执行大括号中的代码，用于构建抽象语法树的根节点。VOID MAIN '(' ')' '{' sentence '}'这样的模式，并构建一个表示主函数的语法树节点。这个 Bison 文件定义了一个编程语言（可能是类似C语言的某种语言）的语法规则和结构。它利用 Bison 的语法定义语言的结构，并在符合特定规则时构建抽象语法树（AST）。这个 AST 是进一步进行语义分析和代码生成的基础。整个文件涵盖了从最基本的元素（如变量、表达式）到高级结构（如函数和控制流语句）的构建过程。