编译器(一)

[chunpu]

词法

从头正则匹配

token: [type, literal, value]

LR(1)

L: left, pop

R: reduce from right

1: 多看一个

LL(1)

从左边推导和从右边推导的优劣对比(待续)

要么LL(K)要么LR(1)

我们无法从终结符看是否可规约

LALR(1)

为什么是左右而不是上下呢?

LA1 = look ahead 1

语法对照表

难点, 为什么先等到乘法, 而不是直接规约加法

可以把语法数组中还需要的牌分出来, lookahead到可能匹配, 就移近之

举个例子, 比如数字接收-, +, *, /这些字符, 那我们移近数字的时候, 把允许继续移近的数组改为[-, +, *, /], 这样就轻松辨别是否该移近了

比如1 + 2 * 3, 我们在栈中已经存好[1, +, 2], 如果后面是*, 我们就贪婪的认为还有可能匹配到计算乘法的情况, 因此选择继续移近而不是规约1, +, 2

但你可能会问, 这样如果语法多起来, 会不会一直在移近, 一次都不规约啊, LR1的一个特性就是终结符, 终结符肯定表示终止啊, 如果我们lookahead1是一个分号; 那就必然终结了, 可以爽快的规约之

麻将听牌, 解析对照表(parse table)

冲突

• 满足多个规约(通过优先级化解)
• 可同时移近和规约(通过移近优先化解)

你既可以吃牌, 又可以摸牌, 自己形成顺子

LR1就是可以偷看一张牌的麻将

shift/reduce 移近优先, 这意味着贪婪匹配

AST语法树

前面就算我们从一个很长的字符串 -> 到一个一个记号(token) -> 再分析成一句一句话

但我们就真的知道怎么处理它了嘛? 这时候我们需要一棵树来最终表示这个很长的字符串(源代码). 还是拿1 + 2 * 3举例

  7
 ---
|   |
1 + 6
   ---
   | |
  2 * 3

表示成一颗树为啥就能看懂了? 首先我们看到, 树的叶子都是最基本的, 我们从词法匹配中获取到的token. 其次是这个数清晰的表达了匹配的顺序, 先算2 * 3, 再算1 + 6, 当然, 这顺序在编译原理中也有一个专业的叫法, 叫自底向上

自底向上

叶子到根, 根是我们唯一认识的东西, 1 + 2 * 3的根就是7, 这就是我们要的结果, 树就像一个金字塔, 只要你拼的整齐, 总是能拼成一个尖尖的点, 对于总是return的函数, 特别有用, 因为不管什么都是值, 我们永远可以返回一个值

那你要问了, 有些语法规约不是求值啊, 比如readfile('1.txt'), 这时候, 我们的函数还需要一个回调, 很容易我们可以看出这个是规约自变量, 左括号, 一个值, 右括号, 规约成一个函数表达式, 这时候, 我们可以直接触发函数表达式规约的回调函数, 具体怎么readfile我们并不管, 这就不属于文法的过程了

同时要注意, 回调函数需要一个返回值, 为了进行下一步规约, 它的返回值应该是一个值, 和其定义的规约内容成为一个新的token, 以供继续规约

可能要用到的东西, array reduce, goto label

如何实现

第一个函数lex, 词法部分

var tokenRule = {
  '{': '{',
  str: /str的正则/,
  ...
}
function lex(str, tokenRule) {
  // 参数1, 字符串
  // 参数2, token的规则
  // tokenRule格式直接就是一个hash
  // 返回值是一个数组[[type, value], [type, value]]
  return tokens
}

第二个函数parser, 语法部分

var grammarRule = {
  'exp': { // 表达式规则
    bnf: ['number', 'number + number', 'number * number', ...]
    cb: function() { // 规约后回调
    }
  }
}
function parser(tokens, grammarRule) {
  // 参数1, lex过来的tokens
  // 参数2, 语法规则
  // 返回一棵树
  return ast
}

bnf是这个意思, 不过我们其实可以把tokenRule和grammarRule都写成数组, 这有什么区别呢, 区别就是数组可以反映优先级, 可以处理/* "*/xxx "到底是先注释还是先字符串的问题, 这里我们选择数组, 并且认为先匹配到谁就是谁, 不管后面, 因此我们也只需要把优先的比如注释规则写在前面就行, 同样要注意的是之前一直念叨的乘法和加法的优先级, 它的grammarrule应该这样

var grammarRules = [
  // [name, bnf, cb]
  ['number1', ['number * number', 'number / number'], function],
  ['number2', ['number + number', 'number - number'], function],
  ['number', ['number1', 'number2']] // 无函数
]

本来画了个分析表的, 但后来都删了, 这种程度的匹配, 直接用indexOf就行了, 比如number, 我可以找到look ahead的匹配数组[*, /, +, -], 同样, 我们可以看出他们的所在的行, 可以完善一下这个lookahead数组

/* 获取如下字符串
number * number  number / number
number + number  number - number
number1  number2
*/

var grammarRules = [
  // [name, bnf, cb]
  ['number1', ['number * number', 'number / number']],
  ['number2', ['number + number', 'number - number']],
  ['number', ['number1', 'number2']] // 无函数
]
var bnf = grammarRules.map(function(rule) {
  return rule[1].join('  ')
})
var reg = /number ([^\s]+)/g
var lookahead = [], ret // [id, 优先级(越小越高)]
for (var i = 0; i < bnf.length; i++) {
  while (ret = reg.exec(bnf[i])) {
    lookahead.push([ret[1], i])
  }
}

如何规约

我一开始根本没想怎么规约, 想着就很简单, 不就是从后面开始匹配, 一样就规约嘛, 没想到现在看来非常复杂, 根本不是10行可以写完的

这样我们就认为优先规约乘除的

目前的结果在gist里, 由于我经常是把胡思乱想写在博客里, 估计就我自己知道在说什么, 唉..but it works