淮北师范大学
编译原理课程设计
课题名称：LR(0)分析过程的实现
班级：2014级非师2班
学号：20141202109
姓名: 夏涛
目录
1．课程设计的目的 (2)
2．课程设计的内容及要求 (2)
3．实现原理 (2)
3.1 LR分析器结构 (2)
3.2 LR分析法寻找可归约句柄的依据 (3)
3.3 LR分析器的核心 (3)
3.4 LR分析器的总控程序 (4)
3.5 具体过程分析如下： (4)
3.6 LR(0)分析表构造基本思想 (4)
3.7 构造LR(0)分析表的方法 (5)
3.7.1生成文法G的LR(0)项目 (5)
3.7.2 由项目构成识别文法活前缀的DFA (5)
3.7.3将所得DFA确定化 (5)
3.7.4 LR(0)项目集规范簇的自动构造 (6)
3.7.5 LR(0)分析表的构造算法 (7)
4．算法实现流程图 (7)
5．测试数据 (8)
6．结果输出及分析 (9)
7．软件运行环境及限制 (12)
8．心得体会 (13)
9．参考文献 (13)
1．课程设计的目的
通过课程设计进一步理解高级语言在计算机中的执行过程，加深对编译原理中重点算法和编译技术的理解，提高自己的编程能力，培养好的程序设计风格。同时通过某种可视化编程语言的应用，具备初步的Windows环境下的编程思想。
2．课程设计的内容及要求
1.可以使用任何语言来完成，例如：Java、C、C++。
2.文法采用常用的方式进行描述，例如：S→aA。
3.以文件方式读取文法。
4.求出项目集规范族（即所有的状态）。
5.给出状态间的关系。
6.给出LR(0)分析表。
7.给定的任意符号串判定是否是文法中的句子，将分析过程用计算机打印出
来。
3．实现原理
3.1 LR分析器结构
LR分析器由三个部分组成：
(1) 总控程序，也可称驱动程序。对所有的LR分析器总控程序都是相同的。
(2) 分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分
析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。
(3) 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。
3.2 LR分析法寻找可归约句柄的依据
1)规范归约的关键问题是找句柄。
2)问题不在于“历史”与“现实”，而是如何基于“历史”对未来“展望”，“展望”可能存在相当多的可能性。
3)一般只是使用简化了的“展望”信息，以便能构造一个可行的分析算法。
4)一个LR分析器实际上是一个带有下推栈的确定的有限状态自动机。可将一个“历史”与这个“历史”下的展望信息综合为抽象的一个状态
5)下推栈可用于存放由“历史”及相应“展望”信息形成的抽象状态。
6)下推栈内的每个状态都概括了从分析开始到归约阶段的全部“历史”和“展望”信息，因此。栈顶的状态可用于决定当前动作，即，LR分析器的每步动作可由栈顶状态和读头下符号唯一确定。
3.3 LR分析器的核心
1、核心
分析表
2、分析表构成
a)动作表(ACTION)
ACTION[S,a]表示在当前状态S下，面临读头下符号a所应采取的动作。
b)转向表(GOTO)
GOTO[S，X]：若X∈VT，表示在当前状态下，读入a应转向什么状态；若X∈VN，表示当前栈顶句柄归约成X后，应转向什么状态。
c)栈结构图
d)分析表格式
3.4 LR分析器的总控程序
总控程序的动作是根据当前栈顶状态Sm和读头下符号ai查表决定。
1、移进
把(Sm, ai)的下一状态S‘=GOTO[Sm，ai]连同读头下符号推进栈内，栈顶成(S’, ai)，而读头前进一格；
2、归约
指用产生式Aα→进行归约。若α的长度为γ，则弹出栈顶γ项，使栈顶状态变为Sm- γ，然后将(Sm- γ,A)的下一状态S’=GOTO[Sm- γ,A]连同非终结符A一起推进栈内，栈顶变为(S’,A)。读头不动，即不改变现行输入符号。
3、接受
宣布分析成功，退出总控程序。
4、报错
报告输入串含有错误，调用相应错误错误处理程序。
3.5 具体过程分析如下：
分析器的动作就是由栈顶状态和当前输入符号所决定。
LR分析器结构：
其中:SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。ACTION[i，a]规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：
(1) 移进：action[i，a]= Sj：状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。
：当在栈顶形成句柄时，则归约为相应的非
(2) 归约：action[i，a]=r
k
终结符A，即文法中有A->B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。
(3) 接受acc:
当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。
(4) 报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。
3.6 LR(0)分析表构造基本思想
只根据“历史”信息识别呈现于栈顶的句柄，而不考虑“展望”信息的状态。
活前缀
1、定义
在规范归约的句型中，不含有句柄以后任何符号的前缀称为活前缀。它有两种情况：归态活前缀和非归态活前缀。
2、归态活前缀
活前缀的尾部正好是句柄之尾，这时可以进行归约。归约之后又会成为另一句型的活前缀。
3、非归态活前缀
句柄尚未形成，需要继续移进若干符号之后才能形成句柄。
3.7 构造LR(0)分析表的方法
3.7.1生成文法G的LR(0)项目
对文法G的每个产生式右部添加一个圆点，称为G的一个LR(0)项目(简称项目)
3.7.2 由项目构成识别文法活前缀的DFA
1)对于一个文法G，我们可以构造一个有限自动机，它能识别G的所有活前缀。
2)由于产生式右部的符号串就是句柄，若这些符号串都已进栈，则表示它已处于归态活前缀，若只有部分进栈，则表示它处于非归态活前缀。要想知道活前缀有多大部分进栈了，可以为每个产生式构造一个自动机，由它的状态来记住当前情况，这时，我们把“状态”称为“项目”。这些自动机的全体就是能识别所有活前缀的有限自动机。
3.7.3将所得DFA确定化
（1）文法G的LR(0)项目生成
在文法的每个产生式右部添加一个圆点，就成为G的一个LR(0)项目。
例如，产生式A → XYZ对应四个项目
A→?XYZ 预期要归约的句柄是XYZ，但都未进栈
A→X?YZ 预期要归约的句柄是XYZ，仅X进栈
A→XY?Z 预期要归约的句柄是XYZ，仅XY进栈
A→X YZ? 已处于归态活前缀，XYZ可进行归约，这个项目也称为归约项目。
(2)产生式右部符号串的长度为n，则可以分解为n+1个项目。
(3)产生式Aε→只有一个项目A→?。
由项目构成识别文法活前缀的NFA
1、将文法进行拓广，保证文法开始符号不出现在任何产生式右部，即增加产生式S`→S，并令S`→? S作为初态项目；
2、凡圆点在串的最右边的项目称终态项目或称归约项目，而S`→S ? 称
为接受项目；
3、设项目i为X →X1…Xi-1?Xi…Xn, 项目j为X →X1… Xi ? Xi＋1 …Xn ，则从项目i画一弧线射向j，标记为Xi ， Xi是终结符则称为移进，Xi是非终结符则称为待约；
4、若项目i为Xα→?Aβ，其中A是非终结符，则从i项目画ε弧射向所有A→? γ的项目，∈γV*
1)构造出的NFA是包含有ε串的NFA，可以使用子集法使之确定化，使之成为一个以项目集为状态的DFA，这个DFA就是建立LR分析算法的基础。
2)相应DFA的每个状态是一个项目集，称作LR(0)项目集，整个状态集称为LR(0)项目集规范簇。
3)在DFA的一个状态对应的项目集内，每个项目是“等价”的，即从期待归约的角度看相同。
4)有一个唯一的初态和一个唯一的接受态，但有若干个归约态，表示有若干种活前缀的识别状态。
5)状态反映了识别句柄的情况，即句柄的多大部分已进栈，即知道了历史情况。
6)手工构造文法的项目集规范
3.7.4 LR(0)项目集规范簇的自动构造
1、拓广文法
增加S` →S 产生式，使文法的开始符号不出现在任何产生式右部，从而保证有唯一的接受项目。
2、定义和构造项目集的闭包
设I是拓广文法G`的一个项目集，如下定义和构造I的闭包CLOSURE(I)：
a) I的任何项目都属于CLOSURE(I)；
b) 若Aα→?Bβ属于CLOSURE(I),B是非终结符，则对任何关于B的产生式Bγ→，项目B→?γ也属于CLOSURE(I);
c) 重复执行步骤b)直到CLOSURE(I)不再扩大为止。
3、定义状态转换函数GO
GO(I,X)定义为CLOSURE(J)，其中I,J都是项目集，X ∈( VN?VT),J={任何形如Aα→X?β的项目| Aα→?X∈βI}。
4、构造LR(0)项目集规范族的算法
PROC ITEMSETS-LR0
{ C:={CLOSURE(S` →?S)} /*初态项目集*/
DO
{ FOR (对C中每个项目集I和G`中每个文法符号X)
IF (GO(I,X)非空且不属于C)
{把GO(I,X)加入C中}
}WHILE C仍然在扩大
}
3.7.5 LR(0)分析表的构造算法
设C={I0,I1,…In},以各项目集Ik(k＝0，…,n)的k作为状态序号，并以包含S` →?S的项目集作为初始状态，同时将G`文法的产生式进行编号。然后按下列步骤填写ACTION表和GOTO表：
1、若项目Aα→?aβ属于Ik状态且GO(Ik,a)= Ij,a为终结符，则置ACTION[k,a]=Sj; 即：移进a，并转向Ij状态。
2、若项目Aα→? ∈Ik,则对任何终结符a(包括语句结束符＃),置ACTION[k,a]=rj;即根据j号产生式进行归约，其中，j为产生式Aα→的编号。
3、若项目S` →S?属于Ik, 则置ACTION[k,＃]=accept,简记为acc;
4、若GO(Ik ，A)= Ij,A是非终结符，则置GOTO[k,A]=j;
5、分析表中凡不能用步骤1至4填入信息的空白项，均置上“出错标志”。
4．算法实现流程图
5．测试数据
[终结符]
a
b
c
d
[非终结符]
E
A
B
[开始符]
E
[产生式]
E->aA
E->bB
A->cA
A->d
B->cB
B->d
6．结果输出及分析
下面是你输入的文法G：
非终结符号集合为：{ E, A, B }
终结符符号集合为：{ a, b, c, d } G[E]:
(1) E->aA
(2) E->bB
(3) A->cA
(4) A->d
(5) B->cB
(6) B->d
下面是生成的拓广文法G'：
非终结符号集合为：{ $, E, A, B } 终结符符号集合为：{ a, b, c, d } G'[E]:
(0) $->E
(1) E->aA
(2) E->bB
(3) A->cA
(4) A->d
(5) B->cB
(6) B->d
该文法的项目如下：
(1) $->.E
(2) $->E.
(3) E->.aA
(4) E->a.A
(5) E->aA.
(6) E->.bB
(7) E->b.B
(8) E->bB.
(9) A->.cA
(10) A->c.A
(11) A->cA.
(12) A->.d
(13) A->d.
(14) B->.cB
(15) B->c.B
(16) B->cB.
(17) B->.d
(18) B->d.
LR(0)项目规范族如下：I0 = { 1, 3, 6 }
I1 = { 2 }
I2 = { 4, 9, 12 }
I3 = { 7, 14, 17 }
I4 = { 5 }
I5 = { 10, 9, 12 }
I6 = { 13 }
I7 = { 8 }
I8 = { 15, 14, 17 } I9 = { 18 }
I10 = { 11 }
I11 = { 16 }
图一:读入文法
图二：分析文法
图三：分析句子：ad
图四：生成树
7．软件运行环境及限制
系统平台：Windows XP/2000
软件平台：VC++ 6.0
8．心得体会
归约的时候应该从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i 为修改指针后的栈顶状态。
而在当归约到文法符号栈中只剩文法的开始符号E时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。
LR(0)分析器归约是个难点，应该认真分析文法结构。通过实验设计加深了对VC的熟练程度和对编译原理课程的理解。
总的来说，形式语言是编译原理的基础，是建立文法，分析文法的重要知识基础。
9．参考文献
《程序设计语言编译方法》（第三版）肖军模大连理工出版社
《编译原理教程习题解析与上机指导》胡元义西安电子科技大学出版社《编译原理学习与应用指导》张永梅国防工业出版社
《编译原理》李建中机械工业出版社
编译原理 实 验 报 告 目的要求 1.构造文法的语法分析程序，要求采用预测分析法对输入的字符串进行语法 分析。 2.加深对预测分析LL（1）分析法的理解和掌握。 实验内容 对文法G进行语法分析，文法G如下所示： *0. S→a */ *1. S→^ *2. S→(T) *3. T→SW * *4. W→,SW *5. W→ε; 并对任给的一个输入串进行语法分析检查。程序要求能对输入串进行预测分析，能判别程序是否符合已知的语法规则，如果不符合（编译出错），则输出错误信息。 程序输入/输出示例： 输入:一个以 # 结束的符号串：例如：(a,a)# 输出: 步数分析栈输入串所用规则 (1) #S (a,a))# 2
源程序： //LL(1)预测分析控制程序 #include
编译原理实验--词法分析器 实验一词法分析器设计 【实验目的】 1(熟悉词法分析的基本原理，词法分析的过程以及词法分析中要注意的问题。 2(复习高级语言，进一步加强用高级语言来解决实际问题的能力。 3(通过完成词法分析程序，了解词法分析的过程。 【实验内容】 用C语言编写一个PL/0词法分析器，为语法语义分析提供单词，使之能把输入的字符 串形式的源程序分割成一个个单词符号传递给语法语义分析，并把分析结果(基本字， 运算符，标识符，常数以及界符)输出。 【实验流程图】
【实验步骤】 1(提取pl/0文件中基本字的源代码 while((ch=fgetc(stream))!='.') { int k=-1; char a[SIZE]; int s=0; while(ch>='a' && ch<='z'||ch>='A' && ch<='Z') { if(ch>='A' && ch<='Z') ch+=32; a[++k]=(char)ch; ch=fgetc(stream); } for(int m=0;m<=12&&k!=-1;m++) for(int n=0;n<=k;n++) {
if(a[n]==wsym[m][n]) ++s; else s=0; if(s==(strlen(wsym[m]))) {printf("%s\t",wsym[m]);m=14;n=k+1;} } 2(提取pl/0文件中标识符的源代码 while((ch=fgetc(stream))!='.') { int k=-1; char a[SIZE]=" "; int s=0; while(ch>='a' && ch<='z'||ch>='A' && ch<='Z') { if(ch>='A' && ch<='Z') ch+=32; a[++k]=(char)ch; ch=fgetc(stream); } for(int m=0;m<=12&&k!=-1;m++) for(int n=0;n<=k;n++) { if(a[n]==wsym[m][n]) ++s; else s=0; if(s==(strlen(wsym[m]))) {m=14;n=k+1;} } if(m==13) for(m=0;a[m]!=NULL;m++) printf("%c ",a[m]);
编译原理实验报告实验名称：实验一编写词法分析程序 实验类型：验证型实验 指导教师：何中胜 专业班级：13软件四 姓名：丁越 学号： 电子邮箱： 实验地点：秋白楼B720 实验成绩： 日期：2016年3 月18 日
一、实验目的 通过设计、调试词法分析程序，实现从源程序中分出各种单词的方法；熟悉词法分析 程序所用的工具自动机，进一步理解自动机理论。掌握文法转换成自动机的技术及有穷自动机实现的方法。确定词法分析器的输出形式及标识符与关键字的区分方法。加深对课堂教学的理解；提高词法分析方法的实践能力。通过本实验，应达到以下目标： 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、实验过程 以编写PASCAL子集的词法分析程序为例 1.理论部分 （1）主程序设计考虑 主程序的说明部分为各种表格和变量安排空间。 数组 k为关键字表，每个数组元素存放一个关键字。采用定长的方式，较短的关键字 后面补空格。 P数组存放分界符。为了简单起见，分界符、算术运算符和关系运算符都放在 p表中 （编程时，还应建立算术运算符表和关系运算符表，并且各有类号），合并成一类。 id和ci数组分别存放标识符和常数。 instring数组为输入源程序的单词缓存。 outtoken记录为输出内部表示缓存。 还有一些为造表填表设置的变量。 主程序开始后，先以人工方式输入关键字，造 k表；再输入分界符等造p表。 主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词；接收键盘上 送来的一个单词；调用词法分析过程；输出每个单词的内部码。 ⑵词法分析过程考虑 将词法分析程序设计成独立一遍扫描源程序的结构。其流程图见图1-1。 图1-1 该过程取名为 lexical，它根据输入单词的第一个字符（有时还需读第二个字符），判断单词类，产生类号：以字符 k表示关键字；i表示标识符；c表示常数；p表示分界符；s表示运算符（编程时类号分别为 1，2，3，4，5）。 对于标识符和常数，需分别与标识符表和常数表中已登记的元素相比较，如表中已有 该元素，则记录其在表中的位置，如未出现过，将标识符按顺序填入数组id中，将常数 变为二进制形式存入数组中 ci中，并记录其在表中的位置。 lexical过程中嵌有两个小过程：一个名为getchar，其功能为从instring中按顺序取出一个字符，并将其指针pint加1；另一个名为error，当出现错误时，调用这个过程， 输出错误编号。 2.实践部分
1.实验目的：掌握LL(1)分析法的基本原理，掌握LL(1)分析表的构造方法，掌握LL(1) 驱动程序的构造方法。 2.实验要求：实现LR分析法（P147,例）或预测分析法（P121,例）。 3.实验环境：一台配置为1G的XP操作系统的PC机;Visual C++. 4.实验原理：编译程序的语法分析器以单词符号作为输入，分析单词符号串是否形成符合语 法规则的语法单位，如表达式、赋值、循环等，最后看是否构成一个符合要求的程序，按该 语言使用的语法规则分析检查每条语句是否有正确的逻辑结构，程序是最终的一个语法单 位。编译程序的语法规则可用上下文无关文法来刻画。 语法分析的方法分为两种：自上而下分析法和自下而上分析法。自上而下就是从文法 的开始符号出发，向下推导，推出句子。而自下而上分析法采用的是移进归约法，基本思想 是：用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生 式的一个候选式时，即把栈顶的这一部分归约成该产生式的左邻符号。 自顶向下带递归语法分析：1、首先对所以的生成式消除左递归、提取公共左因子 2、在源程序里建立一个字符串数组，将所有的生成式都存在这个数组中。 3、给每个非终结符写一个带递归的匹配函数，其中起始符的函数写在main函数里。 这些函数对生成式右边从左向右扫描，若是终结符直接进行匹配，匹配失败，则调用出错函 数。如果是非终结符则调用相应的非终结符函数。 4、对输入的符号串进行扫描，从起始符的生成式开始。如果匹配成功某个非终结符 生成式右边的首个终结符，则将这个生成式输出。匹配过程中，应该出现的非终结符没有出 现，则出错处理。 5.软件设计与编程：对应源程序代码： #include <> #include <> #include
词法分析 一、实验目的 设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 二、实验要求 2.1 待分析的简单的词法 （1）关键字： begin if then while do end 所有的关键字都是小写。 （2）运算符和界符 ： = + - * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 2.2 各种单词符号对应的种别码： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 例如：对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列： (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。
3.1 主程序示意图： 主程序示意图如图3-1所示。其中初始包括以下两个方面： ⑴关键字表的初值。 关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下： Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 图3-1 （2）程序中需要用到的主要变量为syn,token和sum 3.2 扫描子程序的算法思想： 首先设置3个变量：①token用来存放构成单词符号的字符串；②sum用来整型单词；③syn用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。
实验二语法分析器 一、实验目的 通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。 二、实验内容 ◆根据某一文法编制调试LL （1 ）分析程序，以便对任意输入的符号串 进行分析。 ◆构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分 析程序。 ◆分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号 以及LL（1）分析表，对输入符号串自上而下的分析过程。 三、LL（1）分析法实验设计思想及算法 ◆模块结构： （1）定义部分：定义常量、变量、数据结构。 （2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）； （3）控制部分：从键盘输入一个表达式符号串； （4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。
四、实验要求 1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 2、如果遇到错误的表达式，应输出错误提示信息。 3、对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）E->TG （2）G->+TG|—TG （3）G->ε （4）T->FS （5）S->*FS|/FS （6）S->ε （7）F->(E) （8）F->i 输出的格式如下：
五、实验源程序 LL1.java import java.awt.*; import java.awt.event.*; import javax.swing.*; import javax.swing.table.DefaultTableModel; import java.sql.*; import java.util.Vector; public class LL1 extends JFrame implements ActionListener { /** * */ private static final long serialVersionUID = 1L; JTextField tf1; JTextField tf2; JLabel l; JButton b0; JPanel p1,p2,p3; JTextArea t1,t2,t3; JButton b1,b2,b3;
编译技术实验报告 实验题目：词法分析 学院：信息学院 专业：计算机科学与技术学号： 姓名：
一、实验目的 (1)理解词法分析的功能； (2)理解词法分析的实现方法； 二、实验内容 PL0的文法如下 …< >?为非终结符。 …::=? 该符号的左部由右部定义，可读作“定义为”。 …|? 表示…或?，为左部可由多个右部定义。 …{ }? 表示花括号内的语法成分可以重复。在不加上下界时可重复0到任意次 数，有上下界时可重复次数的限制。 …[ ]? 表示方括号内的成分为任选项。 …( )? 表示圆括号内的成分优先。 上述符号为“元符号”，文法用上述符号作为文法符号时需要用引号…?括起。 〈程序〉∷=〈分程序〉． 〈分程序〉∷= [〈变量说明部分〉][〈过程说明部分〉]〈语句〉 〈变量说明部分〉∷=V AR〈标识符〉{，〈标识符〉}：INTEGER； 〈无符号整数〉∷=〈数字〉{〈数字〉} 〈标识符〉∷=〈字母〉{〈字母〉|〈数字〉} 〈过程说明部分〉∷=〈过程首部〉〈分程序〉{；〈过程说明部分〉}； 〈过程首部〉∷=PROCEDURE〈标识符〉； 〈语句〉∷=〈赋值语句〉|〈条件语句〉|〈过程调用语句〉|〈读语句〉|〈写语句〉|〈复合语句〉|〈空〉 〈赋值语句〉∷=〈标识符〉∶=〈表达式〉 〈复合语句〉∷=BEGIN〈语句〉{；〈语句〉}END 〈条件〉∷=〈表达式〉〈关系运算符〉〈表达式〉 〈表达式〉∷=〈项〉{〈加法运算符〉〈项〉} 〈项〉∷=〈因子〉{〈乘法运算符〉〈因子〉} 〈因子〉∷=〈标识符〉|〈无符号整数〉|'('〈表达式〉')' 〈加法运算符〉∷=+|- 〈乘法运算符〉∷=* 〈关系运算符〉∷=<>|=|<|<=|>|>= 〈条件语句〉∷=IF〈条件〉THEN〈语句〉 〈字母〉∷=a|b|…|X|Y|Z 〈数字〉∷=0|1|2|…|8|9 实现PL0的词法分析
实验1-3 《编译原理》S语言词法分析程序设计方案 一、实验目的 了解词法分析程序的两种设计方法之一：根据状态转换图直接编程的方式； 二、实验内容 1．根据状态转换图直接编程 编写一个词法分析程序，它从左到右逐个字符的对源程序进行扫描，产生一个个的单词的二元式，形成二元式（记号）流文件输出。在此，词法分析程序作为单独的一遍，如下图所示。 具体任务有： （1）组织源程序的输入 （2）拼出单词并查找其类别编号，形成二元式输出，得到单词流文件 （3）删除注释、空格和无用符号 （4）发现并定位词法错误，需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 （5）对于普通标识符和常量，分别建立标识符表和常量表（使用线性表存储），当遇到一个标识符或常量时，查找标识符表或常量表，若存在，则返回位置，否则返回0并且填写符号表或常量表。 标识符表结构：变量名，类型（整型、实型、字符型），分配的数据区地址 注：词法分析阶段只填写变量名，其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构：常量名，常量值 三、实验要求 1．能对任何S语言源程序进行分析 在运行词法分析程序时，应该用问答形式输入要被分析的S源语言程序的文件名，然后对该程序完成词法分析任务。 2．能检查并处理某些词法分析错误 词法分析程序能给出的错误信息包括：总的出错个数，每个错误所在的行号，错误的编号及错误信息。 本实验要求处理以下两种错误（编号分别为1，2）： 1：非法字符：单词表中不存在的字符处理为非法字符，处理方式是删除该字符，给出错误信息，“某某字符非法”。 2：源程序文件结束而注释未结束。注释格式为：/* …… */ 四、保留字和特殊符号表
编译原理实验报告
实验一 一、实验名称：词法分析器的设计 二、实验目的：1，词法分析器能够识别简单语言的单词符号 2，识别出并输出简单语言的基本字.标示符.无符号整数.运算符.和界符。 三、实验要求：给出一个简单语言单词符号的种别编码词法分析器 四、实验原理： 1、词法分析程序的算法思想 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 2、程序流程图 （1 （2）扫描子程序
3
五、实验内容： 1、实验分析 编写程序时，先定义几个全局变量a[]、token[]（均为字符串数组),c,s( char型)，i,j,k（int型），a[]用来存放输入的字符串，token[]另一个则用来帮助识别单词符号，s用来表示正在分析的字符。字符串输入之后，逐个分析输入字符，判断其是否‘#’，若是表示字符串输入分析完毕，结束分析程序，若否则通过int digit(char c)、int letter(char c)判断其是数字，字符还是算术符,分别为用以判断数字或字符的情况，算术符的判断可以在switch语句中进行，还要通过函数int lookup(char token[])来判断标识符和保留字。 2 实验词法分析器源程序： #include
本代码只供学习参考： 词法分析源代码： #include
河南工业大学实验报告 课程编译原理实验名称实验二 LL(1)分析法 实验目的 1．掌握LL(1)分析法的基本原理； 2．掌握LL(1)分析表的构造方法； 3．掌握LL(1)驱动程序的构造方法。 一.实验内容及要求 根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。 对下列文法，用LL（1）分析法对任意输入的符号串进行分析： （1）E->TG （2）G->+TG （3）G->ε （4）T->FS （5）S->*FS （6）S->ε （7）F->(E) （8）F->i 程序输入一以#结束的符号串(包括+*（）i#)，如：i+i*i#。输出过程如下： 步骤分析栈剩余输入串所用产生式 1E i+i*i#E->TG ............ 二.实验过程及结果 代码如下： #include
string edge::getlf() { return left; } string edge::getrg() { return right; } string edge::getfirst() { return first; } string edge::getfollow() { return follow; } string edge::getselect() { return select; } string edge::getro() { string str; str+=right[0]; return str; } int edge::getrlen() { return right.length(); } void edge::newfirst(string w) { int i; for(i=0;i
实验2 词法分析程序的设计 一、实验目的 掌握计算机语言的词法分析程序的开发方法。 二、实验内容 编制一个能够分析三种整数、标识符、主要运算符和主要关键字的词法分析程序。 三、实验要求 1、根据以下的正规式，编制正规文法，画出状态图； 标识符<字母>(<字母>|<数字字符>)* 十进制整数0 | (（1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*) 八进制整数0（1|2|3|4|5|6|7）（0|1|2|3|4|5|6|7）* 十六进制整数0x（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）* 运算符和界符+ - * / > < = ( ) ； 关键字if then else while do 2、根据状态图，设计词法分析函数int scan( )，完成以下功能： 1）从文本文件中读入测试源代码，根据状态转换图，分析出一个单词， 2）以二元式形式输出单词<单词种类，单词属性> 其中单词种类用整数表示： 0：标识符 1：十进制整数 2：八进制整数 3：十六进制整数 运算符和界符，关键字采用一字一符，不编码 其中单词属性表示如下： 标识符，整数由于采用一类一符，属性用单词表示 运算符和界符，关键字采用一字一符，属性为空 3、编写测试程序，反复调用函数scan( )，输出单词种别和属性。 四、实验环境 PC微机 DOS操作系统或Windows 操作系统 Turbo C 程序集成环境或Visual C++ 程序集成环境 五、实验步骤 1、根据正规式，画出状态转换图；
一、实验目的 了解词法分析程序的两种设计方法：1.根据状态转换图直接编程的方式；2.利用DFA 编写通用的词法分析程序。 二、实验内容及要求 1．根据状态转换图直接编程 编写一个词法分析程序，它从左到右逐个字符的对源程序进行扫描，产生一个个的单词的二元式，形成二元式（记号）流文件输出。在此，词法分析程序作为单独的一遍，如下图所示。 具体任务有： （1）组织源程序的输入 （2）拼出单词并查找其类别编号，形成二元式输出，得到单词流文件 （3）删除注释、空格和无用符号 （4）发现并定位词法错误，需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 （5）对于普通标识符和常量，分别建立标识符表和常量表（使用线性表存储），当遇到一个标识符或常量时，查找标识符表或常量表，若存在，则返回位置，否则返回0并且填写符号表或常量表。 标识符表结构：变量名，类型（整型、实型、字符型），分配的数据区地址 注：词法分析阶段只填写变量名，其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构：常量名，常量值 2．编写DFA模拟程序 算法如下： DFA（S=S0,MOVE[][],F[],ALPHABET[]） /*S为状态，初值为DFA的初态，MOVE[][]为状态转换矩阵，F[] 为终态集，ALPHABET[] 为字母表，其中的字母顺序与MOVE[][] 中列标题的字母顺序一致。*/ { Char Wordbuffer[10]=“”//单词缓冲区置空 Nextchar=getchar（）；//读 i=0； while（nextchar！=NULL）//NULL代表此类单词 { if （nextcha r！∈ALPHABET[]）{ERROR（“非法字符”），return（“非法字符”）；} S=MOVE[S][nextchar] //下一状态 if（S=NULL）return（“不接受”）；//下一状态为空，不能识别，单词错误 wordbuffer[i]=nextchar ；//保存单词符号 i++； nextchar=getchar（）； } Wordbuffer[i]=‘\0’;
预测分析法实验报告 一、实验项目名称 预测分析法 二、实验目的 根据某一LL(1)文法编制调试预测分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析法的理解。 三、实验环境 Windows 10 Microsoft Visual Studio 2015 四、实验内容 本次实验的LL(1)文法为表达式文法： E→E+T | T T→T*F | F F→i | (E) 编写识别表达式文法的合法句子的预测分析程序，对输入的任意符号串，给出分析过程及分析结果。分析过程要求输出步骤、分析栈、剩余输入串和所用产生式。如果该符号串不是表达式文法的合法句子，要给出尽量详细的错误提示 五、源程序清单、测试数据、结果 #include
词法分析器实验报告 一、实验目的 选择一种编程语言实现简单的词法分析程序，设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 二、实验要求 待分析的简单的词法 （1）关键字： begin if then while do end 所有的关键字都是小写。 （2）运算符和界符 ： = + - * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 各种单词符号对应的种别码： 表各种单词符号对应的种别码 词法分析程序的功能： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 例如：对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列： (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根
据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 主程序示意图： 主程序示意图如图3-1所示。其中初始包括以下两个方面： ⑴关键字表的初值。 关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下： Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 图3-1 （2）程序中需要用到的主要变量为syn,token和sum 扫描子程序的算法思想： 首先设置3个变量：①token用来存放构成单词符号的字符串；②sum用来整型单词；③syn 用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。
河海大学 编译原理课程设计 学生姓名： 学号： 班级： 专业：--------- 指导教师：
编译原理 课程设计指导书
题目一基于语法制导翻译的表达式转换编译器 一、设计目的 通过本课程设计获得对实际编译器的构造原理、过程和方法的感性认识，全面掌握语法制导翻译技术。 二、设计内容 采用语法制导翻译模式设计一个包含词法分析、语法分析、符号表管理、错误处理及输出等功能模块的、由中缀表达式到后缀表达式的完整编译器。该翻译器的规格说明如下： start → list eof list → expr;list |ε expr → expr + term { print(‘+’) } | expr –term { print(‘-’) } | term term → term * factor { print(‘*’) } | term / factor { print(‘/’) } | term div factor { print(‘DIV’) } | term mod factor { print(‘MOD’) } factor → ( expr ) | id { print( https://www.doczj.com/doc/324901021.html, ) } | num { print( num.value ) } 三、设计要求 1、使用模块化设计思想来设计该编译器； 2、词法分析模块用于读入输入串，并将其转换成供语法分析模块使用的记号流。其中包括滤掉空格和注释、识别常数、识别标识符和关键字等功能； 3、要求在语法分析模块中利用语法制导翻译技术完成具体的中缀表达式到后缀表达式的翻译，其中包括按前述翻译器的规格说明构建对应表达式、项、因子的非终结符expr、term 和factor的函数以及检查记号是否匹配的函数；并在不匹配时调用错误处理模块； 4、要求符号表管理模块主要完成符号表对应数据结构的具体实现功能； 5、错误处理模块负责报告错误信息及位置，并终止分析过程； 6、输出模块完成翻译后所得到的后缀表达式的输出。
编译原理实验 词 法 分 析 程 序
实验一：词法分析程序 1、实验目的 从左至右逐个字符的对源程序进行扫描，产生一个个单词符号，把字符串形式的源程序改造成单词符号形式的中间程序。 2、实验内容 表C语言子集的单词符号及内码值 单词符号种别编码助记符内码值 while 1 while -- if 2 if -- else 3 else -- switch 4 switch -- case 5 case -- 标识符 6 id id在符号表中的位置 常数7 num num在常数表中的位置 + 8 + -- - 9 - -- * 10 * -- <= 11 relop LE < 11 relop LT == 11 relop LQ = 12 = -- ; 13 ; -- 输入源程序如下 if a==1 a=a+1; else a=a+2; 输出对应的单词符号形式的中间程序 3、实验过程 实验上机程序如下： #include "stdio.h" #include "string.h" int i,j,k; char s ,a[20],token[20]; int letter() { if((s>=97)&&(s<=122))return 1; else return 0; } int Digit() {if((s>=48)&&(s<=57))return 1;
else return 0; } void get() { s=a[i]; i=i+1; } void retract() {i=i-1;} int lookup() { if(strcmp(token, "while")==0) return 1; else if(strcmp(token, "if")==0) return 2; else if(strcmp(token,"else")==0) return 3; else if(strcmp(token,"switch")==0) return 4; else if(strcmp(token,"case")==0) return 5; else return 0; } void main() { printf("please input you source program,end('#'):\n"); i=0; do { i=i+1; scanf("%c",&a[i]); }while(a[i]!='#'); i=1; memset(token,0,sizeof(char)*10); j=0; get(); while(s!='#') { if(s==' '||s==10||s==13) get(); else { switch(s)
词法分析设计 1. 实验目的 通过本实验的编程实践，了解词法分析的任务，掌握词法分析程序设计的原理和构造方法，对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。 2. 实验内容 用C++语言实现对C++语言子集的源程序进行词法分析。通过输入源程序从左到右对字符串进行扫描和分解，依次输出各个单词的内部编码及单词符号自身值；若遇到错误则显示“Error”，然后跳过错误部分继续显示；同时进行标识符登记符号表的管理。 3. 实验原理 本次实验采用NFA->DFA->DFA0的过程: 对待分析的简单的词法（关键词/id/num/运算符/空白符等）先分别建立自己的FA，然后将他们用产生式连接起来并设置一个唯一的开始符，终结符不合并。 待分析的简单的词法 （1）关键字： "asm","auto","bool","break","case","catch","char","class","
const","const_cast"等 （2）界符（查表） ";",",","(",")","[","]","{","}" （3）运算符 "*","/","%","+","-","<<","=",">>","&","^","|","++","--"," +=","-=","*=","/=","%=","&=","^=","|=" relop： （4）其他单词是标识符（ID）和整型常数（SUM），通过正规式定义。 id/keywords: digit: （5）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。
编译原理 实验报告 实验名称：词法分析及语法分析专业班级： 姓名： 学号： 完成日期：
实验一、sample语言的词法分析 一、实验目的 给出SAMPLE文法规范，要求编写SAMPLE语言的词法分析程序。 二、实验准备 了解sample语言单词的定义，选择任一种编程语言实现词法分析。 三、实验内容 给出SAMPLE语言文法，输出单词（关键字、专用符号以及其它标记）。 1、格式 输入：源程序文件。输出：关键字、专用符号以及其它标记。 2、实现原理 程序中先判断这个句语句中每个单元为关键字、常数、运算符、界符，对与不同的单词符号给出不同编码形式的编码，用以区分之。 3、实验方法 读懂Sample源代码，自己重点独立实现对常量的判别。 四、实验设计 1、设计SAMPLE语言的词法分析器 A、字符集定义 1． <字符集> → <字母>│<数字>│<单界符> 2． <字母> → A│B│…│Z│a│b│…│z 3． <数字> → 0│1│2│…│9 4． <单界符> → +│-│*│/│=│<│>│(│)│[│]│:│. │; │, │' B、单词集定义 5．<单词集> → <保留字>│<双界符>│<标识符>│<常数>│<单界符> 6．<保留字> → and│array│begin│bool│call│case│char│constant│dim│do│else │end│false│for│if│input│integer│not│of│or│output│procedure│program │read│real│repeat│set│stop│then│to│true│until│var│while│write 7．<双界符> → <>│<=│>=│:= │/*│*/│.. 8．<标识符> → <字母>│<标识符> <数字>│<标识符> <字母> 9．<常数> → <整数>│<布尔常数>│<字符常数> 10．<整数> → <数字>│<整数> <数字> 11．<布尔常数> → true│false 12．<字符常数> → ' 除 {'} 外的任意字符串 ' 2、词法分析系统流程设计