《语法分析程序的设计与实现》由会员分享，可在线阅读，更多相关《语法分析程序的设计与实现（13页珍藏版）》请在金锄头文库上搜索。
1、语法分析程序的设计与实现一：实验内容：2二：实验要求：2三：实验方法：2由LEX建立YACC的词法分析程序2yacc原理介绍3词法分析4解析器如何工作5Yacc环境6常用代码7第四：YACC内部名称：7第五：运行结果（源代码见附录）8第六：实验总结9第七：附录10附录一：yacc程序，加注释10附录二：词法分析器的工作原理13 一：实验内容：编写语法分析程序，实现对算术表达式的语法分析，要求所分析的算术表达式由如下的文法产生。E-E+T|E-T|TT-T*F|T/F|FF-id|(E)|num二：实验要求：在对表达式进行分析的同时，输出所采用的产生式。可以采用多种方法编写递归调用程序，实现自顶
2、向下的分析。编写LL(1)语法分析程序，要求：编程实现算法4.2，为给定的文法自动构造预测分析表编程实现算法4.1，构造LL(1)预测分析程序，编写语法分析程序，实现自底向上的分析，要求：构造识别所有活前缀的DFA构造LR分析表编程实现算法4.3，构造LR分析程序利用yacc自动生成语法分析程序，调用LEX自动生成的词法分析器程序三：实验方法：由LEX建立YACC的词法分析程序由LEX产生的词法分析程序可用于YACC，LEX编译程序根据LEX源程序产生词法分析程序yylex(),这个名字就是YACC所需要的词法分析程序的名字。如果YACC要调用LEX产生的词法分析程序，则在YACC源程序的第三
3、部分用语句#include“”代替函数yylex()的定义，这一yylex()就可以访问YACC中记号的名字，因为LEX的输出时候YACC输出文件的一部分，所有，每个LEX的动作都返回YACC知道的终结符。在UNIX的环境下，如果LEX源程序在first.l中，YACC的源程序在second.y中，可以使用以下命令得到所需要的分析程序。Lex first.lYacc second.ycc-o yaccdemo yacc原理介绍Yacc 是用可移植的 C 语言写成的。接受的规定类别是非常一般性的: 带有去歧义规则的 LALR(1) 文法。Yacc 提供了一个通用工具来在计算机程序的输入上施加结构
4、。Yacc 用户准备输入处理的规定；它包括描述输入结构的规则，在识别了这些规则的时候调用的代码，和做基本输入的一个低层例程。Yacc 接着生成一个函数来控制输入处理。这个函数叫做解析器(parser)，它调用用户提供的低层输入例程(词法分析器(analyzer)来从输入流中选取基本项目(叫做记号(token)。依据叫做文法规则的输入结构规则来组织这些记号；在识别了这些规则中的某一个的时候，接着调用为这个规则提供的叫做动作的用户代码；动作有能力返回值并使用其他动作的值。 为了便利在动作和解析器之间的通信，对动作语句要做稍微的改动。在这个上下文中使用美元符号“$”作为给 Yacc 的一个信号。词法
5、分析用户必须提供一个词法分析器来读取输入流并把记号(带有值，如果需要的话)传达到解析器。词法分析器使叫做 yylex 的整数值的函数。这个函数返回一个整数的记号编号，它表示读取的记号的种类。如果这个记号关联着一个值，应当把它赋予外部变量 yylval。 为使通信得以发生，解析器和词法分析器必须在记号编号上达成一致。编号可以由 Yacc 或用户来选择。在这两种情况下，使用 C 语言的“# define”机制允许词法分析器使用符号来返回这些编号。例如，假定在 Yacc 规定文件的声明段中已经定义记号名字 DIGIT。它的意图是返回一个 DIGIT 记号编号，和等于这个数字的数值的一个值。倘若词法分
6、析器代码位于规定文件的程序段，标识符 DIGIT 将被定义为与记号 DIGIT 关联的记号编号。 这种机制导致清晰的、易于修改的词法分析器；唯一的缺点是在文法中需要避免使用任何在 C 语言或解析器中保留的或有意义的记号名字；例如，使用记号名字 if 或 while 就一定会导致编译词法分析器时出现严峻的困难。记号名字 error 保留给错误处理，不应该随便使用。 同上所述，记号编号可以由 Yacc 或用户来选择。在缺省的条件下，编号由 Yacc 选择。文字字符的缺省记号编号是它在本地字符集中的字符数值。其他名字赋予从 257 开始的记号编号。 要把一个记号编号赋予一个记号(包括文字)，可以在声
7、明段中记号或文字的第一次出现时直接跟随着一个非负整数。这个整数被接受为这个名字或文字的记号编号。不通过这种机制定义的名字和文字保持它们的缺省定义。所有记号编号都是不同的是很重要的。 构造词法分析器的一个有用的工具是 Mike Lesk8开发的 Lex 程序。这些词法分析器设计用来与 Yacc 解析器紧密协调工作。这些词法分析器的规定使用正则表达式而不是文法规则。可以轻易的用 Lex 生成非常复杂的词法分析器，但是仍有一些语言(比如 FORTRAN)不适应任何理论框架，它的词法分析器必须手工制作。解析器如何工作Yacc 把规定文件转换成 C 程序，它依据给出的规定解析输入。做从规定到解析器转换的
8、算法是复杂的，就不在这里讨论了(更多信息参见引用)。但是，解析器自身就相对简单了，理解它是如何工作的，尽管不是严格必须的，但会使错误修复和歧义处置更加易于理解。 Yacc 提供的解析器是由带有一个栈的有穷状态自动机组成。解析器自身还有能力读取和记住(叫做超前(lookahead)记号)下一个输入记号。当前状态总是在栈顶。有穷状态自动机的状态是一个给定的小整数标签(label)；最初时，机器是在状态 0 下，栈只包含状态 0，没有读取超前记号。 机器对它只能获得四个动作，叫做移进(shift)、归约(reduce)、接受和错误。 Yacc环境在用户向 Yacc 输入规定的时候，在多数系统上输出文
9、件是叫做 的一个 C 程序文件(因为本地文件系统惯例，它的名字在不同安装中可能是不同的)。Yacc 生成的函数叫 yyparse；它是整数值的函数。在调用的时候，它依次重复的调用用户提供的词法分析器 yylex来获得输入记号。最终，要么是检测到一个错误，在这种情况下(如果没有错误修复是可能的) yyparse 返回值 1，要么词法分析器返回结束标记记号并且解析器接受。在这种情况下，yyparse 返回值 0。 用户必须为解析器提供特定数量的环境来获得一个工作的程序。例如，同每个 C 程序一样，必须被定义程序调用的 main()，它最终调用 yyparse。此外，叫做 yyerror 的一个例程
10、在检测到语法错误的时候打印一个消息。 用户必须以某种形式提供这两个例程。为了减轻使用 Yacc 的起初努力，提供了带有缺省版本的 main 和 yyerror 的一个库。这个库的名字是依赖系统的；在很多系统上使用到装载器的 -ly 参数来访问这个库。到 yyerror 的参数是包含错误信息的字符串，通常是字符串“syntax error”。 一般的应用可能需要更好的消息。通常，程序跟踪输入行数，并与检测到的语法错误一起打印。外部整数变量 yychar 在检测到错误的时候包含超前记号的编号；这对给出更好的诊断有好处。因为 main 程序(需要读参数等等)大多数时候是用户提供的。Yacc 库只在小
11、项目或大点的项目的早期阶段有用。 外部整数变量 yydebug 通常设置为 0。如果设置为非零的值，解析器会输出对它的动作的一个冗余的描述，包括对已经读入哪个输入符号和解析器动作是什么的讨论。依赖于操作系统，可以通过使用调试系统来设置这个变量。 常用代码if( islower( c ) ) yylval = c - a; return ( LETTER ); if( isdigit( c ) ) yylval = c - 0; return( DIGIT ); if(c=a|c=A) yylval=c; return(ID); 第四：YACC内部名称：YACC内部名称说明yyparseyylv
12、al yyerrorerroryyerrok、yycharYYSTYPEyydebugYACC输出文件名YACC生成的头文件，包含有记号定义YACC分析程序栈中的当前记号的值由YACC使用的用户定义的错误信息打印程序YACC错误违记号在错误处理之后，回到正常操作方式变了，记录导致错误的先行记号定义分析栈值类型的预处理器符号变量，用户置1生成有关分析动作的运行信息第五：运行结果（源代码见附录）在linix下输入的命令行依次是：Cd 桌面Yacc translate.yGcc o rong./rong注：Cd 桌面 到桌面目录下Yacc translate.y 用yacc编译器编译translat
13、e.y程序到C文件Gcc o rong 用C编译器生成可执行文件./rong 运行可执行文件输入表达式，打印正确计算结果，否则，输出syntax error第六：实验总结1.用C语言实现词法分析的效率较高，但用LEX可以机械的执行程序，不用思考，虽然效率不是很高，但比较方便。Lex可以智能的读单词，并且按照最长匹配原则和优先匹配原则识别单词。Yacc则很简单的文法式进行分析，不需要定义递归的详细飞计算法则，直接修改生成式和标记符就可以应用于语法分析，简单方便，可移植性高。2.%token ID %token NUM 必须预先定义，否则会显示没有事先定义，此外对于C语言来说，isdigit(c)
14、能判断一个字符是否是数字，但是，本题中要识别的是整数和记号，那么或者选用lex调用表，或者，递归的读取字符，分别判断，此时，我选择了循环判断来解决这个问题。而这段代码是属于基础代码模式。if(isdigit(c)yylval=c-0;return(NUM);else if(c=a|c=A)yylval=c;return(ID);else if(c=n)done = 1;3.yacc程序，是在linix环境下，用命令行执行的，.y文件不能直接在windows环境下打开，但是，下载了Parser Generator后，就可以直接读取.y文件，但此时不能运行yacc，还需要进行环境变量（例如PASH）的配置，才能在windows环境下使用yacc编译器。这个对于未安装虚拟机，初识linix的人使用yacc提供了很大的方便。4.通过lex yacc的编程练习，明白了词法分析和语法分析的基本操作，弄清了原理，为下一步进行语义分析打下了良好的基础。第七：附录附录一：yacc程序，加注释%/*第一节，普通的C语言声明*/#include#include%token ID/*说明记号，在这里说明的记号可以用于随后的翻译规则部分和辅助过程中*/%token NUM% /*文法记号声明，默认第一个产生式的左部非终结符号时候文法的开始符号*/ /*文法产
