看懂编译原理：词法/语法/语义分析阶段 原理

词法分析阶段：使用状态机

词法分析器的目的是识别高级语言中编写的代码转换为token，也就是识别高级语言中的每个单词token

每个token携带的额外信息包括：该单词的token类型，值和位置

因此编写词法分析器也就是编写如何拆解高级语言把他们变成一个个单词token， 用于之后语法分析器解析这些token组成的结构生成ast。

注解处理器&Transform区别

注解处理器对生成的ast进行操作，生成新的token和token结构。生成之后：

javac编译器会检测ast是否变动 从而 重新对 注解处理器修改的东西也就是有改动的ast执行词法语法语义分析

直到所有注解处理器都完成 最后转换ast生成class字节码文件。

而transform是对class操作的，javac是生成class的，transform是对class操作也就是直接对最终产物操作。

javac的中间处理过程词法语法语义这些都是为了最终生成class，而transform是直接生成class。

两者区别在于使用javac可以用高级语言便携代码（这段关于注解处理器去能做的事情后来和petterp聊了聊发现有新的体会，可以去飞书妙计里面apt和transform peter标题的妙计查看）而用transform只能操作class字节码

为什么注解处理器不直接操作java文件呢？

注解处理器一般都是生成新的java文件，不会直接操作java文件，为什么呢？

因为现在的asm都是字节码增强框架，而注解处理器这个阶段还是java文件所以不能用操作class的框架处理java文件（不过也有通过注解生成代码的例子比如butterknife，后面可以看下是怎么做到在原有java文件生成代码的）

词法分析原理：DFA/NFA 状态机

词法分析fsa 分为确定的有限状态机和非确定有限状态机

• DFA确定有限状态
• NFA非确定有限状态（非确定可以理解为二义性输入：一个字符有多个状态符合）

词法分析过程中dfa可以有一个确定的状态转换，而nfa则有多个可能的状态进行转换（NFA一个状态匹配失败会尝试其他可能得状态）

NFA/DFA的优缺点：

NFA 状态数量少 但是 遍历过程可能会出现很多次回溯（因为匹配失败要重新进行匹配）

DFA 虽然不会出现回溯，但是所需的状态就会很多会浪费存储空间效率

因此两者一个是空间换时间，一个是时间换空间。

现在来说空间已经足够了，所以说DFA 可能效率更高

NFA转换-》DFA

nfa是可以转换为dfa的，就是分析所有路径然后生成新的状态 达到和nfa表达式一样的效果，状态可能会翻倍因此占用内存会多各有利弊

语法分析阶段：使用上下文无关语法-文法规则

词法分析用的是正则表达式（也就是状态机），而语法分析用的是文法规则进行匹配

使用文法规则不是正则，是因为单纯的正则已经无法表示复杂的算数表达式的语法ast结构。

词法分析的正则和语法分析的文法规则差异

和正则文法最大的区别是可以递归调用。

比如 加法乘法嵌套这种复杂语法就需要递归解析匹配 正则就无法做到；正则只可以用于简单的结构匹配，比如对于赋值语句可以因为其结构简单

语法分析原理

peek预读token当符合语法规则的文法结构时，生成子节点；如果子节点也符合文法规则时继续生成子节点的子节点。

如2+3识别到+的文法规则先生成+的节点，2和3作为子节点添加到+父节点下面

示例：+和x的文法匹配规则

复杂的文法结构比如算术表达式，由于存在优先级和递归解析的需求因此这种表达式的文法会复杂一些：

1. 加法（+，plus）的文法规则：add包含单纯的两个数字相加也包含加法和乘法共存时的情况（对于第一种add的文法规则就是 a plus b，第二种则是 add + mutiliable）
2. 乘法（x，mutiliable）的文法规则也是如此（可以仅有一个相乘的数字也可以是多个数字相乘。表示是 mutil int/mutil mutil

解析2+3×5语法的文法规则

peek预读token，匹配到 +这个token 符合加法文法 生成add 的ast节点，然后在对应后面的token结构生成对应的ast子节点，此时+文法结构匹配的节点是 add + mutiliable，mutil由于和add在第二个算数运算里所以这两个节点同级（3X5），所以继续解析mutil两个数字匹配的是最简单的文法结构生成两个子节点，最后生成的ast就是：

+

2 ×

3 5

ast从下到上运行就能得出正确结构（使用上下文文法结构可以表达更复杂的文法规则，比如递归调用。无上下文因为预读peek的token只能够用于生成ast，没有额外的token作为上下文进行优化ast，优化ast和上下文token信息读取是在语义阶段进行的）

此处语法分析用的是无上下文的文法结构 只是为了生成正确的AST结构。

但是这种只做到了正确，无法做到优化效率；优化效率意味着要读取更多的token信息（也就是拥有更多的上下文），在此处没有做优化 一是因为ast还未全部生成，二是因为更多的上下文token信息也意味着耗时，耗时长且优化效果很差

因此将ast的优化放置在了分析阶段的最后一个阶段：语义分析

语法分析阶段：左递归问题

左递归问题定义

左递归问题：匹配加法文法时 由于第二个文法（add+mutil）的第一个条件也是加法文法，因此会再次进行匹配；再次进入第二个文法的判断，第一个条件又是add，再次进行匹配。。。。如此一直往复循环

匹配是读取一定数量的token去匹配各种规则而不是单独一个token就直接去匹配

左递归问题 分析& 解决方案

解决：原因是第二条文法规则里面第一个条件和主文法第一个条件 重复了就会递归调用，因此陷入了死循环。

破解就是在匹配文法时加上前置条件而不是一开始就是递归。将递归滞后加入前置判断就可以解决。（比如第二条文法结构匹配时只有第一个条件满足才会递归而不是无条件递归）

• 根源就是无条件递归，解决加入条件再递归
• 另一种解决方案递归次数达到一定条件主动跳出最外层节点，相当于主动式的跳出重新匹配（匹配路径的优化和记录又是一个细分话题）

文法规则 类似 编码前的各种架构流程图 代表的是一种 方案整体上的结构，真正落实到coding和算法阶段 由于程序和模块中出现的各种问题结构会有适当调整是正常的（文法只表明了某个表达式的文法组成规则，并不说明就是最终的实现，最终实现还要解决各种问题：如左递归在第一个条件无限循环的情况就会出现）

由于加入了判断条件因此文法匹配规则发生变化，*对于其他的规则匹配就会造成影响（ *比如ast顺序错乱等问题），因此也需要调整其他的文法规则顺序。

ps：左递归的问题同样如果采用右边先遍历也会出现右递归问题。深度上会出现递归，横向上的节点生成则是拍平后的递归

左递归问题总结

左递归问题：匹配加法文法时由于子规则第二个条件也是加法文法因此只要第一个文法条件不满足，匹配第二条文法节点时又会递归判断是否是加法文法，第二次也如次，由于是第一个条件左边的文法节点所以也叫左递归。

解决：原因是第二条文法规则里面第一个条件和主文法重复第一个条件就是递归调用，因此陷入了死循环。破解就是在匹配文法时加上前置条件而不是一开始就是递归。将递归滞后加入前置判断就可以解决。（比如第二条文法结构匹配时）

词法规则配置

• -》可替换的父节点文法结构
• | 只要有一个规则满足就认定符合文法结构
• 文法结构也可嵌套带入到文法结构中处理复杂的算术表达式（ps add文法规则： add-》mul ！ num+num）

mul匹配不到时退回预读取的token重新匹配第二条规则直到满足。 mul可能也会用到表示num的节点因此num会再次提取成一个单独的父节点文法。

匹配读取token的数量范围：一个一个token读，满足某个文法节点就生成节点，不满足就退回看是否满足该父文法节点的其他子文法规Í

eg：变量声明 表达式的文法规则

如新增赋值表达式，声明变量（初始化变量）表达式，表达式可中可操作变量的表达式。

声明变量表达式的第一种文法结构：数据类型token 标识符token（也就是变量名） 等号token 运算表达式token（需要嵌套解析该token） 分号token

赋值表达式的第二种文法结构：将运算表达式token替换为对应数值类型的token

token匹配实现

匹配是通过预读取token实现的，每次只预读取一个token并判断是否符合文法结构，如果不符合且还有其他的文法结构就需要吐出预读取的token匹配其他文法规则（也叫回溯）

注意：文法结构只表达对应的构成规则，对于如何用算法实现文法结构规则是算法的事情（如出现左递归 说明左文法节点结构中第一个条件就是再次判断是否符合该文法父节点，如此循环。）

吐出预读取的token如何做到？

在开始匹配文法结构时，记录此时读取的token下标，当匹配失败时，恢复到之前保存的下标，继续从那个点匹配其他文法结构直到满足某个规则

也就是尝试一个规则不成功之后恢复原样继续尝试匹配其他规则的过程就叫回溯

语义分析阶段：使用上下文有关语法

语义分析：实现特定的语言特性

语言特性通过在语义分析阶段对特定符号处理实现， 典型的特性比如访问非法变量，方法等提前至编译期抛出。

• 符号就是ast中的节点，单独一个节点无法提供其他信息 因此 需要解析其他的节点获取相应的信息做处理。
• 语法分析阶段使用上下文无关语法产生ast；语义分析阶段通过生成的ast节点，使用上下文有关语法对其进行转换字节码（上下文有关意味着要预读取更多的节点并解析这些节点）。
• 最经典的特性就是作用域的范围还有对变量的赋值操作检测类型是否符合
• 还有最重要的就是对自定义类型消解，当声明自定义类型变量的时候，并不知道这个这个自定义类型有哪些成员，成员引用和方法调用是否正常引用，就需要去读取这个类型相关的节点进行解析和验证

语义分析：实现js语法中的闭包特性

闭包定义：内层函数作为返回值返回后依然能够使用外层函数中的值

语义分析阶段对这个特性做的处理：

扫描到内层函数要返回作为赋值语句使用时，创建一个functionobject对象包含外部变量和内层变量

为什么要做保存？默认情况普通函数退出代表着函数中的变量也会随之销毁，因此如果函数可以赋值或者传递那么由于函数的变量会销毁所以会出现问题，因此识别到函数返回赋值时要创建一个特殊的闭包作用域，这个作用域保存了外部函数和内层函数的变量

总之就是闭包会封装使用的变量到一个独立的结构中， 以便可以使用

这样外部使用赋值后的函数时由于内层函数有functionobject，因此可以访问到外部变量和内部变量

语义分析：实现多态

语义分析阶段对多态特性的支持，本质上就是在编译的时候在对应的地方带上type信息

ast的遍历通过上下文有关文法可以进行很多骚操作，js的闭包封装，java弱类型多态，go的is类型判定........，不同语言对语义的处理成为语言的特色。

程序使用多态（animal是父类作为声明类型，cat和dog是子类作为实际类型使用： Animal animal＝ new cat（）），

都知道java的多态是通过运行时动态绑定实现的。那么编译器如何实现的呢？

多态在编译期间如何实现？

在编译期间可以通过类型推导出animal变量具体的实际类型cat但是并不能让animal变量类型为cat，因为如果指定了animal变量为cat类型那么之后就不能够让animal变量为dog类型

因为java是强类型语言，类型一旦定义，后面就不能进行更改，那么多态运行绑定的功能就无法实现。

强弱类型的边界

因此这里虽然java是强类型语言，但是在对多态这种情况会放宽对类型的限制。

看吧这就是最开始说的强类型语言有弱类型，弱类型语言里面也有强类型。

如何实现多态的动态绑定？

在对ast做处理的时候，会对变量生成一个type属性代表着真实的数据类型，运行时通过找到这个变量的真实属性进行处理。

这种需要额外的信息保存运行时类型信息的技术有个术语是rtti，花费额外的空间来达到弱类型和强类型使用的平衡。

我正在参与2023腾讯技术创作特训营第四期有奖征文，快来和我瓜分大奖！