词法分析2

1《编译原理》实验报告2实验具体内容如下：序号实验名称实验一词法分析设计实验二LL(1)预测分析实验三LR(1)预测分析一、实验课的性质和目的：（1）深刻理解程序语言编译系统的结构及各部分的功能。（2）熟练掌握设计和构造程序语言编译系统的基本原理和技术。（3）能独立编写清晰、工整、结论正确的编译原理的源程序。（4）能学会上机进行正确调试，并进行程序修改。即培养发现程序错误，排除错误的能力和经验。二、实验的重点与难点：对词法分析设计、语法分析设计和中间代码的产生、代码优化等是本课程实践性环节的重点和难点。三、实验教学环境：通过本课程的课内实验，使学生上机编程、调试来验证和巩固所学的编译原理理论及概念，逐步掌握词法分析的设计方法及实现技术。软件实验室为为每个学生提供了一台具有WINDOWS98/XP/NT/2000操作系统的计算机和VC++/VB/JAVA/TC等软件环境。3目录目录.........................................................5实验一:词法分析设计..............................................6实验二：LL(1)分析法.............................................13实验三：LR(1)分析法.............................................164实验一词法分析设计一、实验目的通过本实验的编程实践，使学生了解词法分析的任务，掌握词法分析程序设计的原理和构造方法，使学生对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。二、实验内容用VC++/VB/JAVA语言实现对C语言子集的源程序进行词法分析。通过输入源程序从左到右对字符串进行扫描和分解，依次输出各个单词的内部编码及单词符号自身值；若遇到错误则显示“Error”，然后跳过错误部分继续显示；同时进行标识符登记符号表的管理。以下是实现词法分析设计的主要工作：（1）从源程序文件中读入字符。（2）统计行数和列数用于错误单词的定位。（3）删除空格类字符，包括回车、制表符空格。（4）按拼写单词，并用（内码，属性）二元式表示。(属性值——token的机内表示)（5）如果发现错误则报告出错（6）根据需要是否填写标识符表供以后各阶段使用。单词的基本分类：关键字：由程序语言定义的具有固定意义的标识符。也称为保留字例如if、for、while、printf；单词种别码为1。标识符：用以表示各种名字，如变量名、数组名、函数名；5常数：任何数值常数。如125,1,0.5,3.1416；运算符：+、-、*、/；关系运算符：、=、=、、=、；分界符：；、，、（、）、[、]；三、词法分析实验设计思想及算法1、主程序设计考虑：程序的说明部分为各种表格和变量安排空间。在具体实现时，将各类单词设计成结构和长度均相同的形式，较短的关键字后面补空。k数组------关键字表，每个数组元素存放一个关键字（事先构造好关键字表）。s数组------存放分界符表（可事先构造好分界符表）。为了简单起见，分界符、算术运算符和关系运算符都放在s表中（编程时，应建立算术运算符表和关系运算符表，并且各有类号），合并成一类。id和ci数组分别存放标识符和常数。instring数组为输入源程序的单词缓存。outtoken记录为输出内部表示缓存。还有一些为造表填表设置的变量。主程序开始后，先以人工方式输入关键字，造k表；再输入分界符等造p表。主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词；接收键盘上送来的一个单词；调用词法分析过程；输出每个单词的内部码。例如，把每一单词设计成如下形式:(type,pointer)其中type指明单词的种类，例如：Pointer指向本单词存放处的开始位置。还有一些为造表填表设置的变量。主程序开始后，先以人工方式输入关键字，造k表；再输入分界符等造p表。主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词；接收键盘上送来的一个单词；调用词法分析过程；输出每个单词的内部码。例如，把每一单词设计成如下形式:(type,pointer)6其中type指明单词的种类，例如：Pointer指向本单词存放处的开始位置。7词法分析设计流程图2、词法分析过程考虑根据输入单词的第一个字符（有时还需读第二个字符），判断单词类，产生类号：以字符k表示关键字；id表示标识符；ci表示常数；s表示分界符。对于标识符和常数，需分别与标识符表和常数表中已登记的元素相比较，如表中已有该元素，则记录其在表中的位置，如未出现过，将标识符按顺序填入数组id中，将常数变为二进制形式存入数组中ci中，并记录其在表中的位置。lexical过程中嵌有两个小过程：一个名为getchar，其功能为从instring中按顺序取出一个字符，并将其指针pint加1；另一个名为error，当出现错误时，调用这个过程，输出错误编号。要求：所有识别出的单词都用两个字节的等长表示，称为内部码。第一个字节为t，第二个字节为i。t为单词的种类。关键字的t=１；分界符的t=２；算术运算符的t=３；关系运算符的t=４；无符号数的t=５；标识符的t=６。i为该单词在各自表中的指针或内部码值。表1为关键字表；表2为8分界符表；表3为算术运算符的i值；表4为关系运算符的i值。3．实验的处理单词集单词符号单词种类任意变量0（1）2{3}4；5=6+7*8910,11?12整型常数30main20int21if22then239Else24Return25出错100取字符和统计字符行列位置子程序10四、实验源代码：11121314五、实验结果：“实验程序开始菜单”15“实验程序执行后菜单”“目标文件夹生成的新文件”附：新生成的文件内容proc1标识符(25分界符)26分界符nota1标识符:32分界符int1标识符;29分界符x1标识符:32分界符int1标识符;29分界符a1标识符:32分界符int1标识符;29分界符b1标识符:32分界符int1标识符;29分界符d1标识符:32分界符int1标识符;29分界符16f1标识符:32分界符int1标识符;29分界符y1标识符:32分界符int1标识符;29分界符while14关键字4a3错误47运算符nota1标识符do13关键字a1标识符=45运算符b1标识符+41运算符d1标识符*43运算符b1标识符;29分界符if10关键字x1标识符47运算符f1标识符and23关键字f1标识符47运算符y1标识符then11关键字y1标识符=45运算符x1标识符+41运算符y1标识符else12关键字y1标识符=45运算符x1标识符+41运算符f1标识符end5关键字if10关键字17六、实验小结词法分析（英语：lexicalanalysis）是计算机科学中将字符序列转换为单词（Token）序列的过程。词法分析器一般以函数的形式存在，供语法分析器调用。词法分析阶段是编译过程的第一个阶段，是编译的基础。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。这里的单词是一个字符串，是构成源代码的最小单位。从输入字符流中生成单词的过程叫作单词化（Tokenization），在这个过程中，词法分析器还会对单词进行分类。词法分析器通常不会关心单词之间的关系（属于语法分析的范畴），举例来说：词法分析器能够将括号识别为单词，但并不保证括号是否匹配。sum=3+2;将其单词化后可以得到下表内容：语素单词类型sum标识符=赋值操作符3数字+加法操作符2数字;语句结束18实验二LL(1)分析法一、实验目的通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。二、实验内容根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL（1）分析表，对输入符号串自上而下的分析过程。三、LL（1）分析法实验设计思想及算法模块结构：（1）定义部分：定义常量、变量、数据结构。（2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；（3）控制部分：从键盘输入一个表达式符号串；（4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。19四、实验要求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输出的格式如下：20五、实验源代码21222324252627六、实验结果“开始菜单”“对给定代码的LL（1）分析结果”“LL（1）分析的FIRST集、FOLLOW集”七、实验小结LL(1)分析使用显式栈而不是递归调用来完成分析。以标准方式表示这个栈非常有用，这样LL(1)分析程序的动作就可以快捷地显现出来。在这个介绍性的讨论中，我们使用了生成成对括号的串的简单文法。输入符号由左列向右。美元符号标出了输入的结束（它与由扫描程序生成的EOF记号相对应）。给出了由分析程序执行的动作的简短描述，它将改变栈和（有可能）输入。LL(1)28分析中的重复和选择也存在着与在递归下降程序分析中遇到的类似问题，而且正是由于这个原因，还不能够为的简单算法表达式文法给出一个LL(1)分析表。在了解了first集和follow集的计算方法后，则可以通过另一些规则构造出LL需要的分析表。编译原理里总有很多很多的理论和算法。但正是这些理论和算法，使得编译器的实现变得简单，代码易维护。在某个特定的编程语言中，因为其文法一定，所以对于其LL(1)实现中的分析表就是确定的。我们也不需要在程序里动态构造first和follow集合。实验三LR(1)分析法一、实验目的构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。二、实验内容对下列文法，用LR（1）分析法对任意输入的符号串进行分析：（1）E-E+T（2）E-E—T（3）T-T*F（4）T-T/F（5）F-(E)（6）F-i三、LR（1）分析法实验设计思想及算法(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。LR分析器由三个部分组成：29其中: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]=rk：当在栈顶形成