用javascript寫四則元算編譯器之詞法分析

大三有門課程叫編譯原理，叫我們自己寫一個簡單的編譯器，嗯，隨意什麼語言都可以，那我當然用js啦，這麼優雅，雖然被我用的不怎麼優雅。這個跟語言無關，只是我喜歡用js而已，裡面沒用多少js的特性。

另外程式碼寫的有點爛，別噴。

先說一下我自己的整個過程吧

1. 首先第一步詞法分析：就是需要寫正規表示式然後把裡面的單字和數字符號什麼的全部切割出來。

2. 建構語法規則，這裡我選的是LL(1)文法。這裡設計好自己的文法。

3. 建構中間程式碼。這裡我用了文法樹。

4. 寫轉換程序，什麼樣的文法句就對應什麼樣的程序。

詞法分析：

1. #輸入正規則，將正規表示式轉換成nfa->dfa-> ;dfa最小化。這部分去看網易雲課堂那個用java做的編譯器那個，照著上面的做就好了，我前面nfa部分就照著他的影片做的。

2. 得到dfa最小化的那個表。對於每一個正規表示式來說需要的就只是這個表而已。所以確定好正規表示式之後就可以直接儲存這個表，不需要每次都產生。

3. 然後你需要一大堆正規表示式
   

1. 數字一個

2. 符號一個

3. 關鍵字一個

4. 變數名稱一個

5. 「anything」一個（這個可以用來處理出錯的，如果都不是上面1-4，那就可以用5去接收排除掉）

    var id_ = new build_rule();
    id_.build_from_str(id__str, 3);    //这个变量id__str就是那个已经生成字符串保存起来的dfa最小化的表
    //数字3就是id对应的名字，到时候用来判断来生成类型码的

    var key_word = new build_rule();
    key_word.build_from_str(key_word_str, 1);    //和上面一样

    var ops = new build_rule("{op}{op}*", 1);    //这个使用正则生成的规则的，需要经过nfa---dfa---最小化这几步的转化
    //1符号和关键字统称的类型


    var num = new build_rule("{float}", 4);    //同上

    var anything = new build_rule();
    anything.build_from_str(anything_str);
    anything.rule_name = 5;    //这个就是用来处理错误的，识别5这个类型时候就会出错，也可以记录这个出错让程序一直扫描到后面再输出错误

    //按照自己定义的规定的顺序进行添加规则，到时候就会按照这个顺序进行查找
    var qing = qingai(code);
    qing.add_rules(key_word);
    qing.add_rules(id_);
    qing.add_rules(ops);
    qing.add_rules(num);
    qing.add_rules(anything);
    qing.action();

1. 所有正規表示式有順序的，這個看你自己安排那個重要。例如順序是：
    變數名——–>關鍵字———->其他
   這樣的話，如果辨識到  「var」  會把var當成是變數名，因為var在沒有被定義成為關鍵字時候，這個是可以當作合法的變數名的。
   所以順序需要自己安排好

2. 建構好多個正規表示式以及他們的順序之後，就開始開工了。

3. 原始程式碼從頭開始掃描，主指標指向開頭
   

1. #指標指向開頭

2. 從第一個規則找起

3. 按照dfa自動機規則，也就是那個表，遇到什麼字元就跳到那一行

4. 如果讀入下一個還是可以跳轉的就再跳到另一行。如果不能跳轉，看看這一行是不是有結束標記的，有的話就順利退出，不用再找下一個規則，然後主指針加上這個找到的字符串的長度，順便記錄這個字符串的信息：長度，那一行，那一列，什麼型。如果沒有就要找下一個規則。

5. 因為有那個 都是的規則存在，保證每個都能找到屬性。

6. 還是會有沒找到的，因為有空格換行，需要在最後判斷一下，過濾掉就好了。

4. 然後根據自己寫的原始碼

a=7464;b=7465;a=b+7464*2;

就可以得到這樣的一個表了 8. 後面的類型碼，就是在文法裡面需要用類型碼來表達這個類型的字串。之後文法這邊會透過類型碼去判斷輸入的句子符不符合給定的文法。因為不同的關鍵字和符號都有不同的意思，所以關鍵字和符號的型別碼都是不同的，我的變數名稱就用d來表示

總結步驟

1. 輸入正規表示式

2. 把正規表示式的巨集定義換成正常的字元

3. #切割正規表示式

4. 把切割好的整個表達式傳入nfa自動機構造nfa圖

5. 把nfa圖的頭節點傳入dfa自動機構造dfa表

6. 把nfa表進行dfa最小化得到dfa最小化表

7. 這樣完成一個字串對應的查找自動機的建構

8. 重複1-7直到所有正規表示式都轉換完成。之後只要保存好所有最小化的表，每次只要載入那個表就可以了，不需用每次都生成nfa、dfa什麼的。

9. 按照順序把規則放進掃描器（其實就是一個while循環一次自己寫的來源程式所有的字元而已）裡面，開始掃描。

10. 得到token表格

11. 結束

#相關文章：

#javascript中解析四則運算表達式的演算法與範例

#

JavaScript預編譯原理分析

以上是用javascript寫四則元算編譯器之詞法分析的詳細內容。更多資訊請關注PHP中文網其他相關文章！