New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

san.parseExpr 源码学习 #7

Open
LeuisKen opened this Issue Jun 19, 2018 · 3 comments

Comments

Projects
None yet
4 participants
@LeuisKen
Owner

LeuisKen commented Jun 19, 2018

2018年10月11日更新:

截至3.6.11evalExpr支持了执行调用表达式(readCall)


2018年9月2日更新:

随着 San 的版本迭代,截至3.6.7parseExpr支持了新的特性:


方法说明

san.parseExprSan中主模块下的一个方法。用于将源字符串解析成表达式对象。该方法和san.evalExpr是一对,后者接收一个表达式对象和一个san.Data对象作为参数,用于对表达式进行求值。如下例:

/**
 * 解析表达式
 *
 * @param {string} source 源码
 * @return {Object} 表达式对象
 */
function parseExpr(source) {}

/**
 * 计算表达式的值
 *
 * @param {Object} expr 表达式对象
 * @param {Data} data 数据容器对象
 * @param {Component=} owner 所属组件环境,供 filter 使用
 * @return {*}
 */
function evalExpr(expr, data, owner) {}

san.evalExpr(san.parseExpr('1+1'), new san.Data());     // 2
san.evalExpr(san.parseExpr('1+num'), new san.Data({
    num: 3
}));        // 4

单独拿出parseExpr来分析,其根据源字符串生成表达式对象,从San的表达式对象文档中,可以看到San支持的表达式类型以及这些表达式对象的结构。我们在这里简单记录一下,parseExpr需要解析的表达式都有哪些:

  • TertiaryExpr:三元表达式
  • LogicalORExpr:逻辑或
  • LogicalANDExpr:逻辑与
  • EqualityExpr:判等
  • RelationalExpr:关系(大于、小于等)
  • AdditiveExpr:加减法
  • MultiplicativeExpr:乘除法、取余运算
  • UnaryExpr:一元表达式
  • ParenthesizedExpr:括号表达式

除了上述表示运算关系的表达式外,还有表示数据的表达式,如下:

  • String:字符串
  • Number:数组
  • Boolean:布尔值
  • ArrayLiteral:数组字面量
  • ObjectLiteral:对象字面量
  • Accessor:访问器表达式

由于Accessor存在意义,是为了在evalExpr阶段从Data对象中获取数据,所以这里我将Accessor归类为表示数据的表达式。

现在我们知道了所有的表达式类型,那么,parseExpr是如何从字符串中,解析出表达式对象的呢?

如何读取字符串

parseExpr方法定义在src/parser/parse-expr.js中。我们可以看到其依赖了一个Walker类,注释中的说明是字符串源码读取类。

Walker类包含以下内容:

属性:

  • this.source:保存要读取的源字符串
  • this.len:保存源字符串长度
  • this.index:保存当前对象读取字符的位置

方法:

  • currentCode方法:返回当前读取字符的 charCode
  • charCode方法:返回指定位置字符的 charCode
  • cut方法:根据指定起始和结束位置返回字符串片段
  • go方法:将this.index增加给定数值
  • nextCode方法:读取下一个字符并返回它的 charCode

goUntil 方法

/**
 * 向前读取字符,直到遇到指定字符再停止
 * 未指定字符时,当遇到第一个非空格、制表符的字符停止
 *
 * @param {number=} charCode 指定字符的code
 * @return {boolean} 当指定字符时,返回是否碰到指定的字符
 */
Walker.prototype.goUntil = function (charCode) {
    var code;
    while (this.index < this.len && (code = this.currentCode())) {
        switch (code) {
            // 空格 space
            case 32:
            // 制表符 tab
            case 9:
            // \r
            case 13:
            // \n
            case 10:
                this.index++;
                break;
            default:
                if (code === charCode) {
                    // 找到了
                    this.index++;
                    return 1;
                }
                // 没找到
                return;
        }
    }
};

match 方法

/**
 * 向前读取符合规则的字符片段,并返回规则匹配结果
 *
 * @param {RegExp} reg 字符片段的正则表达式
 * @param {boolean} isMatchStart 是否必须匹配当前位置
 * @return {Array?}
 */
Walker.prototype.match = function (reg, isMatchStart) {
    reg.lastIndex = this.index;

    var match = reg.exec(this.source);
    /**
     * 这里是源码的实现,简洁但是有点晦涩,后面我把逻辑运算符拆成了 if else,希望能好理解一些
    if (match && (!isMatchStart || this.index === match.index)) {
        this.index = reg.lastIndex;
        return match;
    }
    */
    if (match) {
        // 如果是必须匹配当前位置
        // 这个标记是 3.5.11 的时候加上的,changelog 表述为:
        // 【优化】- 在 dev 模式下,增加一些表达式解析错误的提示
        if (isMatchStart) {
            // 判断当前读取字符的 index,是否和匹配结果第一个字符的 index 相等
            if (this.index === match.index) {
                this.index = reg.lastIndex;
                return match;
            }
        }
        // 不必须匹配当前位置
        else {
            this.index = reg.lastIndex;
            return match;
        }
    }
};

如何处理运算符的优先级

在初看parseExpr实现的时候,这就是一个困扰我的难题。学习过程中,我看到San最先是将表达式丢给一个读取三元表达式的方法,这个方法里面去调用读取逻辑或表达式的方法,逻辑或里面调用逻辑与,逻辑与里面调用判等,判等里面调用关系⋯⋯看得我可以说是云里雾里。虽然大致能明白这是在处理运算优先级,但是我觉得肯定有一个更上层的指导思想来让San选择这一方案。

为了寻找这个“指导思想”,我转头去看了一段时间的编译原理,大致上理清了这部分思路。考虑到有些同学应该也和我一样没有系统地学习过这门课程,因此我在下面取《编译原理》中的例子来予以说明(下文内容包含了很多定义性的内容,且为了保证严谨,很多定义都是直接照搬书上的,所以如果你对这部分足够熟悉,跳过即可。)

上下文无关文法及其构成

假设我们现在要解析的expr是一个十以内的四则运算算式(编译原理将其视为一种语言),其包括加减乘除( +、-、*、/ )四则运算。我们可以使用一种叫做产生式的方式,来表示表达式的解析规则。有了产生式,我们可以将一个算式的解析规则表达成如下形式(这一解析过程被称为词法分析):

expr ---> digit         // 这里的 digit 指 0,1,2,3...9 这十个数字
        | expr + expr   // 竖线(|)表示或,这一行定义了加法
        | expr - expr   // 减法
        | expr * expr   // 乘法
        | expr / expr   // 除法
        | (expr)        // 加括号

这里介绍几个概念,这里的digit+ - * / ()等符号,被称为终结符号,表示语言中不可再分的基本符号;而像expr这样能够用于表示终结符号序列的变量,被称为非终结符号。

我们都知道,十以内的四则运算算式的解析是与上下文无关的。在编译原理中,将描述语言构造的层次化语法结构称为“文法”(grammar),我们的十以内的四则运算算式就是一个“上下文无关文法”(context-free grammar)。编译原理中定义了上下文无关文法由四个元素构成:

  • 终结符号集合
  • 非终结符号集合
  • 产生式集合
  • 一个指定的非终结符号作为开始符号(上面的expr)

语法分析树

语法分析树是一种图形表示,他展现了从文法的开始符号推导出相应语言中的终结符号串的过程。例如一个给定一个算式:9 - 5 + 2,可以表示成如下的语法分析树:

            expr
    expr      +     expr
expr  -  expr      digit
digit    digit       2
  9        5

二义性及其消除

单纯从 9 - 5 + 2 出发去画语法分析树,还能得到另一种结果,如下:

            expr
expr         -          expr
digit            expr     +     expr
  9             digit           digit
                  5               2

如果我们从下往上对语法分析树进行计算,前一棵树先计算 9 - 5 得 4,然后 4 + 2 得 6,但后一棵树的结果则是 5 + 2 得 7,9 - 7 得 2。这就是文法得二义性,其定义为:对于同一个给定的终结符号串,有两棵及以上的语法分析树。由于多棵树意味着多个含义,我们需要设计没有二义性的文法,或给二义性文法添加附加规则来对齐进行消除。

在本例中,我们采用设计文法的方式来消除二义性。由于四则运算中,加减位于一个优先级层次,乘除位于另一个,我们创建两个非终结符号exprterm分别对应这两个层次,并使用另一个非终结符号factor来生成表达式中的基本单元,可得到如下的产生式:

factor ---> digit | (expr)
// 考虑乘法和加法的左结合性
term ---> term * factor
        | term / factor
        | factor
expr ---> expr + term
        | expr - term
        | term

有了新的文法之后,我们再看 9 - 5 + 2,其仅能生成如下的唯一语法分析树:

                expr
        expr     +      term
   expr - term          factor
   term   factor        digit
 factor   digit           2
  digit     5
    9

parseExpr 的实现

现在我们回到San中的表达式,有了前面的基础,相信大家都已经清楚了parseExpr解析表达式源字符串方法的缘由。接下来,我们只要合理的定义出来“San中的表达式”这一语言的产生式,函数实现就水到渠成了。

表达式解析入口parseExpr

/**
 * 解析表达式
 *
 * @param {string} source 源码
 * @return {Object}
 */
function parseExpr(source) {
    if (typeof source === 'object' && source.type) {
        return source;
    }

    var expr = readTertiaryExpr(new Walker(source));
    expr.raw = source;
    return expr;
}

其对应的产生式就是:

Expr ---> TertiaryExpr

readTertiaryExpr

/**
 * 读取三元表达式
 *
 * @param {Walker} walker 源码读取对象
 * @return {Object}
 */
function readTertiaryExpr(walker) {
    var conditional = readLogicalORExpr(walker);
    walker.goUntil();

    if (walker.currentCode() === 63) { // ?
        walker.go(1);
        var yesExpr = readTertiaryExpr(walker);
        walker.goUntil();

        if (walker.currentCode() === 58) { // :
            walker.go(1);
            return {
                type: ExprType.TERTIARY,
                segs: [
                    conditional,
                    yesExpr,
                    readTertiaryExpr(walker)
                ]
            };
        }
    }

    return conditional;
}

可以看到,判断条件部分conditionalreadLogicalORExpr的结果。如果存在?:两个和三元表达式相关的终结符号,就返回一个三元表达式类型的表达式对象;否则直接返回conditional。可知产生式:

TertiaryExpr ---> LogicalORExpr ? TertiaryExpr : TertiaryExpr
                | LogicalORExpr

readLogicalORExpr可得产生式:

LogicalORExpr ---> LogicalORExpr || LogicalANDExpr
                 | LogicalANDExpr

readLogicalANDExpr得:

LogicalANDExpr ---> LogicalANDExpr && EqualityExpr
                  | EqualityExpr

readEqualityExpr得:

EqualityExpr ---> RelationalExpr == RelationalExpr
                | RelationalExpr != RelationalExpr
                | RelationalExpr === RelationalExpr
                | RelationalExpr !== RelationalExpr
                | RelationalExpr

readRelationalExpr得:

RelationalExpr ---> AdditiveExpr > AdditiveExpr
                  | AdditiveExpr < AdditiveExpr
                  | AdditiveExpr >= AdditiveExpr
                  | AdditiveExpr <= AdditiveExpr
                  | AdditiveExpr

readAdditiveExpr

/**
 * 读取加法表达式
 *
 * @param {Walker} walker 源码读取对象
 * @return {Object}
 */
function readAdditiveExpr(walker) {
    var expr = readMultiplicativeExpr(walker);

    while (1) {
        walker.goUntil();
        var code = walker.currentCode();

        switch (code) {
            case 43: // +
            case 45: // -
                walker.go(1);
                // 这里创建了一个新对象,包住了原来的 expr,返回了一个新的 expr
                expr = {
                    type: ExprType.BINARY,
                    operator: code,
                    segs: [expr, readMultiplicativeExpr(walker)]
                };
                // 注意到这里是 continue,之前的函数都是 return
                continue;
        }

        break;
    }

    return expr;
}

读加法的这个函数有些特殊,其在第一步先调用了读乘法的方法,得到了变量expr,然后不断地更新expr对象包住原来的对象,以保证结合性的正确。

方法的产生式如下:

AdditiveExpr ---> AdditiveExpr + MultiplicativeExpr
                | AdditiveExpr - MultiplicativeExpr
                | MultiplicativeExpr

readMultiplicativeExpr得:

MultiplicativeExpr ---> MultiplicativeExpr * UnaryExpr
                      | MultiplicativeExpr / UnaryExpr
                      | MultiplicativeExpr % UnaryExpr
                      | UnaryExpr

readUnaryExpr这个函数,包含了除布尔值的表达式之外的,各个表示数据得表达式的解析部分。因此对应的产生式也相对复杂,为了便于说明,我自行引入了一些非终结符号:

UnaryExpr ---> !UnaryExpr
             | 'String'
             | "String"
             | Number       // - 字符开头的部分也会进入 readNumber
             | ArrayLiteral
             | ObjectLiteral
             | ParenthesizedExpr
             | Call

ArrayLiteral ---> []
                | [ElementList]     // 这里引入一个新的非终结符号 ElementList 来辅助说明
ElementList ---> Element
               | ElementList, Element
Element ---> TertiaryExpr
           | ...TertiaryExpr

ObjectLiteral ---> {}
                 | {FieldList}      // 类似上面的 ElementList
FieldList ---> Field
             | FieldList, Field
Field ---> ...TertiaryExpr
         | SimpleExpr
         | SimpleExpr: TertiaryExpr
SimpleExpr ---> true
              | false
              | 'String'
              | "String"
              | Number

readParenthesizedExpr得:

ParenthesizedExpr ---> (TertiaryExpr)

readCall得:

Call ---> Accessor(TertiaryExprList)
        | Accessor()
        | Accessor

TertiaryExprList ---> TertiaryExpr, TertiaryExprList
                    | TertiaryExpr

readAccessor得:

Accessor ---> true
            | false
            | Identifier MemberOperator*        // 此处 * 表示 0个或多个的意思

MemberOperator ---> .Identifier
                  | [TertiaryExpr]

至此,我们终于把所有的产生式都梳理清楚了。

和 JavaScript 文法的对比

在这里我附上一份JavaScript 1.4 Grammar供参考。通过对比两种文法产生式的不同,能找到很多两者之间解析结果得差异。下面是一个例子:

1 > 2 < 3       // 返回 true,相当于 1 > 2 返回 false,false < 3 返回 true
san.evalExpr(san.parseExpr('1 > 2 < 3'), new san.Data());       // 返回 false

注意到 San 中关于RelationalExpression的产生式是:

RelationalExpr ---> AdditiveExpr > AdditiveExpr
                  | AdditiveExpr < AdditiveExpr
                  | AdditiveExpr >= AdditiveExpr
                  | AdditiveExpr <= AdditiveExpr
                  | AdditiveExpr

也就是说,对于1 > 2 < 3,其匹配了RelationalExpr ---> AdditiveExpr > AdditiveExpr。其中1传入了AdditiveExpr解析成Number12 < 3则被视为另一个AdditiveExpr进行解析,由于后面已经没有能够处理<的逻辑了,所以会被解析成Number2。所以,输入的1 > 2 < 3,真正解析出来的就只有1 > 2了,所以上面的代码会返回 false 。

个人认为 San 在这里应该是刻意为之的。因为对于1 > 2 < 3这种表达式,真的没必要保证它按照JavaScript的文法来解析——这种代码写出来肯定是要改的,没有顾及它的意义。

拓展

了解了 parseExpr 是如何从源字符串得到表达式对象之后,也就发现其实很多地方都用了类似的方法来描述语法。比如CSS 线性渐变。这里我的链接直接指向了MDN上关于线性渐变的形式语法(Formal syntax)部分,可以看到这部分对线性渐变语法的描述,和我上面解析 parseExpr 的时候所用的产生式如出一辙。

linear-gradient(
  [ <angle> | to <side-or-corner> ,]? <color-stop> [, <color-stop>]+ )
  \---------------------------------/ \----------------------------/
    Definition of the gradient line        List of color stops

where <side-or-corner> = [left | right] || [top | bottom]
  and <color-stop>     = <color> [ <percentage> | <length> ]?

这种语法形式是MDN定义的CSS属性值定义语法

参照我们前面所写的产生式与上面的CSS属性值定义语法,我写出了如下的产生式:

expr ---> gradientLine , colorStopList
        | colorStopList

gradientLine ---> angle | to sideOrCorner
sideOrCorner ---> horizon
                | vertical
                | horizon vertical
                | vertical horizon
horizon ---> left | right
vertical ---> top | bottom

colorStopList ---> colorStopList, color distance
                 | color distance
color ---> hexColor | rgbColor | rgbaColor | literalColor | hslColor    // 相信大家都懂,我就不做进一步展开了
distance ---> percentage | length       // 同上,不做进一步展开

结语

这一趟下来可以说是补了不少课,也揭示了 San 中内部原理的一角,后面计划把 evalExprDataparseTemplate等方法也学习一遍,进一步了解 San 的全貌。

Repository owner deleted a comment from IWSR Jun 19, 2018

Repository owner deleted a comment from magicianShiro Jun 19, 2018

Repository owner deleted a comment from wotermelon Jun 19, 2018

Repository owner deleted a comment from Dafrok Jun 19, 2018

Repository owner deleted a comment from Nbsaw Jun 19, 2018

@TyroneYvesChen

This comment has been minimized.

TyroneYvesChen commented Jun 19, 2018

围观JK大佬

@yongningfu

This comment has been minimized.

yongningfu commented Jun 19, 2018

想了想,当时对这部分代码的理解还是偏简单了一下,只是理性分析代码的合理行,往深入来讲,确实是需要往上思考这块解析代码部分的方法论,给个赞!

@errorrik

This comment has been minimized.

errorrik commented Oct 12, 2018

由于你的工作,让 call 表达式支持后,代码依旧小于14k,所以3.7.0暂缓,发3.6.11

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment