递归下降解析算法

一种实际中编译器用来构建抽象语法树的算法

递归下降算法的过程

首要规则：根据推导式一个一个尝试，一旦语法树的左下角得到终结符就与输入的最左侧字符对比，如有不同，回溯重新尝试，如果相同，继续推到验证下一个字符

1. 第一次尝试，错误

   ​

   ‍

2. 第二次尝试，错误

   ​​

   ‍

3. 第三次尝试，匹配括号，正确

   ​​

   ‍

4. 推导成功

   ​​

   ‍

递归下降算法的简易实现

本部分的tok​指的是token​，即词法分析后的类型标记，如：INT, OPEN, CLOSE, PLUS, TIMES​ (TIMES​表示乘法)

1. 虚构三大函数term()​, Sn()​, S()​

   • ​term()​判断指针所指内容是否匹配tok​无论是否，都会指针+1

   • ​Sn()​判断是否符合推断式n​

   • ​S()​判断是否符合所有推断式

   ​​

   ‍

2. 实现

   ​​

   ​​

   ‍

3. 局限性

   以此图为例，当我们尝试匹配INT TIMES INT​的时候，程序却只匹配了第一个INT​就结束运行了，这种算法缺乏回溯尝试的机制，任意部分匹配就会结束

   ​​

   ‍

左递归问题

如下语法会导致编译器陷入对S()​的无限递归调用

​​

根本原因：这类语法从右向左产生语句，但是递归下降算法是从左向右匹配的

解决方案：

将以上 语法重写为等价的左推导语法

​​

重写规则：

​​

总之，不能让能推出该推导式的非终结符出现在推导式的最左边

‍