编译原理课程设计--语法分析器.docx

中国海洋大学课程设计课程名称：编译原理课程设计任课教师：葛林学生姓名：甘言海学生学号：020332010027专业班级：计算机信息保密2010级学院名称：信息科学与工程学院2012年12月23日一、 概要设计使用Lex和Yacc设计一个语法分析器，并在语法分析的同时生成分析树。给产生式加上动作，动作为生成一棵语法分析树，输入为实验1所给语言写的源程序文件；输出为一个C语言源程序文件（即输入是所给语言的源程序文件，输出为语义相同的C语言源程序文件）。二、 详细设计1. 基本思路为所给语言写出无二义性的文法，用正规式定义语言的一些基本元素，如变量名、关键字和常数。将基本元素的识别放在词法分析里，语言的语句单元、程序结构等放在语法分析里完成。2. 基本原理词法分析和语法分析合作完成对源语言程序的分析，词法分析返回语法分析所需要的词法单元，包括变量名、关键字、整数和浮点数。语法分析负责源程序语法结构的检查和语法树的构造。语法树的构造通过计算文法符号的综合属性自下而上一步步获得。3. 数据基础为语法树定义数据结构，包括各文法符号属性值的数据结构定义，并为它们实现各自的构造函数。4. 工作流程根据语法树打印出语义相同的C语言源程序需要众多函数的支持，它们分别负责各个语法结构（即文法符号的属性）的打印输出。这些函数单独放在一个文件里，其中打印源程序的函数由主函数调用，然后由打印源程序的函数负责调用其它函数完成整个源程序的打印。5. 提示信息对于能够正确通过词法分析和语法分析的源程序输出分析成功的提示信息，否则提示源程序存在语法错误。三、 实现方法1. 文法符号的定义（为各文法符号指定属性值类型）1) 文法符号类型%union int ival;double fval;string sval;a_id id;a_op op;a_bop bop;ttype typ;a_exp calexp;a_bexp relexp;a_stm sten;a_stm_list stens;a_prog prog;a_dec decl;a_dec_list decltable;a_var_list vartable;a_vardec vardeclare;a_extension exten;2) 终结符定义并指定属性值类型%token ID%token INT%token FLOAT%token INTEGER REAL%token SEMICOLON END VAR PERIOD COLON COMMA ASSIGN IF WHILE LPAREN RPAREN PROGRAM BEGINER ELSE DO THEN %token EQ NEQ LT GT LE GE%left MINUS PLUS%left TIMES DIVIDED3) 为非终结符指定属性值类型%type progr%type EXTENSION%type DECLARE%type DECLARETABLE%type SENTENCE GIVESENTENCE IFSENTENCE WHILESENTENCE%type SENTENCETABLE GROUPSENTENCE%type CALCULATEEXPRESS TERM FACTOR%type RELATIONEXPRESS%type VARIETYTABLE%type VARIETYDECLARE%type VARIETY%type TYPE2. 类型定义1) 程序数据结构定义struct a_prog_ string name; a_pos pos; a_extension exten;2) 分程序数据结构定义struct a_extension_ a_pos pos;a_vardec vardeclare;a_stm_list stmlist;3) 变量声明部分数据结构定义struct a_vardec_ a_pos pos; a_dec_list dectable;4) 变量声明表数据结构定义struct a_dec_list_ a_dec head; a_dec_list tail;5) 变量声明数据结构定义struct a_dec_ ttype type; a_pos pos; a_var_list varlist;6) 变量表数据结构定义struct a_var_list_ a_id head; a_var_list tail;7) 语句表数据结构定义struct a_stm_list_ a_stm head; a_stm_list tail;8) 语句数据结构定义struct a_stm_ enum A_assign, A_if, A_while, A_seq kind; a_pos pos; union struct a_assign_stm_ a_id var; a_exp exp; assign;/赋值语句：var = exp; struct a_if_stm_ a_bexp b; a_stm s1; a_stm s2; iff;/ if语句：if b then s1 else s2; struct a_while_stm_ a_bexp b; a_stm s; whilee;/ while语句：while b do s; a_stm_list seq;/顺序语句：是若干顺序的语句的一个列表。 stm;9) 算数表达式数据结构定义struct a_exp_ enum A_varExp, A_intExp, A_realExp, A_opExp kind; a_pos pos; union struct a_op op; a_exp left; a_exp right; biopExp; /二元运算表达式：left op right a_id var; /变量表达式 int ival; /整型数表达式 double fval;/实型数表达式 exp;10) 布尔表达式数据结构定义struct a_bexp_a_pos pos;struct a_bop bop; a_exp left; a_exp right; bexp;11) 变量数据结构定义struct a_id_ a_pos pos; string val;12) 类型数据结构定义typedef enumT_int, T_real ttype;13) 标识符数据结构定义typedef char *string;14) 二元算数运算符数据结构定义typedef enum A_plusOp, A_minusOp, A_timesOp, A_divideOp a_op;15) 二元布尔运算符数据结构定义typedef enum A_eqOp, A_neqOp, A_ltOp, A_leOp, A_gtOp, A_geOp a_bop;16) 各种指针类型定义typedef struct a_exp_ * a_exp;typedef struct a_bexp_ * a_bexp;typedef struct a_id_ * a_id;typedef struct a_stm_ * a_stm;typedef struct a_stm_list_ * a_stm_list;typedef struct a_dec_ * a_dec;typedef struct a_vardec_ * a_vardec;typedef struct a_dec_list_ * a_dec_list;typedef struct a_var_list_ * a_var_list;typedef struct a_prog_ * a_prog;typedef struct a_extension_ * a_extension;17) 各种数据结构嵌套定义，自顶向下，层次分明3. 词法分析器的设计1) 正规式词法分析器的主要功能就是为语法分析提供词法记号，为此词法分析要能够识别所有合法的词法单元并在识别到一个词法单元后将它的属性值写入全局变量以便语法分析器能够使用这个属性值。最后词法分析器要将这个词法单元所对应的终结符记号返回给语法分析器，使语法分析器知道现在已经得到了一个终结符号，然后采取相应的动作（移进终结符或者归约产生式）。为了实现这些功能，词法分析器需要定义识别这些词法单元的正规式，正规定义如下：delim t nwsdelim+letterA-Za-zdigit0-9idletter(letter|digit)*constinteger digit+constfloat constinteger?.constinteger还有一些词法单元的识别因为较为简单，直接采用正规式的方式放在词法规则段中。2) 定义状态此外为了能够识别注释并做相应的处理，需要设置一个状态，以表示现在词法分析是否处于注释的范围内，状态定义如下：%s COMMENT当遇到注释开始标志时，词法分析器就进入注释状态，遇到注释结束标志再切换回正常状态。3) 标识符属性值识别到标识符时，由于其属性是一个字符串，不能直接将变量yytext的值赋给全局变量yylval，因为yytext的值是一个指针变量，而我们无法知道这个指针所指向的内存区域在下一时刻会发生怎样的变化，因此无法确保在语法分析的最后还能正确地获取标识符的名字。为此在遇到标识符时，我们需要自己开辟一块内存区域来存放标识符的名字，将此刻yytext所指内存区域的值复制一份到我们自己开辟的内存区域。4) 其他符号属性值当词法分析遇到整数或浮点数时，需要将yytext所指字符串转换成整数或浮点数，简单的调用函数atoi()和atof()即可完成。识别到其他词法单元只需要根据词法单元的类型进行简单的赋值即可。4. 语法分析器的设计1) 原理由于语法分析是为了分析源程序的语法结构并建立语法树，因此只需为该语言书写一个有效的文法并在产生式后添加相应的语义动作，在语义动作里通过计算非终结符的综合属性来建立程序的语法树。2) 为该语言书写的文法（含语义动作）如下：progr : PROGRAM ID SEMICOLON EXTENSION program = A_Prog(EM_tokPos,$2,$4); ;EXTENSION : VARIETYDECLARE GROUPSENTENCE PERIOD $=A_Exten(EM_tokPos,$1,$2); ;VARIETYDECLARE : VAR DECLARETABLE $=A_VarDec(EM_tokPos,$2); ;DECLARETABLE : DECLARE SEMICOLON $=A_DecList($1,NULL);|DECLARE SEMICOLON DECLARETABLE $=A_DecList($1,$3); ;DECLARE : VARIETYTABLE COLON TYPE $=A_Dec(EM_tokPos,$1,$3);TYPE :INTEGER |REAL ;VARIETYTABLE :VARIETY $=A_VarList($1,NULL);|VARIETY COMMA VARIETYTABLE $=A_VarList($1,$3); ;SENTENCETABLE :SENTENCE $=A_StmList($1,NULL);|SENTENCE SEMICOLON SENTENCETABLE $=A_StmList($1,$3); ;SENTENCE : GIVESENTENCE | IFSENTENCE | WHILESENTENCE | GROUPSENTENCE $=A_Seq(EM_tokPos,$1); ;GIVESENTENCE : VARIETY ASSIGN CALCULATEEXPRESS $=A_Assign(EM_tokPos,$1,$3); ;IFSENTENCE : IF RELATIONEXPRESS THEN SENTENCE ELSE SENTENCE $=A_If(EM_tokPos,$2,$4,$6); ;WHILESENTENCE : WHILE RELATIONEXPRESS DO SENTENCE $=A_While(EM_tokPos,$2,$4); ;GROUPSENTENCE : BEGINER SENTENCETABLE END $=$2;CALCULATEEXPRESS : TERM | CALCULATEEXPRESS PLUS TERM $=A_OpExp(EM_tokPos,$2,$1,$3);| CALCULATEEXPRESS MINUS TERM $=A_OpExp(EM_tokPos,$2,$1,$3); ;TERM : FACTOR | TERM TIMES FACTOR $=A_OpExp(EM_tokPos,$2,$1,$3); | TERM DIVIDED FACTOR $=A_OpExp(EM_tokPos,$2,$1,$3); ;FACTOR : VARIETY $=A_VarExp(EM_tokPos,$1); | INT $=A_IntExp(EM_tokPos,$1); | FLOAT $=A_RealExp(EM_tokPos,$1); | LPAREN CALCULATEEXPRESS RPAREN $=$2; ;RELATIONEXPRESS : CALCULATEEXPRESS EQ CALCULATEEXPRESS $=A_BExp(EM_tokPos,$2,$1,$3);| CALCULATEEXPRESS NEQ CALCULATEEXPRESS $=A_BExp(EM_tokPos,$2,$1,$3);| CALCULATEEXPRESS GE CALCULATEEXPRESS $=A_BExp(EM_tokPos,$2,$1,$3);| CALCULATEEXPRESS LE CALCULATEEXPRESS $=A_BExp(EM_tokPos,$2,$1,$3);| CALCULATEEXPRESS GT CALCULATEEXPRESS $=A_BExp(EM_tokPos,$2,$1,$3);| CALCULATEEXPRESS LT CALCULATEEXPRESS $=A_BExp(EM_tokPos,$2,$1,$3);VARIETY : ID $=A_Id(EM_tokPos,$1);3) 注意的事项文法的书写要注