语法分析

语法分析

语法分析分为两大类：

• 自上而下的分析方法：
  • 非确定的自上而下分析法：穷举试探法，分析效率低，代价高
  • 确定的自上而下分析法（递归下降的分析法）：要求描述语言的文法无左递归和无回溯即LL（1）文法
• 自下而上的分析方法

一个上下文无关文法G是LL（1）文法，当且仅当对G中每个非终结符A的任何两个不同的规则A->a|b满足__SELECT(A->a)与SELECT(A->b) = 空__且__无左递归__

消除左递归：

• 直接左递归：
  
• 间接左递归：从后往前代入得到左递归式，然后用上式消除，消除多余规则。

构造预测分析表：

1. 计算FIRST集和FOLLOW集
2. 对文法每个规则A->a，若a属于FIRST(a)，则M[A,a]=A->a
3. 若ε属于FIRST(a)，对任何b属于FOLLOW(A),则M[A,a] = A->a
4. 其他无定义标为error

文法的几个集合：

• FIRST集：第一个终结符
• FOLLOW集：
  • 将$将入到文法的开始符号S的FOLLOW（S）集中
  • 若A->aBβ是一条规则，则把FIRST(β)中非ε元素加到FOLLOW(B)中
  • 若A->aB或A->aBβ是规则且β可能为空，则吧FOLLOW(A)加到FOLLOW(B)中
  • 反复使用以上规则

算符文法：

• 算符文法中任何句型都不含两个相邻的非终结符
• 若Ab或bA出现在算符文法的句型e中，则e中任何含b的短语必含A

算符优先文法：

• 一个不含ε规则的算符文法G，如果任意两个终结符对(a,b)在三种关系中只有一种成立。

Firstvt集和Lastvt集的构造：

最左素短语：有终结符的短语且自身不包含素短语。

算符优先关系：

算符优先分析法的局限性：跳过了所有产生式右部只有单个非终结符的规约，可能把不是句子的输入出误认为文法句子。

语法错误恢复策略：

• 紧急方式恢复策略：发现错误抛弃输入符号直到结束。
• 短语级恢复策略：发现错误，局部纠正，缺点不能处理错误实际出现在发现点之前的情况。
• 出错产生式策略：扩充语言文法，将错误当作语法特定结构处理。
• 全局纠正策略：最小代价将错误符号串变为正确符号串。

附上各种语法的思维导图：