基于C语言设计符号表【100011680】

# 基于C语言设计符号表 ## c-语言的语法描述  ## 系统设计 ### 符号表的实现 符号表采用了哈希表的形式，可以方便地查找、插入和删除，但是问题也随之而来，就是符号的作用于较难跟踪。很有可能同一名称的变量在不同作用于出现，如果孤立地对待每一个变量便会出现变量冲突。因此的符号表将作用域做了栈式处理。再将栈中每一个元素，即每一个作用域做延伸，对每一个作用域建立一个哈希表，将范围缩小。这样一来可以对每一个变量框在一个作用域中进行跟踪。 ### 中间代码生成 的中间代码生成运用一遍扫描的方法自下而上归约，但是和课本的方法有出入，进行了一些改变。首先，建立一个链表存储所有的生成的四元式，每个四元式的本质是一个结构体。其中，在对if-else或是while这种需要回填的部分处理时，先对判断条件进行判断，结果存在一个临时变量`t`之中，这个变量的值非0即1. 当面临if语句规约时，判断的是`t`的值，真出口就是继续执行的下一条语句，执行完语句之后，生成了又一个临时变量L，并且新增一个操作叫做`label`，它用来指示整个if-else语句的结尾，这个label四元式是在控制语句的结尾，当生成`（label，L2，-，-）`的同时，顺序查找四元式链表中`j_if_false`后紧跟的`（j,-,-,-）`，并将其填为`（j,L2,-,-）`，代表无条件跳转到L2。 对于假出口的处理同理，只不过是在else语句开始之前就生成一个`（label，L1，-，-）`，记下标号，并且在生成之后顺序查找四元式链表，找到`j_if_false`开头的代码进行回填。这样，真假出口的回填就完成了。其他的四元式根据不同节点的类型直接生成不同的四元式，最后将四元式链表输出到文件当中即可  ## 系统的总体结构 结构框图如图所示，共分为五大部分以及两个辅佐部分，五大部分为词法分析、语法分析、建立符号表、类型检查和中间代码，辅佐部分为符号表和语法树。  ### 主要功能模块的设计 **词法分析和语法分析：**利用flex & bison工具实现，在`cminus.l`文件中写好词法规则和`getToken`函数，在`cminus.y`文件中写好BNF语法和其他相关函数即可，flex和bison可以帮助生成`lex.yy.c`文件和`.tab.`文件。 **语义分析：**生成语法分析树和符号表，借助这两个数据结构分析语义。 **中间代码生成：**通过一遍扫描和回填技术实现中间代码生成。 ## 系统运行流程 C-minus编译器运行于Linux系统。编译完成后即可运行，运行命令 ```shell ./{编译好后的程序的名字} ./{目标程序的位置} ``` 结果存放于同名txt文件中 ## 系统实现 ### 系统主要函数说明（主要功能、输入\输出、实现思想） #### CMINUS.L 这一文件的主要功能为flex分析器的文件。第一部分为定义，flex工具在处理这一部分的时候，会将第一部分的所有代码原封不动的插入到 lex.yy.c（词法分析代码）中，在这一部分中插入了程序需要用到的头文件等内容。第二部分是词法规则部分：正则表达式+代码片段。当匹配相对应的正则表达式时，这些代码片段就会被执行。的代码片段为一个单词符号的编码。最后一个部分包括辅助函数，它们用于在第2个部分被调用且不在任何地方被定义的辅助程序。 #### CMINUS.Y 这一文件的主要功能是产生语法分析代码。首先是定义部分：定义部分包括bison需要用来建立分析程序的有关记号、数据类型以及文法规则的信息，还包括了一些头文件。规则部分：包括修改的BNF格式中的文法规则以及将在识别出相关的文法规则时被执行的C代码中的动作。根据每一条产生式执行不同的语义动作，例如生成节点、赋上相应属性等等。最后是用户自定义函数部分，定义了几个插入节点的函数，可以和语义动作对应起来。最后这个文件会被建立成两个`.tab.`程序，实现语法分析和语法树的建立。 #### BUILDSYMTAB Cminus的语义分析器在`analyze.c`和`symtab.c`中，其对应的主要功能，`analyse.c`是用于语义分析本身，而`symtab.c`则是用于生成其对应的符号表。 进入语义分析部分的代码在main.c中： ```c # if !NO_ANALYZE if (! Error) { if (TraceAnalyze) fprintf(listing, "\nBuilding the symbol table...\n"); buildSymtab(syntaxTree); if (TraceAnalyze) fprintf(listing, "\nChecking type...\n"); typeCheck(syntaxTree); if (TraceAnalyze) fprintf(listing, "\nType check completed!\n"); } ``` 在语义分析之前，编译器最开始的输入是一段代码，经过词法分析，输出的是词法单元，从而被语法分析单元所识别；语法分析的输入是一个个词法单元，通过分析这些词法单元之间的逻辑，利用递归下降等方法，形成一棵语法树，并将语法树的根结点存储在一个TreeNode类中，从而通过根结点就可以实现对于整个语法树的遍历（一般是前序遍历）；之后，来到了语义分析部分，语义分析的输入是一个语法树，这里我的输入是根结点；语义分析的输出，则是符号表和语法报错信息。 符号表的意义在于，分析代码中所有的声明，比如变量函数等内容；而语法报错信息，则会通过语法树结点关系，检测相邻词法单元是否符合文法规则：比如，int 1和int a两种输入，在语法分析阶段均可通过，但是在语义分析阶段，int 1会被识别为一个错误，因为根据语法规则，int是一个声明，声明后面只能跟着一个变量名ID，而词法单元1的属性是NUM，int后面是不允许接着一个NUM的。 函数buildSymtab构造符号，通过语法树的遍历构建。 ```c /* Function buildSymtab constructs the symbol * table by preorder traversal of the syntax tree */ void buildSymtab(TreeNode * syntaxTree) { globalScope = sc_create((char *) "ESCOPO_GLOBAL"); sc_push(globalScope); traverse(syntaxTree, insertNode, afterInsertNode); sc_pop(); sys_free(); if(mainDeclaration == FALSE) { fprintf(listing, "Declaration Error: Undeclared main function\n"); return; } if (TraceAnalyze) { fprintf(listing,"\nSymbol Table:\n"); printSymTab(listing); } } ``` 该函数共分为四个步骤，首先调用sc_create（）函数创建一个作用域栈，作用域栈用于储存一个符号的作用域，如果给出作用域名称作为参数，它将分配内存并填写每个属性。在初始化的时候，如果是全局变量，则它就是最大的全局作用域，如果不是，则把指针设置为该作用域所属的较大作用域的父作用域。 l例如，名为main的作用域将global作为其父作用域。 在main中创建另一个作用域时，它以相同的方式堆叠在栈上。 当main结束时（遇到复合语句时），main作用域弹出并查看全局作用域中的其余TreeNodes。 ```c Scope sc_create(char * funcName) { Scope newScope = (Scope) malloc(sizeof(struct ScopeRec)); newScope->funcName = funcName; newScope->tamanhoBlocoMemoria = 0; if(!strcmp(funcName, "ESCOPO_GLOBAL")) { newScope->parent = NULL; } else { newScope->parent