递归下降分析法

递归下降分析法

4 递归下降分析法
递归下降分析法是确定的自上而下分析法,这种分析法要求文法是 LL ( 1 )文法。它的基本思想是,对文法中的每个非终结符编写一个函数(或子程序),每个函数(或子程序)的功能是识别由该非终结符所表示的语法成分。由于描述语言的文法常常是递归定义的,因此相应的这组函数(或子程序)必然以相互递归的方式进行调用,所以将此种分析法称为递归下降分析法。

构造递归下降分析程序时,每个函数名是相应的非终结符,函数体则是根据规则右部符号串的结构编写。

(1 )当遇到终结符 a 时,则编写语句
if (当前读来的输入符号 == a )读下一个输入符号

(2 )当遇到非终结符 A 时,则编写语句调用 A ()。

(3 )当遇到 A → ε 规则时,则编写语句
if (当前读来的输入符号 ∉FOLLOW ( A )) error ()

(4 )当某个非终结符的规则有多个候选式时,按 LL ( 1 )文法的条件能唯一地选择一个候选式进行推导。

【例 4.9 】设有文法 G [ S ]:

S → a |∧| ( T )
T → T , S | S

试构造一个识别该文法句子的递归下降分析程序。
分析 首先消去文法左递归,得到文法 G’ [ S ]:

S → a |∧| ( T )
T → ST'
T' → , ST' | ε

无左递归的文法不一定是 LL (1 )文法,根据 LL ( 1 )文法的判断条件,对非终结符 S 和 T’ 有

SELECT ( S → a ) ∩SELECT ( S →∧ ) =FIRST ( a ) ∩FIRST ( ∧ )= { a } ∩ { ∧ } = Ø

SELECT ( S → a ) ∩SELECT ( S → ( T )) =FIRST ( a ) ∩FIRST (( T ))= { a } ∩ {(} = Ø

SELECT ( S →∧ ) ∩SELECT ( S → ( T )) =FIRST ( ∧ ) ∩FIRST (( T ))= { ∧ } ∩ {(} = Ø

SELECT ( T' → , ST' ) ∩SELECT ( T' → ε ) =FIRST (, ST' ) ∩FOLLOW ( T' )= {,} ∩ {)} = Ø

所以文法 G’ [ S ]是 LL ( 1 )文法。
对文法 G’ [ S ]可写出相应的递归下降分析程序如下。
分析程序中函数 scaner ()的功能是读进源程序的下一个单词符号并将它放在全程变量sym 中;函数 error ()是出错处理程序。

main ()
{ scaner ();
S ();
if ( sym=='$' ) printf ( ″success″ ); elseprintf ( ″fail″ );
}
S ()
{ if ( sym =='a'||sym=='∧' ) scaner ();
elseif ( sym==' ( ' )
{ scaner (); T ();
if ( sym ==' ) ' ) scaner (); elseerror ();
}
elseerror ();
}
T ()
{ S (); T' ();}
T' ()
{ if ( sym ==' , ' )
{ scaner (); S (); T' ();}
elseif ( sym ! =' ) ' ) error ();
}

上述主函数和 3 个函数合起来是所给文法的递归下降分析程序,可以对文法的任意一个句子进行语法分析。
对这个例子,若采用扩充的 BNF 表示法改写文法,得到 G″ [ S ]:

S → a |∧| ( T )
T → S {, S }

该文法是 LL ( 1 )文法,其递归下降分析程序中主函数和函数 S ()同上,对函数 T ()用while 语句描述如下:

T ()
{ S ();
while ( sym ==' , ' ){ scaner (); S ();}
}

另外,对于无左递归的算术表达式文法,其确定的自上而下的分析方法可以参考习题4.2 。由这些例子可以看出,递归下降分析法简单、直观,易于构造分析程序,但它对文法要求高,必须是 LL ( 1 )文法,同时由于递归调用较多,影响分析器的效率。

今天的文章递归下降分析法分享到此就结束了，感谢您的阅读。