編譯原理（3）——詞法分析

詞法分析

碼文不易，希望支援，謝謝->支援原創

 詞法分析（掃描）器的功能

  輸入源程式，輸出(單詞)符号(token)。

即：把構成源程式的字元串轉換成(單詞)符号序列

 1. 單詞符号的表示

(單詞符号種别，屬性值)           

• 常用單詞符号種别——分類

1.各關鍵字（保留字、基本字），各種運算符，各種分界符——各用一個種别碼辨別

2.其它辨別符——用一個種别碼辨別

3.常數——用一個種别碼辨別

• 單詞符号的值——屬性

常數的值，辨別符的名字等

保留字、運算符、分界符的屬性值可以省略

代碼塊舉例

{            (LP,    _ )
 S        (IDN,符号表項指針)
 =        (EQ,  _)
 S        (IDN,符号表項指針)
 ++       (INC,    _ )
 ;                (SEMI,   _ )
 pointer          (IDN,  符号表項指針)
 ++           (INC,    _ )
 ;                (SEMI,   _ )
 }            (RP,     _ )               

碼文不易，希望支援，謝謝->支援原創

 符号的正規(表達)式描述

  正規文法是左線性文法和右線性文法的統稱。它們都是Chomsky分類下的3型文法。由正規文法産生的語言稱為正規集。下面我們将會看到，這裡之是以用“正規”二字為一種語言命名，是因為這種語言的結構可以用所謂正規式來描述。正規表達式——百度百科

  下面兩種文法中l代表字母（終極符），d代表數字（非終極符）。

  左線性文法

  S→l | Sd | Sl

  右線性文法

  S→ l| lT

  T→ l| d| lT| dT

 1. 正規式

正規語言的另一種描述方法

例：l (l|d)*
 | 表示"或"
 * 表示Kleene閉包
 符号的并清單示符号連接配接關系
           

正規式 r 表示正規集,相應的正規集記為 L(r),意思明确時也可以直接記為r。

  正規(表達)式(Regular Expression——RE)

設 ∑ ∑ 是一個字母表，

⑴ ϕ ϕ 是 ∑ ∑ 上的RE， L(ϕ)=ϕ L ( ϕ ) = ϕ ；

⑵ ε ε 是 ∑ ∑ 上的RE， L(ε)={ε} L ( ε ) = { ε } ；

⑶ 對于 ∃a∈∑ ∃ a ∈ ∑ ， a a 是RE，L(a)=aL(a)=a；

⑷ 如果 r r 和ss是RE， L(r)=R L ( r ) = R , L(s)=S L ( s ) = S ，則：

  r與s的“和” (r|s)是RE，L((r|s))=R∪S，

  r與s的“乘積/連接配接” (rs)是RE，L((rs))=RS，

  r的克林閉包(r*)是RE，L((r*))=R*。

  運算的優先級

• * 高于“連接配接” 和| ， “連接配接” 高于 |
• | 具有交換律、結合律
• “連接配接” 具有結合律、和對|的配置設定律
• ( ) 指定優先關系，意義清楚時，括号可以省略

 2. 正規文法與正規式

正規文法與正規式等價

對任何正規文法，存在定義同一語言的正規式

對任何正規式，存在生成同一語言的正規文法

  正規式到正規文法的轉換

按如下方法構造正規定義式，并逐漸将其轉換成正規文法

1. 引入開始符号S，從如下正規定義式開始

S→r

2. 對r中的形如r1|r2|…|rn的子串

用産生式組 A→ r1|r2|…|rn 表示

3. 對r中的形如r1*的子式子

用産生式組 A→ε|r1A 表示

4. 對r中的形如 r1+ r 1 + 的子式子，

用産生式組 A→ r1|r1A 表示

5. 執行連接配接對|的配置設定律

對連接配接運算，要作特殊處理：按出現順序定義

正規式到正規文法的轉換用到了正規定義式的概念

下面是正規式

a(a|b)*(ε|((.|_)(a|b)(a|b)*))
    = a(a|b)*
    | a(a|b)*.(a(a|b)*|b(a|b)*)
    | a(a|b)*_(a(a|b)*|b(a|b)*)
    =aA | aC
A→aA | bA | ε
C→aC | bC | .B | _B
B→aA | bA | a | b           

下面是轉換後的正規表達式

S→aA | aC
A→aA | bA | ε
C→aC | bC | .B | _B
B→aA | bA | a | b           

  一個簡單詞法的正規定義式

詞法規則	單詞種别	屬性
<辨別符>→<字母>(<字母>|<數字>)*	IDN	符号表項入口
<無符号整數>→ <數字> (<數字>)*	NUM	數值
<指派符>→ :=	ASG	無
<加号>→+	+	無
<減号>→-	MINUS	無
<星号>→*	STAR	無

  變換為正規文法

<辨別符> →letter<辨別符尾>

<辨別符尾>→ε | letter<辨別符尾> | digit<辨別符尾>

<整數> →digit <整數尾>

<整數尾> →ε | digit<整數尾>

<指派号> →:=

<加号> →+

<等号> →=

…

  正規文法到正規定義式的轉換

1. 代入：對于 A→xB, B→y，構造 A→xy
2. 遞歸：對于 A→xA|y，構造 A→x*y
3. 多候選式：對于 A→x，A→y，構造A→x|y

碼文不易，希望支援，謝謝->支援原創

 符号的識别

  1. 狀态轉換圖

用來描述詞法分析器識别記号的分析過程

• 結點：狀态用○表示；終态用◎表示
• 有向弧 ── 箭頭
• 弧标記 ── 輸入字元

    辨別符的狀态圖

    <辨別符>→letter(letter|digit)*

  從正規式到狀态轉換圖

 2.從正規文法出發，構造狀态圖

(1) 以每個非終結符為狀态結點，開始符号對應初态 S

(2) 增設一個終态 T

(3) 對于規則 A→aB，畫從狀态 A 到 B 的弧，标為 a

(4) 對于規則 A→a，畫從狀态 A 到終态 T 的弧，标為 a

(5) 對于規則 A→rB, B→sB，畫從狀态 A 到狀态 B标為 r的弧，從狀态B到B的标記為s的弧

 利用狀态轉換圖識别單詞符号

(1) 從初始狀态出發

(2) 讀入一字元

(3) 按目前字元轉入下一狀态

(4) 重複 2,3 直到完成一個單詞的識别或者發現錯誤

在遇到讀入的字元是Token的分割符時，若進入的狀态是終止态，說明讀入的字元組成一單詞；否則，說明輸入不符合詞法規則

 詞法分析程式的設計與實作

 1. 資料結構與子例程

  資料結構

資料結構	解釋
ch	目前輸入字元
token	輸入緩沖區(字元數組)
symbol	單詞種别（子程式的傳回值）
attr	屬性（全局變量）

  子程式

Lookup(token):将 token 存入符号表，傳回入口指針

isKeyword(token):判别 token是關鍵字？傳回關鍵字種别或 -1

getchar():從輸入緩沖區中讀入一個字元放入ch

isdigit()

isalpha()

···

 2. 需要說明的問題

1. 沖區預處理，超前搜尋
2. 關鍵字的處理，符号表的實作
3. Lookup：查找效率，算法的優化實作
4. 詞法錯誤處理

 3. 掃描器的自動生成

 詞法分析器實作總結

支援原創

碼文不易，希望支援，謝謝->支援原創

再次感謝，大家對本人的支援。