非递归的预测分析法

非递归的预测分析不需要为每个非终结符编写递归下降过程,而是根据预测分析表构造一个自动机,也叫表驱动的预测分析。

例:

如果w是至今为止已经匹配完成的输入部分,那么栈中保存的文法符号序列α满足S => * lm

表驱动的预测分析法

  • 输入:一个串w和文法G的分析表 M
  • 输出:如果w在L(G )中,输出w的最左推导;否则给出错误指示
  • 方法:最初,语法分析器的格局如下:输入缓冲区中是w$,G的开始符号位于栈顶,其下面是$。下面的程序使用预测分析表M生成了处理这个输入的预测分析过程
设置ip使它指向w的第一个符号,其中ip 是输入指针;
令X=栈顶符号;
while ( X ≠ $ ){ /* 栈非空 */ 
    if ( X 等于ip所指向的符号a) 执行栈的弹出操作,将ip向前移动一个位置;
    else if ( M是一个终结符号) error ( ) ;
    else if ( M[X,a]是一个报错条目) error ( ) ; 
    else if ( M[X,a] = X →Y1Y2 … Yk ){
        输出产生式 X →Y1Y2 … Yk ; 弹出栈顶符号;
        将Yk,Yk-1 …,Yi 压入栈中,其中Y1位于栈顶。
    }令X=栈顶符号
}

递归的预测分析法vs.非递归的预测分析法

递归的预测分析法 非递归的预测分析法
程序规模 程序规模较大, 不需载入分析表 主控程序规模较小, 需载入分析表(表较小)
直观性 较好 较差
效率 较低 分析时间大约正比于待分 析程序的长度
自动生成 较难 较易

预测分析法实现步骤

1)构造文法
2)改造文法:消除二义性、消除左递归、消除回溯
3)求每个变量的FIRST集和FOLLOW集,从而求得每个候选式的SELECT集
4)检查是不是 LL(1) 文法。若是,构造预测分析表
5)对于递归的预测分析,根据预测分析表为每一个非终结符编写一个过程;对于非递归的预测分析,实现表驱动的预测分析算法

最后修改日期:2020年6月1日

留言

撰写回覆或留言