js解析器

解释解释，什么是他妈的编译原理

编译原理

黄四郎：三天之后，一定给县长讲明白编译原理
张麻子：汤师爷，你给翻译翻译，什么叫编译原理？翻译翻译，什么叫编译原理？
汤师爷：这还用翻译，都说了。
张麻子：我让你翻译给我听，什么叫编译原理？
汤师爷：不用翻译，这就是编译原理啊。
黄四郎：难道你听不懂什么叫编译原理？
张麻子：我就想让你翻译翻译，什么叫编译原理！
汤师爷：编译原理嘛
张麻子：翻译出来给我听，什么他妈的叫编译原理！什么他妈的叫他妈的编译原理！
汤师爷：什么他妈的叫编译原理啊？（对黄四郎）
黄四郎：编译原理就是三天之后，我写串js脚本，扔进解析器里，词法分析、语法分析再执行，明白了吗？
汤师爷：这就是编译原理啊
张麻子：翻译翻译 翻译翻译！
汤师爷：编译原理就是三天之后，他写串js脚本，扔进解析器里，词法分析、语法分析再执行，！
张麻子：哈，大哥这他妈的编译原理啊，小弟我愿意等你三天
黄四郎：好

源代码分析

源代码分析三个阶段：

  • 词法（线性）分析，将代码从左到右转化为多个 token
  • 层次分析，token 在层次划分中有多个 嵌套组，嵌套组 整体有自己的含义
  • 语义分析，进行某些检查确保各个部分是有意义的组合在一起的。

详细：

词法分析 -> 语法分析 -> 语义分析 -> 中间代码生成 -> 代码优化器 -> 代码生成器

上下文无关文法

包含四个部分：

  • 一个记号集合，如 if else
  • 一个非记号集合
  • 一个产生式集合，分为左部和右部，左部是 非记号集合，右部是记号或非记号集合，由箭头相连接
  • 一个开始符号，指定的非记号集合

stmt 可以为（产生式） …… stmt -> if( expr ) stmt else stmt

分析树

分析树描绘了如何从文法的开始符号开始推导出它的语言的一个语句。
比如产生式 A -> XYZ
可以表示为：

1
2
3
   ----X  
A -----Y
   ----Z

分析树具有以下特性

  • 树根标记为开始符号
  • 每个叶节点由记号或空串组成
  • 每个内节点由非终止符标记

二义性

一个产生式对应了多个分析树，就产生了二义性。

操作符的优先级

从上到下优先级递增，比如：
左结合: + -
左结合: * /

深度遍历

产生分析树之后，通过深度遍历。

词法分析

记号：关键字、操作符、标识符、常量、文字串、标点符号 (id)

词素：记号的真实字符 (PI)

模式：描述记号的规则 (3.1415926……)

正则表达式

是描述模式的方式，每个模式匹配一个字符串集

字符串长度 S

比如 banana

S 的前缀：ban (S = 3)
S 的后缀：ana (S=3)
S 的子字符串：去掉一个前缀和后缀后，中间的字符串
S 的真前缀（后缀/子字符串）：满足以上条件，但不等于 S的
S 的子序列：删除若干个字符后的字符串，可以不相邻

语言

是给定字母表上任意一个字符串集合

状态转换图

描述语法分析器为得到下一记号而调用词法分析器时，词法分析器要做的动作。

圆圈表示状态，箭头表示边，

实现流程

RE -> NFA -> DFA -> 词法分析代码

汤姆森算法

词法分析

汤师爷： 词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用lex等工具自动生成。

黄四郎：说人话！

从 Lex 说起

Lex是 LEXical compiler的缩写，是Unix环境下非常著名的工具,主要功能是生成一个词法分析器(scanner)的C源码，描述规则采用正则表达式(regular expression)。

Lex in Javascript

jison(鸡森？) 库 

# npm install jison -g
# cd jison/example
# jison calculator.jison

在当前目录生成了 calculator.js 文件，这个文件是根据 calculator.jison 生成的
https://github.com/zaach/jison
看了看jison文件，根本不是人看的，

https://www.cnblogs.com/tugenhua0707/p/7759414.html
https://www.cnblogs.com/tugenhua0707/p/7759414.html
https://segmentfault.com/a/1190000017241258