Dive in compilers

本项目的主要目的是从零开始实现一个小型的编译器，并尽可能将其中所涉及到的重要内容可视化.

下一步要支持的主要功能是实现语法分析流程可视化，从而使自底而上的语法分析过程更加直观

《编译原理》里的语法分析这一章究竟在讲什么？

因为LALR语法分析表可以在原来LR0项集的基础上生成LR1项集，这样一来就能同时达到减少项集的数量并且能够识别更多的文法 所以几乎所有的语法分析器都使用了LALR来构造语法分析表.

但是不幸的是在《编译原理》这本书中所举的例子太过于抽象，很难理解

CFLex

CFlex实际上是一个正则表达式解析器。目前能够支持以下的正则表达式特性：

• +

• *

• ?

• [A-Za-z]

• \s 空白符

• \d数字

• ^ 这个符号只能在[]中使用

在这里值得一提的是：根据我通过实践得到的理解，通过一个正则表达式生成一张状态图需要经过两个阶段，第一个阶段是预处理阶段，第二个阶段才是状态机生成阶段。

处理**+ * ？**这三个语法特性是生成状态机的关键步骤，其他的语法特性都是发生在预处理过程。

预处理的含义是就是将字符 \d转换成[123456789],即：展开一个特殊字符

• 我突然发现在实际实现的过程中不能将[]中的东西当成一个整体来实现，必须要把括号里的东西拆开，这样做的原因是为了避免二义性。
  • 对于正则表达式**a*[ab]**这样式子如果在预处理的时候

生成自动机的算法根据《编译原理》第二版第110页中提到的算法来实现。这个算法实际上是先构建了一个自底而上语法分析表，一边向上规约一边建立数据结构，非常类似于“小型编译器”的实现。

CFlex

CBison示例

CBsion是我基于《编译原理》开发的语法分析器生成器。 CBsion的最初想法是为了模仿Yacc架构。与Yacc不同的是，CBison的重点并不侧重于构建一个高可用的语法分析器生成器，而是将主要的工作集中在原理的可视化上。

CBison希望能够做到通过作图的方式理解复杂的编译原理。

左结合、右结合与优先级的真正含义

这三个词实际上决定了当语法分析器究竟是选择规约动作还是选择移入动作。

这里举例说明，

左结合与右结合的区别

假设语法分析器出于以下这种状态

前缀	栈	输入
E+E	X1,X2,X3	+E

那么对于左结合与右结合会发生以下的不同情况

左结合	右结合
先规约，再移入	先移入，再规约

优先级的意义

无论是左结合还是右结合都要先进行优先级高的运算

• 目前我还是认为优先级的作用更大，毕竟这个二义性文法主要是来解决究竟是选择规约还是选择移入的问题

假设语法分析器出于以下这种状态

前缀	栈	输入
E+E	X1,X2,X3	*E

那么对于左结合与右结合会发生以下的不同情况

*的优先级比+低	*的优先级比+高
先规约，再移入	先移入，再规约

这个项目只能支持

• 处理优先级需要处理
• 处理左结合与右结合问题需要考虑goto表与规约的去留
  • 如果是左结合，则需要保留规约项去除goto项
  • 如果是右结合，则需要保留goto项去除规约项

这里用编译原理书中第178页的内容来举一个例子

• 在没有处理优先级与结合性之前
• 解决优先级与二义性问题之后

IR中间表示

本项目使用

构建Dom树

DFS与塔杨算法

理解塔杨算法的关键是必须要弄清楚

• Forward Edge
• Backward Edge
• Cross Edge
• Tree Edge

的性质与区别

开发有感

• 使用json作为开发文件一开始还能感觉到简洁，但是内容一多就发现其臃肿不堪，可读性瞬间变差。果断换成yaml开发。