编译原理报告(6).docx

华中科技大学计算机学院 编译原理实验报告课 程 实 验 报 告课程名称： 编译原理 专业班级： 信息安全1302 学 号： 姓 名： 指导教师： 报告日期： 2015年11月07日 计算机科学与技术学院目录目录21 实验一 词法分析31.1实验目的31.2实验要求31.3算法思想41.4实验程序设计说明61.5词法分析实现61.6词法实验结果及结果分析122 实验二 语法分析132.1 实验目的132.2 实验要求132.3 算法思想142.4 实验程序设计说明162.5 语法分析实现162.6 词法实验结果及结果分析313 实验中遇到的问题及解决32参考资料321 实验一 词法分析1.1 实验目的设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。1.2 实验要求1、待分析的简单的词法（1）关键字： begin if then while do end所有的关键字都是小写。（2）运算符和界符： = + - * / = = = ; ( ) #（3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义：ID = letter (letter | digit)*NUM = digit digit*（4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。2、 各种单词符号对应的种别码：表1 各种单词符号对应的种别码单词符号种别码 单词符号种别码bgin1：17If2：=18Then320wile421do523lettet（letter|digit）*10=24dight dight*11=25+13；2614(27*15)28/16#03、 词法分析程序的功能：输入：所给文法的源程序字符串。输出：二元组（syn,token或sum）构成的序列。其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。例如：对源程序begin x:=9: if x9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列：(1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)1.3 算法思想算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。1、 主程序示意图：主程序示意图如图1所示。其中初始包括以下两个方面： 关键字表的初值。关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下：Char *rwtab6 = “begin”, “if”, “then”, “while”, “do”, “end”,;开始置初值调用扫描子程序输出单词二元组输入串结束?否结束是图1 主程序示意图（2）程序中需要用到的主要变量为syn,token和sum2、 扫描子程序的算法思想：首先设置3个变量：token用来存放构成单词符号的字符串；sum用来整型单词；syn用来存放单词符号的种别码。扫描子程序主要部分流程如图2所示。开始变量初始化忽略空格是否文件结束?否返回是拼数拼字符串字母Syn=11关键字?Syn=10否是Syn为对应关键字的种别码对不同符给出相应的syn值报错其他符号运算符界符等返回数字图2 扫描子程序流程图1.4 实验程序设计说明1、数据结构的设计先来看看WORD结构的设计：typedef struct int typenum;/用于存储该字符串的种别码；char *word; /用于存储字符串；这个词法分析中，我们要将我们识别到的字符串输出他们，而且还要将他们的相应的种别码输出，因此我们得用一个结构体来将这两个属性放在一个结构体中。2、算法的设计首先将输入端的字符串读入然后进行前期的处理，如去掉空白符号。之后在一个字符一个字符的进行处理，判断下一个字符串所属类型，然后给出相应类型的种别码，返回给主函数进行输出。其中主要部分就是分类属性的判断以及判断之后不同属性种别码的赋值，这就是整个程序中的主要部分。1.5 词法分析实现#include #include #include #include #define _KEY_WORD_END waiting for your expanding /*定义关键字结束标志*/HANDLE gh_std_out; /标准输出设备句柄typedef struct /*单词二元组的结构，可以根据需要继续扩充*/ int typenum; char * word; WORDS;char input255; /*输入缓冲区*/char token255=;/*单词缓冲区*/int p_input;/*输入缓冲区指针*/int p_token;/*单词缓冲区指针*/char ch; /*当前读入字符*/char* KEY_WORDS=begin,if,then,while,do,end,_KEY_WORD_END;/*可扩充的关键字数组*/WORDS* scaner();/*词法扫描函数，获得一个单词*/int main()int over=1;WORDS* oneword=new WORDS;printf(Enter Your words(end with #):n);scanf(%#s,input);/*读入源程序字符串到缓冲区，以#结束，允许多行输入*/ getchar();p_input=0;printf(Your words:n%sn,input);printf(The sequence as follow:n( 字符t, 种别码 )n);while(overtypenumword); printf(t,%5d )n,oneword-typenum);/*打印种别码和单词自身的值*/over=oneword-typenum;return 0;/*需要用到的自编函数参考实现*从输入缓冲区读取一个字符到ch中*/char m_getch()ch=inputp_input;p_input=p_input+1;return (ch);/*去掉空白符*/void getbc()while(ch= |ch=10)ch=inputp_input;p_input=p_input+1;/*拼接单词*/void concat()tokenp_token=ch;p_token=p_token+1;tokenp_token=0;/*判断是否为字母*/int letter()if(ch=a&ch=A&ch=0&chtypenum=10;myword-word=;p_token=0;m_getch();getbc();if(letter()while(letter()|digit()concat();m_getch();retract();myword-typenum=reserve();myword-word=token;return(myword);else if(digit()while(digit()concat();m_getch();retract();myword-typenum=11;myword-word=token;return(myword);else switch(ch)case =: m_getch();if (ch=)myword-typenum=39;myword-word=;return(myword);retract();myword-typenum=21;myword-word=;return(myword);break;case +:myword-typenum=13;myword-word=+;return(myword);break;case -:myword-typenum=14;myword-word=-;return(myword);break;case *:myword-typenum=15;myword-word=*;return(myword);break;case /:myword-typenum=16;myword-word=/;return(myword);break;case (:myword-typenum=27;myword-word=(;return(myword);break;case ):myword-typenum=28;myword-word=);return(myword);break;case :myword-typenum=29;myword-word=;return(myword);break;case :myword-typenum=30;myword-word=;return(myword);break;case :myword-typenum=31;myword-word=;return(myword);break;case :myword-typenum=32;myword-word=;return(myword);break;case ,:myword-typenum=33;myword-word=,;return(myword);break;case :m_getch();if (ch=)myword-typenum=18;myword-word=:=;return(myword);retract(); myword-typenum=17;myword-word=:;return(myword);break;case ;:myword-typenum=26;myword-word=;return(myword);break;case : m_getch();if (ch=)myword-typenum=24;myword-word=;return(myword);retract();myword-typenum=23;myword-word=;return(myword);break;case typenum=22;myword-word=typenum=20;myword-word=typenum=21;myword-word=!=;return(myword);retract();myword-typenum=-1;myword-word=ERROR;return(myword);break;case 0:myword-typenum=1000;myword-word=OVER;return(myword);break;default:myword-typenum=-1;myword-word=ERROR;return(myword);1.6 词法实验结果及结果分析输入begin x:=9: if x9 then x:=2*x+1/3; end # 程序输出序列的结果如下图3所示：图3 程序运行结果2 实验二 语法分析2.1 实验目的 编写语法分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。2.2 实验要求 利用C语言编写词法分析程序，并对语言进行语法分析。2.2.1、待分析的简单语言的语法 用扩充的BNF表示如下： （1） :=beginend （2） :=；语句 （3） := （4） :=ID:= （5） :=+|- （6） :=*|/ （7） :=ID|NUM|()2.2.2、实验要求说明 输入单词串，以“#”结束，如果文法是正确的句子，则输出成功信息，打印“success”，否则输出“error”并给出相应的错误提示。 例如： 输入 begin a:=9;x:=2*3;b:=a+x;end# 输出 success 输入 x:=a+b*c;end# 输出 error 缺少begin2.3 算法思想2.3.1 主程序流程图如下：2.3.2 语句串分析示意图：2.3.3 语句分析函数judge流程图：2.4 实验程序设计说明程序中定义了一个结构变量如下：typedef struct DisplayTableint Index; /标识符所在表的下标int type; /标识符的类型int line; /标识符所在表的行数char symbol20;/标识符所在表的名称Table;Table *table = new TableMax;表table用来存放经词法分析后的结果的信息，包含单词的值、单词的类型嘛、单词所在源程序的行数，以及分析后单词在表中的下标。另外还使用到几张关键字表、运算符表、界符表如下：/关键字const char* const KeyWordMaxKeyWord = and,array, begin,case,char,constant,do,else,end,false,for,if,not,of,or,procedure,repeat, then, until, var,while; / A类运算符const char OptA = +,-,*,/,=,#,;/B类运算符const char *OptB = =,:=,;/ 界符const char End = (, ) , , , ; , . , , , : , , , ; 输入的源程序经过Scanner函数进行词法分析后，分析结果存放在table表中，然后再主函数中通过下标依次对table表中的单词进行句型判断等语法分析。2.5 语法分析实现语法分析器具体代码实现如下：#include #include #include #include #include #include using namespace std;#define Max 655 /最大代码长度#define WordMaxNum 256 /变量最大个数#define DigitNum 256/常量最大个数#define MaxKeyWord21/关键字数量#define MaxOptANum 8/运算符最大个数#define MaxOptBNum 4/运算符最大个数#define MaxEndNum 11/界符最大个数typedef struct DisplayTableint Index; /标识符所在表的下标int type;/标识符的类型int line;/标识符所在表的行数char symbol20;/标识符所在表的名称Table;int TableNum = 0; /display表的表项总数char WordWordMaxNum20; /标识符表char DigitWordMaxNum20; /数字表int WordNum = 0; /变量表的下标int DigNum = 0; /常量表的下标bool errorFlag = 0; /错误标志int TableIndex = -1; /display 表的下标索引int beginCount = 0;/遇到begin加1，遇到end减1int ifCount = 0; /遇到if加1Table *table = new TableMax;/关键字const char* const KeyWordMaxKeyWord = and,array, begin,case,char,constant,do,else,end,false,for,if,not,of,or,procedure,repeat, then, until, var,while; / A类运算符const char OptA = +,-,*,/,=,#,;/B类运算符const char *OptB = =,:=,;/ 界符const char End = (, ) , , , ; , . , , , : , , , ; void error(char str20,int nLine, int errorType)errorFlag = 1;cout nError : ;switch(errorType)case 1:cout 第 nLine-1 行 str 变量的长度超过限制！n;break;case 2:cout 第 nLine-1 行 str 小数点错误！n;break;case 3:cout 第 nLine-1 行 str 常量的长度超过限制！n;break;/switch/errorvoid Scanner(char ch,int chLen,int nLine)int chIndex = 0; while(chIndex 20) /标识符超过规定长度，报错处理error(str,nLine,1);elseint i;for(i = 0;i = MaxKeyWord) /不是关键字tableTableNum.Index = WordNum;strcpy(WordWordNum+,str);tableTableNum.type = 2; /变量标识符strcpy(tableTableNum.symbol,str);tableTableNum.line = nLine;TableNum +;/*常数*/else if(isdigit(chchIndex) /遇到数字int flag = 0;char str256;int strLen = 0;/数字和小数点while(isdigit(chchIndex) | chchIndex = .)/flag表记小数点的个数，0时为整数，1时为小数，2时出错if(chchIndex = .) flag +;strstrLen + = chchIndex;chIndex +;strstrLen = 0;if(strlen(str) 20) /常量标识符超过规定长度20，报错处理error(str,nLine,3);if(flag = 0)tableTableNum.type = 3; /整数if(flag = 1)tableTableNum.type = 4; /小数if(flag 1)error(str,nLine,2);tableTableNum.Index = DigNum;strcpy(DigitDigNum +,str);strcpy(tableTableNum.symbol,str);tableTableNum.line = nLine;TableNum +;/*运算符*/else/用来区分是不是无法识别的标识符，0为运算符，1为界符int errorFlag;char str3;str0 = chchIndex;str1 = chchIndex + 1;str2 = 0;int i;for( i = 0;i = MaxOptBNum)for( int k = 0;k MaxOptANum; k+)if(OptAk = chchIndex)errorFlag = 0;tableTableNum.type = 5;tableTableNum.symbol0 = chchIndex;tableTableNum.symbol1 = 0;tableTableNum.line = nLine;tableTableNum.Index = k;TableNum +;chIndex +;break;/*界符*/for(int j = 0;j MaxEndNum;j +)if(Endj =chchIndex)errorFlag = 1;tableTableNum.line = nLine;tableTableNum.symbol0 = chchIndex;tableTableNum.symbol1 = 0;tableTableNum.Index = j;tableTableNum.type = 7;TableNum +;chIndex +;/*其他无法识别字符*/开头的不是字母、数字、运算符、界符if(errorFlag != 0 & errorFlag != 1)char str256;int strLen = -1;strstrLen + = chchIndex;chIndex +;while(*ch != | *ch != 9 | chchIndex != 10)strstrLen + = chchIndex;chIndex +;strstrLen = 0;tableTableNum.type = 8;strcpy(tableTableNum.symbol,str);tableTableNum.line = nLine;tableTableNum.Index = -2;TableNum +; /*语法错误*/void Gerror(int errorType,int nIndex)errorFlag = 1;switch(errorType)case 1:cout 第 tablenIndex.line 行： tablenIndex.symbol 应该为赋值号：:= n;break;case 2:cout 第 tablenIndex.line 行： tablenIndex.symbol 应为变量 n;break;case 3:cout 第 tablenIndex.line 行： tablenIndex.symbol 应为逗号 n;break; case 4:cout 第 tablenIndex.line 行： tablenIndex.symbol 应为分号 n;break;case 5:cout 第 tablenIndex.line 行： tablenIndex.symbol 应为运算符 n;break;case 6:cout 第 tablenIndex.line 行： tablenIndex.symbol 应为变量或常量 n;break;case 7:cout 第 tableTableIndex.line 行 tablenIndex.symbol 与tableTableIndex + 1.symbol 之间缺少运算符 n;break;case 8:cout 第 tablenIndex.line 行： tablenIndex + 1 .symbol 应为( n;break;case 9:cout 第 tableTableIndex.line 行 tableTableIndex.symbol 与 tablenIndex + 1.symbol 之间缺少( n;break;case 10:cout 第 tableTableIndex - 1.line 行: 缺少then endl;break;case 11:cout 第 tableTableIndex.line 行: tablenIndex.symbol 应为then n;break;case 12:cout 第 tableTableIndex.line 行: end 后不能接 tableTableIndex.symbol endl;break;case 13:cout 第 tablenIndex.line 行： tablenIndex - 1.symbol 与 tableTableIndex.symbol 之间缺少变量 n;break;case 14:cout 第 tablenIndex .line 行 tablenIndex .symbol 后缺少; n;break;case 15:cout 第 tableTableIndex.line 行:tablenIndex.symbol 应为) n;break;case 16:cout 第 tableTableIndex.line 行,begin 后不能接 tableTableIndex.symbol = TableNu