编译原理与技术（三）——语法分析（二）自顶向下-递归下降

一、语法分析的两种方法

自顶向下（Top-down）：

针对输入串，从文法的开始符号出发，尝试根据产生式规则推导（derive）出该输入串。

从根部开始构造语法树。

自底向上（Bottom-up）：

针对输入串，尝试根据产生式规则归约（reduce）到文法的开始符号。

从叶子开始构造语法树。

二、递归下降法

举个例子。

开始递归下降语法分析。

 

 

 

 

 

 

 

 

 

 

 

 

 

匹配到数字”3”后，程序从expr返回。

 

 

至此，递归下降分析结束。

三、递归下降法存在的问题及解决方法

（一）陷入无限左递归中

首先介绍什么是文法的递归。

若文法G存在推导：A ---> aAb，那么就称文法G是一个递归文法。

当文法G的唯一一个递归推导A ---> aAb中的a是空串时，就称文法G是一个左递归文法。同样可以定义右递归文法。

左递归又可分为直接左递归和间接左递归。

 

解决方法：消除直接左递归。

消除左递归的通用方法

上面的方法是消除直接左递归。

遇见了间接左递归时，要将文法先变换为直接左递归，再消除直接左递归。

 

（二）如何选择推导式

当遇见有左公因子的文法时。

 语法分析要选择一个进行推导，为了获取足够多的信息来做出正确的选择，我们尽可能延迟对该产生式的决策。而我们实现延迟决策的方法就是提取左公因子。

 典型的例子是if-else语句的文法。

（三）复杂的回溯

参考资料：

 [1]USTC 编译原理和技术 2023 (ustc-compiler-principles.github.io)