[工学]第4章语法分析20090408.ppt

LL（1）文法的引入 　　　　　　　　　　　　　　　　　　　　　　　　　　　 S-文法： ①每个产生式右边都以终结符开始； ②同一个非终结符的各个侯选式的首终结符不同； 例如:文法G[S]: (1)S→aBC (2)B→bC (3)B→dB (4)C→c (5)C→a 分析句子adbca LL（1）文法的引入 Q-文法： ①每个产生式右边都为ε或以终结符开始； ②具有相同左部的产生式具有不相交的可选集； 例如:文法G[S]: (1)S→aBC (2)B→bC (3)B→dB (4)B→ ? (5)C→c (6)C→a 分析句子ada LL（1）文法的判别 一个上下文无关文法称为是LL（1）文法，当且仅当同一非终结符的各个产生式的可选集互不相交。 LL(1)含义: 自左向右扫描输入串,使用最左推导方法分析句子,1表示分析时需要向前查看一个符号 FOLLOW(S)={$}；FOLLOW(A) = FOLLOW(S)∪{*} = {*, $};FOLLOW(A?)=FOLLOW(A) = {*, $},FOLLOW(B) = FIRST(A?) ∪ FOLLOW(A?) ∪ FOLLOW(A)={i, *, $};FOLLOW(B?)=FOLLOW(B)={i, *, $}； 例 设文法G[S]： 1 S→ A 2 A→ BA? 3 A? → iBA??? 4 B→ CB? 5 B? → +CB??? 6 C → ) A*| ( 改写成简单产生式 1 S→ A 2 A→ BA? 3 A?→ iBA? 4 A?→ ? 5 B→ CB? 6 B?→ +CB? 7 B?→ ? 8 C → ) A* 9 C → ( S→aSb|A A→bA A→Ac|Bc B→aB B→aB|? SELECT(S→aSb)={a} SELECT(S→A)={b} SELECT(A→Ac)={b} SELECT(A→Bc)={a} SELECT(B→aB)={a} SELECT(B→aB)={a} SELECT(B→?)=FOLLOW(B) = FOLLOW(B)={c} 4.2.4 递归下降分析程序及其设计 它是一种确定的自上而下分析方法,也是编译程序中使用得最为广泛的一类分析程序。 要求：所依据的文法是LL（1）文法。 基本思想：为文法中的每个非终结符编写一个函数（或子程序），这个函数或子程序的功能是识别由该非终结符表示的语法成分。 由于描述语言的文法常常是递归定义的，因此相应的这组函数（或子程序）必然以相互递归的方式进行调用，所以将这种方法成为“递归下降法”。 一般情况下，用非终结符表示过程的名字，过程体则按产生式右部符号串顺序编写。每匹配一个终结符，则再读入下一个符号，对于产生式右部的每一个非终结符，则调用相应的过程。当一个非终结符对应多个侯选式时，则过程体将按可选集来决定选用哪个侯选式。在递归下降法中，递归子程序数等于文法中的非终结符个数。 递归子程序的设计方法 构造递归下降分析程序时，每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构编写。 （1）当遇到终结符a时，则编写语句： if （当前读入的输入符号=a)(匹配),读入下一个符号； if (ch = a） then READ(ch) else error （2）当遇到非终结符A时，则编写语句调用相应的函数A（）； （3）当遇到A→ε时，则编写语句： if（当前读入的符号≠FOLLOW（A））,ERROR( ); (4)当某个非终结符的规则有多个侯选式时，按LL（1）文法的条件唯一地选择一个侯选式进行匹配。 框图设计 设文法G [S]： S→ (A)?aAb A→ eA??dSA? A?→ dA??? 此文法的递归下降程序框图设计如下所示。图中省略了递归入口RI和递归出口RO部分，如果采用低级语言编程，只需要在程序框图的开头和末尾加上这两个部分。 程序设计 例中的文法G [S]： 子程序P(S)： READ(ch) if ch = ?(? then begin READ(ch); P(A); if ch = ?)? then goto L else error end else if ch ? ?a? then error else begin READ(ch); P(A)