重學前端學習筆記（二十八）--通過四則運算的解釋器快速理解編譯原理

Crazy_Coder 發(fā)布于2019-08-30 11:06 / 2136人閱讀

摘要：實現(xiàn)狀態(tài)機可能產(chǎn)生四種輸入元素，其中只有兩種，狀態(tài)機的第一個狀態(tài)就是根據(jù)第一個輸入字符來判斷進入了哪種狀態(tài)用函數(shù)表示狀態(tài)，用表示狀態(tài)的遷移關系，用值表示下一個狀態(tài)。運行狀態(tài)機輸出結(jié)果四語法分析語法分析根據(jù)每一個產(chǎn)生式來寫一個函數(shù)。

筆記說明

重學前端是程劭非（winter）【前手機淘寶前端負責人】在極客時間開的一個專欄，每天10分鐘，重構你的前端知識體系，筆者主要整理學習過程的一些要點筆記以及感悟，完整的可以加入winter的專欄學習【原文有winter的語音】，如有侵權請聯(lián)系我，郵箱：[email protected]。

一、分析

按照編譯原理相關的知識，將其分成幾個步驟。

定義四則運算：產(chǎn)出四則運算的詞法定義和語法定義。

詞法分析：把輸入的字符串流變成 token。

語法分析：把 token 變成抽象語法樹 AST。

解釋執(zhí)行：后序遍歷 AST，執(zhí)行得出結(jié)果。

二、定義四則運算 2.1、定義詞法

Token

Number: 1 2 3 4 5 6 7 8 9 0 的組合

Operator: +、-、*、/ 之一

Whitespace：

LineTerminator：

2.2、定義語法

語法定義多數(shù)采用 BNF。巴科斯范式(BNF: Backus-Naur Form 的縮寫)是由 John Backus 和 Peter Naur 首次引入一種形式化符號來描述給定語言的語法（最早用于描述ALGOL 60 編程語言）。JavaScript 標準里面就是一種跟 BNF 類似的自創(chuàng)語法。

1、加法是由若干個乘法再由加號或者減號連接成的：

 ::=
    

 ::=
    
    |<+>
    |<->

2、可把普通數(shù)字當成乘法的一種特例：

 ::=
    
    |<*>
    |

上面就是四則運算的定義。

三、詞法分析：狀態(tài)機

詞法分析：把字符流變成 token 流，有兩種方案，一種是狀態(tài)機，一種是正則表達式，它們是等效的。

3.1、實現(xiàn)狀態(tài)機

// 可能產(chǎn)生四種輸入元素，其中只有兩種 token，狀態(tài)機的第一個狀態(tài)就是根據(jù)第一個輸入字符來判斷進入了哪種狀態(tài)

var token = [];
function start(char) {
    if(char === "1" || char === "2"|| char === "3"
        || char === "4"|| char === "5"|| char === "6"|| char === "7"
        || char === "8"|| char === "9"|| char === "0") {
        token.push(char);
        return inNumber;
    }
    if(char === "+" || char === "-" || char === "*" || char === "/") {
        emmitToken(char, char);
        return start
    }
    if(char === " ") {
        return start;
    }
    if(char === "
" || char === "
") {
        return start;
    }
}
function inNumber(char) {
    if ( char === "1" || char === "2" || char === "3"
        || char === "4"|| char === "5" || char === "6" || char === "7"
        || char === "8" || char === "9" || char === "0") {
        token.push(char);
        return inNumber;
    } else {
        emmitToken("Number", token.join(""));
        token = [];
        // put back char
        return start(char);
    }
}

// 用函數(shù)表示狀態(tài)，用 if 表示狀態(tài)的遷移關系，用 return 值表示下一個狀態(tài)。

3.2、運行狀態(tài)機

function emmitToken(type, value) {
    console.log(value);
}

var input = "1024 + 2 * 256"

var state = start;

for(var c of input.split(""))
    state = state(c);

state(Symbol("EOF"))

// 輸出結(jié)果
1024
+
2
*
256

四、語法分析：LL

LL 語法分析根據(jù)每一個產(chǎn)生式來寫一個函數(shù)。

4.1、寫好函數(shù)名

function AdditiveExpression( ){

}
function MultiplicativeExpression(){

}

4.2、假設已經(jīng)拿到 token

var tokens = [{
    type:"Number",
    value: "1024"
}, {
    type:"+",
    value: "+"
}, {
    type:"Number",
    value: "2"
}, {
    type:"*",
    value: "*"
}, {
    type:"Number",
    value: "256"
}, {
    type:"EOF"
}];

4.3、AdditiveExpression處理

1、三種情況

 ::=
    
    |<+>
    |<->

2、AdditiveExpression 的寫法

AdditiveExpression 的寫法是根傳入的節(jié)點，利用產(chǎn)生式合成新的節(jié)點。

function AdditiveExpression(source){
    if(source[0].type === "MultiplicativeExpression") {
        let node = {
            type:"AdditiveExpression",
            children:[source[0]]
        }
        source[0] = node;
        return node;
    }
    if(source[0].type === "AdditiveExpression" && source[1].type === "+") {
        let node = {
            type:"AdditiveExpression",
            operator:"+",
            children:[source.shift(), source.shift(), MultiplicativeExpression(source)]
        }
        source.unshift(node);
    }
    if(source[0].type === "AdditiveExpression" && source[1].type === "-") {
        let node = {
            type:"AdditiveExpression",
            operator:"-",
            children:[source.shift(), source.shift(), MultiplicativeExpression(source)]
        }
        source.unshift(node);
    }
}

4.4、函數(shù) Expression 處理

1、把解析好的 token 傳給的頂層處理函數(shù) Expression。

Expression(tokens);

2、如果 Expression 收到第一個 token，是個 Number，就需要對產(chǎn)生式的首項層層展開，根據(jù)所有可能性調(diào)用相應的處理函數(shù)，這個過程在編譯原理中稱為求 closure。

function Expression(source){
    if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "EOF" ) {
        let node = {
            type:"Expression",
            children:[source.shift(), source.shift()]
        }
        source.unshift(node);
        return node;
    }
    AdditiveExpression(source);
    return Expression(source);
}
function AdditiveExpression(source){
    if(source[0].type === "MultiplicativeExpression") {
        let node = {
            type:"AdditiveExpression",
            children:[source[0]]
        }
        source[0] = node;
        return AdditiveExpression(source);
    }
    if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "+") {
        let node = {
            type:"AdditiveExpression",
            operator:"+",
            children:[]
        }
        node.children.push(source.shift());
        node.children.push(source.shift());
        MultiplicativeExpression(source);
        node.children.push(source.shift());
        source.unshift(node);
        return AdditiveExpression(source);
    }
    if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "-") {
        let node = {
            type:"AdditiveExpression",
            operator:"-",
            children:[]
        }
        node.children.push(source.shift());
        node.children.push(source.shift());
        MultiplicativeExpression(source);
        node.children.push(source.shift());
        source.unshift(node);
        return AdditiveExpression(source);
    }
    if(source[0].type === "AdditiveExpression")
        return source[0];
    MultiplicativeExpression(source);
    return AdditiveExpression(source);
}
function MultiplicativeExpression(source){
    if(source[0].type === "Number") {
        let node = {
            type:"MultiplicativeExpression",
            children:[source[0]]
        }
        source[0] = node;
        return MultiplicativeExpression(source);
    }
    if(source[0].type === "MultiplicativeExpression" && source[1] && source[1].type === "*") {
        let node = {
            type:"MultiplicativeExpression",
            operator:"*",
            children:[]
        }
        node.children.push(source.shift());
        node.children.push(source.shift());
        node.children.push(source.shift());
        source.unshift(node);
        return MultiplicativeExpression(source);
    }
    if(source[0].type === "MultiplicativeExpression"&& source[1] && source[1].type === "/") {
        let node = {
            type:"MultiplicativeExpression",
            operator:"/",
            children:[]
        }
        node.children.push(source.shift());
        node.children.push(source.shift());
        node.children.push(source.shift());
        source.unshift(node);
        return MultiplicativeExpression(source);
    }
    if(source[0].type === "MultiplicativeExpression")
        return source[0];

    return MultiplicativeExpression(source);
};

var source = [{
    type:"Number",
    value: "3"
}, {
    type:"*",
    value: "*"
}, {
    type:"Number",
    value: "300"
}, {
    type:"+",
    value: "+"
}, {
    type:"Number",
    value: "2"
}, {
    type:"*",
    value: "*"
}, {
    type:"Number",
    value: "256"
}, {
    type:"EOF"
}];
var ast = Expression(source);

console.log(ast);
// 輸出結(jié)果 children: Array(1) children: Array(3)還可以繼續(xù)展開。。。
{
    type: "Expression",
    children: [
        {
            type: "AdditiveExpression",
            operator: "+",
            children: [
                {
                    type: "AdditiveExpression",
                    children: Array(1)
                },
                {
                    type: "+",
                    value: "+"
                },
                {
                    type: "MultiplicativeExpression",
                    operator: "*",
                    children: Array(3)
                }
            ]
        },
        {
            type: "EOF"
        }
    ]
}

五、解釋執(zhí)行

得到了 AST 之后，只需要對這個樹做遍歷操作執(zhí)行即可。

// 根據(jù)不同的節(jié)點類型和其它信息，用 if 分別處理即可：
function evaluate(node) {
    if(node.type === "Expression") {
        return evaluate(node.children[0])
    }
    if(node.type === "AdditiveExpression") {
        if(node.operator === "-") {
            return evaluate(node.children[0]) - evaluate(node.children[2]);
        }
        if(node.operator === "+") {
            return evaluate(node.children[0]) + evaluate(node.children[2]);
        }
        return evaluate(node.children[0])
    }
    if(node.type === "MultiplicativeExpression") {
        if(node.operator === "*") {
            return evaluate(node.children[0]) * evaluate(node.children[2]);
        }
        if(node.operator === "/") {
            return evaluate(node.children[0]) / evaluate(node.children[2]);
        }
        return evaluate(node.children[0])
    }
    if(node.type === "Number") {
        return Number(node.value);
    }
}

個人總結(jié)

這下完全懵逼了 _(:3」∠)_

云服務器 GPU云服務器二十八深度學習的理解怎么理解前端工程師學習前端的網(wǎng)站

文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/114779.html

重學前端學習筆記（二十八）--通過四則運算的解釋器快速理解編譯原理

摘要：實現(xiàn)狀態(tài)機可能產(chǎn)生四種輸入元素，其中只有兩種，狀態(tài)機的第一個狀態(tài)就是根據(jù)第一個輸入字符來判斷進入了哪種狀態(tài)用函數(shù)表示狀態(tài)，用表示狀態(tài)的遷移關系，用值表示下一個狀態(tài)。運行狀態(tài)機輸出結(jié)果四語法分析語法分析根據(jù)每一個產(chǎn)生式來寫一個函數(shù)。筆記說明重學前端是程劭非（winter）【前手機淘寶前端負責人】在極客時間開的一個專欄，每天10分鐘，重構你的前端知識體系，筆者主要整理學習過程的一些要點...

Towers 2019-08-02 15:14 評論0 收藏0
重學前端學習筆記（二十八）--通過四則運算的解釋器快速理解編譯原理

摘要：實現(xiàn)狀態(tài)機可能產(chǎn)生四種輸入元素，其中只有兩種，狀態(tài)機的第一個狀態(tài)就是根據(jù)第一個輸入字符來判斷進入了哪種狀態(tài)用函數(shù)表示狀態(tài)，用表示狀態(tài)的遷移關系，用值表示下一個狀態(tài)。運行狀態(tài)機輸出結(jié)果四語法分析語法分析根據(jù)每一個產(chǎn)生式來寫一個函數(shù)。筆記說明重學前端是程劭非（winter）【前手機淘寶前端負責人】在極客時間開的一個專欄，每天10分鐘，重構你的前端知識體系，筆者主要整理學習過程的一些要點...

hot_pot_Leo 2019-08-23 17:58 評論0 收藏0
重學前端學習筆記（十八）--JavaScript的閉包和執(zhí)行上下文

摘要：申明與賦值立即執(zhí)行的函數(shù)表達式，通過創(chuàng)建一個函數(shù)，并且立即執(zhí)行，來構造一個新的域，從而控制的范圍。函數(shù)接受一個的形參，該參數(shù)是一個對象引用，并執(zhí)行了。在最新的標準中，引入了一個新概念。筆記說明重學前端是程劭非（winter）【前手機淘寶前端負責人】在極客時間開的一個專欄，每天10分鐘，重構你的前端知識體系，筆者主要整理學習過程的一些要點筆記以及感悟，完整的可以加入winter的專欄...

liaorio 2019-08-26 13:48 評論0 收藏0

發(fā)表評論

登陸后可評論

0條評論

Crazy_Coder

男|高級講師

我要關注我要私信

TA的文章

深入JavaScript高級語法-coderwhy大神新課王紅元新課

閱讀 1020·2021-11-25 09:43
css—盒子模型理解

閱讀 1679·2019-08-30 13:59
div-section-article標簽的同異

閱讀 1612·2019-08-30 11:22
重學前端學習筆記（二十八）--通過四則運算的解釋器快速理解編譯原理

閱讀 2137·2019-08-30 11:06
每周前端開源推薦第二期

閱讀 1308·2019-08-28 17:51
百度地圖2.0離線版與echarts結(jié)合

閱讀 3744·2019-08-26 12:12
JavaScript面向?qū)ο缶幊獭狾bject類型

閱讀 790·2019-08-26 12:11
JavaScript學習第六天筆記（對象）

閱讀 456·2019-08-26 12:10

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

重學前端學習筆記（二十八）--通過四則運算的解釋器快速理解編譯原理

相關文章