编译原理实验教案

1、黄黄冈冈师师范范学学院院计计算算机机系系 编编译译原原理理 实实验验教教案案 （20092009秋）秋） 授课对象：计科授课对象：计科0303 授课教师：张授课教师：张 瑞瑞 红红 授课时间：授课时间：2009200920102010 学年度第一学期学年度第一学期 实验一、词法分析实验一、词法分析 一、授课内容：一、授课内容： （一） 授课科目：编译原理 （二） 授课内容：实验一 词法分析 （三） 授课类型：实 验 （四） 授课时间：8 学时 （五） 主讲教师：张瑞红 二、教学目的要求：二、教学目的要求： 1.目的：通过设计、编制、调试一个具体的词法分析程序加深对词法分析原理的理解，并掌握在对

2、 程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 2.要求： （1）选择在国际国内有代表性的高级程序设计语言的源程序作为词法分析对象。 （2）根据数学要求和学生具体情况，从上列语言之一中选取一个适当大小的子集，可以选取一类典 型单词，也可以尽可能使各种类型的单词都能兼顾到。 （3）时间为 6 小时。 时间分为三次： 第一讲、介绍词法分析器的设计原理，以 PASCAL 子集为例； 第二讲、根据学生时间上机情况，辅导学生设计； 第三讲、先辅导，再进行上机操作检查。 三、教学设想：三、教学设想： 1教学方法设想：先以例子讲解，然后学生动手实验，实验为主。 2教具运用设想：多媒体。

3、 四、教学过程：四、教学过程： 1题目 试用直接分析方法编制 PASCAL 语言子集的词法分析程序。其 BNF 定义如下： PASCAL 子集程序：=变量说明BEGIN语句表ENG。 变量说明：=空| VAR变量表：类型 变量表：=变量|变量表 ， 变量 类型：=标识符 语句表：=语句|语句表 语句 语句：=赋值语句|条件语句|WHILE 语句|复合语句|过程定义 赋值语句：=变量：=算术表达式 条件语句：=IF 布尔表达式THEN语句ELSE语句 WHILE 语句：=WHILE布尔表达式DO语句 复合语句：=BEGIN语句表END 过程定义：=PROCEDURE标识符 参数表BEGIN语句表

4、END 参数表：=空|（标识符表 ） 标识符表：=标识符|标识符表 ， 标识符 算术表达式：=项|算术表达式+项 项：=初等量|项*初等量 初等量：=无符号数|变量|（算术表达式 ） 布尔表达式：=算术表达式 关系符 算术表达式 变量：=标识符 标识符：=字母|标识符 字母|标识符 数字 无符号数：=数字|无符号数 数字 关系符：= = | | 字母：=A | B| C| D| E | F| G | H | I | J | K | L| M | N | O | P|Q | R |S | T| U| V| W| X| Y| Z 数字：=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7

5、| 8 | 9 空：= 词法分析是编译程序的第一个处理阶段。这里所谓直接分析方法，即自左至右扫描源程序，一旦 发现有独立意义的字符串时，立即将其改造成长度统一的最小语法单位，同时查填各类单词表格并 做一些语法检查，为以后的语法分析提供方便。 具体的处理过程是，在扫描字符串时，一旦识别出关键字（K） 、标识符（I） 、常数（C）和界符 （P）中之一，即以单词形式（剔去多余的空白符）输出。每次调用词法分析程序，它均能自动继续 扫描下去，形成下一个单词，直至整个源程序全部扫描完毕，习惯年成相应的单词串。 各类单词均有相同的结构和长度。每个单词由两部分组成： （t, i） 其中 t 表示单词种类。共分

6、四类，即 K 类、I 类、C 类和 P 类。每类对应一种表格，分别存放该类各个 不同的单词。i 为指向该类表格一个特定项目的指针。因此， （t, i）唯一地确定了一个单词。 K，P 两种表格的内容取决于所选语言的子集，而 I，C 两种表格则是根据临时输入的源程序字符串形 成的。 2算法 词法分析程序在扫描过程中，依次从源程序驱除源字符，并根据第一个字符（有时还需 多读一个字符）判断属于 K，I，C，P 中的哪一类单词，确定单词的 t 和 i 。在词法分析过程中， K、P 两表是固定不变的（由语言来确定） ，源程序字符串只能从其中选取。I、C 两表是在分析过程中 不断形成的。其词法分析的算法如图

7、 2-7-2 所示。 为了防止实习良过大，达不到实习的目的，实习时采用的数据结构在不同程度上均应作适当的简化， 所选的关键字（K）和界符表（P）如表 2-7-1 和表 2-7-2 所示。 表 2-7-1 K 表 表 2-7-2 P 表 BEGIN DO ELSE END IF PROCEDURE THEN VAR WHILE To 关键字表包括九个代表性的关键字。界符表包括关系运算符三种（其中小于等于和不等于均系由两个 字符组成的符合字符） ，算术运算符和分隔符各两种，圆括号一对，加上赋值号共十一种。这两个表的内 容表明，PASCAL 语言的赋值语句、条件语句、WHILE 型循环语句、复合语句

8、过程及变量说明均可作为 源程序例子输入给词法分析程序。标识符表中的每一项包含一个标识符。常数表中的每一项包含一个整 常数。后两表都是在词法分析过程中产生的。 3程序及运行结果 下面用 PASCAL 语言编出符合以上几项要求的一个具体的词法分析程序为： PROGRAM plexical (INPUT,OUTPUT); = （ * ：= ： + ） ； ， LABEL 1; CONST keylen=10; identlen=10; TYPE tstring=ARRAY1.identlen OF CHAR; outreco=RECORD ty:CHAR; point:INTEGER; END;ou

9、treco VAR cip,ip,pint,i,j,l,m:INTEGER; CHAR1:CHAR; ci:ARRAY1.10 OF INTEGER; k,id:ARRAY1.keylen OF tstring; token:tstring; outtoken:outreco; instring:ARRAY1.10 OF CHAR; p:ARRAY1.11 OF ARRAY1.2 OF CHAR; PROCEDURE lexical; var l,m,num:INTEGER; b:BOOLEAN; PROCEDURE getCHAR; BEGIN CHAR1:=instringpint; pi

10、nt:=pint+1; END;getCHAR PROCEDURE error; BEGIN writeln (error); pint:=pint+1 END;error BEGIN FOR l:=1 TO identlen DO tokenl:= ; getCHAR; while CHAR1= DO getCHAR; IF CHAR1 IN a.z THEN BEGIN m:=1; while (CHAR1 IN a.z) OR (CHAR1 IN 0.9) DO BEGIN IF m=identlen THEN BEGIN tokenm:=CHAR1; m:=m+1; END; getC

11、HAR; END;while pint:=pint-1; l:=1; b:=FALSE; while (l=keylen) AND (not b) DO BEGIN b:=TRUE; i:=1; while (i=identlen) AND b DO IF kli=tokeni THEN i:=i+1 ELSE b:=FALSE; IF not b THEN l:=l+1 END; IF l=keylen THEN BEGIN outtoken.ty:=k; outtoken.point:=l; END ELSE BEGIN l:=1; b:=FALSE; while (l=ip) AND (

12、not b) DO BEGIN b:=TRUE; i:=1; while (iip THEN BEGIN ip:=ip+1; FOR m:=1 TO identlen DO idipm:=TOkenm; END; outtoken.ty:=i; outtoken.point:=l; END END ELSE IF CHAR1 IN 0.9 THEN BEGIN num:=0; while CHAR1 IN 0.9 DO BEGIN num:=num*10+ORd(CHAR1)-ORd(0); getCHAR END; pint:=pint-1; l:=0; REPEAT l:=l+1 unti

13、l (l=cip) OR (num=cil); IF l=cip THEN BEGIN cicip:=num; cip:=cip+1; END; outtoken.ty:=c; outtoken.point:=l ENDINTEGER ELSE IF CHAR1 IN ,(,*,:,+,),;, THEN BEGIN outtoken.ty:=p; CASE CHAR1 OF : BEGIN getCHAR; IF (CHAR1=)AND (CHAR1) THEN BEGIN outtoken.point:=3; pint:=pint-1 END ELSE CASE CHAR1 OF =: o

14、uttoken.point:=1; : outtoken.point:=2 END; END; (:outtoken.point:=4; *:outtoken.point:=5; :BEGIN getCHAR; IF CHAR1= THEN outtoken.point:=6 ELSE BEGIN outtoken.point:=7; pint:=pint-1 END END; +:outtoken.point:=8; ):outtoken.point:=9; ;:outtoken.point:=10; ,:outtoken.point:=11 ENDCASE END ELSE error E

15、ND; lexical BEGIN writeln(K-TABLE,INPUT!); FOR l:=1 TO keylen DO FOR m:=1 TO identlen DO READ(klm); READLN; FOR l:=1 TO identlen DO FOR m:= 1 TO identlen DO idlm:= ; writeln(P-TABLE,INPUT!); FOR l:=1 TO 11 DO FOR m:=1 TO 2 DO READ(plm); READLN; ip:=0; cip:=1; 1: pint:=1; writeln(source,input!); FOR

16、j:=1 TO identlen DO READ( instringj); lexical; writeln(outtoken.ty); writeln(outtoken.point); FOR l:=1 TO identlen DO write( tokenl); writeln; GOTO 1; END. 词法分析的过程名为 lexical，它根据输入字符串第一个字符来划分单词类型。若第一个字符为字 母，则属关键字类或标识符类（凡 K 表中查不到的为后者） ；若第一个字符为数字，则为整数类；否则， 为界符类或本例无定义字符。 Lexical 过程中嵌入两个小过程，一个名为 gethar，其

17、功能是从输入字符串 instringpint中取出一个 字符，同时指针 pint 加 1，为下一个取字符作好准备。另一个过程名为 error，负责出错处理。这里知识 简单输出字符串 error，通知外界作进一步的处理。实习时，可略加扩充，如指出出错的位置、原因和性 质等。 注意，主程序是以调试程序的形式给出的，它主要完成： （1）准备工作。给 K 表和 P 表置初值； （2）读入 PASCAL 源程序字符串，如合法的关键字、标识符、整常数和界符等； （3）调用词法分析程序，对输入字符串进行词法分析； （4）输出词法分析的结果，即单词的 t 和 i，以及单词本身。其它表格的输出略去了。 运行结果

18、示例如下（输入时注意每个单词 10 个字符，在输入 P 表时每个字要占两个位置）： K-TABLE,INPUT! begin do else end if procedure then var while P-TABLE,INPUT! = ( * :=: + ) ; , source,input! begin k 1 begin source,input! + p 8 + source,input! c i 1 c source,input! a i 2 a 五、实验小结五、实验小结 （1）实习前的准备。根据实习目的和要求，用 PASCAL 语言编写一个规模适当的词法分析程序， 并选择相应的数

19、据结构。 （2）调试。调试例子应有词法正确的，也有错误的或超出实习要求的字符串。 （3）输出。主要将调试例子与词法分析结果以对照形式输出。必要时，凡是对以后编译有影响的数 据都予以输出，如单词串、K 表、I 表、C 表、P 表以及正误信息。 （4）扩充（任选） 。有余力的学生可适当扩大题目。譬如： 扩充界符和关键字数目； 允许有实型常数； 加细词法错误检查； 增加单词类（如字符类） ，或把界符类分成两类，即算符类和其它界符类； 处理对象是整个 PASCAL 语言的字符集合。 （5）编写上机实习报告。 实验二、语法分析实验二、语法分析 一、授课内容：一、授课内容： （一） 授课科目：编译原理 （

20、二） 授课内容：实验二 语法分析 （三） 授课类型：实 验 （四） 授课时间：12 学时 （五） 主讲教师：张瑞红 二、教学目的要求：二、教学目的要求： 1.目的：通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列 进行语法检查和结构分析，进一步掌握常用的语法分析方法。 2.要求： (1) 选择最有代表性的语法分析方法，算符优先法、递归子程序法和状态矩阵法之一进行实验。 (2) 选择对各种常见的程序语言都通用的语法结构，如赋值语句（尤其指表达式）作为分析对象， 并且与所选语法分析方法要比较贴切。 (3) 实验时间为 4 小时。 时间分为二次： 第一讲、介绍语法分析器

21、的设计原理（递归子程序法）为主，以 PASCAL 子集为例，并布置设计题； 第二讲、根据学生时间上机情况，辅导学生设计，并进行上机操作检查。 三、教学设想：三、教学设想： 1教学方法设想：先以例子讲解，然后学生动手实验，实验为主。 2教具运用设想：多媒体。 四、教学过程：四、教学过程： 1题目 试采用具有递归功能的高级语言（如 PASCAL 等等）编制递归下降法的语法分析程序， 并用它对 FORTRAN 语言算术表达式的一个简化子集进行语法分析。分析过程不嵌入任何语义动作。 分析对象的 BNF 定义如下： 算术表达式：=项|算术表达式+项|算术表达式-项 项：=因式|项*因式|项/因式 因式：

22、=变量| （算术表达式 ） 变量：=字母 字母：=A|B|C|D|E|f|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z 2算法 用递归下降法分析上述算术表达式的框图，如图 2-7-5 所示。这里，ZC 过程为总控制 程序，主要完成： （1）通知外界键入算术表达式； （2）控制 E 过程分析算术表达式； （3）根据分析结果之正误，分别通知外界不同的信息。 ZC 过程被设计成可以分析无穷多个算术表达式。 （在修该后，只要输入的开是字符为：# 就可以返回，终止分析程序。 ）E、T、F 三个过程分别对应算术表达式 、 项 、 因式三个产生 式的处理。它们用到两个公共过

23、程。一个是函数过程 SYS，它负责从输入字符串 ST 中取出下一个字 符，并存入 SYM 中等待分析。另一个过程 ADVANCE 负责剔除 ST 中的首字符。 3 程序及运行结果 采用 PASCAL 语言描述递归下降法分析算术表达式的一个程序和表达式分析 示例为： PROGRAM parser(intput,output); LABEL 1; LABEL 2; VAR p,tz,i:INTEGER; st:array1.20 of CHAR; FUNCTION sym:CHAR; BEGIN sym:=stp END; PROCEDURE error(n:INTEGER); BEGIN wri

24、teln(error,n); END; PROCEDURE e; PROCEDURE t; PROCEDURE f; BEGIN IF sym ina.z THEN p:=p+1 ELSE IF sym=( THEN BEGIN p:=p+1; e; IF sym=) THEN p:=p+1 ELSE BEGIN error(p); tz:=1; END END ELSE BEGIN error(p); tz:=1 END END; BEGIN f; while (sym=*) or (sym=/)do BEGIN p:=p+1; f; END; END; BEGIN t; while (sy

25、m=+)or(sym=-) do BEGIN p:=p+1; t; END; END; BEGIN 1: writeln(input expression,please!); FOR i:=1 to 20 do read(sti); readln; p:=1; IF sym=# THEN BEGIN writeln(finished!); GOTO 2; END; e; IF (sym#) or(tz=1) THEN BEGIN writeln(error, again); tz:=0; END ELSE writeln(right,again!); GOTO 1; 2: END. RUN:

26、input expression,please! a+b*c# right,again! input expression,please! (c+h)*i)/j)# right,again! input expression,please! a(+g# error, again input expression,please! (a+i)# error, again input expression,please! # finished! 在该程序中，过程 ADVANCE 未单独列出，是依靠挪动字符串指针（P 加 1）的办法来实现的。变 量 TZ 之值标志分析的结果（表达式）是否有错。 五、实

27、验小结五、实验小结 （1）实习前的准备 按实习目的和要求，用 PASCAL 语言编写一个递归下降法的语法分析程序， 同时考虑相应的数据结构。 （2）调试 调试例子应包括符合语法规则的算术表达式，以及分析程序能够判别的若干错例。 （3）输出 对于所输入的算术表达式，不论对错，都应有明确的信息告诉外界。 （4）扩充 有余力的同学，可适当扩大分析对象。譬如： 算术表达式中变量名可以是一般标识符，还可含一般常数、数组元素、函数调用等等。 除算术表达式外，还可扩充分析布尔、字符、位等不同类型的各种表达式。 加强语法检查，尽量多和确切地指出各种错误。 （5）编写上机实习报告。 提高型实验提高型实验语法器的

28、设计语法器的设计 一、授课内容：一、授课内容： （一） 授课科目：编译原理 （二） 授课内容：实验三 提高型实验语法器的设计 （三） 授课类型：实 验 （四） 授课时间：10 学时 （五） 主讲教师：张瑞红 二、教学目的要求：二、教学目的要求： 为了提高学生的程序设计能力，同时掌握编译原理中重要的组成部分语法分析的思想，为此， 经过大量的资料的查找，再结合学生的实际情况，制定了六个共选课题作为学生的提高型实验。每个实 验课题都有不同的思想，类型属于设计型。 具体的实验课题如下： (一)、LL（1）分析表的构造 (二)、LL（1）分析程序的设计 (三)、OPG 分析表的构造 (四)、OPG 分析

29、程序的设计 (五)、LR（0）分析表的构造 (六)、LR（0）分析程序的设计 (七)、SLR（1）分析表的构造 (八)、SLR（1）分析程序的设计 三、实验目的与要求以及算法三、实验目的与要求以及算法 （一） 、LL（1）分析表和分析程序的设计 LL（1）分析表的构造）分析表的构造 实验目的和要求：通过设计，编写和调试构造 LL(1)分析表（也称预测分析表）的程序，了解构造 LL(1)分析表的步骤，对文法的要求，能够从文法 G 出发自动生成 LL(1)分析表。 实验原理分析（包括算法）：设计一个自动构造 LL(1)分析表的程序，该程序的输入是任一个文法 G， 出是对应的 LL(1)分析表，并指

30、出该文法是否为 LL(1)文法。 例如：设文法 G 为：E-TE E-+TE|#(用#代替空字符) T-FT T-*FT|#(用#代替空字符) F-(E)|i 注：i 为整型常数或为标识符表示的整型变量。 构造 LL(1)分析表的算法：构造 LL(1)分析表需以下几个步骤 1 对于文法 G 的每个符号 X，构造 FIRST(X)集合。 2 构造 FIRST(X)集合又分为几种情况： a.若 X-a.(a 为终结符)，则 FIRST(X)=a。 b.若 X-#（为空） ，则 FIRST(X)=#。 c.若 X-Y1Y2Y3则先求出 Y1 的 FIRST 集，将 Y1 的 FIRST 集加入到 X

31、 的 FIRST 集 中，直到 FIRST 集不再扩大为止。 3 将所有的非终结符的 FIRST(X)集合用一个二维布尔矩阵 Fmn表示，其中 m 的大小表示 非终结符的个数，n 的大小表示终结符的个数+1，若 n 对应的终结符属于 m 对应的非终结 符的 FIRST 集，则 Fmn=1，否则为 0。 4 对于文法 G 的每个非终结符符号 X，构造 FOLLOW(X)集合. 5 构造 FOLLOW(X)集合又分为以下几种情况： a若 A-aB(a 可以为空)，则将 FIRST（）加入到 FOLLOW（B）中。 b若 AaB 或 AaB,且 =(即 FIRST（）)，则把 FOLLOW（A）加到

32、 FOLLOW（B）中。 6 构造分析表 M。 a、对文法 G（S）的每个产生式 Aa 执行以下步。 b、对每个终结符 aFIRST (A)，把 Aa 加入到 MA,a中，其中 a 为含有首字符 a 的候选式或为 惟一的候选式。 c、若 FIRST（A） ，则对任何属于 FOLLOW（A）的终结符 b，将 A 加入到 MA,b中。 d、把所有无定义的 MA,a标记为“出错” 。 实验方案及算法说明：各子程序的构造及功能说明： i. get_front(Gene ,front ,pos)。对每一个产生式取头部存储在 front 里，以便后面求 first 集和 follow 集。 ii. set

33、_ter_non( ):是对产生式分类，将产生式分成有候选式与没有候选式，分别存储在 Terminal 和 Nonterm 数组中，以便后面求 first 集和 follow 集。 iii. set_mrc(Gune ):提取终结符和非终结符，分别存储在 m_r 数组和 m_c 数组从而构造 first 集布 尔矩阵，follow 集布尔矩阵和 LL(1)二维表。 iv. Init( ):初始化 first 集矩阵，使每一个非终结符与每一个终结符对应的 first 为 0。 v. Find_r( ):为二维表的查找定位行标，使得填充 first 集布尔矩阵正确查找非终结符的行下标。 vi. F

34、ind_c( ):为二维表的查找定位列标，使得填充 first 集布尔矩阵正确查找终结符的列下标。 vii. Write_t( ):初步建立 first 集布尔矩阵，当每行的终结符为对应非终结符的 first 集时，first 填充为 1。 viii. Comp(array1,array2):二维矩阵的比较，用于求 first 集和 follow 集循环控制条件，当 first 集，follow 集不再增加时，即 array1:array2 时停止。 ix. Add( ):添加 first 集。当非终结符的 first 集新增加一个时，要在布尔矩阵中修改一次。 x. Add_null( ):添

35、加空集。 xi. Write_n( ):整体填充 first 集布尔矩阵，first 集不再增加时，整体填入到 first 集布尔矩阵。 xii. Fisrt_table( ):first 集布尔矩阵主程序。后面的程序大致相类似。 LL（1）分析程序的设计）分析程序的设计 实验目的和要求：通过设计、编写和调试预测分析程序，了解一般预测分析器的组成结构及对文 法的要求，掌握构造通用的总控制程序实现预测分析的方法。 实验原理分析（包括算法）：预测分析属于自上而下不带回溯的语法分析方法，这种分析方法要求 文法是 LL(1)的，语法分析程序的输入是终结符号串（即单词符号串，一一个“#”结尾） ，如果输

36、入串是 句子，则输出 YES，否则输出 NO 和错误信息。 （1）文法： 设 LL（1）文法 G 为： ETE E+TE| TFT T*FT| F（E）|i 注：i 为整型常数或者为标示符表示的整型变量。 （2）分析表 设 LL（1）分析表 M 如下表所示。 (3) 预测分析算法 实现预测分析算法需要使用一个分析栈 A 存放文法符号。变量 a 为 A 的栈顶 指针，变量 V1 存放当前输入符号。LL（1）分析表为二维数组 Cmn.用 type cha 来接受 Cmn. 分析算法思想： 若 x=ch=#,则分析成功，分析器停止工作。 若 x=ch#，即栈顶符号 x 与相当扫描的输入符号 ch 匹

37、配；则将 x 从栈顶弹出指针指向下一个 输入符号，继续对下一个字符进行分析。 若 x 为一非终结符号 V2,则查 Cmn: 若 Cmn中为一个 V2的产生式，则将 V2自栈顶弹出，并将 Cmn中的产生式右部符号串 array5逆序逐一入栈；如果 Cmn中的产生式为 ，则只将非终结符号自栈顶弹出。 控制程序如下： 将“#“和文法开始符号 E 依次压入栈中； 把第一个输入符号读入 ch； do 把栈顶符号弹出并放入 x 中； if(xVT) if(x=ch)将下一个输入符号读入 ch； Else error(); else if(Cmn=”xY1Y2Yk”) i+*()# E ETEETE E E

38、+TEEE T TFTTFT T TT*FTTT F FiF(E) 按逆序依次把 Yk,Yk-1Y1 压入栈中， 输出”xY1Y2Yk”； Else error(); while (x!=”#”) 实验方案或步骤（流程图、主要数据结构、程序、小结） (二)、OPG 分析表和分析程序的设计 OPG 分析表的设计分析表的设计 实验目的和要求：通过设计、编写和调试构造优先关系表的程序，了解构造算符优先关系表的 步骤以及对文法的要求，并能够从文法 G 出发自动生成算符优先关系表。 实验原理分析（包括算法）：设计一个自动构造优先关系表的程序，该程序的输入是算符文法 G，输出的是相应的优先关系表，并指出是

39、否为算符优先文法。 （1）例如以下文法： E-T+E|T T-F*T|F F-FP|P P-(E)|i 注：I 为整型常数后者为标识符表示的整型变量，使用中用*表示。 （2）构造优先分析表的算法 构造优先分析表需以下几个步骤： 构造文法 G 中非终结符号的 FIRSTVT 集合 FIRSTVT 集合用一个布尔数组 FP,a表示，F 是一个 m*n 的二维数组（m=文法 G 中非终结符 号个数，n=文法 G 中终结符号个数） 。其中 PVN，aVT，FP,a=TRUE 的条件是当且仅当 aFIRSTVTP。对于文法 G 的所有非终结符号，构造布尔数组 FP,a的算法（该算法使用 一个数据结构 S

40、TACK 栈，用于存放相应于 FP,a=TRUE 的符号对（P,a） ）如下： BEGIN FOR 任何非终结符号 P 和终结符号 a 对(P,a)DO FP,a=FALSE; FOR 任何形如 P-a或 P-Qa的产生式 DO IF NOT FP,a THEN BEGIN FP,a=TRUE; (P,a)进 STACK 栈； END; WHILE STACK 栈非空 DO BEGIN 将 STACK 的栈顶元素，记为（Q,a）,并出栈； FOR 每个形如 P-Q的产生式 DO IF NOT FP,a THEN BEGIN FP,a=TRUE; (P,a)进 STACK 栈; END; END

41、 OF WHILE; END. 构造文法 G 中非终结符号的 LASTVT 集合 类似于构造 FIRSTVT 集合，LASTVT 集合用一个布尔数组 LP,a表示，F 是一个 m*n 的二维数 组（m=文法 G 中非终结符号个数，n=文法 G 中终结符号个数） 。其中 PVN，aVT，LP,a =TRUE 的条件是当且仅当 aLASTVTP。对于文法 G 的所有非终结符号，构造布尔数组 LP,a的算法（该算法使用一个数据结构 STACK 栈，用于存放相应于 LP,a=TRUE 的符号对 （P,a） ）如下： BEGIN FOR 任何非终结符号 P 和终结符号 a 对(P,a)DO LP,a=F

42、ALSE; FOR 任何形如 P-a 或 P-aQ 的产生式 DO IF NOT LP,a THEN BEGIN LP,a=TRUE; (P,a)进 STACK 栈； END; WHILE STACK 栈非空 DO BEGIN 将 STACK 的栈顶元素，记为（Q,a）,并出栈； FOR 每个形如 P-Q 的产生式 DO IF NOT LP,a THEN BEGIN LP,a=TRUE; (P,a)进 STACK 栈; END; END OF WHILE; END. 构造文法 G 的优先关系表 使用文法 G 任何非终结符号的 FIRSTVT 集合和 LASTVT 集合，可以构造文法 G 的优先

43、关系表。 优先关系表用一个数组 Ra,b表示，R 是一个 n*n 的二维数组（n=文法 G 中终结符号个数） 。 其中 a,bVT,Ra,b = 、 或空（可能为多值） ，表示终结符号对（a,b）之间 具有“=” “”优先关系或无优先关系。构造优先关系表 Ra,b的算法如下： BEGIN FOR 每个产生式 P-X1X2.Xn DO FOR i:=1 TO n-1 DO BEGIN IF Xi 和 Xi+1 都是终结符 THEN 置 RXi,Xi+1为=; IF in-2 且 Xi 和 Xi+2 都是终结符而 Xi+1 是非终结符 THEN 置 RXi,Xi+2为=; IF Xi 是终结符而

44、Xi+1 是非终结符 THEN FOR FIRSTVT(Xi+1)中的每个 a DO 置 RXi,a 为; END; END. 判断文法 G 是否为算符优先文法 构造出文法 G 的算符优先表 Ra,b后，判别文法 G 是否为算符优先文法的算法如下： BEGIN FLAG=TRUE; FOR 文法 G 中的每个终结符号 a DO FOR 文法 G 中的每个终结符号 b DO IF Ra,b多于一种优先关系 THEN FLAG=FALSE; IF FLAG THEN 文法 G 是算符优先文法 ELSE 文法 G 不是算符优先文法; END. 实验方案或步骤（流程图、主要数据结构、程序、小结）实验方案或步骤（流程图、主要数据结构、程序、小结） OPG 分析程序的设计 实验目的和要求：通过设计，编写和调试算符优先分析程序，了解算符优先分析器的组成结 构以及对文法的要求，掌握实现通用算符优先分析算法的方法。 实验原理分析（包括算法）：算符优先分析属于自下而上的分析方法，该语法分析程序的输 入是终结符号串（即单词符号串，以一个“#”结尾） 。如果输入串是句子，则输出“YES” ，否则输出