PL真有意思（二）：程序設計語言語法

前言

雖然標題是程序語言的語法，但是講的是對詞法和語法的解析，其實關於這個前面那個寫編譯器系列的描述會更清楚，有關語言語法的部分應該是穿插在整個設計當中的，也看語言設計者的心情了

和英語漢語這些自然語言不一樣，計算機語言必須是精確的，它們的語法和語義都必須保證沒有歧義，這當然也讓語法分析更加簡單

所以對於編譯器一項很重要的任務就是時別程序設計語言的結構規則，要完成這個目標就需要兩個要求：

• 完成對語法規則的描述
• 確定給定程序是否按照這些規則構造起來，也就是符合語法規則

第一個要求主要由正則表達式和上下文無關文法來描述完成，而第二個要求就是由編譯器來完成，也就是語法分析了

描述語法：正則表達式和上下文無關語法

對於詞法，都可以用三種規則描述出來：

1. 拼接
2. 選擇
3. Kleene（也就是重複任意多次）

比如一個整數常量就可以是多個数字重複任意多次，也叫做正則語言。如果對於一個字符串，我們再加入遞歸定義即可以描述整個語法，就可以稱作上下文無關語法

單詞正則表達式

對於程序語言，單詞的類型不外乎關鍵字、標識符、符合和各種類型的常量

對於整數常量就可以用這樣的正則表達式來表示

integer -> digit digit* digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

上下文無關文法

一般正則表達式只適用於描述單詞，因為正則表達式無法描述嵌套結構，一般正則表達式的實現都是用有限狀態自動機，之前用Python實現了一個簡單的也是這樣，但是對於匹配任意深度的嵌套結構就需要有一個任意大的狀態機，顯然不符合。而定義嵌套結構對於描述語法非常有用，所以就有了上下文無關文法

expr := id | number | - expr | ( expr ) | expr or expr

op := + | - | * | /

對於上下文無關文法，每條規則叫做一個產生式，產生式左部的符合稱為非終結符，而右部則是多個終結符或者非終結符，最後所有規則都會推到至終結符上，而終結符就是正則表達式定義的單詞

推導和語法樹

一個正確的上下文無關文法，就可以指導我們如何生成一個合乎語法的終結符串

最簡單的就是從開始符號開始，用這個產生式的右部取代開始符合，再從得到的串選擇一個非終結符繼續進行推導，直到沒有剩下的非終結符，這個過程就像遞歸構造一個樹的過程

expr := expr op expr
     := expr op id
     := expr + id
     := expr op expr + id
     := expr op id + id
     := expr * id + id
     := id * id + id

但是對於給定的上下文語法有可能會推導出不止一顆語法分析樹，我們就說這個上下文語法是存在歧義性的。所以對於上面的上下文無關語法還有更好的文法

掃描

掃描也就是詞法分析，詞法分析完全可以不需要什麼正則表達式、自動機什麼的，徒手擼出來，現在業界為了更好的生成錯誤信息，應該很多也是手工的詞法分析器

手工的詞法分析器，無非就是一直讀入字符，到能判斷出它的token在送入語法分析器

有限狀態自動機

使用有限狀態機的詞法分析一般都是這樣的幾個步驟

• 給出詞法的正則表達式

• 將正則表達式轉換為非確定有限自動機（NFA）

其實對於任意的正則表達式都可以用拼接、選擇和Kleene閉包來表示

而同樣的，有限自動機也可以通過這三種方式來表示，圖就不畫了，這個在之前寫Python正則表達式引擎的文章里都畫過了（溜了

• 將NFA轉換為確定性有限狀態自動機（DFA）

將NFA轉換到DFA可以採用的是子集構造法，主要思想就是，在讀入給定輸入之後所到達的DFA狀態，表示的是原來NFA讀入同樣輸入之後可能澳大的所有狀態

• 最小化DFA

對於最小化DFA的主要思想是，我們把DFA所有狀態分為兩個等價類，終止態狀態和非終止狀態。然後我們就反覆搜索等價類X和輸入符合c，使得當給定C作為輸入時，X的狀態能轉換到位於k>1個不同等價類中的狀態。之後我們就把X劃分為k個類，使得類中所有轉檯對於C都會轉移到同一個老類的成員。直到無法再按這種方式找到劃分的類時，我們就完成了

這四個步驟在之前的寫的正則表達式引擎中都完成了，在那三篇文章里會更詳細一點

語法分析

一般語法分析器的輸入是token流，而輸出是一顆語法分析樹。其中分析方法一般可以分為自上而下和自下而上兩類，這些類中最重要的兩個分別稱為LL和LR

LL表示從左向右，最左推導，LR表示從左向右，最右推導。這兩類文法都是從左到右的順序讀取輸入，然後語法分析器試圖找出輸入的推導結果

自上而下的方式

一般自上而下的語法分析器比較符合之前的推導方法，從根節點開始像恭弘=叶 恭弘節點反覆的遞歸推導，直到當前的恭弘=叶 恭弘節點都是終結符

• 遞歸下降

遞歸下降很符合上面說的從根節點出發進行推導，一般用於一些相對簡單一些的語言

read A
read B
sum := A + B
write sum
write sum / 2

比如對於這個程序的遞歸下降，語法分析器一開始調用program函數，在讀入第一個單詞read后，program將調用stmt_list，再接着調用stmt才真正開始匹配read A。以這種方式繼續下去，語法分析器執行路徑將追溯出語法分析樹的從左向右、自上而下的遍歷

• 表格驅動的LL自上而下

表格驅動的LL是基於一個語法分析表格和一個棧

分析流程是

1. 初始化一個棧
2. 將開始符號壓入棧
3. 彈出棧頂，然後根據棧頂的符號和當前的輸入符號查表
4. 如果彈出的是非終結符，將會繼續查表來確定下一個壓入棧中的產生式
5. 如果是終結符將進行匹配

預測集合

從上面可以看出來最重要的就是那個語法分析表格了，語法分析表格其實就是根據當前輸入字符對下一個產生式的預測，這裏就要用到一個概念：預測集合，也就是First和Follow集合。這個在之前寫編譯器系列講的比較詳細，在這裏就不寫了

當然LL語法也會有很多處理不了的文法，所以也才會有其它的語法分析方法

自下而上的方式

在實踐中，自下而上的語法分析都是表格驅動的，這種分析器在一個棧中保存所有部分完成的子樹的根。當它從掃描器中得到一個新的單詞時，就會將這個單詞移入棧。當它發現位於棧頂的若干符號組成一個右部時，它就會將這些符號歸約到對應的左部。

一個自底向上的語法分析過程對應為一個輸入串構造語法分析書的過程，它從恭弘=叶 恭弘子節點開始，通過shift和reduce操作逐漸向上到達根節點

自底向上的語法分析需要一個堆棧來存放解析的符號，例如對於如下語法：

0.  statement -> expr
1.  expr -> expr + factor
2.           | factor
3.  factor ->  ( expr )
4.           | NUM

來解析1+2

stack	input
null	1 + 2
NUM	+ 2	開始讀入一個字符，並把對應的token放入解析堆棧，稱為shift操作
factor	+ 2	根據語法推導式，factor -> NUM,將NUM出棧，factor入棧，這個操作稱為reduce
expr	+ 2	這裏繼續做reduce操作，但是由於語法推導式有兩個產生式，所以需要向前看一個符合才能判斷是進行shift還是reduce，也就是語法解析的LA
expr +	2	shift操作
expr + NUM	null	shift操作
expr + factor	null	根據fator的產生式進行reduce
expr	null	reduce操作
statement	null	reduce操作

此時規約到開始符號，並且輸入串也為空，代表語法解析成功

有限狀態自動機的構建

0.  s -> e
1.  e -> e + t
2.  e -> t
3.  t -> t * f
4.  t -> f
5.  f -> ( e )
6.  f -> NUM

• 對起始推導式做閉包操作

先在起始產生式->右邊加上一個.

s -> .e

對.右邊的符號做閉包操作，也就是說如果 . 右邊的符號是一個非終結符，那麼肯定有某個表達式，->左邊是該非終結符，把這些表達式添加進來

s -> . e
e -> . e + t
e -> . t

對新添加進來的推導式反覆重複這個操作，直到所有推導式->右邊是非終結符的那個所在推導式都引入

• 對引入的產生式進行分區

把 . 右邊擁有相同非終結符的表達式划入一個分區，比如

e -> t .
t -> t . * f

就作為同一個分區。最後把每個分區中的表達式中的 . 右移動一位，形成新的狀態節點

• 對所有分區節點構建跳轉關係

根據每個節點 . 左邊的符號來判斷輸入什麼字符來跳入該節點

比如， . 左邊的符號是 t, 所以當狀態機處於狀態0時，輸入時 t 時， 跳轉到狀態1。

• 對所有新生成的節點重複構建

最後對每個新生成的節點進行重複的構建，直到完成所有所有的狀態節點的構建和跳轉

小結

這一篇主要是提了對詞法和語法的分析過程，因為想要結合語言設計和實踐，更詳細的應該去看前面的寫一個編譯器系列

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

※帶您來了解什麼是 USB CONNECTOR  ?

※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象

※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站，提高曝光率!!

※綠能、環保無空污,成為電動車最新代名詞，目前市場使用率逐漸普及化

※廣告預算用在刀口上，網站設計公司幫您達到更多曝光效益