T(β)=Φ;它们不应该都能推出空字ε;3)对于文法中的每个非终结符A,若它存在某个候选首符集包含ε。即:假若β包含ε,那么,FIRST(α)∩FOLLOW(A)=Φ.4)主要算法A.递归下降分析程序定义:若一个文法G不含有左递归,而且每个非终结符的所有候选式的首符集都是两两不相交的,那么就能为G中每个非终结符编写一个相应的递归过程。把该文法中所有这样的递归过程组合起来就可能构成一个不带回溯的自上而下分析程序——递归下降分析程序。实现思想:为文法中每个非终结符编写一个递归过程,每个过程的功能是识别由该非终结符推出的串,当某非终结符的产生式有多个候选式时,按LL(1)形式唯一确定选择哪个候选式进行推导,若遇到某候选式为e,认为其自动匹配。把这些递归过程组合起来就构成了文法的递归下降分析程序。实现方法:a)使用LL(1)文法先将文法消除左递归、提取公共左因子,使之成为LL(1)文法,后将每个非终结符对应一个递归过程,过程体是按照相应产生式的右部符号串顺序编写。每匹配一个终结符,则再读入下一个符号,对产生式右部的每个非终结符,则调用相应的过程。b)使用BNF范式先将文法改写为BNF形式,后再书写递归子程序。优点:容易理解。缺点a)对文法的要求高,必须满足LL(1)文法。 b)高深度的递归调用会影响语法分析的效率,速度慢,占空间多。B.预测分析程序定义:使用高级语言的递归过程描述递归下降分析器,只有当具有实现这种过程的编译系统时才有实际意义。实现LL(1)分析的另一种有效方式是使用一张分析表和一个栈进行联合控制。实现思想:预测分析程序就是属于这种类型的LL(1)分析器。实现方法:构造分析表和栈,设栈顶符号为X,读入符号为a,则a)若X=a=‘#’,则表示识别成功,退出分析程序;b)若X=a¹’#’,则表示匹配,弹出栈顶符号X,读头前进一格,让读头指向下一个符号,以读入下一个符号;若
全文预览
