编译原理实验报告1-2-

1、编译原理课程实验指导书陈志刚 编写 课程编号 320144X1 总 学 时 48 实验学时 10 课外学时 0 实验成绩： 批阅教师：2015年 6 月 5 日实验1词法分析程序设计与实现实验学时： 2 实验地点： x204 实验日期： 2015/5 一、实验目的加深对词法分析器的工作过程的理解；加强对词法分析方法的掌握；能够采用一种编程语言实现简单的词法分析程序；能够使用自己编写的分析程序对简单的程序段进行词法分析。二、实验内容自定义一种程序设计语言，或者选择已有的一种高级语言，编制它的词法分析程序。词法分析程序的实现可以采用任何一种编程语言和编程工具。从输入的源程序中，识别出各个具有独立意

2、义的单词，即关键字、标识符、常数、运算符、界符。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）三、实验方法实验方法：使用VS2013进行编写,C+语言作为基础原理：词法分析器原理词法分析器的功能输入源程序，按照构词规则分解成一系列单词符号。单词是语言中具有独立意义的最小单位，包括关键字、标识符、运算符、界符和常量等(1) 关键字 是由程序语言定义的具有固定意义的标识符。例如，Pascal 中的begin，end，if，while都是保留字。这些字通常不用作一般标识符。(2) 标识符 用来表示各种名字，如变量名，数组名，过程名等等。(3

3、) 常数 常数的类型一般有整型、实型、布尔型、文字型等。(4) 运算符 如+、-、*、/等等。(5) 界符 如逗号、分号、括号、等等。输出：词法分析器所输出单词符号常常表示成如下的二元式： (单词种别，单词符号的属性值)单词种别通常用整数编码。标识符一般统归为一种。常数则宜按类型（整、实、布尔等）分种。关键字可将其全体视为一种。运算符可采用一符一种的方法。界符一般用一符一种的方法。对于每个单词符号，除了给出了种别编码之外，还应给出有关单词符号的属性信息。单词符号的属性是指单词符号的特性或特征。四、实验步骤1. 定义目标语言的可用符号表和构词规则；2. 依次读入源程序符号，对源程序进行单词切分和

4、识别，直到源程序结束；3. 对正确的单词，按照它的种别以的形式保存在符号表中；4. 对不正确的单词，做出错误处理。五、实验结果我所采用的编码表和老师的有所不同，所以我单独给出来：下面是我所编写的词法分析器的编码表：单词/符号种别码Begin1If2Then3While4Do5End6Int7For8Return9Break10Continue11letter(letter|digit)*12 digit(digit)*13*14*15/16+17-18:19:=202122=23=25=26;27(28)293031输入为：IF 3X THEN X := 4*5 ; ELSE Y:=4#输出为

5、：输入为：输出为：经过测试后，发现与我编写的表格的对照表是无误的六、实验结论实验的设计：与保留字相关的：保留字的数组，只是为了判断是否是属于保留字以返回具体的编码种别;保留字声明如下：string BaoLiu11 =begin, if, then, while, do, end, int, for, return, break, continue;下面是判断是否是保留字的函数的函数的定义：bool IsBaoLiu(string str)for (int i = 0; i = 0 & (ch - Z) = 0 & (ch - z) = 0 & (ch - 0) = 0 & (ch - Z)

6、= 0)return (ch - A) + a);return ch;string toLowwerString(string a)/字符串变小写字符串以便于比较string s = ;for (int i=0; i (int)a.length(); i+)s.push_back(toLowwerLetter(ai);return s;下面是词法分析器的主要函数的定义：void cifa(string a, int length)/a为输入字符的字符串，length为字符串长度int code, value;code = 0;string strToken = ;/置strToken为空串，s

7、trToken是把一句语言里面的单词隔离出来char ch;/定义一个字符，便于输入ch = GetChar(a, code);/读入一个字符到字符chch = GetBC(a, code, ch);/查看是否为空白字符，是的话，移入下一个非空字符while (ch != #)if (IsLetter(ch)/如果是字母while (IsLetter(ch) | IsDigit(ch)Concat(strToken, ch);/链接成串ch = GetChar(a, code);/得到下一个字符,code是指针！/链接成串Retract(code);/读多了一个，回退一个value = Res

8、erve(toLowwerString(strToken), code);/查看是不是保留字if (value = 0)/不是保留字，又是字母开头的字符串，那么一定可能上，是普通标识符，【标识符很多，但是根据词法分析器来说，却是11个】cout (12, strToken ) endl;strToken = ;/为了下一次判断else/说明是保留字了，所以返回保留字对应的种别码for (int i = 0; i 11; i+)if (toLowwerString(strToken) = BaoLiui)/是保留字，返回编码value = (i + 1);break;cout ( value ,

9、 strToken ) endl;else if (IsDigit(ch)/如果是数字，那么做判断int flag = 0;while (IsDigit(ch)Concat(strToken, ch);/链接成串,数字串ch = GetChar(a, code);/得到下一个字符flag+;if (flag = 1 & (IsLetter(ch)/说明后面一个字符不是数字那么肯定有错了printError();elseRetract(code);/读多了一个，回退一个cout (13, strToken ) endl;strToken = ;/数字返回1else if (ch = =)cout

10、 (26, ch ) endl;else if (ch = +)cout (17, ch ) endl;else if (ch = *)ch = GetChar(a, code);/得到下一个字符if (ch = *)cout (15, ch ) endl;elseRetract(code);cout (14, ch ) endl;else if (ch = :)ch = GetChar(a, code);/得到下一个字符if (ch = =)cout (20,: ch ) endl;elseRetract(code);cout (19, ch ) endl;else if (ch = /)c

11、out (16, ch ) endl;else if (ch = _)cout (18, ch ) )ch = GetChar(a, code);/得到下一个字符if (ch = =)cout (25, ch ) endl;elseRetract(code);cout (21, ch ) endl;else if (ch = )cout (22, ch ) endl;if (ch = =)cout (23, ch ) endl;elseRetract(code);cout (24, ch ) endl;else if (ch = ;)cout (27, ch ) endl;else if (c

12、h = ()cout (28, ch ) endl;else if (ch = )cout (29, ch ) endl;else if (ch = )cout (30, ch ) endl;else if (ch = )cout (31, ch ) endl;elseif (ch != n)printError();strToken = ;ch = GetChar(a, code);/读入一个字符到字符chch = GetBC(a, code, ch);/查看是否为空白字符，是的话，移入下一个非空字符实验的完整源代码：#include #include #include using name

13、space std;/* 假定单词符号表为如下单词 符号种值 begin1 if2 then3 while4 do5 end6 int7 for8 return9 break10 continue11 letter(letter|digit)*12 digit(digit)*13 *14* 15/16+17_18:19:=202122=23=25=26;27(28)293031*/保留字表，以返回编码string BaoLiu11 =begin, if, then, while, do, end, int, for, return, break, continue;char toLowwerL

14、etter(char ch)/字符变小写if (ch - A) = 0 & (ch - Z) = 0)return (ch - A) + a);return ch;string toLowwerString(string a)/字符串变小写字符串以便于比较string s = ;for (int i=0; i = 0 & (ch - Z) = 0 & (ch - z) = 0 & (ch - 0) = 9)return true;return false;/字符串链接void Concat(string &strToken, char ch)strToken.push_back(ch);/字符

15、串尾部添加字符/判断是否是保留字bool IsBaoLiu(string str)for (int i = 0; i 11; i+)if (str = BaoLiui)/是保留字，返回编码return true;return false;/若是保留字，返回编码，若不是则返回0；int Reserve(string str, int &code)/判断ch是不是保留字if (IsBaoLiu(str)/如果是返回1return 1;return 0;void Retract(int &code)code-;/指针回退void printError()cout error endl;void ci

16、fa(string a, int length)/a为输入字符的字符串，length为字符串长度int code, value;code = 0;string strToken = ;/置strToken为空串，strToken是把一句语言里面的单词隔离出来char ch;/定义一个字符，便于输入ch = GetChar(a, code);/读入一个字符到字符chch = GetBC(a, code, ch);/查看是否为空白字符，是的话，移入下一个非空字符while (ch != #)if (IsLetter(ch)/如果是字母while (IsLetter(ch) | IsDigit(ch

17、)Concat(strToken, ch);/链接成串ch = GetChar(a, code);/得到下一个字符,code是指针！/链接成串Retract(code);/读多了一个，回退一个value = Reserve(toLowwerString(strToken), code);/查看是不是保留字if (value = 0)/不是保留字，又是字母开头的字符串，那么一定可能上，是普通标识符，【标识符很多，但是根据词法分析器来说，却是11个】cout (12, strToken ) endl;strToken = ;/为了下一次判断else/说明是保留字了，所以返回保留字对应的种别码for

18、 (int i = 0; i 11; i+)if (toLowwerString(strToken) = BaoLiui)/是保留字，返回编码value = (i + 1);break;cout ( value , strToken ) endl;else if (IsDigit(ch)/如果是数字，那么做判断int flag = 0;while (IsDigit(ch)Concat(strToken, ch);/链接成串,数字串ch = GetChar(a, code);/得到下一个字符flag+;if (flag = 1 & (IsLetter(ch)/说明后面一个字符不是数字那么肯定有错

19、了printError();elseRetract(code);/读多了一个，回退一个cout (13, strToken ) endl;strToken = ;/数字返回1else if (ch = =)cout (26, ch ) endl;else if (ch = +)cout (17, ch ) endl;else if (ch = *)ch = GetChar(a, code);/得到下一个字符if (ch = *)cout (15, ch ) endl;elseRetract(code);cout (14, ch ) endl;else if (ch = :)ch = GetCh

20、ar(a, code);/得到下一个字符if (ch = =)cout (20,: ch ) endl;elseRetract(code);cout (19, ch ) endl;else if (ch = /)cout (16, ch ) endl;else if (ch = _)cout (18, ch ) )ch = GetChar(a, code);/得到下一个字符if (ch = =)cout (25, ch ) endl;elseRetract(code);cout (21, ch ) endl;else if (ch = )cout (22, ch ) endl;if (ch =

21、 =)cout (23, ch ) endl;elseRetract(code);cout (24, ch ) endl;else if (ch = ;)cout (27, ch ) endl;else if (ch = ()cout (28, ch ) endl;else if (ch = )cout (29, ch ) endl;else if (ch = )cout (30, ch ) endl;else if (ch = )cout (31, ch ) endl;elseif (ch != n)printError();strToken = ;ch = GetChar(a, code)

22、;/读入一个字符到字符chch = GetBC(a, code, ch);/查看是否为空白字符，是的话，移入下一个非空字符int main()int code = 0, value = 0;/code相当于指针cout 请输入一个字符串以#结尾 aQQ-bSQ-a其中非终结符为：a,b,#终结符为：S,Q输入的时候，不算#为终结符，等到计算出文法具体的时候，就把其当终结符文法的First集合：First(S) = aFirst(Q) = b,a文法的Follow集合：Follow(S)=#Follow(Q) = #LLR分析表：ab#SS-aQerrorerrorQQ-aQ-bSerror分析

23、的句子提供下列的句子：1) ab#2) aa#3) aabb#4) abab#结果应该如下：1) not accept2) accept3) not accept4) not accept运行结果：首先需要输入，S,Q如下所示：输入y,已确认其接下来输入非终结符：类似的我就不叙述了，现在我输入文法：接下来输出一堆信息：可以看见文法所求出的First和Follow集合是正确的下面的阶段是输入文法的句型分析：如果需要分析句子则输入y,然后输入句子分析的句子提供的下列的句子：1) ab#2) aa#3) aabb#4) abab#结果如下：结果正确具有直接左递归的文法G2：S-SaS-b因为是直接左

24、递归，不符合LL(1)文法，所以，需要改造，则改造后为：S-bSS-aSS-下面改造后的非终结符为：S,S终结符为：a,b,#First集合和Follow集合为：First（S）= bFirst（S）= a,Follw(S)=#Follow(S) = #LL(1)分析表ba#SS-bSerrorerrorSerrorS-aSS-实验句子的分析：1) ba#2) baa#3) ab#分析后为：1) accept2) accept3) not accept实验运行结果：具有间接左递归的文法的测试G3：S-QaQ-RbR-Sc改造文法后为：S-QaQ-RbR-bacRR-改造后的非终结符为：S、Q、

25、R、R终结符为：b a cFirst和Follow集合如下：First（S） = b First（Q） = b First（R） = b First（R） = Follow(S) = # Follow(Q) = a Follow(R) = b Follow(R) = b LL(1)预测分析表为：abc#SerrorerrorerrorQerrorerrorerrorRerrorerrorerrorRerrorerrorerror实验句子的分析：1. bacba#2. ab#3. bac#预计结果：1. accpet2. not accpet3. not accpet实验结果如下：六、实验结论数

26、据结构：文法的以及first和follow集合和计算VN_C非终结符的struct PRulestring left;/文法的左部string right;/文法的右部/允许的输入;struct firststring begin;/哪一个符号的vectorFIRST;/某个符号的first的集合的元素有什么;struct followstring begin;/什么符号的，避免S的vectorFOLLOW;struct VN_Cstring vn;/终结符的输出和使用对终结符处理的函数：输入函数：/输入非终结符void InputVn()/输入非终结符bool flag = true;/是否

27、输入正确标志，如果错误，重新输入int n;/n用来计算有多少个VN，即非终结符，char ch;while (flag)/使得输入必须确保能够正确的函数cout n请输入所有的非终结符，注意： ;cout 请将文法的开始符放在第一位，并以#号结束：n;ch = ;n = 0;/初始化非终结符数组while (n MaxVnNum)VNn+ = 0;n = 0;while (ch != #) & (n MaxVnNum)if (ch != ) & (ch != n)&!IsExistVT(ch)VNn+ = ch;vnNum+;ch = getchar();/把终结符集合给初始化成功VNn =

28、 #;/用#标志结束用于判断长度是否合法if (ch != #)if (ch = getchar() != #)while (ch = getchar() != #)cout n符号数目超过限制n;flag = true;continue;/正确则执行下下面，否则重新输入VNn = 0;cout 这是您所输入的非终结符：n;showArray(VN);/输出非终结符的符号ch = ;cout n;while (ch != y & ch != n)if (ch != n)cout ch;if (ch = n)cout 录入错误，请重新输入！n;flag = true;elseflag = fal

29、se;判断函数：/判断是否在非终结符中bool IsExistVN(char ch)bool isExist = true;for (int i = 0; i vnNum; i+)if (ch = VNi)isExist = false;return isExist;查找非终结符返回下标的函数：/返回所在的VT的下标的编号int IndexVT(char ch)int index = -1;for (int i = 0; i vtNum;i+)if (ch = VTi)return i;return index;核查某个某个文法有没有终结符的函数：/检查字符串右部没有终结符bool Check

30、IsExistVT(string s)for (int i = 0; i StringLength(s); i+)for (int k = 0; k vtNum; k+)if (si = VTk)return false;return true;判断能否加入的函数/判断是否能加入vt中bool addVT(char ch)string s;s.append(1, ch);if (ch = )return false;if (IsExistVN_C(s)return false;for (int i = 0; i vtNum;i+)if (VTi = ch)return false;return

31、 true;对非终结符的函数输入函数/输入非终结符void InputVn()/输入非终结符bool flag = true;/是否输入正确标志，如果错误，重新输入int n;/n用来计算有多少个VN，即非终结符，char ch;while (flag)/使得输入必须确保能够正确的函数cout n请输入所有的非终结符，注意： ;cout 请将文法的开始符放在第一位，并以#号结束：n;ch = ;n = 0;/初始化非终结符数组while (n MaxVnNum)VNn+ = 0;n = 0;while (ch != #) & (n MaxVnNum)if (ch != ) & (ch != n

32、)&!IsExistVT(ch)VNn+ = ch;vnNum+;ch = getchar();/把终结符集合给初始化成功VNn = #;/用#标志结束用于判断长度是否合法if (ch != #)if (ch = getchar() != #)while (ch = getchar() != #)cout n符号数目超过限制n;flag = true;continue;/正确则执行下下面，否则重新输入VNn = 0;cout 这是您所输入的非终结符：n;showArray(VN);/输出非终结符的符号ch = ;cout n;while (ch != y & ch != n)if (ch != n)cout ch;if (ch = n)cout 录入错误，请重新输入！n;flag = true;elseflag = false;返回符号所在的非终结符的下标/返回所在的VT的下标的编号int IndexVT(char ch)int index = -1;for (int i = 0; i vtNum;i+)if (ch = VTi)return i;return index;核查文法有没有非终结符/检查字符串右部有没有非终结符bool CheckIsExistVN(string s)for (int i =