源码

Sk.parse = function parse (filename, input) {
    var T_COMMENT = Sk.token.tokens.T_COMMENT;
    var T_NL = Sk.token.tokens.T_NL;
    var T_OP = Sk.token.tokens.T_OP;
    var T_ENDMARKER = Sk.token.tokens.T_ENDMARKER;
    var T_ENCODING = Sk.token.tokens.T_ENCODING;

    var endmarker_seen = false;
    var parser = makeParser(filename);

    // 由于lines.pop()因此需要reverse()
    function readline(input) {
        var lines = input.split("\n").reverse().map(function (l) { return l + "\n"; });
        return function() {
            if (lines.length === 0) {
                throw new Sk.builtin.Exception("EOF");
            }
            return lines.pop();
        };
    }

    Sk._tokenize(filename, readline(input), "utf-8", function (tokenInfo) {
        // tokenInfo.start[0]保存了token的开始行号，tokenInfo.start[1]保存了token的开始列号
        // tokenInfo.end[0]保存了token的结束行号，tokenInfo.end[1]保存了token的结束列号
        // tokenInfo.value保存了token
        var s_lineno = tokenInfo.start[0];
        var s_column = tokenInfo.start[1];
        var type = null;
        var prefix, lineno, column;

        if (tokenInfo.type === T_COMMENT || tokenInfo.type === T_NL || tokenInfo.type === T_ENCODING) {
            prefix += tokenInfo.value;
            lineno = tokenInfo.end[0];
            column = tokenInfo.end[1];
            if (tokenInfo.string[tokenInfo.string.length - 1] === "\n") {
                lineno += 1;
                column = 0;
            }
        } else {
            // 如果是运算符，用更加具体的type取代T_OP
            if (tokenInfo.type === T_OP) {
                type = Sk.OpMap[tokenInfo.string];
            }
            // context 包含了 开始位置(tokenInfo.start), 结束位置(tokenInfo.end), 行(tokenInfo.line)
            parser.addtoken(type || tokenInfo.type, tokenInfo.string, [tokenInfo.start, tokenInfo.end, tokenInfo.line]);

            if (tokenInfo.type === T_ENDMARKER) {
                endmarker_seen = true;
            }
        }
    });

    // endmarker_seen 用于标记 输入是否残缺
    if (!endmarker_seen) {
        throw new Sk.builtin.SyntaxError("incomplete input", this.filename);
    }
    return {"cst": parser.rootnode, "flags": parser.p_flags};
};

function makeParser (filename, style) {
    if (style === undefined) {
        style = "file_input";
    }
    var p = new Parser(filename, Sk.ParseTables);
    // for closure's benefit
    if (style === "file_input") {
        p.setup(Sk.ParseTables.sym.file_input);
    } else {
        Sk.asserts.fail("todo;");
    }
    return p;
}
function Parser (filename, grammar) {
    this.filename = filename;
    this.grammar = grammar;
    this.p_flags = 0;
    return this;
}
Parser.prototype.setup = function (start) {
    var stackentry;
    var newnode;
    start = start || this.grammar.start;
    //print("START:"+start);

    newnode =
    {
        type    : start,
        value   : null,
        context : null,
        children: []
    };
    stackentry =
    {
        dfa  : this.grammar.dfas[start],
        state: 0,
        node : newnode
    };
    this.stack = [stackentry];
    this.used_names = {};
};

setup中 的 node 为 下图 中 的 E或id

源码

Parser.prototype.addtoken = function (type, value, context) {
    var errline, itsfirst, itsdfa, state, v, t, newstate, i, a, arcs, first, states, tp;
    var ilabel = this.classify(type, value, context);

    OUTERWHILE:
    while (true) {
        tp = this.stack[this.stack.length - 1];
        states = tp.dfa[0];
        first = tp.dfa[1];
        arcs = states[tp.state];

        // LR算法 中的 查表 操作
        for (a = 0; a < arcs.length; ++a) {
            i = arcs[a][0];
            newstate = arcs[a][1];
            t = this.grammar.labels[i][0];
            v = this.grammar.labels[i][1];
            if (ilabel === i) {
                // 本处进行归约操作
                Sk.asserts.assert(t < 256);
                this.shift(type, value, newstate, context);
                // pop while we are in an accept-only state
                state = newstate;
                while (states[state].length === 1
                    && states[state][0][0] === 0
                    && states[state][0][1] === state) {
                    this.pop();
                    if (this.stack.length === 0) { return true; }
                    tp = this.stack[this.stack.length - 1];
                    state = tp.state;
                    states = tp.dfa[0];
                    first = tp.dfa[1];
                }
                return false;
            } else if (t >= 256) {
                itsdfa = this.grammar.dfas[t];
                itsfirst = itsdfa[1];
                if (itsfirst.hasOwnProperty(ilabel)) {
                    this.push(t, this.grammar.dfas[t], newstate, context);
                    continue OUTERWHILE;
                }
            }
        }
        if (findInDfa(arcs, [0, tp.state])) {
            this.pop();
            if (this.stack.length === 0) {
                throw new Sk.builtin.SyntaxError("too much input", this.filename);
            }
        } else {
            errline = context[0][0];
            throw new Sk.builtin.SyntaxError("bad input", this.filename, errline, context);
        }
    }
};

Parser.prototype.classify = function (type, value, context) {
    var ilabel;
    if (type === Sk.token.tokens.T_NAME) {
        this.used_names[value] = true;
        // 是不是 keywords
        ilabel = this.grammar.keywords.hasOwnProperty(value) && this.grammar.keywords[value];

        // Check for handling print as a builtin function
        if(value === "print" && (this.p_flags & Parser.CO_FUTURE_PRINT_FUNCTION || Sk.__future__.print_function === true)) {
            ilabel = false; // ilabel determines if the value is a keyword
        }

        if (ilabel) { return ilabel; }
    }
    ilabel = this.grammar.tokens.hasOwnProperty(type) && this.grammar.tokens[type];
    if (!ilabel) {
        // throw new Sk.builtin.SyntaxError("bad token", type, value, context);
        // Questionable modification to put line number in position 2
        // like everywhere else and filename in position 1.
        let descr = "#"+type;
        for (let i in Sk.token.tokens) {
            if (Sk.token.tokens[i] == type) {
                descr = i;
                break;
            }
        }

        throw new Sk.builtin.SyntaxError("bad token " + descr, this.filename, context[0][0], context);
    }
    return ilabel;
};

源码

Parser.prototype.push = function (type, newdfa, newstate, context) {
    var dfa = this.stack[this.stack.length - 1].dfa;
    var node = this.stack[this.stack.length - 1].node;
    var newnode = {
        type      : type,
        value     : null,
        lineno    : context[0][0],      // throwing away end here to match cpython
        col_offset: context[0][1],
        children  : []
    };
    this.stack[this.stack.length - 1] = {
        dfa  : dfa,
        state: newstate,
        node : node
    };
    this.stack.push({
        dfa  : newdfa,
        state: 0,
        node : newnode
    });
};

源码

Parser.prototype.shift = function (type, value, newstate, context) {
    var dfa = this.stack[this.stack.length - 1].dfa;
    var state = this.stack[this.stack.length - 1].state;
    var node = this.stack[this.stack.length - 1].node;
    var newnode = {
        type      : type,
        value     : value,
        lineno    : context[0][0],
        col_offset: context[0][1],
        children  : null
    };
    if (newnode) {
        node.children.push(newnode);
    }
    this.stack[this.stack.length - 1] = {
        dfa  : dfa,
        state: newstate,
        node : node
    };
};

源码

Parser.prototype.pop = function () {
    var node;
    var pop = this.stack.pop();
    var newnode = pop.node;
    if (newnode) {
        if (this.stack.length !== 0) {
            node = this.stack[this.stack.length - 1].node;
            node.children.push(newnode);
        } else {
            this.rootnode = newnode;
            this.rootnode.used_names = this.used_names;
        }
    }
};