LL(1)动作文法的编译器的自动生成器的设计与实现

1、论文分类号 TP31 单 位 代 码 10183密 级 内部 研 究 生 学 号 20015352033吉 林 大 学硕 士 学 位 论 文LL(1动作文法的编译器的自动生成器的设计与实现The Design and Implementation of LL(1 Action Grammar CompilersAutomatical Constructor作者姓名：成 会 明专 业：计算机软件与理论导师姓名金 成 植及 职 称教 授论文起止年月： 2003年 1月至2004年4月提 要编译器的构造工具比如YACC，BISON根据语言的高级描述生成语言处理器(编译器，解释器，转换器。根据用户输入

2、的语言的文法，编译器的构造工具可以生成程序来处理以用户输入的文法书写的文本。随着计算机应用范围的扩大，在软件自动生成，文档处理，特定专业的语言等领域，编译器的构造工具这一技术显得越来越重要。类YACC的编译器的构造工具是基于LALR(1方法，这一方法在时间和空间代价方面是有效的，而且所能解析的语言也覆盖了大部分语言，因些大多数的编译器的编译器都是针对LALR(1的,而很少有针对LL(1文法的。本文所做的工作是用VC要建立一个针对LL(1文法的编译器的编译器。本文以定义好的文法书写的文件作为输入，其中包括语法及语义动作，鉴于输入文件的所用的文法可以用LL(1分析，于是对输入的文件用递归下降的分析

3、方法在内存中建立它的存储结构，然后分别计算所输入的文法的非终结符号是否可以生成空，每个非终结符号的first集合，每个非终结符号的follow集合，以及每个规则的predict集合，接着判断任意一个非终结符号的任意两个规则的Predict集的交集是不是都为空，如果是则输入文法可以用递归下降法分析，否则不可以，用户应该对所输入的文法作适当的修改，使其满足LL(1文法分析的要求，。如果所输入的文法可以用递归下降法分析，生成相应文法的语法分析程序。目 录 第一章 前言 111 编译器的结构 112 编译器的实现 313 主要完成的工作 5第二章 LL(1文法以及属性文法 621 LL(1文法及其分析

4、器 622 动作文法 8第三章 输入文件的结构及词法 1131 词法工具的使用说明 1132 输入文件的语法结构 1233 输入文件的词法结构及其实现 14第四章 系统设计与实现 1841 规则的存储结构 1842 建立规则的存储 1943 非终结符推出空 2044 计算FIRST集 2045 计算FOLLOW集 2146 计算PREDICT集 2147 判断是否LL(1 2148 输出文件中函数的格式 21第五章 实 例 24参考文献 33致 谢摘 要 1ABSTRACT 1第一章 前言11 编译器的结构不同的编译器都有自己的组织和工作方式，它们都是根据源语言的具体特点和对目标语言的具体要求

5、来决定和设计出来的。因此，并没有一种固定的编译器的结构，但从功能结构几乎都是一致的。这里说的功能结构是指编译器内部都做哪些工作，以及它们彼此之间的关系。图1说明了一般的编译程序的功能结构。图1 编译器的功能结构图其中各部分完成的主要任务如下： 词法分析：根据语言的词法规则，扫描源程序的ASCII码序列，把它识别为一个一个具有独立意义的最小语法单位，即“单词”，并识别出与其相关的属性（如标识符，界限符，常数等等），并把每个单词的ASCII码序列替换为统一的标准形式所谓的机内表示TOKEN形式（这种形式既刻画了单词本身，又刻画了它所具有的属性），同时完成词法错误的检查以及去掉注释等。词法分析阶段不

6、依赖于语言的语法定义。 语法分析：根据语言的语法规则，逐一地扫描源程序的ASCII码序列或者是词法分析后的TOKEN序列（前者情形，词法分析程序将作为语法分析程序的子程序），以确定它们是怎样构成声明和语句的，以及声明和语句是怎样构成程序的。分析时如发现有不符合语法规则的地方，则打印出错位置和错误类型，以便程序员进行修改；如果未发现语法错误，则将源程序转换成能够表示程序结构的语法树的形式。很多编译程序在进行语法分析的同时还要完成其他的工作，但要注意到如果语法有错误那么其他工作也白做。 语义分析：根据语言的语义规则对语法分析得到的语法树进行语义检查（确定类型，类型和运算的合法性检查等），并建立标识

7、符的符号表等各种信息表。如果有语义错误，则不用进行下面的编译工作，只有当没有语义错误时才继续下面的编译过程。语义分为静态语义和动态语义，编译阶段一般只检查静态语义，而静态语义检查中重点是类型检查。 中间代码生成：扫描对象通常是语义分析后的结果，这一部分把源程序的TOKEN序列转换成更接近于目标代码的中间代码（如三元式或四元式的序列）。如果不搞优化，那么这部分的工作可以不要。 中间代码优化：扫描对象是中间代码，任务是把原中间代码转换成可产生高质量目标代码的中间代码，其中的优化工作包括常表达式优化、公共子表达式优化、不变表达式外提和削减运算强度等。12 编译器的实现编译程序是一个相当复杂的系统程序

8、，通常有上万甚至几万条指令。随着编译技术的发展，编译程序的开发周期也在逐渐缩短，但仍然需要很多人年，而且工作很艰巨，正确性也不易保证。要实现一个编译程序，通常需要做到：（1） 对源语言的语法和语义要有准确无误的理解，否则难以保证编译程序的正确性。（2） 对目标语言和编译技术也要有很好的了解，否则会生成质量不高的目标代码。（3） 确定对编译程序的要求，如搞不搞优化，搞优化搞到哪一级？等等。（4） 根据编译程序的规模，确定编译程序的扫描次数、每次扫描的具体任务和所要采用的技术。（5） 设计各遍扫描程序的算法并加以实现。一般开发编译程序有如下几种可能途径： 转换法（预处理法）：假如我们要实现L语言，

9、现在有L语言的编译器，那么可以把L语言程序转换成L语言的程序，再利用L语言的编译器实现L语言，这种方法通常用于语言的扩充。如把C+程序转换成C程序，我们用C语言的编译器进行编译，常见的宏定义和宏使用都属于这种典型。 移植法：假设在A机器上已有L语言的编译程序，想在B机器上开发一个L语言的编译程序。这里有两种实现方法：实现方法一：最直接的办法就是将A机的代码直接转换成B机代码。实现方法二：假设A机和B机上都有高级程序设计语言W的编译程序，并且A机上的L语言编译程序是用W语言写的，我们可以修改L编译程序的后端，即把从中间代码生成A机目标代码部分改为生成B机的目标代码。这种在A机上产生B机目标代码的

10、编译程序称为交叉编译程序（Cross Compiler）。 自展法：实现思想：先用目标机的汇编语言或机器语言书写源语言的一个子集的编译程序，然后再用这个子集作为书写语言，实现源语言的编译程序。通常这个过程会分成若干步，像滚雪球一样直到生成预计源语言的编译程序为止。我们把这样的实现方式称为自展技术。 工具法：70年代随着诸多种类的高级程序设计语言的出现和软件开发自动化技术的提高，编译程序的构造工具陆续诞生，如70年代Bell试验室推出的LEX，YACC至今还在广泛使用。其中LEX是词法分析器的自动生成工具，YACC是语法分析器的自动生成工具。然而，这些工具大都是用于编译器的前端，即与目标机有关的

11、代码生成和代码优化部分由于对语义和目标机形式化描述方面所存在的困难，虽有不少生成工具被研制，但还没有广泛应用。 自动生成法：如果能根据对编译程序的描述，由计算机自动生成编译程序，是最理想的方法，但需要对语言的语法语义有较好的形式化描述工具，才能自动生成高质量的编译程序。目前，语法分析的自动生成工具比较成熟，如前面提到的YACC等，但是整个编译程序的自动生成技术还不是很成熟，虽然有基于属性文法的编译程序自动生成器和基于指称语义的编译程序自动生成器，但产生目标程序的效率很低，离实用尚有一段距离，因此，要想真正的实现自动化，必须建立形式化描述理论。13 主要完成的工作本文所做的工作是用VC要建立一个

12、针对LL(1文法的编译器的编译器。本文以定义好的文法书写的文件作为输入，其中包括语法及语义动作，鉴于输入文件的所用的文法可以用LL(1分析，于是对输入的文件用递归下降的分析方法在内存中建立它的存储结构，然后分别计算所输入的文法的非终结符号是否可以生成空，每个非终结符号的first集合，每个非终结符号的follow集合，以及每个规则的predict集合，接着判断任意一个非终结符号的任意两个规则的Predict集的交集是不是都为空，如果是则输入文法可以用递归下降法分析，否则不可以，用户应该对所输入的文法作适当的修改，使其满足LL(1文法分析的要求，。如果所输入的文法可以用递归下降法分析，生成相应文

13、法的语法分析程序。第二章 LL(1文法以及属性文法21 LL(1文法及其分析器文法分析的基本问题之一是确定那些非终结符号导(空串。这一信息很重要，因为可导出(空串的非终结符号在语法分析的时候可能消失。可以用以下算法判定一个非终结符号是否可以导出(空串。设S_Lambda表示可导出(空串的非终结符号集，则求它的算法如下:(1.令S_Lambda=Aj|AjProduction;(2.对每一个产生式 p: Ap X1Xn ， 若X1.Xn S_Lambda(3.重复第二步的循环，直至S_Lambda收敛为止。文法分析中最的用的技术是求以下种集合(终结符集的技术，这三种集合的具体定义如下(其中 (V

14、N VT * ，A VN:First (=a VT| * a if * then else ØFollow(A=a VT |S + Aaif S *A then # else Ø Predict(A =First (， 当First(不含有 =First(-Follow(A，当First(含有 其中#表示输入的结束符号，first(表示串所能推导的终极符串的头终结符集，如果能推导出空串，则令First(包括 。 follow(A表示所有那些终结符的集合,这些终极在某个句型中出现在A的紧后面。这种集合主要用于求predict(A 的集合.LL(1语法分析方法是一种自顶向下的语

15、法分析方法，它是LL(k分析方法的特例，其中的k表示向前看k个符号的意思。和递归下降法有相同的问题，即在推导过程中如何唯一选择产生式的问题，因此，LL（1）语法分析方法与递归下降法一样对文法做了相同的限制，即：假设A的全部产生式为A1|2|n则有：Predict(A iPredict(A j Ø I j有了上面的限制条件，可以保证选择产生式的唯一性，满足上面条件的文法称为LL（1）文法。LL(1语法分析程序是由两部分组成的，第一部分是语法分析表，也称为LL(1分析矩阵。第二部分是语法分析驱动程序。LL(1矩阵的作用是如何选择语法规则，它的行表是由所有非终极符组成，它的列表是由所有终极

16、符即特殊符号（结束符），矩阵的值有两种：一种是产生式编号，另外一种是错误编号，其一般形式可定义为：LL(A,a=k 其中AVn,aVt#,k为规则编号P或错误编号error k。设有规则Ak,若aPredict(A,那么有LL(A,a=k；若a不属于任何一个以A为左部的规则的Predict集，则LL(A,a=错误编号。LL(1分析程序工作原理是首先初始化，即把开始符压入栈中，以后的每步分析必为下面的四种情况之一：1 析栈的栈顶元素是终极符，则看其是否与输入流的头符相匹配，如果匹配成功，去掉栈顶元素,并读下一个单词；若匹配不成功，则报错。2 栈顶是非终极符，则用栈顶和输入流的当前单词去查当前矩阵

17、，如果查得的值是产生式编号，则把对应的产生式右部逆序压入栈中；如果查得的值为错误信息，则报错。1、 栈已空，输入流不空，这时输入流报错。2、 若栈已空，输入流也空，则语法分析成功。由上可以看出，LL（1）语法分析驱动程序对于任何文法都是一样的，所不同的是不同的文法LL（1）矩阵是不相同的。所以构造LL(1语法分析程序关键是如何构造文法的LL(1矩阵。LL（1）的构造可以是手工操作的，也可以是自动生成的22 动作文法编译器中语义分析和中间代码生成等部分是比较细致而复杂的部分,因此希望能用比较规范抽象的方式把这些部分描述出来。当前所用的主要方法是,把语义信息附加到文法中,使得它既描述文法,同时还指

18、出动作信息。这种描述方法不仅能简化细节并增强可读性,而且可自动化。动作符(Action Symbol动作符主要用于构造动作文法。它可以出现于产生式中,但没有任何语法意义,而且 能出现于具体程序中。由于它不起任何语法作用，所以必须与实际的语法符号 相区别，比如动作符号的结构可定义成#Name的形式,其中#表示是非语法符号,并且 Name是某种形式的字符串,具体规定可由具体系统来定义。动作符可出现于产生式右部的任何地方,其主要作用是用来,指明某种语义动作,即动作符 #Name中的Name代表某语义子程序,因此在使用动作符时必须给出每个动作符所对应的语义子程序 。动作符的作用对LL分析显得十分突出。

19、如果想用LL分析法,那么Yacc就无能为力,但动作文 法可方便地被应用 。如果把Yacc说成是针对LR分析的,那么把动作文法说成是针对LL分析的,也并不过份。形式上说,动作文法是这样一种文法,即在产生式的右部带动作符,其中动作符可出现于产生式右部的任何地方,包括产生式右部的开始和尾部。动作文法中的每个动作符号都有相应的语义子程序,因此,动作符实际上是一个无参过程的子程序名字。在什么地方插入动作符以及动作符所对应的子程序应写成什么样子,完全由用户决定。动作文法的主要用途是描述语义动作。作为例子考虑下面文法:L D L | D a | b显然,L代表的由a和b组成的串或空串。我们要构造的是这样一个

20、语义处理器,它将输入L串并将其中b的个数打印出来。因为处理方式可以有多种,动作文法也可以有多种。我们考虑这样一种方案,即开始令,S:=0,以后每输入一个b就作S:=S+1,当结束输入时将S的值打印出来。下面是按上述思想写出来的动作文法:L D LL #OutD aD b #Add其中动作符有#Add和#Out。它们所对应的动作子程序分别如下:Add: S:=S+1Out: Print(S假定给定L串"bab",则用LL分析法实现上述动作文法的过程如下:在运行前令S=0并把开始符压入语法分析栈;之后进行LL分析;此时每当动作符成为栈顶符号时,将执行相应的动作子程序。具体实现过

21、程如下图。SyntexStack InputStreamActionL Bab$DL Bab$BLBab$LAb$S=:S+1LAb$DLAb$ALAb$Lb$DLb$BLb$L$S:=S+1L$Print(S$第三章 输入文件的结构及词法31 词法工具的使用说明Flex是Lex的的改进版本。Lex是词法分析器的自动生成工具，它从基于正规式的专门表示构造词法分析器，并已广泛用于说明各种语言的词法分析器。Flex程序包括三个部分：声明翻译规则辅助过程声明部分包括变量，显明常量和正规定义。显明常量是表示常量的标识符。Flex程序的翻译规则为形如P1 动作1P2 动作2 Pn 动作n的语句。这里，每

22、个Pi是正规式，每个动作i是描述模式pi匹配单词时词法分析器应执行的程序段。第三部分包括了动作所需要的辅助过程。这些过程也可以分别编译，然后和词法分析器一同装入。由Flex建立的词法分析器和分析器联系的方式是：词法分析器被分析器激活时，开始逐个字符地读它的剩余输入，直到它发现能和正规式pi匹配的输入的最长前缀为止；然后执行动作i。典型的，动作i将把控制返回分析器。如果不是这样，词法分析器继续寻找下面的单词，直到有一个动作引起控制回到分析器为止。这种重复的搜索单词，直到显示的返回的方式允许词法分析器方便的处理空白和注解。词法分析器仅返回一个值（记号）给分析器。为了传递记号的属性值，可以将值置于全

23、程变量yylval中。32 输入文件的语法结构下面是用户输入的动作文法所采用的语法结构,并且该文法可以用LL(1方法分析。grammar: global_prelude_part token_declaration_part rule_part;global_prelude_part :global_prelude |empty;global_prelude:“%prelude” block;global_prelude主要包括动作文法中的动作要用到的数据结构,函数过程,全局变量,预定主常量block:“” c_code “” ;block主要生成动作文法中要加入的语义动作,以及一个非终结符号

24、的local_preludeempty: ;token_declaration_part:“%token” token_declaration_list “”|empty;token_declaraton_list:token_declaration “,”tail_token_declaration_list|token_declaration ;token_declaration: identifier ;rule_part : rule_list;rule_list: rule rule_list|rule;rule : left_hand_side “:” right_hand_sid

25、e “;”left_hand_side: nonterminal formal_parameter_spec ;nonterminal: identifier;formal_parameter_spec: empty|“<” ”%in” parameter_spec_list “> | “<” “%out” parameter_spec_list“>” |“<” “%in” parameter_spec_list “%out” parameter_spec_list “>”%in 参数用于值传参数,%out参数用于引用传递parameter_spec_lis

26、t: parameter_spec “,” parameter_spec_list |parameter_spec;parameter_spec : parameter_type parameter_name;parameter_type: identifier ;parameter_name： parameter_name; right_hand_side: local_prelude_option alternative_list;local_prelude_option: local_prelude |empty;local_prelude: “%prelude” block;local

27、_prelude的内容插入到处理左边的非终结符号的函数的开头部分.alternative_list: member_list;member_list member member_list;member : item;item: symbol | literal |semantic_action;symbol: symbol_name actual_parameters_option;symbol_name: identifier;actual_parameters_option : actual_parameters|empty;actual_parameters: “<” actual

28、_parameter_list ”>”;actual_parameter_list：actual_parameter “,” actual_parameter_list|actual_parameter;literal: char_constant;semantic_action: block; 33 输入文件的词法结构及其实现输入文件的词法结构主要包括两部分,一部分是用户输入的规则的所用到的词法,另一部分是语义动作用到的词法，语义动作用到的词法是C语言所使用的词法. 当在处理用户输入的动作文法的时候,如果遇到了'',表明遇到了C语言块,对''的计数加1,

29、转入到C语言的词法分析部分。在C语言的词法分析部分,若遇到单词'',对''的计数加1,若遇到'',则对''的计数减1,如果些时计数为零,切换词法分析程序所匹配的规则到文法所用的规则.下面举个例子来说明使用方法。刚打开文件匹配的时候,匹配的是前面没有 四个规则, 当匹配到''时,执行BEGIN(qq是就开始匹配前面带有 的规则, 如果遇到'',执行BEGIN(0,后面接着开始匹配前面没有 的规则.%x qq"%prelude" return 90;"%token"

30、; return 100;"" BEGIN(QQ;. A-Za-z_+ return 101;'+' return 102;'-' return 103;'*' return 104;'/' return 105;'' BEGIN(0;. 下面是读用户输入文件的词法,为了对用户输入文件出现错误的地方进行定位,需要在匹配完每个单词要对当前的单词在文法中的位置进行定位. 其中yyleng是当前匹配单词的长度,column是当前的列,position是当前匹配的字符串在文件中的位置规则部分前面加 的部

31、分是用来c语言的词法,前面不加 的是规则的词法%x cc ccc%"%prelude" printf("word:%s,length=%d",yytext,yyleng;position=position+yyleng;column=column+yyleng;return PRELUDE_A;"%token" position=position+yyleng;column=column+yyleng;return TOKEN_A;"" position+=yyleng;column+=yyleng;right_c

32、urly=1;BEGIN(cc;return LEFT_CURLY; ."auto" position+=yyleng;column+=yyleng;"break" position+=yyleng;column+=yyleng;"case" position+=yyleng;column+=yyleng;"" position+=yyleng;column+=yyleng;right_curly-;if (right_curly=0BEGIN(0;/回到原来的部分return RIGHT_CURLY; .第四章

33、系统设计与实现41 规则的存储结构下面这个数组结构存储的是一个非终结符号所对应的所有的规则class CRule public:in_parameters,out_parameters 这个非终结符号所对应输入与输出参数集合, in_parameters是值参 out_parameters是引用参数其/中每个数组的第i(i%2=0表示类型; (i%2=1表示这个串是参数名CStringArray in_parameters,out_parameters; int initialized; 表示这个非终结符号名字CString nonterminal;指针数组,每个指针指向一个CObList对象

34、。每个对象存储这个非终结符号的一个规则。CPtrArray right_parts;/ 这一规则所对应的local_prelude_block在文件中的定位 如果这两个值为-1的话,就是说这个非终结符没有这样local_prelude_block。否则有int local_prelude_block_begin_position;int local_prelude_block_end_position;int local_prelude_block_begin_line ;int local_prelude_block_begin_column;pi=0,1,2分别表示当前的计算结果第i个规则

35、未知能否生成空,能生成空,不能生成空int *status;当前已有多少个规则已有确定的结果int finished_rules; select_seti表示这个非终结符号的第i个规则的select集CDWordArray *select;class CRightSymbol 这个数组结构用来存储规则右部的一个符号的信息public:表示这个类存储的是字符,语义动作,还是TOKEN_A(用户定义的符号串常量,CHARACTER,SEMANTIC_ACTIONint type;存储一个非终结符号可能的参数CStringArray actual_parameters; /如果类型是语义动作,存储在

36、文件中的起始与结束地址。int semantic_action_begin_line,semantic_action_begin_column;int semantic_action_end_line,semantic_action_end_column;int,semantic_action_end_position;int semantic_action_begin_position/如果是token和非终结符时所对应的值|也有可能是一个终结字符int value; ;42 建立规则的存储根据计算可得输入文件的文法是满足LL(1分析方法的文法, 对该文法写一个递归下降分析程序,建立对这些规

37、则的存储。43 非终结符推出空1.初始化所有的非终结符号以及每个非终结符号的所有规则未知其能否生成空.2.置迭代标志为1,i=03.如果迭代标志为1转4,否则计算结束5.分析第i个非终结符号的每一个没有确定其是否能生成空的规则:如果这个规则右部为空,或全部是已确定能推出空的非终结符号,则标记第i个非终结符号可以生成空,并置迭代表记为1,转6;如果这个规则的分析中遇到了非终结符号或遇到了已确定不能生成空的非终结符号,则标记该规则不能推出空,当这个规则第i个非终结符号的最后一个不能确定生成空的规则,则标记第I个非终结符号不能生成空.转6.6.i=i+1,如果i=rules.GetSize(转3,否

38、则转444 计算first集1.初始化所有的非终结符号的first集为空;2.置changed=13.如果changed为1,转4,否则转结束.4.changed=0;i=0;5.如果i 转 6, 否则转 3 6.从左到右分析第i个非终结符号的每个规则的右部。如果遇到一个终结符号,则把这个非终结符号加到第i个非终结符号的first集中,加入后若改变这个非终结符号first集则置changed为1,接着分析其它规则;如果遇到一个非终结符号则把这个非终结符号的first集并到第i个非终结符号的first集当中,此时若改变了第i个非终结符号的first集置,changed为1,若这个规则可以导出空,

39、则继续分析这个规则的后面的符号。7.i=i+1,转545 计算follow集1.初始化所有的非终结符号的follow集为空;2.置changed=13.如果changed为1,转4,否则计算结束.4.changed=0;i=0;5.如果i 转 6, 否则转 3 6.从左到右分析第i个非终结符号的每个规则的右部。对于在这个规则右部的每一个非终结符号 1计算这个符号后面符号串的first集,把它并入到这个符号的follow集,如果并运算改变了这个符号的follow集,则置changed为1; 2计算这个符号后面的符号串能否推出空,若能推出空,则把第i个非终结符号的follow集并入到这个非终结符号

40、的follow集,如果改变了这个非终结符号的follow集,则置changed为1.7.i=i+1,转546 计算predict集每个规则的predict计算如下:如果这个非终结符号右部的串能导出空,则这个规则的predict集为这个规则左部非终结符号follow集并上这个规则右部串的first集,并去掉空串;如果这个规则的右部导不出空,则这个规则的predict集为这个规则右部串的first集.47 判断是否LL(1计算任意一个非终结符号的任意两个规则的predict集的交集是不是为空。如果存在某一个非终结符号的某两个规则的predict集的交集为不为空,则该文法不能用LL(1方法分析。48

41、 输出文件中函数的格式下面是某动作文法系统中的一条规则,假设计算所得select(expr_list:expression expr_tail=IDENTIFIER ,NUM ,'('select(expr_list:='B'expr_list<%out P_WRITEPARAMETER p_writeparameter> :p_writeparameter=(P_WRITEPARAMETERnew structwriteparameter;P_EXPRESSION &p_expr=p_writeparameter->p_expr;P_

42、WRITEPARAMETER &p_wp=p_writeparameter->next;expression expr_tail | p_writeparameter=NULL;处理这个非终结符号所对应的程序如下：int expr_list (P_WRITEPARAMETERp_writeparameter,int &tok /根据select集选择规则1if (tok=IDENTIFIER|tok=NUM|tok='(' p_writeparameter= (P_WRITEPARAMETER new struct writeparameter;P_EXP

43、RESSION &p_expr=p_writeparameter->p_expr;P_WRITEPARAMETER &p_wp=p_writeparameter->next;ret=expression (p_expr ,tok ;if (ret=0return 0;ret=expr_tail (p_write_parameters_tail ,tok ;if (ret=0return 0;return 1;/根据select选把规则2 if (tok='B' p_writeparameter=NULL;return 1;return 0;/ 如果参

44、数tok不属于这个非终结符任何一个规则的/select集,就出错第五章 实 例 下面这个例子输入的是一个语言动作文法,该动作文法是要建立对这个文法的语言在内存中的存储， 以便作更进一步的处理。一个这样的文件是用一个语句链表存储,读语句的参数是用一个字符串数组存储;write语句的表达式序列用表达式链存储%prelude struct expression char op;/0:integer 1:variable name '+' or '-'union struct expression *left,*right;/two /sub-expressionsin

45、t value;/constantCString var_name; /variable name node; ; /用来存储一个表达式typedef struct expression EXPRESSION,*P_EXPRESSION;struct writeparameter P_EXPRESSION *p_expr;struct writeparameter *next; ;typedef struct writeparameterWRITEPARAMETER,*P_WRITEPARAMETER;struct assign CString id;struct expression * p

46、_exp; ;typedef struct assign ASSIGN; struct statement int type;/0:read 1:write 2:assignunion CStringArray parameters;/parameters of read ASSIGN assign; /assign sentence P_WRITEPARAMETERS p_writeparameters;/ value; struct statement *next; /typedef struct statement STATEMENT,*P_STATEMENT; %token BEGIN

47、,END,READ,WRITE,IDENTIFIER,NUM;program<%out P_STATEMENT p_statement>:BEGIN statement_list< p_statement>END;statement_list<%out P_STATEMENT p_statement>:statement P_STATEMENT &next=p_statement->next;statement_tail ; statement_tail<%out P_STATEMENT p_statement>:statement

48、 P_STATEMENT &tail=p_statement->next;statement_tail | p_statement=NULL;；statement<%out P_STATEMENT p_statement>:IDENTIFIER p_statement=new struct statement; p_statement->type=2;p_statement->value.assign.id.Copy(yytext;P_EXPRESSION &p_exp=p_statement->value.assign.p_exp; 

49、9;:' '=' expression ''| READ p_statement=new struct statement; p_statement->type=0;/read sentence CStringArray &parameters=p_statement->value.parameters; '(' id_list< parameters> '' ''|WRITE p_statement=new struct statement; p_statement->

50、;type=1;/write sentenceP_WRITEPARAMETER&p_writeparameter=p_statement->value.p_writeparameters;'('expr_list '' '' ；id_list<%out CStringArray parameters>:IDENTIFIER parameters.Add(yytext; id_tail ; id_tail<%out CStringArray parameters>:',' IDENTIFIER

51、parameters.Add(yytext; id_tail | ;expr_list<%out P_WRITEPARAMETER p_writeparameter> :p_writeparameter= (P_WRITEPARAMETER new struct writeparameter;P_EXPRESSION &p_expr=p_writeparameter->p_expr;P_WRITEPARAMETER &p_wp=p_writeparameter->next;expression expr_tail ; expr_tail<%out

52、P_WRITEPARAMETER p_writeparameter> :p_writeparameter= new WRITEPARAMETER;P_EXPRESSION &p_expr=p_writeparameter->p_expr;P_WRITEPARAMETER &p_wp=p_writeparameter->p_next;',' expression expr_tail |p_writeparameter=NULL;；expression<%out P_EXPRESSION p_expr> : P_EXPRESSION p

53、_temp;P_EXPRESSION p_temp1;primary primary_tail ; primary_tail<%out P_EXPRESSION p_expr>:%preludeP_EXPRESSION p_temp1,p_temp2,p_temp3;add_op primary primary_tail if (p_temp3=NULL p_tmep1->node.right=p_temp2;p_expr=p_temp1; else p_temp3->node.left=p_temp2;p_temp1->node.right=t_temp3;p_

54、expr=p_temp1; |p_expr=NULL; primary<%out P_EXPRESSION p_expr>:IDENTIFIERp_expr= (P_EXPRESSION new struct expression; p_expr->op=1;/variable namep_expr->node.varname.Copy(yytext;NUM p_expr=(P_EXPRESSION new struct expression;p_expr->op=0; /integerp_expr->node.value=atoi(yytext; |

55、9;(' expression '' add_op<%out P_EXPRESSION p_exp>:'+'p_exp=(P_EXPRESSION new struct expression ;p_exp->op='+' |'-' p_exp=(P_EXPRESSION new struct expression;p_exp->op='-' ;计算可得该动作文法可以用LL(1方法分析。下在这个函数是由系统自动生成的一个函数。这个函数用来处理非终结符statement的规则int st

56、atement (P_STATEMENTp_statement,int &tokif (tok=IDENTIFIER /选择赋值语句表达式if (tok!=IDENTIFIER/ /当前要处理的语句是赋值语句return -1; /tok=yylex(;p_statement=new struct statement; p_statement->type=2;p_statement->value.assign.id.Copy(yytext;P_EXPRESSION &p_exp=p_statement->value.assign.p_exp;if (tok!=':'return 0;tok=yylex(;if (tok!='='return 0;tok=yylex(;ret=expression (p_exp ,tok ;if (ret=0return 0;if (tok!=''return 0;tok=yylex(;return 1;if (tok=READ /当前要处理的语句是读语句 if (tok!=READreturn -1;tok=yylex(;p_statement=new s