基于C语言设计符号表

素颜马尾好姑娘i 2024-04-07 15:36 131阅读 0赞

基于C语言设计符号表

c-语言的语法描述

在这里插入图片描述

系统设计

符号表的实现

  1. 符号表采用了哈希表的形式，可以方便地查找、插入和删除，但是问题也随之而来，就是符号的作用于较难跟踪。很有可能同一名称的变量在不同作用于出现，如果孤立地对待每一个变量便会出现变量冲突。因此的符号表将作用域做了栈式处理。再将栈中每一个元素，即每一个作用域做延伸，对每一个作用域建立一个哈希表，将范围缩小。这样一来可以对每一个变量框在一个作用域中进行跟踪。

中间代码生成

  1. 的中间代码生成运用一遍扫描的方法自下而上归约，但是和课本的方法有出入，进行了一些改变。首先，建立一个链表存储所有的生成的四元式，每个四元式的本质是一个结构体。其中，在对if-else或是while这种需要回填的部分处理时，先对判断条件进行判断，结果存在一个临时变量`t`之中，这个变量的值非0即1.
  3. 当面临if语句规约时，判断的是`t`的值，真出口就是继续执行的下一条语句，执行完语句之后，生成了又一个临时变量L，并且新增一个操作叫做`label`，它用来指示整个if-else语句的结尾，这个label四元式是在控制语句的结尾，当生成`（label，L2，-，-）`的同时，顺序查找四元式链表中`j_if_false`后紧跟的`（j,-,-,-）`，并将其填为`（j,L2,-,-）`，代表无条件跳转到L2。
  5. 对于假出口的处理同理，只不过是在else语句开始之前就生成一个`（label，L1，-，-）`，记下标号，并且在生成之后顺序查找四元式链表，找到`j_if_false`开头的代码进行回填。这样，真假出口的回填就完成了。其他的四元式根据不同节点的类型直接生成不同的四元式，最后将四元式链表输出到文件当中即可

在这里插入图片描述

系统的总体结构

结构框图如图所示，共分为五大部分以及两个辅佐部分，五大部分为词法分析、语法分析、建立符号表、类型检查和中间代码，辅佐部分为符号表和语法树。

在这里插入图片描述

主要功能模块的设计

**词法分析和语法分析：**利用flex & bison工具实现，在cminus.l文件中写好词法规则和getToken函数，在cminus.y文件中写好BNF语法和其他相关函数即可，flex和bison可以帮助生成lex.yy.c文件和.tab.文件。

**语义分析：**生成语法分析树和符号表，借助这两个数据结构分析语义。

**中间代码生成：**通过一遍扫描和回填技术实现中间代码生成。

系统运行流程

C-minus编译器运行于Linux系统。编译完成后即可运行，运行命令

  1. ./{
  2.     编译好后的程序的名字}  ./{
  3.     目标程序的位置}

结果存放于同名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中：

  1. # if !NO_ANALYZE
  2.     if (! Error) {
  4.         if (TraceAnalyze) fprintf(listing, "\nBuilding the symbol table...\n");
  5.         buildSymtab(syntaxTree);
  6.         if (TraceAnalyze) fprintf(listing, "\nChecking type...\n");
  7.         typeCheck(syntaxTree);
  8.         if (TraceAnalyze) fprintf(listing, "\nType check completed!\n");
  9.     }

在语义分析之前，编译器最开始的输入是一段代码，经过词法分析，输出的是词法单元，从而被语法分析单元所识别；语法分析的输入是一个个词法单元，通过分析这些词法单元之间的逻辑，利用递归下降等方法，形成一棵语法树，并将语法树的根结点存储在一个TreeNode类中，从而通过根结点就可以实现对于整个语法树的遍历（一般是前序遍历）；之后，来到了语义分析部分，语义分析的输入是一个语法树，这里我的输入是根结点；语义分析的输出，则是符号表和语法报错信息。

符号表的意义在于，分析代码中所有的声明，比如变量函数等内容；而语法报错信息，则会通过语法树结点关系，检测相邻词法单元是否符合文法规则：比如，int 1和int a两种输入，在语法分析阶段均可通过，但是在语义分析阶段，int 1会被识别为一个错误，因为根据语法规则，int是一个声明，声明后面只能跟着一个变量名ID，而词法单元1的属性是NUM，int后面是不允许接着一个NUM的。

函数buildSymtab构造符号，通过语法树的遍历构建。

  1. /* Function buildSymtab constructs the symbol
  2.  * table by preorder traversal of the syntax tree
  3.  */
  4. void buildSymtab(TreeNode * syntaxTree) {
  6.     globalScope = sc_create((char *) "ESCOPO_GLOBAL");
  7.     sc_push(globalScope);
  8.     traverse(syntaxTree, insertNode, afterInsertNode);
  9.     sc_pop();
  10.     sys_free();
  11.     if(mainDeclaration == FALSE) {
  13.         fprintf(listing, "Declaration Error: Undeclared main function\n");
  14.         return;
  15.     }
  16.      if (TraceAnalyze) {
  18.         fprintf(listing,"\nSymbol Table:\n");
  19.         printSymTab(listing);
  20.       }
  21. }

该函数共分为四个步骤，首先调用sc_create（）函数创建一个作用域栈，作用域栈用于储存一个符号的作用域，如果给出作用域名称作为参数，它将分配内存并填写每个属性。在初始化的时候，如果是全局变量，则它就是最大的全局作用域，如果不是，则把指针设置为该作用域所属的较大作用域的父作用域。

l例如，名为main的作用域将global作为其父作用域。 在main中创建另一个作用域时，它以相同的方式堆叠在栈上。 当main结束时（遇到复合语句时），main作用域弹出并查看全局作用域中的其余TreeNodes。

  1. Scope sc_create(char * funcName) {
  3.     Scope newScope = (Scope) malloc(sizeof(struct ScopeRec));
  4.     newScope->funcName = funcName;
  5.     newScope->tamanhoBlocoMemoria = 0;
  6.     if(!strcmp(funcName, "ESCOPO_GLOBAL")) {
  8.         newScope->parent = NULL;
  9.     } else {
  11.         newScope->parent = globalScope;
  12.     }
  13.     scopes[nScope++] = newScope;
  14.     return newScope;
  15. }
  16. 123456789101112

之后，调用sc_push（）函数，将全局作用域先推入栈中：

  1. void sc_push(Scope scope) {
  3.     scopeStack[nScopeStack++] = scope;
  4. }
  5. 123

接着，调用traverse（）函数，它采用深度遍历，即先遍历preProc（t）以及它的子节点，再遍历postProc（t）。

  1. /* Procedure traverse is a generic recursive
  2.  * syntax tree traversal routine:
  3.  * it applies preProc in preorder and postProc
  4.  * in postorder to tree pointed to by t
  5.  */
  6. static void traverse( TreeNode * t,
  7.                void (* preProc) (TreeNode *),
  8.                void (* postProc) (TreeNode *) )
  9. {
  10.      if (t != NULL)
  11.   {
  12.      preProc(t);
  13.     {
  14.      int i;
  15.       for (i=0; i < MAXCHILDREN; i++)
  16.         traverse(t->child[i],preProc,postProc);
  17.     }
  18.     postProc(t);
  19.     traverse(t->sibling,preProc,postProc);
  20.   }
  21. }
  22. 123456789101112131415161718

最后，调用printSymTab（）打印函数，间接调用printSymTabRows（）：打印符号表的一行和insertNode（）：把一个节点插入到符号表中，最终将打印出所有的函数名和每个函数里所有的变量名，打印项目有名字、id类型、数据类型、作用域、大小（以字为单位）、相对位置和在源程序中出现的行数。

ST_INSERT（）、ST_CREATE（）

将bucketList添加到作用域栈中， 使用hash函数获取哈希值。 从scope_top搜索指定的作用域名称，直到找到正确的作用域，并将bucketList放在指定作用域的bucket数组中的哈希值处。 此时，如果没有相同的bucketList，则添加一个新的bucketList。

  1. void st_insert(char * name, int lineno, int loc, TreeNode * treeNode, int tamanho) {
  3.     int h = hash(name);
  4.     Scope top = sc_top();
  6.     if(top->hashTable[h] == NULL) {
  8.     // Add scope to syntax tree node
  9.         treeNode->kind.var.scope = top;
  10.         top->hashTable[h] = st_create(name, lineno, loc, treeNode, tamanho);
  11.         treeNode->kind.var.scope->tamanhoBlocoMemoria += tamanho;
  12.     } else {
  14.         BucketList l = top->hashTable[h];
  15.         while ((l->next != NULL) && (strcmp(name, l->name))) {
  17.             l = l->next;
  18.         }
  19.         if (l->next == NULL && (strcmp(name, l->name))) {
  20.      /* Variable not yet in table */
  21.             //Add scope to syntax tree node
  22.             treeNode->kind.var.scope = top;
  23.             //Add a new item to the symbol table
  24.             l->next = st_create(name, lineno, loc, treeNode, tamanho);
  25.             treeNode->kind.var.scope->tamanhoBlocoMemoria += tamanho;
  26.         }
  27.     }
  28. } /* st_insert */
  30. BucketList st_create(char * name, int lineno, int loc, TreeNode * treeNode, int tamanho) {
  32.     BucketList l = (BucketList) malloc(sizeof(struct BucketListRec));
  33.     l->name = name;
  34.     l->lines = (LineList) malloc(sizeof(struct LineListRec));
  35.     l->lines->lineno = lineno;
  36.     l->lines->next = NULL;
  37.     l->memloc = loc;
  38.     l->tamanho = tamanho;
  39.     l->treeNode = treeNode;
  40.     l->next = NULL;
  41.     return l;
  42. } /* st_create */
  43. 123456789101112131415161718192021222324252627282930313233343536
ST_LOOKUP()、ST_LOOKUP_TOP（）

st_lookup()从当前堆栈顶部的范围中查找父范围。st_lookup_top仅在当前作用域内查找，它以范围名称作为参数，并仅检查该范围的BucketList。

TYPECHECK（）

在建立完符号表之后，语义分析的下一个任务是对于语法错误的检查，该部分的实现原理是，通过检查相邻语法树结点的词法属性，确保是符合常规的。具体的实现函数在analyse.c中的type check函数：

  1. /* Procedure typeCheck performs type checking
  2.  * by a postorder syntax tree traversal
  3.  */
  4. void typeCheck(TreeNode * syntaxTree) {
  6.     traverse(syntaxTree, beforeCheckNode, checkNode);
  7. }
  8. 123456

typeCheck直接调用了一个遍历函数traverse，传入的三个参数，第一个是syntaxTree，代表语法树，第二个beforeCheckNode，它是一个函数，代表遍历的终止条件，即遍历到叶子结点时，语法树遍历停止，第三个函数则是需要重点分析的checkNode，它制定了语法规则分析的过程。

  1. static void beforeCheckNode(TreeNode * t) {
  3.     if (t->node == EXPK) {
  5.         if (t->kind.var.varKind == FUNCTIONK) {
  7.             funcName = t->kind.var.attr.name;
  8.         }
  9.       }
  10. }

check node函数的工作原理是，一边遍历语法树，遍历到当前的一个结点之后，检查该结点的相邻结点是否符合语法规则，如果不符合就报错，如果符合就可以继续。

例如：如果该节点是t->node == EXPK，那么它有三种情况，第一种是赋值语句，那么它的孩子节点的类型必须相同；如果是判断表达式，那么结点类型必须是void；如果是算术表达式，它的类型必须是int，这样对应起来。

  1. /* Procedure checkNode performs
  2.  * type checking at a single tree node
  3.  */
  4. static void checkNode(TreeNode * t) {
  6.     if (t->node == STMTK) {
  8.         switch (t->kind.stmt) {
  10.             case INTEGERK: t->child[0]->type = INTEGER_TYPE; break;
  11.             case VOIDK:
  12.                 if (t->child[0]->kind.var.varKind == IDK) {
  14.                     typeError(t, "Variable cannot be void!");
  15.                 } else {
  17.                     t->child[0]->type = VOID_TYPE;
  18.                 }
  19.                 break;
  20.             case IFK: break;
  21.             case WHILEK: break;
  22.             case RETURNK: break;
  23.             case COMPK: break;
  24.         }
  25.     } else if (t->node == EXPK) {
  27.         switch (t->kind.exp) {
  29.             case ATRIBK:
  30.                 if ((t->child[0]->type != INTEGER_TYPE) || (t->child[1]->type != INTEGER_TYPE)) {
  32.                     typeError(t, "Invalid assignment, int value expected and void received");
  33.                 } else  {
  35.                     t->type = INTEGER_TYPE;
  36.                 }
  37.                 break;
  38.             case RELK: t->type = VOID_TYPE; break;
  39.             case ARITHK: t->type = INTEGER_TYPE; break;
  40.         }
  41.     } else if (t->node == VARK) {
  43.         switch (t->kind.var.varKind) {
  45.             case IDK: t->type = INTEGER_TYPE; break;
  46.             case VECTORK: t->type = INTEGER_TYPE; break;
  47.             case CONSTK: t->type = INTEGER_TYPE; break;
  48.             case FUNCTIONK: break;
  49.             case CALLK: break;
  50.         }
  51.     }
  52. }

至此，语义分析结束了。

CODEGEN（）

接下来的中间代码生成则也是对于语法树进行操作，传入一棵语法树，从根结点，根据该节点的词法属性，分析词法结点之间的逻辑，翻译成四元式。

进入中间代码生成部分的代码在main.c中，将中间代码写入同名的txt文件中，strcspn函数的作用是，在pgm字符串中查找到第一个“.”，并返回它之前的所有字符作为子串，这样做的目的在于，传入给编译器的文件是一个文件，、中间代码的输出结果也需要保存在一个文件中，输出文件在这里这样做，是为了保持和输入文件同名。strncpy函数的作用是拷贝字符串，这里用于将strcspn提取的文件名存入字符串供输出文件使用。

  1. # if !NO_CODE
  2.     if (! Error) {
  4.         char * codefile;
  5.         int fnlen = strcspn(codeInfo.pgm, ".");
  6.         codefile = (char *) calloc(fnlen + 4, sizeof(char));
  7.         strncpy(codefile, codeInfo.pgm, fnlen);
  8.         strcat(codefile, ".txt");
  9.         code = fopen(codefile, "w");
  10.         if (code == NULL) {
  12.             printf("Cannot open the file %s\n", codefile);
  13.             exit(1);
  14.         }
  15.         if (TraceCode) fprintf(listing, "\nGenerate intermediate code...\n");
  16.         codeGen(syntaxTree, codefile, codeInfo);
  17.         free(syntaxTree);
  18.         fclose(code);
  19.         if (TraceCode) fprintf(listing, "\nIntermediate code generation is complete!\n");
  20.     }

codeGen函数传入了语法树根结点以及需要写入的文件，进行后续操作

  1. /* Procedure codeGen generates code to a code
  2.  * file by traversal of the syntax tree. The
  3.  * second parameter (codefile) is the file name
  4.  * of the code file, and is used to print the
  5.  * file name as a comment in the code file
  6.  */
  7. void codeGen(TreeNode * syntaxTree, char * codefile, CodeInfo codeInfo) {
  9.     cGen(syntaxTree);
  10.         // If it is a Common Program code, add SYSCALL to the end of the code.
  11.     insertQuad(createQuad(SYSCALL, NULL, NULL, NULL));
  12.     emitCode("********** Intermediate Code **********\n");
  13.     printIntermediateCode();
  14. }
  15. 12345678910111213

这和函数主要调用了 cGen（）、insertQuad（）和printIntermediateCode（）

INSERTQUAD（）

生成四元式函数。四元式由一个结构体构成。

  1. Quadruple * insertQuad(Quadruple q) {
  3.     Quadruple * ptr = (Quadruple *) malloc(sizeof(struct Quad));
  4.     if(head == NULL) {
  6.         head = q;
  7.         head->next = NULL;
  8.         ptr = &head;
  9.     } else {
  11.         Quadruple temp = head;
  12.         while(temp->next != NULL) {
  14.             temp = temp->next;
  15.         }
  16.         temp->next = q;
  17.         temp->next->next = NULL;
  18.         ptr = &temp->next;
  19.     }
  20.     return ptr;
  21. }
  22. 1234567891011121314151617
CGEN()
  1. static void cGen(TreeNode * tree) {
  3.     if (tree != NULL) {
  5.         switch (tree->node) {
  7.             case STMTK:
  8.                 genStmt(tree);
  9.                 break;
  10.             case EXPK:
  11.                 genExp(tree);
  12.                 break;
  13.             case VARK:
  14.                 genVar(tree);
  15.                 break;
  16.             default:
  17.                 break;
  18.         }
  19.         /*If the number of parameters is greater than 0, cGen () will be called automatically*/
  20.         if(paramHead == NULL) {
  22.             cGen(tree->sibling);
  23.         } else {
  25.             if(paramHead->count == 0) {
  27.                 cGen(tree->sibling);
  28.             }
  29.         }
  30.     }
  31. }

可以看到，传入的语法树在一边遍历的同时，检查结点的类型，分为三种语句结点，一种是STMTK，主要分析保留字和复合语句；一种是EXPK，主要分析表达式，一种是VARK，主要分析不同类型的变量。

**genStmt（）：**该函数的作用主要是处理Cminus中所包含的关键字——int，void，if，while，return和compound。以if作为一个例子来分析说明这个函数需要做的工作：if结点包括三个子结点：if本身的判断表达式、复合语句、以及else。对于每个if的子结点递归分析，因为if的子结点可能也会是一个表达式，比如if的条件判断，这样的话就需要对它进行递归分析。

  1. case IFK:
  2.             p1 = tree->child[0];
  3.             p2 = tree->child[1];
  4.             p3 = tree->child[2];
  5.             /* Generate code for test expression */
  6.             cGen(p1);
  7.             /* Assigns as the first operand*/
  8.             op1 = operandoAtual;
  9.             /* Assigns instruction type */
  10.             instrucaoAtual = JP;
  11.             /* Create and insert a new intermediate code representation*/
  12.             q = insertQuad(createQuad(instrucaoAtual, op1, NULL, NULL));
  13.             /* Save if's IR to update with label representing end of block */
  14.             pushLocation(q);
  15.             /* Generate code for block */
  16.             cGen(p2);
  17.             /* set second operand */
  18.             op2 = createOperand();
  19.             op2->kind = String;
  20.             op2->contents.variable.name = createLabelName();
  21.             op2->contents.variable.scope = tree->kind.var.scope;
  22.             /* update if intermediate code instruction */
  23.             updateLocation(op2);
  24.             popLocation();
  25.             if(p3 != NULL) {
  27.                 q = insertQuad(createQuad(GOTO, NULL, NULL, NULL));
  28.                 pushLocation(q);
  29.             }
  30.             /* Label used to mark end of block */
  31.             insertQuad(createQuad(LBL, op2, NULL, NULL));
  32.             cGen(p3);
  34.             if(p3 != NULL) {
  36.                 op1 = createOperand();
  37.                 op1->kind = String;
  38.                 op1->contents.variable.name = createLabelName();
  39.                 op1->contents.variable.scope = tree->kind.var.scope;
  40.                 /* update if intermediate code instruction */
  41.                 updateLocation(op1);
  42.                 popLocation();
  44.                 /* Label used to mark end of block else*/
  45.                 insertQuad(createQuad(LBL, op1, NULL, NULL));
  46.             }
  47.             break; /* IFK */

instrucaoAtual用来标记四元式的第一区间，即操作类型，它是一个枚举类型，记录在cgen.h中：

  1. typedef enum instrucao {
  2.     ADD, SUB, MULT, _DIV, MOD,
  3.     VEC, VEC_ADDR,
  4.     EQ, NE, _LT, LET,_GT, GET, ASN,
  5.     FUNC, RTN, GET_PARAM, SET_PARAM, CALL, PARAM_LIST,
  6.     JP, GOTO, LBL, SYSCALL, HALT} InstructionKind;

pushLocation（）用于保存if的地址，记录递归的返回位置，待分析完这一条路径之后，就可以找到函数在哪里被调用了，在调用的过程中，由于各个节点都需要递归地访问，实现回填。

其他的处理也是类似的，比如在while语句里面，包含的是两个结点，一个是循环它本身，第二个是与之对应的条件，同if一样，分为两块进行分别的一个递归处理。

**genExp（）：**处理表达式结点的逻辑比较简单，如果表达式的结点类型是ID或者数字，就直接记录它，但有一个需要特殊处理的地方就是数组，在赋值中，如果左操作数是数组，则存储此变量的内存位置。如果结点是一个运算符，那么据所知，运算符是由子结点构成的，它的子结点就是运算的两个数字，或者是ID字符。需要使用LD命令将子结点里面的具体数字或字符读取出来，再根据运算符的类型构造相应的四元式。

M, CALL, PARAM_LIST,
JP, GOTO, LBL, SYSCALL, HALT} InstructionKind;

  1. pushLocation（）用于保存if的地址，记录递归的返回位置，待分析完这一条路径之后，就可以找到函数在哪里被调用了，在调用的过程中，由于各个节点都需要递归地访问，实现回填。
  3. 其他的处理也是类似的，比如在while语句里面，包含的是两个结点，一个是循环它本身，第二个是与之对应的条件，同if一样，分为两块进行分别的一个递归处理。
  5. **genExp（）：**处理表达式结点的逻辑比较简单，如果表达式的结点类型是ID或者数字，就直接记录它，但有一个需要特殊处理的地方就是数组，在赋值中，如果左操作数是数组，则存储此变量的内存位置。如果结点是一个运算符，那么据所知，运算符是由子结点构成的，它的子结点就是运算的两个数字，或者是ID字符。需要使用LD命令将子结点里面的具体数字或字符读取出来，再根据运算符的类型构造相应的四元式。
  7. **genVar（）：**对于CONSTK、IDK、VECTORK，FUNCTIONK，在四元式中记录他们的类型和名字、CALLK节点记录跳转的函数，参数个数和参数列表的地址。

发表评论

表情：
评论列表 （有 0 条评论，131人围观）

还没有评论，来说两句吧...

相关阅读

    相关 C语言中的*和&符号

    之前对\和&符号一直理解的比较浅显。只知道： \p好像表示的是一个指针； &p表示的是一个地址。 然而这次当遇到了下面这个情况的时候： int a = 10;

    冷不防冷不防/ 0 赞/ 55 阅读