Parsing Algorithms

课程大纲

解析或句法分析是设计和实现编译器的首要阶段之一。精心设计的编程语言语法是用户偏爱并准确选择您的语言的一大动力。

———————————————————-

经典编译器学校和书籍中的“解析器理论”的问题在于，该理论通常被认为“太高级”，直接从计算理论和形式语法中进入复杂的形式描述。因此，学生可能会对已经在解析阶段构建编译器失去兴趣。

描述解析器时经常看到的相反问题是仅描述手动（通常是递归下降）解析的肤浅方法，这使学生在理解自动解析器背后的实际技术时遇到问题。

———————————————————-

我相信对解析理论的深入研究应该与实践方法相结合，这种方法并行进行，并允许在实践中看到所有学到的理论材料。

在解析基础（又名解析算法）课程中，我们深入探讨了解析理论的不同方面，详细描述了LL和LR解析器。然而，同时为了使学习过程和理解变得轻松有趣，我们从头开始并行构建一个用于完整编程语言的自动解析器，类似于 JavaScript 或 Python。

学完这门课后，您不仅可以使用解析器生成器为编程语言构建解析器，而且还将了解解析器生成器本身是如何工作的。

为一种编程语言实现解析器也将使您对其他编程语言的实际使用更加专业。

这门课是为谁准备的？

本课程适用于任何好奇的工程师，他们希望获得构建复杂系统的技能（为编程语言构建解析器是一项非常高级的工程任务！），并获得构建此类系统的可转移知识。

如果您对编译器、解释器和源代码转换工具特别感兴趣，那么这门课也适合您。

这个类的唯一先决条件是基本的数据结构和算法：树、列表、遍历。

什么用于实施？

由于我们构建的语言在语义上与 JavaScript 或 Python（当今最流行的两种编程语言）非常相似，因此我们专门使用 JavaScript——其优雅的多范式结构结合了函数式编程、基于类和基于原型的 OOP，非常适合那。

许多工程师都熟悉 JavaScript，因此立即开始编码应该更容易。为了生成自动解析器，我们使用语法工具，它是一个与语言无关的解析器生成器，支持 Python、Ruby、C#、PHP、Java、Rust 等插件。也就是说，这个解析器的实现可以很容易地转移到任何您选择和品味的其他语言。

注意：我们希望我们的学生自己真正遵循、理解和实现解析器的每个细节，而不是仅仅从最终解决方案中复制粘贴。该语言的完整源代码可在视频讲座中获得，展示和指导如何构建特定模块。

这门课有什么特别的？

这些讲座的主要特点是：

• 简明扼要。每个讲座都是自给自足的，简洁的，并描述与主题直接相关的信息，而不是分散在不相关的材料或谈话上。
• 动画演示与实时编辑笔记相结合。这使得对主题的理解更容易，并显示对象结构是如何（以及何时）连接的。静态幻灯片根本不适用于复杂的内容。
• 带作业的端到端实时编码会话。完整的源代码，从头开始，一直到最后都在课程的视频讲座中呈现

课程内容是什么？

课程分为四个部分，共22节课，每节课设多个子课题。下面是目录和课程表。

第 1 部分：上下文无关文法和语言
在这一部分中，我们将描述不同的解析管道，讨论形式文法、派生、什么是模棱两可和无野心的文法，并开始构建我们的编程语言。

第 2 部分：自顶向下 LL 解析
在这一部分中，我们将详细讨论自顶向下解析，描述手动递归和回溯解析器，并深入研究 LL(1) 解析算法。

第 3 部分：自底向上 LR 解析
在这一部分中，我们将描述自底向上解析器和 LR 解析算法。与此同时，我们继续构建我们的编程语言，分析减少班次冲突并修复它们。

第 4 部分：练习和最终解析器
本课程的最后一部分是完全实用的，我们将完成 Letter 编程语言、构建变量、函数、循环、控制结构、面向对象编程和最终解析器。