2022年编译原理课程设计实验报告

编译原理课程设计实验报告实验目的这个实验的目的是构造语言的编译器，要求能够编译c minusC语言的程序并且生成中间代码在实验的过程中，学会使用minus这两个重要的工具flex/bison实验内容参见教材p491appendix A.设计一语言编译器cminus语言介绍语言的关键字Decaf cminusintwhile ifelse returnvoid运算符+-*/=z.!={}[]====0语言的限制C minus数字支持进制整数小数可以采用科学记数法，如也是合法101E3的字符串字符串内部不允许出现换行，即字符串变量必须在同一行内注释语言允许采用/*…*/注释，并且注释不可以嵌套，即下面Cminus的注释是不合法的/*This is/*a valid*/comment*//*插入函数void st_insert char*name,int lineno,int loc;*//*查找函数*/int stjookupchar*name;/*用来打印哈稀void printSymTabFILE*listing;表内容*/#endif符号表设计的好坏直接影响到整个程序运行的速度，效率以及准确度因为接下来的工作是基于符号表的，是从符号表里提取进parse token行语法分析的为了提高程序运行的的效率，我们把直接通过scan parse来调用具体的来讲就是，程序运行时，首先进入部分，当parse parse要用到时，调用部分扫描原文件生成储存在符号表token scan token中，并同时提供给进行语法分析这样就可以一遍完成整个原文parse件的扫描第二部分运用实现词法分析程序LEX cminus这一部比较关键，设计的正确与否直接影响到在过程中scantoken的产生以及整个程序运行的结果的正确与否在这里主要定义cminus的基本语法规则，以及类型，运算符类型，并且定义tok㊀n cminus关键字，便于在程序运行时能对其进行识别一下为文件原代cminus.I码/*定义全局变量、函数及包含文件说明7%#include globals.h#include util.h#include scan.h#define MAXTOKENLEN40char tokenstring

[40];int lineno=0;%}有关语法规则以及的定义:tokendigit[0-9]number{digit}+letter[a-zA-Z]identifier{letterj+newline\nwhit㊀spcic㊀[\t]+%%/*以下为关键字定义:*/if{return IF;}else{return ELSE;}int{return INT;}void{return VOID;}return{return RETURN;}以下为运算符号定义:*/while{return WHILE;}{return ASSIGN;}{return LTEQ;}={returnGTEQ;}{return LT;}{return GT;}{return EQ;}!={return NOTEQ;}{return PLUS;}{return MINUS;}{return TIMES;},,H{return OVER;}{return LPAREN;}{return RPAREN;}{return LBRACK;}{return RBRACK;}{return LCURL;}{return RCURL;}{return SEMI;}终结符及注释符号*/{return COMMA;}{number}{return NUM;}{identifier}{return ID;}{newline}{lineno++;}{whitespace}{/*skip whitespace*/}7*”{char c;char d;c=input;if c!=EOFdod=c;c=input;if c==EOF break;if c==\n lineno++;}while!d==c==7;.{return ERROR;}%%定义函数体:g㊀tTok㊀n Tok㊀nTyp㊀getTokenvoid{static intfirstTime=TRUE;TokenType currentToken;if firstTime{firstTime=FALSE;lineno++;yyin=source;yyout=listing;二currentToken yylex;strncpytokenString,yytext MAXTOKENLEN;zif TraceScan{fprintflisting\t%d:Jineno;,printTokenfcurrentTokenJokenString;return currentToken;说明以上代码已经能通过工具产生代码的设计lex ccminus.l基本结构是参考的结构设计而成，但要注意的是，由于在接下来tiny.l的中所定义的语法规则不同，这里的也要稍做修改比如在cnimus.y这里的函数，要于文件里的设计的返回参数要一getToken cminus.y一对应，否则在编译的过程中会出现类型不匹配等等的错误，修改起来比较麻烦第三部分为设计语法树结构，使之适用于分析器产生C-语法树是分析的前提因此在进行语法分析之前，必须设计LALR语法树结构，使接下来的语法分析有一个具体的数据结构其代码段如下#define MAXTOKENSIZE50/*定义语法树结构*/typedef intTokenType;typedef structTokenType tok;char*tokString;}TokenStruct;typedef enum{lfK,Whil㊀K,AssignK,ReturnK,CcillK,/*枚VarDecIKzFunDecIKzOpKzConstKJdK}NodeKind;举结点类型*//*枚举返typedef㊀num{VoicLInteg㊀r,Bool㊀on}ExpType;回变量类型*//*声明一个结点最多有三#define MAXCHILDREN3个子结点*//*定义语法树结点结构*/typedef struct treeNode{struct treeNode*child[MAXCHILDREN];structtreeNode*sibling;int lineno;NodeKind kind;union{TokenType op;int vol;甘char*name;}r;ExpType type;}TreeNode;说明在这里当当只是设计的语法树的基本数据结构，至于要用到过程中还要进行具体的修改，调试这些工作都已经在程序原代parse码调试过程中做好第四部分分析（使用工具）LALR ycicc这一部分完成了整个编译过程中的语法分析，二异性冲突处理,lese悬挂问题的处理，运算符优先级处理以及错误报告参考课本P492条并且通过细心理解体会，写出了文29cminus BNFcminus.y件，并能通过生成代码ycicc c代码以及一些具体功能如下所述Cnimus.y一.源程序的结构YACC说明部分的内容如下%头文件宏定义数据类型定义全局变量定义%}语法开始符定义语义值类型定义终结符定义运算符优先级及结合性定义%#define YYPARSER/*distinguishes Yaccoutput fromothercode files*/#include globals.h#include util.h#include scan.h#include parse.hTreeNode*parseTree;/*stores syntaxtree forlaterreturnvoid yyerrorconst char*s;%语法开始符号的定义非终结符%start注若没有上述说明，自动将第一条语法规则左部的非YACC终结符作为语法开始符语义值类型的定义定义语义值的类型;%union%union{TreeNode*tnode;TokenTypetok;}定义文法符号的语义值类型;%type」%type tnodeprogram declQrcitionist declarationvar_declaration」%type tnodefun.declaration paramsporcim istparamcompound_stmt%type tnodelocaLdeclarations statementjiststatement%type tnodeexpression_stmt selection_stmtiteration_stmt%type tnodereturn_stmt expressionvarsimple_expression%type tnodeadditive_expression termfactor callargs argjist%type toktype.specifier relopaddop mulop在定义终结符号时也可以定义语义值类型%token终结符的定义语义值类型,终结符名编号%token v%token DIGITLEHER%token BEGIN100注:.非终结符不需要特别说明，如果需要说明语义值类1％型则用语句；type.文字字符终结符不需要特别说明，它们的编号取其2在字符集中的值;.在规则中出现文字字符时用单引号括起来3%token ENDFILE,ERROR,%token IF,ELSEJNT,RETURN,VOID,WHILE,%token ID,NUM,%token ASSIGN,%token EQ,NOTEQ,LTEQ,GTEQ,LT,GT,%token PLUS,MINUS,TIMESQVER,%tokenLPAREN,RPAREN,LBRACK,RBRACK,LCURL,RCURL,%token SEMLCOMMA运算符优先级和结合性的定义以％什和％的除定义结合性；2以排列顺序定义优先级；在语法规则中,以％辅助定义优先级prec消除二义性的两条规则.出现移进/归约冲突时，进行移进；•

1.出现归约/归约冲突时，用先出现的规•2则进行归约；stat:IF bexp THEN statIFbexpTHENstat ELSEstat;用结合性和优先级解决冲突；规则的结合性就是规则右部最后一个非•终结符的优先级和结合性；％如果使用了子句，则优先级和结•prec合性由％子句决定；pre c对于无优先级和结合性的规则，用规则•、解决;12程序流程图程序的流程参照了书本编译器的实例程序:语法分析器（）TINY Pcirs㊀r调用词法分析器得到符合词法的字，建立语法树；符号表通过对语法树的分析，建立符号表，同时检查变量未定义等错误；类型检查包括检查表达式两边是否匹配，函数参数是否匹配等等；经由上述步骤而未出错的源程序被认为是合法程序，然后代码生成通过语法树和符表生成P中间代码，并将变量地址存入符号表Code其中类型检查和代码生成不要求实现本次实验要求分组，一组五人，一人完成一个部分本组实验分组成员以及分工介绍汪晨风（设计并实现符号表）；cminus E02620105蔡其星（编写文件,并用工具生成代码）；cminus.l lexc E02620107对于有优先级和结合行的规则，用如下的•规则解决出现移进/归约冲突时，输入符号的优先级大于规则的优先级则移进，若输入符号的优先级小于规则的优先级则归约，若二者的优先级相同，左结合则归约，右结合则移进，无结合则出错二.语法规则program:declarationjist{parseTree=$1;YYACCEPT;」d㊀clorcition ist:declarationjist declaration{TreeNode*t=$1;if t!=NULLwhile t-sibling!=NULLt=TreeNode*t-sibling;t-sibling=$2;；$$=$1else$$=$2;I declaration{$$=$1;}declaration:var_declaration，，Iww-w|fun_declaration、八一，t pw//程序由声明的列表或序列组成，声明可以是函数或变量声明,顺序是任意的至少必须有一个声明接下来是语义限制这些在中不会出c现所有的变量和函数在使用前必须声明这避免了向后bockpcitching弓|用程序中最后的声明必须是一个函数声明，名字为moin门var_declaration:typ㊀_sp㊀cifi㊀D SEMI{$$=TreeNode*newNodeVarDeclK;$$-attr.op=$1;$$-child

[0]=TreeNode*newNodeldK;甘$$-child

[0]-Q r.nom㊀=char*copyStringlastid;//add tosymbol tableI type_specifier IDLBRACK NUM{5tnode$=TreeNode*newNodeVarDeclK;$tnode$-attr.op=$1;$tnode$-child

[0]=TreeNode*newNodeldK;$tnode$-child

[0]-attr.name=char*copyStringlastid;$tnode$-child

[0]=TreeNode*newNodeConstK;$tnode$-child

[0]-attr.val二atoicurToken.tokString;//add tosymbol tableRBRACKSEMI$$=$tnode5;type_specifier:INT{$$=INT;}|VOID{$$=VOID;}变量声明或者声明了简单的整数类型变量，或者是基类型为整数的数组变量，索引范围从到注意，在中仅有的基本类型NUM-1C-是整型和空类型在一个变量声明中，只能使用类型指示符int void用于函数声明参见下面也要注意，每个声明只能声明一个变量fun_declaration:type_specifier ID{$tnode$=TreeNode*newNodeFunDeclK;$tnode$-attr.op=$1;$tnode$-child

[0]=TreeNode*newNodeldK;$tnode$-child

[0]-attr.name=char*copyStringlastid;LPAREN paramsRPAREN compound_stmt{$$=$tnode3;$$-child[l]=$5;⑵$$-child=$7;params:paramjist,《《一《一▽，，i-1t ww|VOID{$$=NULL;}paramjist:paramjist COMMAparam{TreeNode*t=51;if t!=NULLwhile t-sibling!=NULLt=TreeNode*t-sibling;t-sibling=$3;$$二$1;}else$$=$3;|param{$$二$1;}，param:type_specifier ID{$$二TreeNode*newNodeVarDeclK;$-attr.op=$1;$-child[O]=TreeNode*newNodeldK;$-child[O]-attr.name=char*copyStringlastid;//odd tosymbol table}Itype_specifier ID{$tnode$=TreeNode*]newNodeVarDeclK;$tnode$-attr.op=$1;$tnode$-child

[0]=TreeNode*newNodeldK;二$tnode$-child

[0]-ottr.name char*copyStringlastid;//add tosymbol tableLBRACKRBRACK{$$=$tnode3;}函数声明由返回类型指示符、标识符以及在圆括号内的用逗号分开的参数列表组成，后面跟着一个复合语句，是函数的代码如果函数的返回类型是那么函数不返回任何值（即是一个过程）函数的参数可以void,是即没有参数，或者一列描述函数的参数参数后面跟着方括号void是数组参数，其大小是可变的简单的整型参数由值传递数组参数由引用来传递也就是指针，在调用时必须通过数组变量来匹配注意，类型“函数”没有参数一个函数参数的作用域等于函数声明的复合语句，函数的每次请求都有一个独立的参数集函数可以是递归的对于使用声明允许的范围compound_stmt:LCURL local_declarationsstatementjist RCURL{TreeNode*t=$2;if t!=NULLwhile t-sibling!=NULLt=TreeNode*t-sibling;t-sibling=$3;$$=$2;else$$=$3;/复合语句由用花括号围起来的一组声明和语句组成复合语句通过用给定的顺序执行语句序列来执行局部声明的作用域等于复合语句的语句列表，并代替任何全局声明；二{TreeNode*t51local declarations:local declarationsvar declarationif t!=NULLwhile t-sibling!=NULLt=TreeNode*t-sibling;t-sibling=$2;else$$=$2;$$=NULL;}statementjist:statementjist statement{TreeNode*t=$1;if t!=NULLwhile t-sibling!=NULLt=TreeNode*t-sibling;t-sibling=$2;；=!）二else$$$2;）I{$$=NULL;}/注意声明和语句列表都可以是空的（非终结符夕如秘表示空字符串,有时写作）£statement:expression_stmt{$$=$］；}|compound_stmt

一、，I PI/|selection_stmt{$$=$1;}I iteration_stmt，）t ww-w|return_stmtexpression_stmt:expression SEMI，Iww-w/{$$=$1;}I SEMI{$$=NULL;}/表达式语句有一个可选的且后面跟着分号的表达式这样的表达式通常求出它们一方的结果因此，这个语句用于赋值和函数调用selection_stmt:IF LPAREN expression RPARENstatement{$$=TreeNode*newNodelfK;二$$-child

[0]$3;$$-child[l]=$5;|IF LPARENexpression RPARENstatementELSE statement{$$=TreeNode*newNodelfK;$$-child

[0]=$3;$$-child[l]=$5;；$$-child

[2]=$7・/语句有通常的语义表达式进行计算；非值引起第一条语句的执行；if0值引起第二条语句的执行，如果它存在的话这个规则导致0赵婷（设计语法树结构）;cminus E02620106马培良编写文件，并用工具生成可执行代码）;cminus.y yoccE02620121丘廷（进行程序的测试）以下为具体实验分步报告以及过程第一部分设计符号表cminus符号表是编译器中的主要继承属性，并且在语法树之后，形成了主要的数据结构符号表主要的操作有插入、查找和删除杂凑表（hash表）通常为符号表的实现提供了最好的选择，因为所有种操作都能在3几乎恒定的时间内完成，在实践中也是最常使用该课程设计所用的-C符号表采用建立杂凑表的方法杂凑表是一个人口数组，称作“桶（），使用一个整数范围的索引，通常从到表的尺寸减杂bucket”01凑函数（）把索引键（在这种情况下是标识符名，组成一个hash fuction字符串）转换成索引范围内的一个整数的杂凑值,对应于索引键的项存储在这个索引的“桶”中每个“桶”实际上又是一个线性表，通过把新的项插入到“桶”表中来解决冲突在任何情况下，“桶”数组的实际大小要选择一个素数，因为这将使一般的杂凑函数运行得更好杂凑函数在符号表实现中使用的杂凑函数将字符串（标识符名）转换成-范围内的一个整数一般这通过步来进行首

0...s iz㊀13先，字符串中的每个字符转换成一个非负整数然后，这些整数用一定的方法组合形成一个整数最后，把结果整数调整到-了典

0...s iz㊀型的悬挂二义性，可以用一种标准的方法解决部分通常作为Hs㊀㊀Is㊀当前的一个子结构立即分析“最近嵌套”非二义性规则ifiteration_stmt:WHILE LPARENexpression RPARENstatement{$$二TreeNode*newNodeWhileK;$$-child

[0]=$3;$$-child[l]=$5;/语句是中唯一的重复语句它重复执行表达式，并且如果whil㊀C-表达式的求值为非则执行语句，当表达式的值为时结束0,return_stmt:RETURN SEMI{$$=TreeNode*newNodeReturnK;}I RETURNexpression SEMI{$$=TreeNode*newNodeReturnK;$$-child

[0]=$2;/返回语句可以返回一个值也可无值返回函数没有说明为void就必须返回一个值函数声明为就没有返回值引起控制void eturn返回调用者如果它在中，则程序结束moinexpression:var ASSIGNexpression{$$二TreeNode*newNodeAssignK;；$$-child

[0]=$1$$-child[l]=$3;}|simple_expression，t ww-w IJ varID{$$=TreeNode*newNodeldK;$$-attr.name=char*copyStringlostid;}I ID{$tnode$=TreeNode*newNodeldK;char$tnode$-attr.name=copyStringlastid;}LBRACK expressionRBRACK{$$二$tnode2;$-child[O]=$4;/表达式是一个变量引用，后面跟着赋值符号等号和一个表达式，或者就是一个简单的表达式赋值有通常的存储语义找到由碳示的变量的地址，然后由赋值符右边的子表达式进行求值，子表达式的值存储到给定的地址这个值也作为整个表达式的值返回/度简单的整型变量或下标数组变量负的下标将引起程序停止与不同然而，不C进行下标越界检查simple_expression:additive_expression relopadditive_expression{$$=TreeNode*newNodeOpK;甘r.op=$2;$$-child

[0]=$1;$$-child[l]=$3;|additive_expressionr ee_

1.irelop:EQt{$WW$-=4EIQ，;/}I NOTEQ{=NOTEQ;}I LTEQ{$$=LTEQ;}|GTEQ{$$=GTEQ;}I LT{$$=LT;}I GT{$$=GT;}/简单表达式由无结合的关系操作符组成即无括号的表达式仅有一个关系操作符简单表达式在它不包含关系操作符时，其值是加法表达式的值，或者如果关系算式求值为其值为求值为时值为tu re,1,fols㊀0additive_expression:additive_expression addopterm{$$二TreeNode*newNodeOpK;甘$$-Q r.op=$2;$$-child

[0]=$1;$$-child

[2]=$3;|termaddop:PLUS{$$=PLUS;}|MINUS{$$=MINUS;}/term:term mulopfactor{$$二甘TreeNode*newNodeOpK;r.op=$2;$-child

[0]=51;$$-child

[2]=$3;|factor一・141I

一、，I pI j/mulop:TIMES{$$=TIMES;}|OVER{$$=OVER;}加法表达式和项表示了算术操作符的结合性和优先级符号表示整数除；即任何余数都被截去factor:LPARENexpressionRPAREN{$$=$2}|var；{$$=$1}|call{$$二；$1}I NUM{$$=TreeNode*newNodeConstK;$$-attr.val=atoicurToken.tokString;/因子是围在括号内的表达式；或一个变量，求出其变量的值；或者一个函数调用，求出函数的返回值；或者一个其值由扫描器计算NUM,数组变量必须是下标变量，除非表达式由单个组成，并且以数组为参ID数在函数调用中使用如下所示ocall:ID$tnode$-child

[0]TreeNode*{$tnode$=TreeNode*newNodeCallK;newNodeldK;char*$tnode$-child

[0]-attr.namecopyStringlastid;LPAREN argsRPAREN{$$=$tnode2;$$-child[l]=$4;args:argjist；{$$=$]}I{$$=NULL;}argjist:argjist COMMAexpression{Tr㊀㊀Nod㊀*t=$1;ift!=NULLwhile t-sibling!=NULLt=TreeNode*t-sibling;t-sibling=$3;$$=$1;二else$$$3;I expression,一《1-I一，IWW WI/函数调用的组成是一个/函数名，后面是用括号围起来的参数参数或者为空，或者由逗号分割的表达式列表组成，表示在一次调用期间分配的参数的值函数在调用之前必须声明，声明中参数的数目必须等于调用中参数的数目函数声明中的数组参数必须和一个表达式匹配，这个表达式由一个标识符组成表示一个数组变量%%三.出错处理遇到错误就终止语法分析；void yyerrorchar*messageprintffError atline%d:%s\n linenomessage;,/说明文件文件是是整个程序的主题部分，直接决定了该程.L.Y序的功能如何因此在设计这两个部分的时候要细心耐心调试难点主要是在语法规则的定义，已经函数间的衔接通过长时间的调试，并且参考编译器，对它的一些工具函数进行修改原程序的文件tiny util.c并使子之能适用于编译器cminus第五部分程序测试测试工作在任何一个程序设计或者软件设计当中是一项必不可少的工序，而且是一项非常重要的工作测试做的好坏，直接可以决定该软件的好坏在测试当中可以发现软件的漏洞，这样就可以对其进行修改，使之完善在本程序测试过程中，可以自己编写语句或者程序，用该cminus编译器来进行扫描，语法分析并且输出语法树，如果语句有cnimus错，编译器会报错基于这样的目的我们做了以下的测试首先利用课本页的测试程序对其进行测试496sample.decaf/*A program to perform EuclidsAlgorithm to compute gcd.*/int x

[10];int gcdint u,int vif v==0return u;else returngcdv,u-u/v*v;/*u-u/v*v==u modv*/通过编译器编译以后出来的结果保存到中:sample.out intID,name=x[NUM,val=10]/・intID,name=gcdintID,name=u/intID,name=vreserved word:if范围内ID,name=v1冲突的一个好的解决办法是，当加上下一个字符的值时，重复地使用一个常量作为乘法因子因此，如果是第个字符的数字值，是在第步计算的部ci ihi i分杂凑值，那么根据下面的递归公式计算，hi hO=O,hi-1=ahi,最后的杂凑值用计算这里是杂凑的名字中字-ci h=hnmodsize n符的个数这等价于下列公式当然，在这个公式中的选择对输出结果有重要影响的一种合理的选择是的帚，如或这样乘216128,法可以通过移位来完成该程序选取a16,size2110由于在数据结构方面为了实现很方便的进行查找，插入，删除等操作我们把它的数据结构设计成一哈稀表结构，哈稀表的查找，插入等操作是飞快的我们所设计的哈稀结构符号表是参考教科书上P295它的结构如下:NUM,vol=0reserved word:return ID,name=u/reserved word:else reserved word:return ID,name=gcdID,name=v/ID,name=uID,name=u/ID,name=v*ID,name=v VarDeci:intId:xConst:10Fun Deci:intId:gcdVar Deci:intId:uVar Deci:intId:vIf二二Op:Id:vConst:0Return:Id:uReturn:Call:Id:gcdId:vOp:-Id:uOp:*Op:/Id:uId:vId:v如果故意在中修改一下使之有语法错误如下scimpl㊀.d㊀cofr AprogramtoperformEuclidsAlgorithmtocomputegcd.*/intx

[10];int gcdint u,int v/*第行，这里少一逗号，本应报错*/ifv==0return u8elsereturn gcdv,u-u/v*v;/*u-u/v*v==u modv*/编译以后结果为ID,name=uINT VAR:u intID,name=vINT VAR:v{reserved word:ifID,name=vNUM,val=0）reservedword:returnID,name=ureserved word:else（在这里提示第行有错）Syntcix errorcit line8:syntax error8Syntcix errorQt line8:syntax error此外，我们自己还写了很多测试程序对编译器进行测试，具体的测试程序在原代码的怕文件夹里其测试结果输出在文件中请老师察阅st progrom.out由测试可以看出，该编译器基本能完成报错的功能，但还不是很完善，有待我们日后进行修改以上就是我们分工的五部分虽然分工清楚，但是在具体做的过程中，每个人都遇到了这样那样的问题以及难题，我们五个人就进行深入的讨论，共同解决问题比如各个部分都做好了，在调试程序能运行了过程中，我们五个人都花了很多的时间进行调试最终使程序能够通顺，能够运行这都是我们通力合作的结果程序原代码已经压缩成压缩包与实验报告一同发到老师的邮箱里请老师检查实验心得体会这次编译器的设计对我们来说可以说是一次大型程序设计cminus我们在实验中学会并能熟练的运用和两个辅助工具学会了写lex yocc和代码，并且能在修改和代码来实现对程序功能的Qx ycicclex yocc修改刚一开始虽然对我们来说是很难的，特别是在写文件的过程yocc中，刚一开始根本弄不清楚是怎么写的，为什么这样写，但是我们都耐心的去边学边做我们到图书馆后者上网查阅了大量的资料，参考人家的东西并对其进行修改，把它变成自己的东西通过这次实验，到最后也弄懂了设计代码的方法以及一些技巧通过这次实验，使我们能把yacc这一学期学的东西运用到实际当中，并深切体会到了编译原理其中的奥秘所在这次实验是多人合作的，在实验中，我们也发挥了团队合作精神通力合作，遇到问题共同解决这次实验也是对我们以前学的VC编程的一个复习，我们既学了好多东西，又巩固了以前的知识，并大大增强了我们的逻辑思维，为以后将要学的课程以及其他知识打下了基础2005-1-28符号表的杂凑函数#define SIZE211#defineSHIFT4int hashchar*key{int temp=0;int i=0;while key[i]!=\0{temp=temp«SHIFT+key[i]%SIZE;；++ireturn temp;该符号表完成了插入[void st_insert char*name,int lineno,int]、查找」工作loc[int stookupchar*name]源程序symtab.c#include stdio.h#include stdlib.h#include string.h#include symtab.h/*定义哈稀表的最大值*/#gine SIZE211/*SHIFT isthe powerof twoused asmultiplier inhashfunction*/#defineSHIFT4/*哈稀函数结构*/static int hashchar*key{int temp=0;int i=0;while key[i]!=\0{temp=temp«SHIFT+key[i]%SIZE;；++ireturn temp;typedef struct LineListRec{int lineno;structLineListRec*next;}*LineList;typedef structBucketListRec{char*name;LineList lines;int memloc;/*memory locationfor variable*/structBucketListRec*next;}*BucketList;/*哈稀表*/static BucketListhashTable[SIZE];void stjnsertchar*name,int lineno,int loc{int h=hashname;BucketList I=hashTable[h];while I!=NULLstrcmpname l-name!=0zI=l-next;if I==NULL/*variable notyet intable*/{I=BucketList mallocsizeofstructBucketListRec;l-name=name;l-lines=LineList mallocsizeofstructLineListRec;l-lines-lineno=lineno;l-memloc=loc;l-lines-next=NULL;l-next=hashTable[h];hashTable[h]=I;}else/*found intable,so justadd linenumber*/{LineList t=l-lines;while t-next!=NULL t=t-next;t-next=LineList mallocsizeofstructLineListRec;二t-next-lineno lineno;t-next-next=NULL;int stjookupchar*name{inth=hashname;BucketList I=hashTable[h];while I!=NULLstrcmpname,l-name!=0I=l-next;if I==NULL return-1;else returnl-memloc;void printSymTabFILE*listing{int i;fprintf listing,Variable NameLocation LineNumbers\n;--------------------------------甘fprin listing,\n;for i=0;iSIZE;++i{if hashTable[i]!=NULL{BucketList I=hashTable[i];while I!=NULL{LineList t=l-lines;fprintflisting,%-14s,l-name;fprintflisting,%-8dJ-memloc;while t!=NULL甘％{fprin listing,“4cT,t-lin㊀no;t=t-next;；fprintflisting,\nI=l-next;}/*printSymTab*/symtab.h#ifndef_SYMTAB_H_#define_SYMTAB_H_。