在程式語言運行的過程中,會先經過詞法分析階段,由於完整的程式語言往往具有複雜的文法,因此,剖析器的設計並不容易,所以,相關文件往往提出建議,希望你使用現成的剖析器程式庫。

然而,試著自行打造剖析器,也有不少好處,非但有助於理解剖析器程式庫之原理,更有助於理解手中正在打造的程式語言。

符號的識別

自行打造語言剖析器,確實有一定的複雜度,然而,照著相關文件採用現成剖析器程式庫練習時,因為文法掌握在撰文者心中,看似可省去不少剖析語言的功夫,實際上,若對於手中打造的語言文法沒有徹底認識,等到我們收起文件之後,往往只會陷入混亂的文法泥淖。

而打造語言剖析器之所以複雜,是因為一開始就設定了過於複雜的文法。不過,我們可以將目標降低,試著從簡單的文法剖析開始,成功後再逐步加入新文法,按需求逐步重構來自行建立剖析器。其實,這個過程也符合語言文法的構造,從基本單字開始,建立基礎語句,再由基礎語句建構出更複雜的語句。

從基本的單字開始,意謂著剖析器必須能進行符號的識別,語言中固定的關鍵字,像是if、else、while、true、false等的識別是最簡單的,接下來是不固定的文字,像是數字、文字、變數等,雖說不固定,然而,語言中的這類元素,必然會有「規則」,也就是哪些符號組合方式,才能是語言中允許的數字、文字、變數等。

談到文字的識別比對,對於開發者而言,應該要能直覺聯想到規則表示式(Regular expression)。因為,現代語言內建的規則表示式,在功能完備、性能上,多半比自行設計比對程式庫來得好上許多,若無特殊原因,應該加以善用。

基本上,數字、文字、變數等規則表示式,是易於建構的。以JavaScript的規則表示式寫法為例,基本的數字規則可以是[0-9]+\.?[0-9]*;面對文字的時候,若以''來含括文字,不考慮字元跳脫(escape)的話,會是/'(.*)'/,然而,考慮到文字中會有\\、\t、\r、\n、\'等情況,規則表示式會是/'((\\'|\\\\|\\r|\\n|\\t|[^'\\])*)'/;至於一般語言中允許的變數格式,基本上,規則表示式的用法會是/[a-zA-Z_]+[a-zA-Z_0-9]*/。

分支的處理

識別符號是建構剖析器的出發點,接下來,要將剖析器對應至抽象語法樹的建構規則。

由於語言中符號眾多,在判斷哪個符號必須對應哪個規則時,不免會形成許多的條件分支。單純地使用原生語言(撰寫剖析器時使用的語言)的if..else、switch語句,並非不行,只不過,當原始碼中充斥大量分支語句時,可讀性就會迅速降低,造成後續添加文法時的困難度急遽上升。

如果符號是一對一地對應至簡單的規則,那麼,使用Map之類的結構會是最方便的作法,只要將規則實作為物件存放在Map中成為值,查找到的符號作為鍵,如此就能夠將符號對應至規則物件,又不會建立複雜、難閱讀的分支判斷。

然而,由於無法事先預測語言使用者,會以何種組合方式、順序來撰寫程式碼,剖析器必須逐一測試,看看目前的符號是哪種類型,例如,這會是個陳述句嗎?或者是運算式、函式呼叫等?

因而,流程上會形成「如果OOO成立,就XXX,否則繼續下一個類型測試」瀑布地重複地出現。在這個時候,我們可採取Chain of Responsibility模式的方式,建立不同職責物件,各自負擔類型判斷;若不是,則轉交下個職責物件。

因此,關於剖析器的處理,在設計上,往往會以物件導向的概念來進行,而當分支處理涉及類型的判斷,此時,我們可以嘗試使用物件導向的多型概念來解決。

而對於分支處理的其他可能性,在先前專欄〈避免隨意而重複的if...else〉(https://goo.gl/iXPcXr)中,所提到的一些方式,你也可以參考。

文法的遞迴

設計語言剖析器的難處之一,就是對付文法的遞迴性。

例如,運算式中可能還會有運算式,像是((1 + 2 * 3) + 4 * 5),從括號來看,可以看成是兩條運算式的組合。當然,這種簡單的運算式,還可以使用中序式轉後序式,以後序式進行運算來解決,而且,此種方式同時可以處理運算子優先順序問題,就原理來說,由於處理過程使用了堆疊,相當於使用下推自動機的運算能力,來解決了問題。

然而,當運算式中允許像函式呼叫之類的元素出現時,剖析的複雜性就會急遽上升。例如:1 + sub(2, add(3, len('Hello'))) + len('World')要怎麼剖析?勢必要判斷sub的引數列、add的引數列,以及len的引數列,各是為何,此時,我們有辦法使用規則表示式來識別嗎?

/\(.*\)/是最簡單的想法,可惜的是,它會吃掉最後一個括號前全部的字元。就上例而言,就是匹配到(2, add(3, len('Hello'))) + len('World'),這對sub而言,並不是正確的引數;/\([^)]*\)/吃的字元又太少,會匹配到(2, add(3, len('Hello'),對sub也是錯誤的引數列。

根本的原因在於,規則表示式本質上等同於有限狀態機,任意深度對稱括號的匹配,已經超出了其運算能力。

因為有限狀態機沒有記憶設備,若想以規則表示式來設計對稱括號匹配,必須能事先知道括號的最大深度。例如,允許有一層括號的話,規則表示式會是/\(([^()]|\([^()]*\))*\)/;而在更多層的情況下,規則表示式會更複雜,像是三層的話,會是/\(([^()]|\(([^()]|\(([^()]|\([^()]*\))*\))*\))*\)/。

實際上,允許三層深度的情況下,撰寫出來的程式碼,已經不易閱讀了,然而,若自行打造的語言,想要能允許使用者自訂對稱括號深度,可自行設計函式來產生,例如:

function nestingParentheses(level) {
if (level === 0)
return '[^()]*';
return `([^()]|\\(${nestingParentheses(level - 1)}\\))*`;
}

例如`\\((${nestingParentheses(4)})\\)`,就可以產生允許四層對稱括號的規則表示式;像這類情況,也可以採類似方式解決。

逐步重構建立剖析器

在設計剖析器的過程中,隨著文法的逐漸複雜,需要的規則表示式,也會變得複雜,這時,我們必須對規則表示式進行重構,將共用的表示式提取出來,用以組合為複雜的規則表示式。日後,若要修改共用的表示式,即使是複雜的表示式,也就能適應複雜的語句比對。

剖析器的分支判斷,也應隨著文法的日益複雜,視需求進行重構。而每一次的重構,都是重新審視文法構造流程、遞迴性的時候,往往也會因此而發現更多可能性——雖是自行打造的語言,然而,在建構文法時有著許多缺失,在重構之後,能予以修正,對於文法,也就更能掌握,若日後打算改用既有、成熟的剖析器,這種掌握度會是一大助益。

作者簡介


Advertisement

更多 iThome相關內容