资源描述：
《【精品】算符优先文法分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、算符优先文法分析1•问题描述基于算符优先分析法的语法分析程序要求：(1)输入已知文法，生成文法矩阵，判断该文法是否是算符优先文法。(2)用程序自动生成该文法的算符优先关系炬阵。(3)对人工输入的句型或句子，分析该句型或句子是否合法,能否用已知文法推出。(4)具有通用性。所开发的程序可适用于不同的文法和任意输入串，且能判断该文法是否为算符优先文法。(5)有运行实例。对于输入的文法和符号串，所编制的语法分析程序应能正确判断此串是否为文法的句子，并要求输出分析过程。2.算符优先分析法2.1算符优先文法定义
2、：设有不含空串的一文法G,如果G屮没有形如G>……BC……的产生式，其中B和C为非终结符，且对任意两个终结符a,b之间Z多只有<,>,二，三种关系的一种成立，则称G是一个算符优先文法。非终结符的FIRSTVT集合和LASTVT集合FIRSTVT(B)二{b
3、B->b・・・或B->Cb・・・}LASTVT(B)={b
4、B->-a或B—aC}2.2算符优先矩阵算符优先关系矩阵，判断输入是否满足已知文法的依据。根据非终结符的FTRSTVT集合和LASTVT集合产生。1.“二”关系若A-*・・・ab…或A~
5、・・・aBb…，贝Ua=b；2.“〈•”关系若A-…aB…，对每一个b属于FIRSTVT(B),有a<-b；3.“•〉”关系若A—・Bb…,对每一个a属于LASTVT（B）,有a・〉b。2.3如何规约在分析过程中，利用分析栈存放已识别的那部分句型，而句型的其余部分由剩余输入串组成，通过比较栈顶符号和下一个输入符号之间的关系，可以判别栈顶符号是否为句柄尾符号。如果是句柄尾，则沿栈顶向下，在栈内寻找句柄头（利用关系）。由关系和关系Z间包括的符号串就是句柄，然后把它们弹出栈，并代之以归约后的非终结符。这样
6、就完成了一次归约过程。2.4算符优先分析方法的局限性由于算符优先分析法去掉了单非终结符Z间的归约，尽管在分析过程中，当决定是否为句柄时采取一些检查措施，但仍难完全避免把错误的句子得到正确的归约。此外，通常一个适用语言的文法也很难满足算符优先文法的条件，因而致使算符优先分析法仅适用于表达式的语法分析。3概要设计，即算法或流程图本程序有java面向对象的程序设计方法设计。主要类有Suanfu（界面类），Grammar,FirstLeist,Table,Guiyue。其中Suanfu完成所有与界面相关的操
7、作；Grammar完成文法的提取，和终结符，非终结符的识别，和初步判断输入文法的正确性；FirstLast完成非终结符FTRSTVT集合和LASTVT集合的构造；Table完成算符优先关系矩阵的构造，并检查文法的二义性。除界面类外，其他类均由构造函数完成其数据处理功能。3.1算符优先分析流程图算符优先文法的执行过程为：输入已知文法，分析其正确性,提取非终结符和终结符，构造非终结符的FIRSTVT集和LASTVT集，再次基础上构造算符优先关系矩阵，并用來判断表达式是否符合该文法。算符优先文法程序总的流
8、程图为：程序总的程序流程图2.2文法分析Grammar类提取文法，识别终结符和非终结符，并简单判断文法是不是算符优先文法。主要数据：g：String[]用于存储所有产生式；T：char[]用于存储非终结符；t：char[]用于存储终结符。大写字母作为非终结符，其余字符均作为终结符。文法分析主要解决的问题有：(存在这些问题的文法，都不是算符优先文法)1.产生式左边含有终结符2.产生式右边有相邻非终结符3.存在非终结符只在产生式右侧不在产生式左侧的4.不可终结的产生式，即文法没有右侧全为终结符的产生式，
9、此种文法不可产生终结的字符串。5.不可到达的产生式，即产生式右侧的非终结符补岀现在其他产生式屮，开始字符除外。2.3文法每个非终结符的FIRSTVT集和LASTVT集FirstLast类用于FIRSTVT集合和LASTVT集合构造。主要数据：first：char[][]用于存储非终结符的FIRSTVT集合;last：char[]□用于存储非终结符的LASTVT集合。对FIRSTVT集的构造我们可以给出一个算法，这个算法基于下面两条规则：(1)若有产生式A-a・・诚A-Ba…，则&属于FTRSTVT(
10、A),其中A,B为非终结符，a为终结符(2)若a属于FIRSTVT(B)且有产生式A-B・••则有a属TFIRSTVT(A)o为了计算方便，我们建立一个布尔数组F[ni,n](m为非终结符个数，n为终结符个数)和一个后进先出栈STACKo我们将所有的非终结符排序，用的序号，再将所有的终结符排序，用表示终结符a的序号。算法的a的是要合数组每一个元素最终取什满足：F［,］的值为真，当且仅当a属于F1RSTVT(A)。至此，显然所有非终结符的FIRSTVT集己完全确定。步骤
