資訊專欄INFORMATION COLUMN
摘要：這樣的程序或稱工具有很多現(xiàn)成的可供選擇包括在平臺(tái)上可用的，但既然我這個(gè)系列叫做從零開始寫個(gè)編譯器吧，那顯然如果我用現(xiàn)成的工具，那是犯規(guī)行為。
Parser（語法分析器）的編寫相對(duì)于 Tokenizer （詞法分析器）要復(fù)雜得多，因此，在編寫之前可能也會(huì)鋪墊得更多一些。當(dāng)然，本系列旨在“寫出”一個(gè)編譯器，所以理論方面只會(huì)簡(jiǎn)單介紹 tao 語言所涉及的部分。
之前的幾章中，我純手寫了tao 語言的 Tokenizer。但如果我準(zhǔn)備也純手寫一個(gè) Parser，那將是非常麻煩且繁瑣的一件事情。實(shí)際上，就在在寫出這篇文章之前，我已完成了 Parser 的編寫，并測(cè)試妥當(dāng)，因此我可以在此面對(duì)各位得出這個(gè)結(jié)論。
我將使用這么一種方式“制造”出 Parser：
將 tao 語言的所有語法細(xì)節(jié)描述出來，即定義 tao 語言。
寫一個(gè)能”根據(jù)定義，生成 tao 語言的 Parser“的程序。
如果以上描述有些讓人困惑，那我舉個(gè)通俗點(diǎn)的例子吧：
假如我想要制作一雙鞋子，通常的方案是，我會(huì)買好材料，并把鞋子做出來。但還有另一種方案，我先畫出鞋子的設(shè)計(jì)圖，再造一臺(tái)能依照設(shè)計(jì)圖造出鞋子的機(jī)器，然后把設(shè)計(jì)圖交給機(jī)器，再發(fā)動(dòng)機(jī)器，得到鞋子。
在”制造鞋子的世界“中，除非我要開鞋廠，否則若我僅僅想造雙鞋子，那么前一個(gè)方案顯然更好。但在”制造編譯器的世界“中，卻與直覺相反，當(dāng)語言本身足夠復(fù)雜的時(shí)候，后一種方案比前一種方案要方便得多。
至此，我需要一個(gè)能讀懂 tao 語言的定義，并根據(jù)定義生成 Parser 的一個(gè)程序。這種程序我們稱之為 Compiler-compiler 。這樣的程序（或稱工具）有很多現(xiàn)成的可供選擇（包括在 Java 平臺(tái)上可用的），但既然我這個(gè)系列叫做《從零開始寫個(gè)編譯器吧》，那顯然如果我用現(xiàn)成的工具，那是犯規(guī)行為。
因此，我還要寫一個(gè) Compiler-compiler 出來才行。
那么，讓我先貼一張圖，以描述我將會(huì)寫出的 Compiler-compiler 的工作原理吧。
Compiler-compiler 會(huì)將 tao 語言的定義編譯成某種數(shù)據(jù)結(jié)構(gòu)，而這種數(shù)據(jù)結(jié)構(gòu)是 Parser 初始化的參數(shù)。Parser 只有獲得了這種數(shù)據(jù)結(jié)構(gòu)才能正常工作。
當(dāng) Parser 初始化之后，它會(huì)讀取 Tokenizer 生成的 Token 序列，并同時(shí)通過解釋 Compiler-compiler 生成的數(shù)據(jù)結(jié)構(gòu)，最后生成 Syntax Tree。
至此，在編寫 Parser 的章節(jié)中，我必須完成如下三個(gè)任務(wù)。
定義 tao 語言的語法細(xì)節(jié)，并挑選一個(gè)合適的形式描述出來。
編寫一個(gè) Compiler-compiler，它能編譯 tao 語言的定義，并生成某種數(shù)據(jù)結(jié)構(gòu)。
編寫一個(gè) Parser，它通過解釋 Compiler-compiler 生成的數(shù)據(jù)結(jié)構(gòu)，將 Token 序列編譯成 Syntax Tree。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/64263.html
摘要：自然，我們還是先從語言的編譯器下手吧。在動(dòng)手寫編譯器之前，得容我將編譯器的結(jié)構(gòu)進(jìn)行進(jìn)一步的劃分。這些將被語法分析器接收并進(jìn)行進(jìn)一步處理。由于本系列將著重于寫出編譯器，必要的理論和概念還是會(huì)交代的。從零開始寫個(gè)編譯器吧編譯器的結(jié)構(gòu)的博客 自然，我們還是先從 tao 語言的編譯器下手吧。在動(dòng)手寫編譯器之前，得容我將編譯器的結(jié)構(gòu)進(jìn)行進(jìn)一步的劃分。編譯器可視為一個(gè)黑盒，從其一端輸入源代碼，另一...
摘要：是的，這個(gè)系列將呈現(xiàn)一個(gè)完整的編譯器從無到有的過程。但在寫這個(gè)編譯器的過程中，我可不會(huì)偷工減料，該有的一定會(huì)寫上的。該語言的虛擬機(jī)將運(yùn)行于之上，同時(shí)編譯器將使用實(shí)現(xiàn)。我早有寫編譯器的想法之前沒寫過，故希望一邊寫編譯器一邊完成這個(gè)系列。 是的，這個(gè)系列將呈現(xiàn)一個(gè)完整的編譯器從無到有的過程。當(dāng)然，為了保證該系列內(nèi)容的簡(jiǎn)潔（也為了降低難度），僅僅保證編譯器的最低要求，即僅能用。但在寫這個(gè)編譯...
摘要：詞法分析器本身就是一個(gè)狀態(tài)機(jī)，生成這個(gè)狀態(tài)機(jī)有很多種方法，而我打算采取手寫的方式。狀態(tài)機(jī)不斷從源代碼即一個(gè)字符串中讀入一個(gè)一個(gè)字符，讀到不同的字符將使?fàn)顟B(tài)機(jī)的狀態(tài)從一個(gè)狀態(tài)變化到另外一個(gè)狀態(tài)。 詞法分析器 Tokenizer 本身就是一個(gè)狀態(tài)機(jī)，生成這個(gè)狀態(tài)機(jī)有很多種方法，而我打算采取手寫的方式。因?yàn)?tao 語言的詞法還是相對(duì)比較簡(jiǎn)單的，手寫不成問題。 先新建一個(gè)LexicalAna...
摘要：對(duì)于而言，終結(jié)符與的是對(duì)應(yīng)的。這些內(nèi)容，我將其稱之為終結(jié)符的值。對(duì)于一個(gè)非終結(jié)符的產(chǎn)生式對(duì)于非終結(jié)符，其對(duì)象的字段則會(huì)表現(xiàn)成如下形式。對(duì)于里面的數(shù)組，其元素可能為終結(jié)符對(duì)象非終結(jié)符對(duì)象或表達(dá)式枚舉對(duì)象。 首先是 TerminalSymbol.java 即終結(jié)符。 package com.taozeyu.taolan.analysis; import java.util.HashSet...
摘要：基于這個(gè)結(jié)論，對(duì)某個(gè)非終結(jié)符展開形式的判定就變得明了起來。但嚴(yán)格的要求一個(gè)非終結(jié)符最多只能有一個(gè)產(chǎn)生式可以導(dǎo)出。這意味著我們必須明確知道每一個(gè)非終結(jié)符能不能導(dǎo)出。如果集包含這個(gè)終結(jié)符，則表明該非終結(jié)符需要導(dǎo)出。 tao 語言的 Parser 的語法分析是不帶回溯的，自頂向下的。文法選用 LL(1)，這種文法雖然略顯薄弱，但還尚可用。 回顧上一章提到的 LL(1) 的定義，可以得出如下結(jié)...
閱讀 3107·2021-11-02 14:40
閱讀 889·2019-08-30 15:53
閱讀 1345·2019-08-30 15:53
閱讀 3316·2019-08-30 13:53
閱讀 3376·2019-08-29 12:50
閱讀 1196·2019-08-26 13:49
閱讀 1930·2019-08-26 12:20
閱讀 3727·2019-08-26 11:33
