关于javascript:语言解析之回溯法和记忆法

本篇文章想要聊聊语法解析中的回溯法和记忆法，看本篇文章须要理解以下概念：

1、编译中的递归降落识别器
2、词法剖析与语法分析
3、bnf
4、LL(1) 与 LL(k)

语法规定越简单，就越须要灵便地向前看 k 个字符，回溯法与 LL(k)相比，相当于任意多的向前看符号。能满足更多的场景和需要，但回溯法有一个最大的问题是性能绝对较差，所谓的记忆法就是在回溯法的根底上，对于曾经计算过的后果进行缓存，以升高回溯法的工夫复杂度。

首先咱们看下一个根本的回溯法的代码构造，以便对于回溯法进行理解

function parse(){if(speculate1()){ // 尝试匹配推断 1
        rule1()     // 推断胜利之后，就执行 rule1} else if(speculate2()){ // 尝试匹配推断 2
        rule2()} else if(speculate3()){ // 尝试匹配推断 3
        rule3()} else {throw new RecognitionError()
    }
}

function speculate1(){
    let success = true
    mark()      // 标记以后输出的地位
    try{rule1()  // 尝试规定 1
    } catch(e){success = false}
    release()   // 放回以后输出的地位
    return success
}

能够看到回溯法相当弱小，能够依据理论规定动静地任意向前看，但执行效率会低很多。

从下面的代码能够看出，即便是最顺利的状况下，每条规定的推演也会执行两次（rule1 函数执行的两次）。

而在上面代码所示的 bnf 中，推演失败，在以后 token 的地位从新推演，很有可能使子规定执行很屡次。

stat: list EOF
    | list '=' list

记忆法能够防止同样的输出，同样的规定，进行第二次的计算。

记忆法的外围是每条规定都有一个记忆映射表，状态分为三种状况 unkonwn,failed,succeeded。

当没有解析到的时候，默认返回 unknown，应用正数标识 failed，应用一个负数标识 succeded，该负数记录了解析胜利的下一个词法单元下标。所以每条规定解析过一次之后，有起始的词法单元下标，就能找到规定完结的词法单元下标，就不必做反复的计算。

记忆法的代码框架如下：

function rule1(){
    let failed = false
    let startTokenIndex = getIndex()
    if(isSpeculating() && alreadyParsedRule(ruleMemo)) return
    try{_rule1()
    } catch(e){
        failed = true
        throw e
    } finally{
        // 无论推演胜利还是失败，都对后果进行记录
        if(isSpeculating()){memoize(ruleMemo, startTokenIndex, failed)
        }
    }
}

这里要留神 isSpeculating 函数代表是否是推演阶段，推演阶段时，代码不能执行一些有副作用的操作，只有推演通过之后，才会执行一些有副作用的操作。

当初咱们来实现 alreadyParsedRule：

function alreadyParsedRule(memo){const startTokenIndex = getIndex()
    if(!memo[startTokenIndex]){return false}
    if(memo[startTokenIndex] < 0){thorw new RecognitionError()
    }
    const endTokenIndex = memo[startTokenIndex]
    // 跳过去，就像曾经解析过这个规定一样
    advance(endTokenIndex)
    return true
}

alreadyParsedRule 函数，就是从 memo 中取缓存的值，如果没有值就返回 false，以便 rule1 函数中持续进行匹配，如果匹配失败，就抛出一个异样。如果匹配胜利，就取得对应词法单元的 index, 将指针前移后，返回 true。

如果不应用记忆法，回溯法的解析速度就会很慢，通过记忆法，只须要大量的内存，就能将整个解析过程的复杂度升高到线性程度。