编译原理第4章第2部分剖析.ppt

4.2.4 递归下降分析法 * 递归下降分析法是确定的自上而下分析法，这种分析法要求文法是LL(1)文法。 4.2.4 递归下降分析法 基本思想 对文法中的每个非终结符编写一个函数 (或子程序), 每个函数（或子程序）的功能是识别由该非终结符所表示的语法成分。由于描述语言的文法常常是递归定义的，因此相应的这组函数（或子程序）必然以相互递归的方式进行调用，所以将此种分析法称为递归下降分析法。 4.2.4 递归下降分析法 构造递归下降分析程序的方法: 为每个非终结符编制一个递归下降分析函数，每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构和顺序编写。 A→α1α2…αn αi∈VT αi∈VN α1α2…αn=ε 4.2.4 递归下降分析法 (1) 当遇到终结符a时，则编写语句 if (当前读来的输入符号==a) 读下一个输入符号； (2) 当遇到非终结符A时，则编写语句调 用 A( )； (4) 当某个非终结符的规则有多个候选式 时，按LL(1)文法的条件能唯一地选 择一个候选式进行推导。 (3) 当遇到规则A→ε 时，则编写语句 4.2.4 递归下降分析法 if (当前读来的输入符号?FOLLOW(A)) error( )； 例 设有文法G[S] S→a |∧| (T) T→T, S | S 1.消去文法左递归,改写文法G[S]为G’[S] 2.计算文法G’[S]每个非终结符的FIRST集 和FOLLOW集 。 3.判断文法G’[S] 是否LL(1)文法,是，构造递归下降子程序 分析 引进新的非终结,改写文法,得到文法G[S]: S →a |∧| (T) T →ST T→,ST| ε S→a |∧| (T) T→T, S | S S T T FIRST FOLLOW FIRST(S)= FIRST(a)∪FIRST(∧)∪FIRST((T)) = {a, ∧, ( } S →a |∧| (T) T →ST T→,ST | ε FOLLOW(S) = { $, , ,) } { a, ∧, ( } { ) } {, ,ε} { ) } { a, ∧, ( } {$, , , ) } 根据FIRST集和FOLLOW集的定义,求出文法每个非终结符的FIRST集和FOLLOW集： 无左递归的文法不一定是LL(1)文法，根据LL(1)文法的判断条件，对非终结符S和T有： SELECT(S→a)∩SELECT(S→∧) ∩SELECT(S→(T)) = FIRST(a)∩FIRST(∧) ∩FIRST((T)) ={a}∩{∧} ∩{ ( }=Φ SELECT(T→,ST)∩SELECT(T→ε) = FIRST(,ST)∩{FIRST(ε)∪FOLLOW(T)} ={,}∩{ ε,)} =Φ 所以文法G[S]是LL(1)文法。 分析程序中定义两个函数： (1) 函数 Scaner( ) 功能: 读进源程序的下一个单词符号 并将它放在全程变量sym。 (2) 函数 error( ) 功能: 出错处理程序。 4.2.4 递归下降分析法 T′( ) {if (sym= =′,′) { scaner ( );S( ); T′( )；} else if (sym!= ′) ′) error（）;} main() {scanner(); S(); if (sym= =‘$’) printf (“success”); else printf (“fail”);} S( ) {if (sym= =′a′) scaner( ); else if (sym=′＾′) scaner ( ); else if (sym=′(′) { scaner ( ); T( ); if (sym= =′)′) scaner ( ); else error（）;} else error（）;} T( ) {S( );T′( );} S →a |∧| (T) T →ST T→,ST | ε 缺点: 对文法要求高，必须是LL(1)文 法，同时由于递归调用较多，影响分析器的效率。 优点: 递归下降分析法简单、直观，易 于构造分析程序。 4.2.4 递归下降分析法 E→ E + T | T T