保健哥的编译原理学习笔记

编译器是一个程序，他的核心功能是把源代码翻译成目标代码

编译器结构:

语法分析检查是否合法 ，然后在内存当中建立一个AST抽象语法树(对程序语法的一个抽象表示),对语法树的合法性做处理(一个变量使用之前是否被声明),  

PS：在ANTLR4中(我的理解是一个个的上下文无关文法->lexer,   那个句子就对应着parser(由一个个上下文无关文法组合而成的句子),  parser会根据输入的charstream来匹配一个个的文法,从而将那些我们需要的属性值抽取出来，轻而易举的完成正则表达式难以完成的功能。从而我们输入的每条SQL语句会通过visitor模式来访问经过语法分析后形成的AST抽象语法树，为什么不用listener模式是因为listener模式的话虽然是可以自动调用，但是这个接口是没有返回值的，如果需要值的存储我们需要定义一个可变变脸，而visitor模式是可以返回值的， 更加适合实际开发需求)

以上2个图其实就是对词法进行解析.

词法分析器主要通过手工编码和生成器实现(一个比较麻烦，但是性能效率比较高，第二个的话方便快速，但是比较难控制细节),

手工构造的话主要要理解转移图.

语法分析器的话主要是对输入的记号流以及所使用的编程语言的语法规则进行处理，然后生成一个抽象语法树.(平常ide开发时报错的依据原理就是这里);

再然后就是了解上下文无关文法，

显然看一眼就明白了什么叫上下文无关文法.

再需要了解的一个知识点就是分析树和二义性文法

显然看一眼也明白了分析树和二义性文法的意义.

匹配同一个句子也会产生两颗不同的分析树，分析树的含义要从树的后续遍历来查看.

给定文法G,如果存在句子S，使得产生两颗不同的分析树，那么G就是二义性文法.(会导致程序运行结果不唯一)

语法分析器面临的一个问题就是给定文法G和句子S，回答S是否能从G推导出来

第一个实现算法是自顶向下分析的算法思想，从G的开始符号出发，随意推导某个句子t,比较t和s,也就是通过暴力遍历回溯的方法来进行，他对应于分析树自顶向下的构造顺序,

第二个算法是递归下降分析算法

他把一个句子能否推导成功的运算进行分治求解(N V N 分别能否推导出 g d w)

 

LL(1)分析算法:

注意是从右向左压栈,

显然，看一眼也就明白了first集是什么含义.

在这个图就了解了FIRST集的不动点算法的迭代过程.(核心思想是"不动")

这里的话就是说FIRST集的通用特性推导.

总结一下： LL1算法的流程的话 首先我们要根据文法以及句子 然后使用FIRST集的不动点算法推导出FIRST集，推出FIRST集以后，再根据这个FIRST集和给出的文法来构造LL1分析表(这个过程比较难记 在保健哥LL1算法第一讲的第4个子视频中讲解),有了LL1分析表以后我们才能对输入的字符序列进行匹配.

 

显然，下图一眼就看明白了什么叫不动点冲突现象

看完了LL1冲突后 再了解下LL1分析表构造需要考虑的空串情况

后面就是冲突处理了， 主要是2个办法 消除左递归->变成右递归，  还有就是进行提公因子 。 在LL1分析第二讲的第一个子视频中记录.

补充一点，我们需要知道一般情况下LL1分析表的构造所需要的条件如下图(这也就是为什么需要求出NULLABLE和FOLLOW集的原因)

 

以上LL1算法就是ANTLR4的底层算法实现

接下来就是ANTLR4了， 在实际应用中，我们可以直接查找SparkSQL中的Catalyst优化器的源码，就有ANTLR4使用的例子，直接C+V即可, 具体插件安装步骤和文法撰写rule可自行google.

 

https://theendian.com/blog/antlr-4-lexer-parser-and-listener-with-example-grammar/#Lexer

贴出ANTLR参考链接