计算机13-3班实验报告李

1、编译原理实验班级：计算机科学与技术 13-3：李学号：2013211705实验一、 词法分析设计一、实验目的通过本实验的编程实践，使学生了解词法分析的任务，掌握词法分析程序设计的原理和构造方法，使学生对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。二、实验内容用 VC+/VB/JAVA 语言实现对 C 语言子集的源程序进行词法分析。通过输入源程序从左到右对字符串进行扫描和分解，依次输出各个单词的编码及单词符号自身值；若遇到错误则显示“Error”，然后跳过错误部分继续显示 ；同时 进行标识符登记符号表的管理。 以下是实现词法分析设计的主要工作：从源程序文件中读入字符。

2、统计行数和列数用于错误单词的定位。删除空格类字符，包括回车、制表符空格。按拼写单词，并用（内码，属性）二元式表示。 (属性值token 的机内 表示)（5）如果发现错误则出错（6）根据需要是否填写标识符表供以后各阶段使用。 单词的基本分类：关键字：由程序语言定义的具有固定意义的标识符。也称为保留字例如if、 for、 while、 prf ； 单词种别码为 1。标识符：用以表示各种名字，如变量名、数组名、函数名；常数： 任何数值常数。如 125, 1,0.5,3.1416；运算符： +、 -、 *、 /；关系运算符： 、 、 =、 ；分界符： ；、，、（、）、 、 ；三、词法分析实验设计1、主

3、程序设计考虑：及算法程序的说明部分为各种表格和变量安排空间。 在具体实现时，将各类单词设计成结构和长度均相同k 数组关键字表，每个数组元素存放一个关键字（事先构造好关键字表）。的形式，较短的关键字后面 补空。s 数组存放分界符表（可事先构造好分界符表）。为了简单起见，分界符、 算术运算符和关系运算符都放在 s 表中（编程时，应建立算术运算符表和关系运 算符表，并且各有类号），合并成一类。id 和 ci 数组分别存放标识符和常数。instring 数组为输入源程序的单词缓存。outtoken为输出表示缓存。主程序开始后，先以人工方式输入关键字，造 k 表；再输入分界符等造 p表。主程序的工作部分

4、设计成便于调试的循环结构。每个循环处理一个单词； 接收键盘上送来的一个单词；调用词法分析过程；输出每个单词的码。 例如，把每一单词设计成如下形式: (type,poer) 其中 type 指明单词的种类，例如： Poer 指向本单词存放处的开始位置。2.词法分析设计根据输入单词的第一个字符（有时还需读第二个字符）， 判断单词类，产生类号：以字符 k 表示关键字； id 表示标识符； ci 表示常数； s 表示分界符。对于标识符和常数，需分别与标识符表和常数表中已登记的元素相比较， 如表中已有该元素，则其在表中的位置，如未出现过，将标识符按顺序填入 数组 id 中，将常数变为二进制形式存入数组中

5、 ci 中，并其在表中的位置。lexical 过程中嵌有两个小过程：一个名为 getchar， 其功能为从 instring中按 顺序取出一个字符，并将其指针 p加 1 ；另一个名为 error， 当出现 错 误 时 ，调 用 这 个 过 程 ， 输 出 错 误。四、实验截图五、代码：#include #include #includeusing namespatd;string key8=do,end,for,if,prstring optr5=+,-,*,/,+;f,scanf,then,while;string separator6=,;,(,);char ch;/判断是否为保留字boo

6、l IsKey(string ss)i;for(i=0;i=a)&(c=A)&(c=0&c=9) return true;return false;/运算符判断函数 bool IsOptr(string ss)i; for(i=0;i5;i+)if (!strcmp(optri.c_str(), ss.c_str() return true;return false;/分界符判断函数bool IsSeparator(string ss)i; for(i=0;i6;i+)if(!strcmp(separatori.c_str(),ss.c_str() return true;return fal

7、se;voidyse(ifstream &in)string st=; char ch;line=1,row=0; while(in.get(ch)st=;if(ch= )|(ch=t) /空格，tab 健else if(ch=n)line+;row=0;/换行行数加一处理 elseif (IsLetter(ch)row+;/关键字、标识符的处理while(IsLetter(ch)|IsDigit(ch)st+=ch; in.get(ch);in.seekg(-1,ios:cur);/文件指针（光标）后退一个字节if(IsKey(st)/判断是否为关键字 查询关键字表；coutstt(1,st

8、)ttt(line,row)endl;关键字else/否则为标示符 coutstt(2,st)tt标识符t(line,row)endl;elseif(IsDigit(ch)row+; st+=ch; if(IsLetter(ch)ch=in.get(); st+=ch;coutsttErrortError( line , row ) endl;elsewhile (IsDigit(ch)st += ch;ch = in.get();in.seekg(-1, ios:cur);cout st t(3,st) t t 常数 t ( line , row ) endl;elsest=; st+=ch

9、; if(st=+)char ch; ch=in.get(); st=st+ch; if(st=+)coutsttErrorttErrort(line,row)endl;elseif(IsOptr(st) /运算符处理row+;coutstt(4,st)tt(line,row)endl;elseif(IsSeparator(st)/分隔符处理row+; coutstt(5,st)ttt(line,row)endl;elseswitch(ch)row+; case= :row+;运算符分界符cout=t(6,=)tt 关系运算符t(line,row) :row+;ch=in.get(); if(

10、ch=)cout=t(6,=)ttt(line,row)endl;else关系运算符coutt(6,)tt 关系运算符t(line,row)endl;in.seekg(-1,ios:cur); break; case :row+;ch=in.get(); if(ch=)cout=t(6,=)t 关系运算符t(line,row)cout t ( 6 , ) t t 关系运算符 t ( line , row ) endl; elsecout t( 6 , ) t t 关系运算符 t ( line , row ) endl;in.seekg(-1, ios:cur);break; default:r

11、ow+; cout ch t t$无法识别字符 t ( line , row ) endl;main()ifstream in;in.open(测试文.txt, ios:in);cout 备注：关键字 1系运算符 6 endl; if (in.is_open()yse(in);in.close();system(pause);标识符 2常数 3运算符 4分隔符 5关elsecout 文件操作出错 endl; return 0;六、总结通过本次实验，巩固了关于词法分析器的知识，并且在程序不断的完善中，深入理解了 C+程序的完善过程。LL(1)分析法实验二一、实验目的通过完成分析法的语法分析程序，

12、了解分析法和递归子程序法的区 别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方 法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培 养适应社会多方面需要的能力。二、实验内容1.根据某一文法编制调试 LL（1）分析程序，以便对任意的输入符号串进行分析2.构造分析表，并利用分析表和一个栈来 实现上述程序设计语言的分析程序3.分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL（1）分析表，对输入符号串自上而下的分析过程。三、LL（1）分析法实验设计1、模块结构定义部分：定义常量、变量、数据结构初始化：建立LL（1）分析表，初始化向量空

13、间 (3)控制部分：从键盘输入一个表达式符号串(4)利用 LL（1）分析算法进行表达式处理，输出分析结果，如遇到错误则显示错误信息四、实验截图五、代码：#includeusing namespatd;constMaxLen = 20; /初始化栈的长度constLength = 20;/初始化数组长度char Vn5 = E, G, T, S, F ;/非终结符数组char Vt8 = i, (, ), +, -, *, /, # ;/终结符数组char ch, X;/ch 读当前字符，X 获取栈顶元素char strTokenLength;/规约表达式struct LL/ll(1)分析表的构

14、造字初始化char*c;LL E8 = TG, TG, error, error, error, error, error, error ;LL G8 = error, error, null, +TG, -TG, error, error, null ;LL T8 = FS, FS, error, error, error, error, error, error ;LL S8 = error, error, null, null, null, *FS, /FS, null ;LL F8 = i, (E), error, error, error, error, error, error ;

15、 class stack/栈的构造及初始化public:stack();/初始化bool empty() const;/是否为空 bool full() const;/是否已满bool get_top(char &c)const;/取栈顶元素 bool push(const char c);/入栈bool pop();/删除栈顶元素 void out();/输出栈中元素stack()/析构 private:count;/栈长度char dataMaxLen;/栈中元素;stack:stack()count = 0;bool stack:empty() const if (count = 0)r

16、eturn true; return false;bool stack:full() const if (count = MaxLen)return true; return false;bool stack:get_top(char &c)const if (empty()return false;elsec = dount - 1;return true;boolstack:push(const char c) if (full()return false;dount+ = c;return true;boolstack:pop() if (empty()count-; return tr

17、ue;return false;voidstack:out() for (i = 0; icount; i+)cout datai;cout t;length(char *c)l = 0;for (l+;i = 0; ci != 0; i+)return l;void prfor (i, char*c)/剩余输入串的输出j = i; jLength; j+)cout cj;cout t;void run() bool flag = true;/循环条件step = 0, polen;/长度= 0;/步骤、指针cout 输入规约的字符串： strToken;ch = strTokenpostac

18、k s;+;/第一个字符s.push(#);/栈中数据初始化 s.push(E);s.get_top(X);/取栈顶元素cout 步骤t 分析栈t 剩余输入串tt 所用产生式t 动作 endl; cout step+ t;s.out();pr(po- 1, strToken);cout t 初始化 endl; while (flag)if (X = Vt0) | (X = Vt1) | (X = Vt2) | (X = Vt3) | (X = Vt4)| (X = Vt5) | (X = Vt6) /判断是否为终结符（不包括#）if (X = ch)/终结符,识别，进行下一字符规约s.pop(

19、);s.get_top(X);ch = strTokenpo +; cout step+ t; s.out();pr(po- 1, strToken);cout t GETNEXT(I) endl;elseflag = false;elseif (X = #)/规约结束if (X = ch)cout step+ t; s.out();pr(po- 1, strToken);cout X ch t 结束 endl; s.pop();flag = false;elseflag = false;else if (X = Vn0) /非终结符 Efor (i = 0; iX1X2 的产生式进行入栈操作

20、s.pop();len = length(Ei.c) - 1;for (j = len; j = 0; j-)s.push(Ei.cj);cout step+ t; s.out();pr(po- 1, strToken);cout X Ei.c t = 0; j-)cout Ei.cj;cout ) endl; s.get_top(X);else if (X = Vn1) /同上，处理 Gfor (i = 0; i8; i+)if (ch = Vti)if (strcmp(Gi.c, null) = 0)s.pop();cout step+ t; s.out();pr(po- 1, strTo

21、ken);cout X t POP = 0; j-)s.push(Gi.cj);cout step+ t; s.out();pr(po- 1, strToken);cout X Gi.c t = 0; j-)cout Gi.cj; cout ) endl;s.get_top(X);else if (X = Vn2) /同上 处理 Tfor (i = 0; i= 0; j-)s.push(Ti.cj);cout step+ t; s.out();pr(po- 1, strToken);cout X Ti.c t = 0; j-)cout Ti.cj;cout ) endl; s.get_top(

22、X);else if (X = Vn3)/同上 处理 Sfor (i = 0; i8; i+)if (ch = Vti)if (strcmp(Si.c, null) = 0)s.pop();cout step+ t; s.out();pr(po- 1, strToken);cout X t POP = 0; j-)s.push(Si.cj); cout step+ t;s.out();pr(po- 1, strToken);cout X Si.c t = 0; j-)cout Si.cj; cout ) endl;s.get_top(X);else if (X = Vn4) /同上 处理 Ff

23、or (i = 0; i= 0; j-)s.push(Fi.cj);cout step+ t; s.out();pr(po- 1, strToken);cout X Fi.c t = 0; j-)cout Fi.cj; cout ) endl;s.get_top(X);else /出错处理flag = false;main()cout 实验二 E+T（2）E-T（3）T-T*F（4）T-F（5）F-(E)（6）F-i三、LR(1)分析法实验设计（1）总控程序（2）分析表或分析函数，不同的文法分析表将不同，同一个文法采用的 LR 分析器不同时，分析表将不相同。（3）分析栈，包括文法符号栈和相应的

24、状态栈，他们均是先进后出栈，分析器的动作就是由栈顶状态和当前输入符号决定四、实验截图五、代码#includeusing namespatd;constconstMaxLen=20; /初始化栈的长度Length=20;/初始化数组长度char ch, Y;/全局变量，ch 用于读当前字符，Y 用于获取栈顶元素char strTokenLength;/bool flag=true;/循环条件规约表达式po=0,step=1;/步骤、指针class stack/栈的构造及初始化public:stack();/初始化bool empty() const;/是否为空 bool full() const

25、;/是否已满bool get_top(char &c)const;/取栈顶元素 bool push(const char c);/入栈bool pop();void out();/输出栈中元素 void out1();stack()/析构 private:count;/栈长度char dataMaxLen;/栈中元素; stack l,r;/l 代表符号栈，r 代表状态栈stack:stack()count=0;boolstack:empty() const if(count=0)return true;return false;boolstack:full() const if(count=

26、MaxLen)return true;return false;boolstack:get_top(char &c)constif(empty()return false;elsec = dount - 1;return true;boolstack:push(const char c)if (full()return false;dount+ = c;return true;boolstack:pop()if (empty()return false; count-;return true;voidstack:out()for (i = 0; icount; i+)cout datai;co

27、ut t;void stack:out1()for (i = 0; icount; i+)cout (datai);cout t;void pr(i, char*c)/剩余输入串的输出for(j=i;jLength;j+)coutcj;coutt;void Goto(i,char c)/状态转换函数 ,对应于表中 GOTOif(i=0)if(c=E)r.push(1);cout ,GOTO(0,E)=1 入栈 endl;else if (c = T)r.push(2);cout ,GOTO(0,T)=2 入栈 endl;else if (c = F)r.push(3);cout ,GOTO(0

28、,F)=3 入栈 endl;elseflag = false;elseif (i = 4)if (c = E) r.push(8);cout ,GOTO(4,E)=8 入栈 endl;else if (c = T)r.push(2);cout ,GOTO(4,T)=2 入栈 endl;else if (c = F) r.push(3);cout ,GOTO(4,F)=3 入栈 endl;elseflag = false;elseif (i = 6)if (c = T) r.push(9);cout ,GOTO(6,T)=9 入栈 endl;else if (c = F)r.push(3);co

29、ut ,GOTO(6,F)=3 入栈 endl;elseflag = false;elseif (i = 7)if (c = F)r.push(10);cout ,GOTO(7,F)=10 入栈 endl;elseflag = false;elseflag = false;voidAction0()/状态 0 时if(ch=i)/下一个操作符为 i ,移进coutstep+t; r.out1();l.out();pr(po-1,strToken);coutACTION0,i=S5,状态 5 入栈endl; r.push(5);l.push(ch);ch=strTokenpo+;elseif(c

30、h=()/下一个操作符为( ,移进coutstep+t; r.out1();l.out();pr(po-1,strToken);coutACTION0,(=S4,状态 4 入栈endl; r.push(4);l.push(ch);ch=strTokenpo+;elseflag = false;voidAction1()/状态 1if(ch=+)/下一个操作符为 i ,移进coutstep+t; r.out1();l.out();pr(po-1,strToken);coutACTION1,+=S6,状态 6 入栈endl; r.push(6);l.push(ch);ch=strTokenpo+;

31、else if(ch=#)/分析成功flag=false; coutstep+t; r.out1();l.out();pr(po-1,strToken);coutAcc：分析成功endl;elseflag=false;voidAction2() /状态 2if(ch=*)/下一个操作符为* ,移进coutstep+t; r.out1();l.out();pr(po-1,strToken);coutACTION2,*=S7,状态 7 入栈endl; r.push(7);l.push(ch);ch=strTokenpo+;elseif(ch=+)|(ch=)|(ch=#)/下一个操作符为+，），#

32、规约coutstep+t;r.out1();l.out();strToken);l.pop();cout r2: ET 归约;l.push(E);r.pop();pr(po- 1,r.get_top(Y);Goto(Y), E);elseflag = false;void Action3()/状态 3if(ch=+)|(ch=*)|(ch=)|(ch=#)/下一个操作符为+，*,），#规约coutstep+t; r.out1();l.out();l.pop(); l.push(T);pr(po-1,strToken);coutr4: TF 归约; r.pop();r.get_top(Y);Go

33、to(Y),T);elseflag=false;void Action4_6_7(x)/状态 4,6,7if(ch=i)/下一个操作符为 i ,移进coutstep+t; r.out1();l.out();pr(po-1,strToken);coutACTION;coutx,i=S5,状态 5 入栈endl; r.push(5);l.push(ch);ch=strTokenpo+;elseif (ch = ()/下一个操作符为（ ,移进coutstep+t; r.out1();l.out();pr(po-1,strToken);coutACTION;coutx,(=S4,状态 4 入栈endl

34、; r.push(4);l.push(ch);ch=strTokenpo+;elseflag=false;voidAction5()/状态 5if(ch=+)|(ch=*)|(ch=)|(ch=#)/下一个操作符为+，*,），#规约coutstep+t; r.out1();l.out();l.pop(); l.push(F);pr(po-1,strToken);coutr6: Fi 归约; r.pop();r.get_top(Y);Goto(Y),F);elseflag=false;voidAction8()/状态 8if(ch=+)/下一个操作符为+ ,移进coutstep+t; r.out

35、1();l.out();pr(po-1,strToken);coutACTION8,+=S6,状态 6 入栈endl; r.push(6);l.push(ch);ch = strTokenpo+;elseif (ch = )/下一个操作符为） ,移进coutstep+t; r.out1();l.out();pr(po-1,strToken);coutACTION8,)=S11,状态 11 入栈endl; r.push(11);l.push(ch);ch=strTokenpo+;elseflag=false;voidAction9()/状态 9if(ch=*)/下一个操作符为* ,移进coutstep+t; r.out1();l.out();pr(po-1,strToken);coutACTION9,*=S7,状态 7 入栈endl; r.push(7);l.push(ch);ch=strTokenpo+;elseif(ch=+)|(ch=)|