[精品]对输入串abbcde#进行分析,检查该符号串是否是G[S]的句子..ppt

第六章???自底向上的优先分析法;它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，(该句柄对应某产生式的右部)，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，;例(P102);自底向上构造语法树的过程 ;在上述移进-归约或自底向上构造语法树的过程中，我们怎么知道何时移进，何时归约，不能只简单地看成栈顶出现某一产生式的右部就可用相应产生式归约，例如在表6.1分析到第5)步时栈中的符号串是#aAb，栈顶符号串b和Ab分别是产生式(2)，(3)的右部，这时到底用(2)归约还是用(3)归约是自底向上分析要解决的关键问题。;6.2简单优先分析法;(1)X Y 当且仅当G中存在产生式A→…XY… (2)X Y 当且仅当G中存在产生式A→…XB…,且B Y… (3)X Y 当且仅当G中存在产生式A→…BD…, 且B …X和D Y… 见P104-105页的例题6.2;6.3 算符优先分析法 　　 算符优先分析的基本思想是只规定算符(广义为终结符)之间的优先关系，也就是只考虑终结符之间的优先关系，不考虑非终结符之间的优先关系。;如何确定算符优先关系？;例如:若有文法G为：　　(1) E→E+E　　(2) E→E*E　　(3) E→i　　对输入串i+i*i的归约过程可表示为表6.3。; 算符优先文法的定义;证明：性质1　　用归纳法　　设γ是句型，即S ?? γ　　S=ω0 ???? ω1 ???? ... ?? ωn-1 ???? ωn=γ　　推导长度为n，归纳起点n=1时，　　S=ω0 ???? ω1=γ，即S ?? γ，必存在产生式S→γ，而由算符文法的定义，文法的产生式中无相邻的非终结符，显然满足性质1。　　假设n＞1, ωn-1满足性质1。　　若ωn-1=αAδ，A为非终结符。　　由假设α的尾符号和δ的首符号都不可能是非终结符，否则与假设矛盾。　　又若A→β是文法的产生式，则有　　ωn-1 ???? ωn=αβδ=γ　　而A→β是文法的原产生式，不含两个相邻的非终结符，所以αβγ也不含两个相邻的非终结符。满足性质1。证毕。 ; 证明：性质2　　用反证法。　　因为由算符文法的性质1知可有：　　S ?? γ=αbAβ　　若存在B ?? αb，这时b和A不同时归约，则必有S ?? BAβ, 这样在句型BAβ中存在相邻的非终结符B和A，所以与性质1矛 盾，证毕。注意：含b的短语必含A，含A的短语不一定含b。;算符优先关系的定义：;在 OG文法 G 中，若任意两个终结符间至多有一种算符优先关系存在，则称G 为算符优先文法(OPG)。 注意：不允许 bc, bc, b=c中任两个 同时存在。 b=c 不一定 c = b。 例：G：(1) E→E+E 　 (2) E→E*E (3) E→i对i+i*I可以画两棵语法树如图 E E E+E E*E E*E E+E i i i i i i 结论 : 算符优先文法是无二义的。;算符优先关系表的构造;如何求FIRSTVT集: 若有产生式A →a… 或A →Ba… 则a∈FIRSTVT(A) 若a ∈FIRSTVT(B)且有产生式A →B… 则a ∈FIRSTVT(A);计算算符优先关系;(0)E’→#E# (1) E→E+T (2) E→T (3) T→T*F (4) T→F(5) F→P?F|P (6) P→(E) (7) P→i;表达式文法G’[E’]的算符优先关表;算符优先分析;文法G[E]：(1) E→E+T(2) E→T(3) T→T*F(4) T→F(5) F→P?F|P(6) P→(E)(7) P→i;算符优先分析算法前面介绍了如何对已给定的文法按其产生式构造算符优先关系表，有了算符优先关系表并满足算符优先文法时，我们就可以对任意给定的符号串进行归约分析，进而判定输入串是否为该文法的句子。然而用算符优先分析法的归约过程与规范归约是不同的。例：表达式文法：(0)E’→#E# (1) E→E+T (2) E→T (3) T→T*F (4) T→F(