个人中心
gpt4 book ai didi

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

转载 作者：撒哈拉 更新时间：2025-01-13 22:40:47 57 4
gpt4 key购买 nike

1.工具简单介绍 。

Flex 和 Bison 是编译器开发中常用的两个工具，分别用于生成词法分析器和语法分析器。它们通常一起使用，共同完成源代码的词法分析和语法分析工作.

Flex

Flex通过读取一个规则文件（通常是.l文件），这个文件中定义了一系列的模式和对应的动作。模式用于匹配输入文本中的特定字符序列，动作则是当匹配成功时要执行的操作。Flex会根据这些规则生成一个词法分析器的C代码，这个生成的词法分析器能够识别输入文本中的词法单元，并执行相应的动作，如返回一个token给语法分析器.

输入文件：以 .l 为扩展名，包含三个主要部分:

头部定义部分：定义正则表达式和宏。 规则部分：定义词法规则和相应的动作。 用户代码部分：定义用户自定义的函数和全局变量.

格式如下:

定义部分 %% 识别规则 %% 用户代码部分 。

输出文件：通过对源文件的扫描自动生成相应的词法分析函数yylex()， 生成一个 C 源文件，后缀为.yy.c，其中包含词法分析器的实现代码 .

定义部分:

位于 Flex 文件的顶部，通常用于定义全局变量、包含头文件等，以 %{ 开始，以 %} 结束.

如 。

%{
#include <stdio.h>
#include <stdlib.h>
%}

识别规则:

定义了词法规则和相应的动作。每个规则由一个模式（正则表达式）和一个动作（C 语言代码）组成.

其中此次可以会用到flex提供的2个全局变量： yytext：刚刚匹配到的字符串 yyleng：刚刚匹配到的字符串的长度 。

{IDENT} { printf("IDENTIFIER: %s\n", yytext); }
{DIGIT}+ { printf("INTEGER: %s\n", yytext); }
"+" { printf("PLUS\n"); }
"-" { printf("MINUS\n"); }
"*" { printf("MULTIPLY\n"); }
"/" { printf("DIVIDE\n"); }
\n { return 0; }

用户代码部分:

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

int yywrap() { return 1; } 。

Bison： Bison是一个语法分析器生成器。它用于生成语法分析器程序，语法分析器的任务是根据语法规则对词法分析器返回的词法单元序列进行分析，构建语法树等结构，从而实现对输入文本（如程序代码）的语义理解.

Bison读取一个语法规则文件（通常是.y文件），这个文件中定义了语法规则以及对应的语义动作。语法规则描述了输入文本的结构，例如如何由词法单元组成语句等。语义动作则是在语法规则匹配成功时执行的操作，如构建抽象语法树（AST）节点等。Bison根据这些规则生成一个语法分析器的C代码，这个语法分析器能够对词法分析器返回的词法单元序列进行分析，并执行语义动作.

输入文件：以 .y 为扩展名，包含三个主要部分:

头部定义部分：定义标记、类型、先决条件等。 规则部分：定义语法规则和相应的动作。 用户代码部分：定义用户自定义的函数和全局变量.

输出文件：生成一个后缀为 .tab.c 的 C 文件，其中包含了根据语法规则生成的代码，以及一个头文件后缀为 .tab.h，包含标记的定义.

2.代码逻辑解释 。

.l文件:

%{
#include "parser.tab.h"
#include <string.h>
#include <stdlib.h>
%}

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

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

%%

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

%%

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

用户代码部分就写了一个yywrap就不多赘述了.

.y文件:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 符号表：存储变量名和值
#define MAX_VARS 100
typedef struct {
    char *name;
    int value;
} Variable;

Variable symbol_table[MAX_VARS];
int symbol_count = 0;

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

void set_variable_value(const char *name, int value) {
    // 检查符号表中是否已有该变量
    for (int i = 0; i < symbol_count; i++) {
        if (strcmp(symbol_table[i].name, name) == 0) {
            symbol_table[i].value = value;
            return;
        }
    }
    // 如果没有，插入新变量
    symbol_table[symbol_count].name = strdup(name);
    symbol_table[symbol_count].value = value;
    symbol_count++;
}

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

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

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


int yylex(void);

声明 Flex 生成的词法分析器函数.

// 定义抽象语法树节点
typedef enum {
    NODE_NUMBER,
    NODE_IDENTIFIER,
    NODE_PLUS,
    NODE_MINUS,
    NODE_MULTIPLY,
    NODE_DIVIDE,
    NODE_ASSIGN,
    NODE_PAREN
} NodeType;

typedef struct ASTNode {
    NodeType type;
    int value; // 用于存储数字
    char *name; // 用于存储变量名
    struct ASTNode *left;
    struct ASTNode *right;
} ASTNode;

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

ASTNode* createNode(NodeType type, int value, char *name, ASTNode *left, ASTNode *right) {
    ASTNode *node = (ASTNode*)malloc(sizeof(ASTNode));
    node->type = type;
    node->value = value;
    node->name = name;
    node->left = left;
    node->right = right;
    return node;
}

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

int evaluateNode(ASTNode *node) {
    if (node == NULL) return 0;
    switch (node->type) {
        case NODE_NUMBER:
            return node->value;
        case NODE_IDENTIFIER:
            return get_variable_value(node->name);
        case NODE_PLUS:
            return evaluateNode(node->left) + evaluateNode(node->right);
        case NODE_MINUS:
            return evaluateNode(node->left) - evaluateNode(node->right);
        case NODE_MULTIPLY:
            return evaluateNode(node->left) * evaluateNode(node->right);
        case NODE_DIVIDE:
            return evaluateNode(node->left) / evaluateNode(node->right);
        case NODE_ASSIGN:
            return node->right->value;
        case NODE_PAREN:
            return evaluateNode(node->left);
        default:
            return 0;
    }
}

evaluateNode：计算 AST 节点的值.

void printAST(ASTNode *node, int level) {
    if (node == NULL) return;
    for (int i = 0; i < level; i++) printf("  ");
    switch (node->type) {
        case NODE_NUMBER:
            printf("Number: %d\n", node->value);
            break;
        case NODE_IDENTIFIER:
            printf("Identifier: %s\n", node->name);
            break;
        case NODE_PLUS:
            printf("Plus\n");
            break;
        case NODE_MINUS:
            printf("Minus\n");
            break;
        case NODE_MULTIPLY:
            printf("Multiply\n");
            break;
        case NODE_DIVIDE:
            printf("Divide\n");
            break;
        case NODE_ASSIGN:
            printf("Assign\n");
            break;
        case NODE_PAREN:
            printf("Paren\n");
            break;
    }
    printAST(node->left, level + 1);
    printAST(node->right, level + 1);
}

void printSymbolTable() {
    printf("Symbol Table:\n");
    for (int i = 0; i < symbol_count; i++) {
        printf("%s = %d\n", symbol_table[i].name, symbol_table[i].value);
    }
}

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

%union {
    int intVal;
    char *strVal;
    struct ASTNode *astNode;
}

%token <intVal> NUMBER
%token <strVal> IDENTIFIER
%token PLUS MINUS MULTIPLY DIVIDE 
%token LPAREN RPAREN EOL ASSIGN
%type <astNode> exp term factor program

%right ASSIGN
%left PLUS MINUS
%left MULTIPLY DIVIDE
%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指换行符不结合.

program:
      exp EOL { 
          $$ = $1; 
          $$->value = evaluateNode($1); 
          printf("Result: %d\n", $$->value); 
          printAST($1, 0); 
      }
    | program exp EOL { 
          $$ = $2; 
          $$->value = evaluateNode($2); 
          printf("Result: %d\n", $$->value); 
          printAST($2, 0); 
      }
    ;

exp     : term { $$ = $1; $$->value = evaluateNode($1); }
        | exp PLUS term { 
            $$ = createNode(NODE_PLUS, 0, NULL, $1, $3); 
            $$->value = evaluateNode($1) + evaluateNode($3); 
        }
        | exp MINUS term { 
            $$ = createNode(NODE_MINUS, 0, NULL, $1, $3); 
            $$->value = evaluateNode($1) - evaluateNode($3); 
        }
        | IDENTIFIER ASSIGN exp {
            set_variable_value($1, evaluateNode($3)); 
            $$ = createNode(NODE_ASSIGN, 0, strdup($1), NULL, $3);
            $$->value = $3->value;
        }
        ;

term    : factor { $$ = $1; $$->value = evaluateNode($1); }
        | term MULTIPLY factor { 
            $$ = createNode(NODE_MULTIPLY, 0, NULL, $1, $3); 
            $$->value = evaluateNode($1) * evaluateNode($3); 
        }
        | term DIVIDE factor { 
            $$ = createNode(NODE_DIVIDE, 0, NULL, $1, $3); 
            $$->value = evaluateNode($1) / evaluateNode($3); 
        }
        ;

factor  : NUMBER { $$ = createNode(NODE_NUMBER, $1, NULL, NULL, NULL); }
        | IDENTIFIER { 
            $$ = createNode(NODE_IDENTIFIER, get_variable_value($1), strdup($1), NULL, NULL); 
        }
        | LPAREN exp RPAREN { 
            $$ = createNode(NODE_PAREN, 0, NULL, $2, NULL); 
            $$->value = evaluateNode($2); 
        }
        ;

这部分代码定义了输入文本的结构和对应的语义动作.

就拿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）.

int main() {
    printf("Enter expression: \n");
    yyparse();
    printSymbolTable();
    return 0;
}

主函数好像也没啥说的 。

3.最终代码及效果 。

.l文件 。

%{
#include "parser.tab.h"
#include <string.h>
#include <stdlib.h>
%}

%%

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

%%

int yywrap()
{
    return 1;
}

.y文件 。

%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 符号表：存储变量名和值
#define MAX_VARS 100
typedef struct {
    char *name;
    int value;
} Variable;

Variable symbol_table[MAX_VARS];
int symbol_count = 0;

void set_variable_value(const char *name, int value) {
    // 检查符号表中是否已有该变量
    for (int i = 0; i < symbol_count; i++) {
        if (strcmp(symbol_table[i].name, name) == 0) {
            symbol_table[i].value = value;
            return;
        }
    }
    // 如果没有，插入新变量
    symbol_table[symbol_count].name = strdup(name);
    symbol_table[symbol_count].value = value;
    symbol_count++;
}

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

void yyerror(const char *s) {
    fprintf(stderr, "error: %s\n", s);
}

int yylex(void);

// 定义抽象语法树节点
typedef enum {
    NODE_NUMBER,
    NODE_IDENTIFIER,
    NODE_PLUS,
    NODE_MINUS,
    NODE_MULTIPLY,
    NODE_DIVIDE,
    NODE_ASSIGN,
    NODE_PAREN
} NodeType;

typedef struct ASTNode {
    NodeType type;
    int value; // 用于存储数字
    char *name; // 用于存储变量名
    struct ASTNode *left;
    struct ASTNode *right;
} ASTNode;

ASTNode* createNode(NodeType type, int value, char *name, ASTNode *left, ASTNode *right) {
    ASTNode *node = (ASTNode*)malloc(sizeof(ASTNode));
    node->type = type;
    node->value = value;
    node->name = name;
    node->left = left;
    node->right = right;
    return node;
}

int evaluateNode(ASTNode *node) {
    if (node == NULL) return 0;
    switch (node->type) {
        case NODE_NUMBER:
            return node->value;
        case NODE_IDENTIFIER:
            return get_variable_value(node->name);
        case NODE_PLUS:
            return evaluateNode(node->left) + evaluateNode(node->right);
        case NODE_MINUS:
            return evaluateNode(node->left) - evaluateNode(node->right);
        case NODE_MULTIPLY:
            return evaluateNode(node->left) * evaluateNode(node->right);
        case NODE_DIVIDE:
            return evaluateNode(node->left) / evaluateNode(node->right);
        case NODE_ASSIGN:
            return node->right->value;
        case NODE_PAREN:
            return evaluateNode(node->left);
        default:
            return 0;
    }
}

void printAST(ASTNode *node, int level) {
    if (node == NULL) return;
    for (int i = 0; i < level; i++) printf("  ");
    switch (node->type) {
        case NODE_NUMBER:
            printf("Number: %d\n", node->value);
            break;
        case NODE_IDENTIFIER:
            printf("Identifier: %s\n", node->name);
            break;
        case NODE_PLUS:
            printf("Plus\n");
            break;
        case NODE_MINUS:
            printf("Minus\n");
            break;
        case NODE_MULTIPLY:
            printf("Multiply\n");
            break;
        case NODE_DIVIDE:
            printf("Divide\n");
            break;
        case NODE_ASSIGN:
            printf("Assign\n");
            break;
        case NODE_PAREN:
            printf("Paren\n");
            break;
    }
    printAST(node->left, level + 1);
    printAST(node->right, level + 1);
}

void printSymbolTable() {
    printf("Symbol Table:\n");
    for (int i = 0; i < symbol_count; i++) {
        printf("%s = %d\n", symbol_table[i].name, symbol_table[i].value);
    }
}

%}

%union {
    int intVal;
    char *strVal;
    struct ASTNode *astNode;
}

%token <intVal> NUMBER
%token <strVal> IDENTIFIER
%token PLUS MINUS MULTIPLY DIVIDE 
%token LPAREN RPAREN EOL ASSIGN
%type <astNode> exp term factor program

%right ASSIGN
%left PLUS MINUS
%left MULTIPLY DIVIDE
%nonassoc EOL

%%

program:
      exp EOL { 
          $$ = $1; 
          $$->value = evaluateNode($1); 
          printf("Result: %d\n", $$->value); 
          printAST($1, 0); 
      }
    | program exp EOL { 
          $$ = $2; 
          $$->value = evaluateNode($2); 
          printf("Result: %d\n", $$->value); 
          printAST($2, 0); 
      }
    ;

exp     : term { $$ = $1; $$->value = evaluateNode($1); }
        | exp PLUS term { 
            $$ = createNode(NODE_PLUS, 0, NULL, $1, $3); 
            $$->value = evaluateNode($1) + evaluateNode($3); 
        }
        | exp MINUS term { 
            $$ = createNode(NODE_MINUS, 0, NULL, $1, $3); 
            $$->value = evaluateNode($1) - evaluateNode($3); 
        }
        | IDENTIFIER ASSIGN exp {
            set_variable_value($1, evaluateNode($3)); 
            $$ = createNode(NODE_ASSIGN, 0, strdup($1), NULL, $3);
            $$->value = $3->value;
        }
        ;

term    : factor { $$ = $1; $$->value = evaluateNode($1); }
        | term MULTIPLY factor { 
            $$ = createNode(NODE_MULTIPLY, 0, NULL, $1, $3); 
            $$->value = evaluateNode($1) * evaluateNode($3); 
        }
        | term DIVIDE factor { 
            $$ = createNode(NODE_DIVIDE, 0, NULL, $1, $3); 
            $$->value = evaluateNode($1) / evaluateNode($3); 
        }
        ;

factor  : NUMBER { $$ = createNode(NODE_NUMBER, $1, NULL, NULL, NULL); }
        | IDENTIFIER { 
            $$ = createNode(NODE_IDENTIFIER, get_variable_value($1), strdup($1), NULL, NULL); 
        }
        | LPAREN exp RPAREN { 
            $$ = createNode(NODE_PAREN, 0, NULL, $2, NULL); 
            $$->value = evaluateNode($2); 
        }
        ;

%%

int main() {
    printf("Enter expression: \n");
    yyparse();
    printSymbolTable();
    return 0;
}

使用方法： 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 然后输入你的表达式，按回车键结束输入。编译器会解析表达式并输出结果.

运行截图:

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

最后此篇关于一篇解决编译原理大作业，基于Flex、Bison设计编译器（含语法分析树和符号表）的文章就讲到这里了,如果你想了解更多关于一篇解决编译原理大作业，基于Flex、Bison设计编译器（含语法分析树和符号表）的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

57 4 0
文章推荐： 推荐4款基于.NET开源、功能强大的CMS建站系统
文章推荐： G1原理—6.G1垃圾回收过程之FullGC
文章推荐： 如何修改Docker和DockerCompose默认占用的网段
文章推荐： 【事件分析】20250112-Usual赎回机制调整事件
撒哈拉
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com