第4章自顶向下语法合编.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）文法的条件唯一地选择一个侯选式进行匹配。 问题:为什么要编成递归子程序？ 因为文法具有递归性。前面已经讲过，自顶向下分析不能处理左递归文法，若有左递归，则应改写文法，但是消除了左递归并不等于消除了文法中的所有递归性质，此时文法有右递归性或自嵌入性。如在文法中可能有如下规则： U→…U U→…U… 此仍为递归规则，所以要编成递归子程序。 递归下降法的优缺点 优点： ①最主要一点是编写速度快； ②由于分析器和文法的紧密对应性，容易保证语法分析器的正确性。至少使得错误都变得简单和易于发现。 ③构造方法非常简单,程序结构清晰。 缺点： ①递归调用较多，占用内存多、速度慢， ②如果所采用的高级语言不允许递归，则不能使用此方法 对于LL(1)文法，利用SELECT集，我们还可以得到十分有助于句子分析的结果： (1)分析过程某一步，当非终结符U正处于栈顶时， 若a∈SELECT (U→?),且