语法分析-编译原理期末复习

自上而下的语法分析

自上而下语法分析法:或从开始符号出发,找最左推导;或从根开始,构造推导树。

自下而上语法分析法:从输入串开始,归约,直至文法开始符。

回溯分析法

产生回溯的原因：公共左因子（开始匹配上了，可能走错分枝）、左递归（不知道递归多少次）、空产生式。

公共左因子

左递归（直接、间接）

空产生式

提取公共左因子

将文法
S→xAy
A→ab│ac
改造成：
S→xAy
A→aB
B→b│c

消除左递归

消除直接左递归

别忘了改写之后的空。

消除间接左递归

预测分析法

预测分析是一种表驱动方法，由下推栈、预测分析表和控制程序组成。它实际上一种下推自动机的实现模型。

初始时,#和开始符（S）入栈,输入指针指向第一个符号,
然后根据下推栈栈顶符x和当前输入符a进行工作:
① x=a=#, 成功
② x=a不等于#, 匹配（一定是终结符，从栈顶和输入串中去除）
③ x是非终结符VN, 查表（非终结符查表，才可以逐步推导替换为终结符）。并把产生式右部符号按逆序推进栈

构建预测分析表

1. FIRST集

FIRST（a）表示可能由a推导的开头终结符以及可能的空。

对每个文法符号X：VT和VN，连续使用入下规则，直到每个FIRST(X)不再增大

假设X-〉X1X2…Xn