一篇办理编译原理大作业，基于Flex、Bison设计编译器（含语法分析树和符号 ...

1.工具简朴介绍
Flex 和 Bison 是编译器开发中常用的两个工具，分别用于天生词法分析器和语法分析器。它们通常一起使用，共同完成源代码的词法分析和语法分析工作。
Flex:
Flex通过读取一个规则文件（通常是.l文件），这个文件中定义了一系列的模式和对应的动作。模式用于匹配输入文本中的特定字符序列，动作则是当匹配成功时要实行的操作。Flex会根据这些规则天生一个词法分析器的C代码，这个天生的词法分析器可以或许辨认输入文本中的词法单元，并实行相应的动作，如返回一个token给语法分析器。
输入文件：以 .l 为扩展名，包罗三个主要部分：
头部定义部分：定义正则表达式和宏。
规则部分：定义词法规则和相应的动作。
用户代码部分：定义用户自定义的函数和全局变量。
格式如下：
定义部分
%%
辨认规则
%%
用户代码部分
输出文件：通过对源文件的扫描自动天生相应的词法分析函数yylex()， 天生一个 C 源文件，后缀为.yy.c，其中包罗词法分析器的实现代码                             。
定义部分：
位于 Flex 文件的顶部，通常用于定义全局变量、包罗头文件等，以 %{ 开始，以 %} 结束。
如

1. %{
2. #include <stdio.h>
3. #include <stdlib.h>
4. %}

复制代码

辨认规则：
定义了词法规则和相应的动作。每个规则由一个模式（正则表达式）和一个动作（C 语言代码）构成。
其中此次可以会用到flex提供的2个全局变量：
yytext：刚刚匹配到的字符串
yyleng：刚刚匹配到的字符串的长度

1. {IDENT} { printf("IDENTIFIER: %s\n", yytext); }
2. {DIGIT}+ { printf("INTEGER: %s\n", yytext); }
3. "+" { printf("PLUS\n"); }
4. "-" { printf("MINUS\n"); }
5. "*" { printf("MULTIPLY\n"); }
6. "/" { printf("DIVIDE\n"); }
7. \n { return 0; }

复制代码

用户代码部分：
用户代码部分位于规则部分之后，包罗用户自定义的c语言函数，以 %% 开始，会直接复制到 lex.yy.c的C语言文件中。如可以定义一些辅助函数。比方yywrap()函数，这个函数在词法分析器读取完输入后被调用。返回1表示没有更多的输入了，这在处理单个输入文件时很常见。

1. int yywrap()
2. {
3.     return 1;
4. }

复制代码

Bison：
Bison是一个语法分析器天生器。它用于天生语法分析器程序，语法分析器的任务是根据语法规则对词法分析器返回的词法单元序列举行分析，构建语法树等结构，从而实现对输入文本（如程序代码）的语义明白。
Bison读取一个语法规则文件（通常是.y文件），这个文件中定义了语法规则以及对应的语义动作。语法规则描述了输入文本的结构，比方怎样由词法单元构成语句等。语义动作则是在语法规则匹配成功时实行的操作，如构建抽象语法树（AST）节点等。Bison根据这些规则天生一个语法分析器的C代码，这个语法分析器可以或许对词法分析器返回的词法单元序列举行分析，并实行语义动作。
输入文件：以 .y 为扩展名，包罗三个主要部分：
头部定义部分：定义标记、类型、先决条件等。
规则部分：定义语法规则和相应的动作。
用户代码部分：定义用户自定义的函数和全局变量。
输出文件：天生一个后缀为 .tab.c 的 C 文件，其中包罗了根据语法规则天生的代码，以及一个头文件后缀为 .tab.h，包罗标记的定义。
2.代码逻辑解释
.l文件：

• 
  

1. %{
2. #include "parser.tab.h"
3. #include <string.h>
4. #include <stdlib.h>
5. %}

复制代码

这里parser.tab.h是Bison天生的头文件，它包罗了词法单元的定义等信息，string.h和stdlib.h提供了字符串操作和动态内存分配等功能。

• 
  

定义了一系列的模式和动作。模式可以是简朴的字符、字符类、正则表达式等。比方[0-9]+用于匹配一个或多个数字字符，[a-zA-Z][a-zA-Z0-9]*用于匹配以字母开头，后跟任意个字母或数字字符的字符串。动作是花括号困绕的C代码块。

1. %%
3. [0-9]+        { yylval.intVal = atoi(yytext); return NUMBER; }
4. [a-zA-Z][a-zA-Z0-9]* { yylval.strVal = strdup(yytext); return IDENTIFIER; }  // 变量
5. "\n"      { return EOL; }
6. [ \t]   { /* 忽略空白字符 */ }
7. "+"          { return PLUS; }
8. "-"          { return MINUS; }
9. "*"          { return MULTIPLY; }
10. "/"          { return DIVIDE; }
11. "("          { return LPAREN; }
12. ")"          { return RPAREN; }
13. "="          { return ASSIGN; }
14. .            { fprintf(stderr, "lexical error at line %d: unexpected character '%s'\n", yylineno, yytext); return yytext[0]; }
16. %%

复制代码

就拿[0-9]+解释。这里yylval是一个全局变量，用于转达词法单元的值给语法分析器。intVal是yylval的成员，用于存储整数值。atoi(yytext)将匹配到的数字字符串转换为整数。return NUMBER;表示返回一个名为NUMBER的词法单元给语法分析器。

• 
  

用户代码部分就写了一个yywrap就不多赘述了。
.y文件：

• 
  

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <string.h>
5. // 符号表：存储变量名和值
6. #define MAX_VARS 100
7. typedef struct {
8.     char *name;
9.     int value;
10. } Variable;
12. Variable symbol_table[MAX_VARS];
13. int symbol_count = 0;

复制代码

引用了C语言的一些库，定义了结构体、数组和一个变量；分别存储变量名和值、存储结构体和已存储的变量数目

• 
  

1. void set_variable_value(const char *name, int value) {
2.     // 检查符号表中是否已有该变量
3.     for (int i = 0; i < symbol_count; i++) {
4.         if (strcmp(symbol_table[i].name, name) == 0) {
5.             symbol_table[i].value = value;
6.             return;
7.         }
8.     }
9.     // 如果没有，插入新变量
10.     symbol_table[symbol_count].name = strdup(name);
11.     symbol_table[symbol_count].value = value;
12.     symbol_count++;
13. }

复制代码

设置变量的值。如果变量已存在，则更新其值；如果不存在，则插入新变量。

• 
  

1. int get_variable_value(const char *name) {
2.     // 查找变量值
3.     for (int i = 0; i < symbol_count; i++) {
4.         if (strcmp(symbol_table[i].name, name) == 0) {
5.             return symbol_table[i].value;
6.         }
7.     }
8.     // 如果未找到变量，报错并退出
9.     printf("Error: Undefined variable %s\n", name);
10.     exit(1);
11. }

复制代码

获取变量的值。如果变量不存在，则报错并退出。

• 
  

1. int yylex(void);

复制代码

声明 Flex 天生的词法分析器函数。

1. // 定义抽象语法树节点
2. typedef enum {
3.     NODE_NUMBER,
4.     NODE_IDENTIFIER,
5.     NODE_PLUS,
6.     NODE_MINUS,
7.     NODE_MULTIPLY,
8.     NODE_DIVIDE,
9.     NODE_ASSIGN,
10.     NODE_PAREN
11. } NodeType;
13. typedef struct ASTNode {
14.     NodeType type;
15.     int value; // 用于存储数字
16.     char *name; // 用于存储变量名
17.     struct ASTNode *left;
18.     struct ASTNode *right;
19. } ASTNode;

复制代码

NodeType：定义一个枚举类型，表示 AST 节点的类型。
ASTNode：定义一个结构体，表示 AST 节点。

• 
  

1. ASTNode* createNode(NodeType type, int value, char *name, ASTNode *left, ASTNode *right) {
2.     ASTNode *node = (ASTNode*)malloc(sizeof(ASTNode));
3.     node->type = type;
4.     node->value = value;
5.     node->name = name;
6.     node->left = left;
7.     node->right = right;
8.     return node;
9. }

复制代码

createNode：创建一个新的 AST 节点。

• 
  

1. int evaluateNode(ASTNode *node) {
2.     if (node == NULL) return 0;
3.     switch (node->type) {
4.         case NODE_NUMBER:
5.             return node->value;
6.         case NODE_IDENTIFIER:
7.             return get_variable_value(node->name);
8.         case NODE_PLUS:
9.             return evaluateNode(node->left) + evaluateNode(node->right);
10.         case NODE_MINUS:
11.             return evaluateNode(node->left) - evaluateNode(node->right);
12.         case NODE_MULTIPLY:
13.             return evaluateNode(node->left) * evaluateNode(node->right);
14.         case NODE_DIVIDE:
15.             return evaluateNode(node->left) / evaluateNode(node->right);
16.         case NODE_ASSIGN:
17.             return node->right->value;
18.         case NODE_PAREN:
19.             return evaluateNode(node->left);
20.         default:
21.             return 0;
22.     }
23. }

复制代码

evaluateNode：计算 AST 节点的值。

• 
  

1. void printAST(ASTNode *node, int level) {
2.     if (node == NULL) return;
3.     for (int i = 0; i < level; i++) printf("  ");
4.     switch (node->type) {
5.         case NODE_NUMBER:
6.             printf("Number: %d\n", node->value);
7.             break;
8.         case NODE_IDENTIFIER:
9.             printf("Identifier: %s\n", node->name);
10.             break;
11.         case NODE_PLUS:
12.             printf("Plus\n");
13.             break;
14.         case NODE_MINUS:
15.             printf("Minus\n");
16.             break;
17.         case NODE_MULTIPLY:
18.             printf("Multiply\n");
19.             break;
20.         case NODE_DIVIDE:
21.             printf("Divide\n");
22.             break;
23.         case NODE_ASSIGN:
24.             printf("Assign\n");
25.             break;
26.         case NODE_PAREN:
27.             printf("Paren\n");
28.             break;
29.     }
30.     printAST(node->left, level + 1);
31.     printAST(node->right, level + 1);
32. }
34. void printSymbolTable() {
35.     printf("Symbol Table:\n");
36.     for (int i = 0; i < symbol_count; i++) {
37.         printf("%s = %d\n", symbol_table[i].name, symbol_table[i].value);
38.     }
39. }

复制代码

printAST：打印 AST 节点及其子节点。
printSymbolTable：打印符号表的内容。

• 
  

1. %union {
2.     int intVal;
3.     char *strVal;
4.     struct ASTNode *astNode;
5. }
7. %token <intVal> NUMBER
8. %token <strVal> IDENTIFIER
9. %token PLUS MINUS MULTIPLY DIVIDE
10. %token LPAREN RPAREN EOL ASSIGN
11. %type <astNode> exp term factor program
13. %right ASSIGN
14. %left PLUS MINUS
15. %left MULTIPLY DIVIDE
16. %nonassoc EOL

复制代码

%union：定义 yylval 的联合体类型，可以存储不同类型的数据。
intVal，用于存储整数值；
strVal，用于存储字符串值；
astNode，用于存储 AST 节点指针。
%token，声明词法单元及其类型。
NUMBER，整数，类型为 intVal；
IDENTIFIER，标识符，类型为 strVal；
PLUS、MINUS、MULTIPLY、DIVIDE、LPAREN、RPAREN、EOL、ASSIGN分别为操作符和特殊字符。
%type，声明语法规则的结果类型。
exp、term、factor、program：这些语法规则的结果类型为 astNode。
当然还得说明优先级和联合性。
%right ASSIGN指赋值运算符右联合；
%left PLUS MINUS指加减运算符左联合；
%left MULTIPLY DIVIDE指乘除运算符左联合；
%nonassoc EOL指换行符不联合。

• 
  

1. program:
2.       exp EOL {
3.           $$ = $1;
4.           $$->value = evaluateNode($1);
5.           printf("Result: %d\n", $$->value);
6.           printAST($1, 0);
7.       }
8.     | program exp EOL {
9.           $$ = $2;
10.           $$->value = evaluateNode($2);
11.           printf("Result: %d\n", $$->value);
12.           printAST($2, 0);
13.       }
14.     ;
16. exp     : term { $$ = $1; $$->value = evaluateNode($1); }
17.         | exp PLUS term {
18.             $$ = createNode(NODE_PLUS, 0, NULL, $1, $3);
19.             $$->value = evaluateNode($1) + evaluateNode($3);
20.         }
21.         | exp MINUS term {
22.             $$ = createNode(NODE_MINUS, 0, NULL, $1, $3);
23.             $$->value = evaluateNode($1) - evaluateNode($3);
24.         }
25.         | IDENTIFIER ASSIGN exp {
26.             set_variable_value($1, evaluateNode($3));
27.             $$ = createNode(NODE_ASSIGN, 0, strdup($1), NULL, $3);
28.             $$->value = $3->value;
29.         }
30.         ;
32. term    : factor { $$ = $1; $$->value = evaluateNode($1); }
33.         | term MULTIPLY factor {
34.             $$ = createNode(NODE_MULTIPLY, 0, NULL, $1, $3);
35.             $$->value = evaluateNode($1) * evaluateNode($3);
36.         }
37.         | term DIVIDE factor {
38.             $$ = createNode(NODE_DIVIDE, 0, NULL, $1, $3);
39.             $$->value = evaluateNode($1) / evaluateNode($3);
40.         }
41.         ;
43. factor  : NUMBER { $$ = createNode(NODE_NUMBER, $1, NULL, NULL, NULL); }
44.         | IDENTIFIER {
45.             $$ = createNode(NODE_IDENTIFIER, get_variable_value($1), strdup($1), NULL, NULL);
46.         }
47.         | LPAREN exp RPAREN {
48.             $$ = createNode(NODE_PAREN, 0, NULL, $2, NULL);
49.             $$->value = evaluateNode($2);
50.         }
51.         ;

复制代码

这部分代码定义了输入文本的结构和对应的语义动作。
就拿program 举例说明一下
这部分定义了程序的结构，一个程序可以是一个表达式后跟一个换行符，大概是一个程序后跟一个表达式和换行符。
exp EOL：
匹配：一个表达式后跟一个换行符。
语义动作：
$$ = $1;：将表达式的结果赋值给当前规则的结果。
$$->value = evaluateNode($1);：计算表达式的值并赋值给当前规则的结果。
printf("Result: %d\n", $$->value);：打印表达式的计算结果。
printAST($1, 0);：打印表达式的抽象语法树（AST）。
program exp EOL：
匹配：一个程序后跟一个表达式和换行符。
语义动作：
$$ = $2;：将表达式的结果赋值给当前规则的结果。
$$->value = evaluateNode($2);：计算表达式的值并赋值给当前规则的结果。
printf("Result: %d\n", $$->value);：打印表达式的计算结果。
printAST($2, 0);：打印表达式的抽象语法树（AST）。

• 
  

1. int main() {
2.     printf("Enter expression: \n");
3.     yyparse();
4.     printSymbolTable();
5.     return 0;
6. }

复制代码

主函数好像也没啥说的
3.终极代码及结果
.l文件

1. %{
2. #include "parser.tab.h"
3. #include <string.h>
4. #include <stdlib.h>
5. %}%%
7. [0-9]+        { yylval.intVal = atoi(yytext); return NUMBER; }
8. [a-zA-Z][a-zA-Z0-9]* { yylval.strVal = strdup(yytext); return IDENTIFIER; }  // 变量
9. "\n"      { return EOL; }
10. [ \t]   { /* 忽略空白字符 */ }
11. "+"          { return PLUS; }
12. "-"          { return MINUS; }
13. "*"          { return MULTIPLY; }
14. "/"          { return DIVIDE; }
15. "("          { return LPAREN; }
16. ")"          { return RPAREN; }
17. "="          { return ASSIGN; }
18. .            { fprintf(stderr, "lexical error at line %d: unexpected character '%s'\n", yylineno, yytext); return yytext[0]; }
20. %%int yywrap()
21. {
22.     return 1;
23. }

复制代码

.y文件

1. %{#include <stdio.h>
2. #include <stdlib.h>
3. #include <string.h>
5. // 符号表：存储变量名和值
6. #define MAX_VARS 100
7. typedef struct {
8.     char *name;
9.     int value;
10. } Variable;
12. Variable symbol_table[MAX_VARS];
13. int symbol_count = 0;void set_variable_value(const char *name, int value) {
14.     // 检查符号表中是否已有该变量
15.     for (int i = 0; i < symbol_count; i++) {
16.         if (strcmp(symbol_table[i].name, name) == 0) {
17.             symbol_table[i].value = value;
18.             return;
19.         }
20.     }
21.     // 如果没有，插入新变量
22.     symbol_table[symbol_count].name = strdup(name);
23.     symbol_table[symbol_count].value = value;
24.     symbol_count++;
25. }int get_variable_value(const char *name) {
26.     // 查找变量值
27.     for (int i = 0; i < symbol_count; i++) {
28.         if (strcmp(symbol_table[i].name, name) == 0) {
29.             return symbol_table[i].value;
30.         }
31.     }
32.     // 如果未找到变量，报错并退出
33.     printf("Error: Undefined variable %s\n", name);
34.     exit(1);
35. }void yyerror(const char *s) {    fprintf(stderr, "error: %s\n", s);}int yylex(void);// 定义抽象语法树节点
36. typedef enum {
37.     NODE_NUMBER,
38.     NODE_IDENTIFIER,
39.     NODE_PLUS,
40.     NODE_MINUS,
41.     NODE_MULTIPLY,
42.     NODE_DIVIDE,
43.     NODE_ASSIGN,
44.     NODE_PAREN
45. } NodeType;
47. typedef struct ASTNode {
48.     NodeType type;
49.     int value; // 用于存储数字
50.     char *name; // 用于存储变量名
51.     struct ASTNode *left;
52.     struct ASTNode *right;
53. } ASTNode;ASTNode* createNode(NodeType type, int value, char *name, ASTNode *left, ASTNode *right) {
54.     ASTNode *node = (ASTNode*)malloc(sizeof(ASTNode));
55.     node->type = type;
56.     node->value = value;
57.     node->name = name;
58.     node->left = left;
59.     node->right = right;
60.     return node;
61. }int evaluateNode(ASTNode *node) {
62.     if (node == NULL) return 0;
63.     switch (node->type) {
64.         case NODE_NUMBER:
65.             return node->value;
66.         case NODE_IDENTIFIER:
67.             return get_variable_value(node->name);
68.         case NODE_PLUS:
69.             return evaluateNode(node->left) + evaluateNode(node->right);
70.         case NODE_MINUS:
71.             return evaluateNode(node->left) - evaluateNode(node->right);
72.         case NODE_MULTIPLY:
73.             return evaluateNode(node->left) * evaluateNode(node->right);
74.         case NODE_DIVIDE:
75.             return evaluateNode(node->left) / evaluateNode(node->right);
76.         case NODE_ASSIGN:
77.             return node->right->value;
78.         case NODE_PAREN:
79.             return evaluateNode(node->left);
80.         default:
81.             return 0;
82.     }
83. }void printAST(ASTNode *node, int level) {
84.     if (node == NULL) return;
85.     for (int i = 0; i < level; i++) printf("  ");
86.     switch (node->type) {
87.         case NODE_NUMBER:
88.             printf("Number: %d\n", node->value);
89.             break;
90.         case NODE_IDENTIFIER:
91.             printf("Identifier: %s\n", node->name);
92.             break;
93.         case NODE_PLUS:
94.             printf("Plus\n");
95.             break;
96.         case NODE_MINUS:
97.             printf("Minus\n");
98.             break;
99.         case NODE_MULTIPLY:
100.             printf("Multiply\n");
101.             break;
102.         case NODE_DIVIDE:
103.             printf("Divide\n");
104.             break;
105.         case NODE_ASSIGN:
106.             printf("Assign\n");
107.             break;
108.         case NODE_PAREN:
109.             printf("Paren\n");
110.             break;
111.     }
112.     printAST(node->left, level + 1);
113.     printAST(node->right, level + 1);
114. }
116. void printSymbolTable() {
117.     printf("Symbol Table:\n");
118.     for (int i = 0; i < symbol_count; i++) {
119.         printf("%s = %d\n", symbol_table[i].name, symbol_table[i].value);
120.     }
121. }%}%union {
122.     int intVal;
123.     char *strVal;
124.     struct ASTNode *astNode;
125. }
127. %token <intVal> NUMBER
128. %token <strVal> IDENTIFIER
129. %token PLUS MINUS MULTIPLY DIVIDE
130. %token LPAREN RPAREN EOL ASSIGN
131. %type <astNode> exp term factor program
133. %right ASSIGN
134. %left PLUS MINUS
135. %left MULTIPLY DIVIDE
136. %nonassoc EOL%%program:
137.       exp EOL {
138.           $$ = $1;
139.           $$->value = evaluateNode($1);
140.           printf("Result: %d\n", $$->value);
141.           printAST($1, 0);
142.       }
143.     | program exp EOL {
144.           $$ = $2;
145.           $$->value = evaluateNode($2);
146.           printf("Result: %d\n", $$->value);
147.           printAST($2, 0);
148.       }
149.     ;
151. exp     : term { $$ = $1; $$->value = evaluateNode($1); }
152.         | exp PLUS term {
153.             $$ = createNode(NODE_PLUS, 0, NULL, $1, $3);
154.             $$->value = evaluateNode($1) + evaluateNode($3);
155.         }
156.         | exp MINUS term {
157.             $$ = createNode(NODE_MINUS, 0, NULL, $1, $3);
158.             $$->value = evaluateNode($1) - evaluateNode($3);
159.         }
160.         | IDENTIFIER ASSIGN exp {
161.             set_variable_value($1, evaluateNode($3));
162.             $$ = createNode(NODE_ASSIGN, 0, strdup($1), NULL, $3);
163.             $$->value = $3->value;
164.         }
165.         ;
167. term    : factor { $$ = $1; $$->value = evaluateNode($1); }
168.         | term MULTIPLY factor {
169.             $$ = createNode(NODE_MULTIPLY, 0, NULL, $1, $3);
170.             $$->value = evaluateNode($1) * evaluateNode($3);
171.         }
172.         | term DIVIDE factor {
173.             $$ = createNode(NODE_DIVIDE, 0, NULL, $1, $3);
174.             $$->value = evaluateNode($1) / evaluateNode($3);
175.         }
176.         ;
178. factor  : NUMBER { $$ = createNode(NODE_NUMBER, $1, NULL, NULL, NULL); }
179.         | IDENTIFIER {
180.             $$ = createNode(NODE_IDENTIFIER, get_variable_value($1), strdup($1), NULL, NULL);
181.         }
182.         | LPAREN exp RPAREN {
183.             $$ = createNode(NODE_PAREN, 0, NULL, $2, NULL);
184.             $$->value = evaluateNode($2);
185.         }
186.         ;%%int main() {
187.     printf("Enter expression: \n");
188.     yyparse();
189.     printSymbolTable();
190.     return 0;
191. }

复制代码

使用方法：
1.天生词法分析器：
使用 Flex 天生词法分析器的 C 代码。在终端中运行以下下令：
flex -o lex.yy.c name1.l
这里 name1.l 是你的 Flex 文件名，lex.yy.c 是天生的 C 代码文件。
2.天生语法分析器：
使用 Bison 天生语法分析器的 C 代码。在终端中运行以下下令
bison -d -o parser.tab.c name2.y
这里 name2.y 是你的 Bison 文件名，parser.tab.c 是天生的 C 代码文件，-d 选项会天生一个头文件 parser.tab.h，这个头文件包罗了词法单元的定义等信息。
3.编译天生的 C 代码
将天生的 C 代码文件编译成可实行文件。在终端中运行以下下令：
gcc lex.yy.c parser.tab.c -o name3
这里 name3 是你想要天生的可实行文件的名称。
步骤 4: 运行编译器
编译完成后，你可以运行天生的编译器来解析输入的表达式。在终端中运行以下下令：
./name3
然后输入你的表达式，按回车键结束输入。编译器会解析表达式并输出结果。
运行截图：

信赖看到这里的你，也是来自广州某大学的吧!

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。