非递归的预测分析法

本站有部分文章来源于网络,如果无意间侵犯了您的权益,我感到非常抱歉,您可以随时联系我,我会第一时间删除文章,邮箱:hylee_lhy@qq.com。可用于广州大学校园网认证的路由器,输入账号密码后一键即可实现认证。还在为手机没有流量烦恼吗?赶紧点我了解详情吧!GM手游,花低价,嗨玩。无限钻石,全网游戏最多的平台。超爽包站VIP,全新热门手游,上新快,超稳定,精品双端。快点击我查看详情吧!

非递归的预测分析法

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

例:

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

表驱动的预测分析法

• 输入：一个串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）对于递归的预测分析，根据预测分析表为每一个非终结符编写一个过程；对于非递归的预测分析，实现表驱动的预测分析算法