淮阴工学院编译原理课程设计报告选题名称:算符优先分析法系（院）:计算机工程学院专业:计算机科学与技术班级:计算机1075 姓名:学号:指导教师:学年学期:2009 ~ 2010 学年第 2 学期2010 年 5 月17 日设计任务书指导教师（签章）：年月日摘要：编译原理是计算机系统的基本组成部分之一，而且多数据计算机系统都配有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。
从功能上看，一个编译程序就是一个语言翻译程序。
算符优先分析法是一种简单直观、广为使用的自下而上分析法。
这种方法特别有利于表达式分析，宜于手工实现。
算符优先分析过程是自下而上的归约过程，但这种归约未必是严格的最左归约。
也就是说，算符优先分析法不是一种规范归约法。
所谓算符优先分析就是定义算符之间(确切地说，终结符之间)的某种优先关系，借助于这种优先关系寻找“可归约串”和进行归约。
关键词：编译原理；归约；算法；算符优先；编译目录1需求分析 (1)2 概要设计 (1)2.1算符优先分析法的思想及其原理 (1)2.2算符优先分析算法 (4)2.3 构建算符优先关系表 (6)2.4 出错处理 (7)3 详细设计 (7)3.1 程序流程图 (7)3.2 构建算符优先关系表 (8)3.3 进栈优先函数 (8)3.4 算符优先规约函数 (10)3.5 弹出窗体 (12)4 程序运行、调试及操作说明 (12)总结 (15)致谢 (16)参考文献 (17)1需求分析本次课程设计的题目是算符优先分析法。
算符优先分析法是一种简单直观、特别方便于表达式分析，易于手式实现的方法。
算符优先法只考虑算符（广义为终结符号）之间的优先关系，它是一种自底向上的归约过程，但这种归约未必严格按照句柄归约。
它是一种不规范归约法。
根据已知文法：E->E+T|E-T|TT->T*F|T/F|FF->(E)|i(E)|i|d（其中d表示0-9的数字，i表示字母，大小写均包括）根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否正确(1)可以使用任何语言来完成，例如：Java、C++。
(2)构造此文法的分析过程(3)输入测试字符串，输出测试结果给出关键类类图、整个应用程序的结构描述文档、关键模块流程图、较详细的接口文档、所有源代码。
对应用程序进行测试，对测试结果进行分析研究，进而对应用程序进行改进，对关键算法进行尽可能的优化，最终得到一个在windows运行的可以根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否正确，输入测试字符串，输出测试结果的完整应用程序。
2 概要设计2.1算符优先分析法的思想及其原理算符优先分析算法算法原理：（1）初始化栈：k=1; S[k]=‘#’；（2）依次从输入串中读入符号a：①当前单词若为标识符，则a值为i，若为常数则a值为d；其它a直接取单词值。
②若a大于等于栈顶第一个终结符的优先级，则a进栈；③若a小于栈顶第一个终结符的优先级，则重复做：i)找出最左子串S[j]⋖S[j+1]=…=S[k]⋗a；ii)把S[j+1]…S[k]归约为某个N；iii)将归约后的非终结符N入栈；④出错处理。
若输入串扫描完毕，且栈中呈现#S，且a 为#，则符合语法要求，否则就不符合语法要求。
2.1.1算符优先分析法的基本思想仿照算术表达式的四则运算过程算符优先分析的基本思想是只规定算符(广义为终结符)之间的优先关系，也就是只考虑终结符之间的优先关系，不考虑非终结符之间的优先关系。
在归约过程中只要找到可归约串就归约，并不考虑归约到那个非终结符名，算符优先分析的可归约串不一定是规范句型的句柄，所以算符优先归约不是规范归约。
算符优先分析的可归约串是当前符号栈中的符号和剩余的输入符号构成句型的最左素短语。
2.1.2优先关系的定义设G是一个不含ε产生式的算符文法，a和b是任意两个终结符，A、B、C 是非终结符，算符优先关系、、定义如下：① a b 当且仅当G中含有形如A→…ab…或A→…aBb…的产生式②a b 当且仅当G中含有形如A→…aB …的产生式，且B b… 或B Cb…③a b当且仅当G中含有形如A→…Bb …的产生式，且B…a 或B…aC以上三种关系也可由下列语法树来说明：① a b 则存在语法子树如图2.1(a)其中δ为ε或为B，这样a, b在同一句柄中同时归约所以优先级相同。
② a b 则存在语法子树如图2.1(b)其中δ为ε或为C。
a,b不在同一句柄中，b先归约，所以a的优先级低于b。
③ a b 则存在语法子树如图2.1(c) 。
图2.1 由语法树结构决定优先性2.1.3算符优先文法的定义那么定义FirstVT(P)={a|P->a 、、、或P->Qa 、、、，a 属于终结字符集，而Q 属于非终结字符集}LastVT （P ）={a|P->...a 或P->...aQ ，a 属于终结字符集，而Q 属于非终结字符集}由以下两条规则来构造FirstVT 集：(1)若有产生式P-〉a …、或P->Qa …，则a 属于FirstVT （P ）；(2)若有a 属于FirstVT （Q ），且有产生式P-〉Q …，则a 属于FirstVT(P); 类似的有构造LastVT 集的规则：(1)若有产生式P->…a 或P->…aQ ，则a 属于LastVT 集。
(2)若a 属于LastVT （Q ），且有产生式P-〉…Q ，则a 属于LastVT 集。
构造FirstVT 集的算法： BeginFor 每个非终结符P 和终结符a Do F[P ，a]=FALSE ； For 每个形如P-〉a …或P-〉Qa …的产生式……（1） DO insert （P ，a ） While Stack 非空 Do Begin把Stack 的顶项，记为（Q ，a ），上托出去；(a)ab (b)a b (c)abFor 每条形如P-〉Q …的产生式DO …….（2） Insert （P ，a ） End of while ； END2.2算符优先分析算法2.2.1算符优先分析句型的性质如果aNb(或ab)出现在句型r 中，则a 和b 之间有且只有一种优先关系,即： 若a b 则在r 中必含有b 而不含a 的短语存在。
若a b 则在r 中必含有a 而不含b 的短语存在。
若ab 则在r 中含有a 的短语必含有b ，反之亦然。
2.2.2最左素短语设有文法G[S],其句型的素短语是一个短语,它至少包含一个终结符，并除自身外不包含其它素短语，最左边的素短语称最左素短语。
例如,若表达式文法G[E]为： E→E+T|T T→T*F|F F→P↑F|P P→(E)|i图2.2 句型T+T*F+i 的语法树若有句型#T+T*F+i#，它的语法树如图2.2。
其短语有： T+T*F+i 相对于非终结符E 的短语 T+T*F 相对于非终结符E 的短语E T +E T+ E TT * F FPiT 相对于非终结符E的短语T*F 相对于非终结符T的短语i 相对于非终结符P,F,T的短语由以上内容知i和T*F为素短语，T*F为最左素短语。
也为算符优先分析的可归约串。
由算符优先分析算法可知一个算符优先文法的最左素短语满足如下条件：ai-1 ai ai+1 ... aj aj+1上述句型#T+T*F+i#写成算符分析过程的形式为：#N1a1N2a2N3a3a4#其中a1 = +, a2 = *, a3 = +, a4 = ia1 a2 (因+ *)a2 a3 (因* +)由此N2a2N3 即T*F为可归约串，也就是前面分析的最左素短语。
2.2.3 算符优先分析归约过程的算法自底向上的算符优先分析法，也为自左向右归约，我们已经知道它不是规范归约。
规范归约的关键问题是如何寻找当前句型的句柄，而算符优先分析归约的关键是如何找最左素短语。
最左素短语NiaiNi+1ai+1 … ajNj+1 应满足：ai-1 aiai ai+1 … ajaj aj+1在文法的产生式中存在右部符号串的符号个数与该素短语的符号个数相等，非终结符号对应Nk,(k=i，…，j+1)不管其符号名是什么。
终结符对应ai，…，aj，其符号名要与ai，…，aj的实际名相一致，相应位置也一致，才有可能形成素短语。
由此，我们在分析过程中可以设置一个符号栈S，用以寄存归约或待形成最左素短语的符号串，用一个工作单元a存放当前读入的终结符号，归约成功的标志是当读到句子结束符#时，S栈中只剩#N，即只剩句子最左括号'#'和一非终结符N。
下面给出分析过程的示意图如图2.3。
S[j] a S[j] a?S[j] a?S[j] ’#S[j] Q图 2.3 算符优先分析归约过程框图在归约时要检查是否有对应产生式的右部与S[j+1]…S[k]相符，若有才可归约，否则出错。
在这个分析过程中把'#'也放在终结符集中。
S[j+1]…S[k]为S栈中符号串，S[k]为栈顶符号。
所谓检查是否有对应产生式的右部与S[j+1]…S[k]相符，是指符号个数是否相等，对应的终结符名是否相同。
不管非终结符名字。
规范归约时句柄为某一产生式的右部，归约结果为从符号栈中去掉与句柄相同的产生式右部符号串，并把左部非终结符放入栈中，代替归约前的句柄。
2.3 构建算符优先关系表假定G是一个不含e-产生式的算符文法。
对于任何一对终结符a、b，我们说：1. a≖b当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式；2. a⋖b当且仅当G中含有形如P→…aR…的产生式，而Rb…或RQb…；3. a⋗b当且仅当G中含有形如P→…Rb…的产生式，而R…a或R…aQ。
如果一个算符文法G中的任何终结符对（a，b）至多只满足下述三关系之一：a≖b，a⋖b，a⋗b则称G是一个算符优先文法。
现在来研究从算符优先文法G构造优先关系表的算法。
通过检查G的每个产生式的每个候选式，可找出所有满足a≖b的终结符对。
为了找出所有满足关系⋖和⋗的终结符对，我们首先需要对G的每个非终结符P 构造两个集合FIRSTVT（P）和LASTVT（P）：FIRSTVT（P）＝{a | Pa…或PQa…，aÎVT而QÎVN}LASTVT（P）＝{a | P…a或P…aQ，aÎVT而QÎVN}2.4 出错处理使用算符优先分析法时，可在两种情况下，发现语法错误：1. 若在栈顶终结符号与下一输入符号之间不存在任何优先关系；2. 若找到某一“句柄”（此处“句柄”指素短语），但不存在任一产生式，其右部为此“句柄”。
针对上述情况，处理错误的子程序也可分成几类。