03 | 语法分析：两个基本功和两种算法思路
该思维导图由 AI 生成，仅供参考
上下文无关文法（Context-Free Grammar）
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
本文深入探讨了语法分析阶段的核心知识点，主要介绍了递归下降算法和LL算法。递归下降算法通过匹配语法规则来生成AST，但存在左递归和回溯的问题，作者提出了解决方案，如改写产生式和转化递归调用为循环。此外，文章还介绍了LR算法，它是一种自底向上的算法，通过移进和规约的方式逐步构建AST。LR算法相对于LL算法的优点在于能够处理左递归文法，但也存在不利于输出全面的编译错误信息的缺点。通过本文的阅读，读者可以清晰地了解语法分析阶段的基本功和算法思路，为进一步深入学习提供了清晰的学习路径和理解框架。
《编译原理实战课》，新⼈⾸单¥59
全部留言(13)
- 最新
- 精选
Charles置顶开始的地方提到算术表达式无法用正则表达式匹配，好像不对吧？ 我试了一下，[0-9]+((\+[0-9]+)*(\*[0-9]+)*)*就可以匹配。作者回复: 你的问题非常好，体现了锲而不舍钻研的精神！ 我把你的回答再整理一下。你的意思是： IntLiteral （（ '+' IntLiteral）* （ '*' IntLiteral）* ）* 或者更简化一下：IntLiteral (OP IntLiteral)*，其中OP代表任意的二元运算符。 改写成产生式： exp -> IntLiteral exp' exp' -> OP IntLiteral exp' | ε 到目前为止，这个产生式是线性的。 然而，如果我们再加一点要求，要支持括号，比如：2+（2*（3+5）），就有问题了。它的产生式是： exp -> pri exp' exp'-> OP pri exp' | ε pri -> IntLiteral | ( exp ) 上述一组产生式，就不是线性的了，就不能再改写成正则表达式。 你再分析一下，加括号和不加括号，到底有啥不同？你会看到，左括号和右括号的数量一定是一样的，并且是对称出现。这种表达，就是正则表达式做不到的。 更简单一点，n个0后面跟着n个1，比如01, 0011, 000111 ...，也是用正则表达式不能表示的。 如果你想更加严密的了解一下与文法有关的知识，可以看一下《计算理论引导》这本书的第一部分。 再一次肯定你的钻研精神，加油！
2020-06-0919- thomas1994赞，老师的实战课程比编译原理之美更加通俗易懂
作者回复: 谢谢肯定！ 说明老师也有进步:-)
2020-06-083 - Apsaras老师，递归下降算法、LL(1)算法、LR算法的相互之间是替代关系吗？还是LL(1)和LR都是递归下降的补充？
作者回复: 递归下降算法和LL算法都是自顶向下的。递归下降强调的是用“递归调用”和“层层下降”的方式来书写代码。所以LL算法可以用递归下降的方式编写（Java编译器），也可以用查表的方式编写（Python编译器），这两种方式你在后面的课程里都可以看到。 LR算法是完全不同的，是自底向上的算法。
2020-06-0522 
击水湘江参考资料可以再丰富些不？初次接触编译原理，感觉看完一头雾水😭作者回复: 好，我尽量多补充点链接！
2020-06-091
Gaollard老师您好 add : add '+' mul | mul; 这个怎么理解呢？推导依据是什么呢？我理解不了，困扰我好久了，望老师能够解答。作者回复: 我没有太get到你不清楚的点。我猜是你对这种语法书写方式不习惯吗？我换成等价的产生式的方式，你看是否会更容易理解一些？ add -> add + mul //add表达式可以由另一个add表达式、+号和一个乘法表达式构成。 add -> mul //mul表达式也是一个合格的add表达式 如果我没有回到你的问题点，你可以再描述得细致一点:-)
2021-05-09
易昊我的计算结果是： FIRST(block) = {'{'} FIRST(blockStmts) = {'{', ε} FIRST(stmt) = {Int, Long, IntLiteral, Id, '(', return, '{'} FIRST(varDecl) = {Int, Long} FIRST(returnStmt) = {return} FIRST(expStmt) = {IntLiteral, Id, '('} FOLLOW(block) = FOLLOW(stmt) = FOLLOW(varDecl) = FOLLOW(returnStmt) = FOLLOW(expStmt) = {'}', $, Int, Long, Intliteral, id, '(', return} FOLLOW(blockStmt) = {'}', $} PS:我是按照课程前面“stmt = varDecl | expStmt | returnStmt | block;”这个产生式推导的，课程后面不知道为何stmt变成三个产生式了。作者回复: 你再仔细检查一下，有些地方不对。 比如，blockStmts的First集合应该包含stmt的First集合中的元素。
2020-06-09
SIGHOR慢慢的恢复大学里学习这门课的感觉，需要再多看几遍。 而且我突然发现有点不太会学习了作者回复: 嗯，肯定要多看几遍。因为里面知识点还是挺密集的。
2020-06-05
Romber编写编译器时是选用自顶向下的算法好还是用自底向上的算法好?该如何选择? 有没有一些指导性方法论啊?2022-10-14归属地：上海
A君生成好的token序列可以采用递归下降算法来匹配生成ast树，递归下降算法是深度遍历算法，产生式一旦写得不严谨就容易出现持续左子树无限递归问题，如果换成终结符在左边，递归发生在右子树，虽然可以解决左递归问题，但计算顺序也会发生改变（深度右子树的节点先被访问），要解决这个问题，可以采用循环来代替递归。 递归下降算法的又一问题是不断回溯产生式会导致算力浪费，因此可以采用先预读下N字符来判断下一个执行产生式的LL算法，还有一种算法也是通过预读来选择产生式，但它是从底层的产生式向上匹配，是一种自底向上的遍历算法，LR。2022-04-29
ifelse
厉害了2022-01-07
