編譯原理實驗題

實驗一 小型詞法分析器的設計

一、實驗原理

1、詞法分析器

詞法分析器的功能輸入源程序，按照構詞規則分解成一系列單詞符號。詞法分析是編譯過程中的一個階段，在語法分析前進行。詞法分析作為一遍，可以簡化設計，改進編譯效率，增加編譯系統的可移植性。也可以和語法分析結合在一起作為一遍，由語法分析程序調用詞法分析程序來獲得當前單詞供語法分析使用。

2、詞法分析器的設計目標

(1)正確性；

(2)可讀性；

(3)健壯性；

(4)高時間效率；

(5)高空間效率；

二、實驗要求和目的

1、理解符號串的基本特點；

2、理解符號串切割的特點；

3、理解單詞符號的特點與基本特點。

三、實驗環境

環境不限。

四、作業要求

編寫一個程序，對于輸入的一段英語文本，可以統計：

（1）該文本中有多少英語單詞，并把每個單詞都列出來；

（2）該文本中有多少不同的英語單詞，并把不同的單詞都列出來。

如，輸入 I am a good student. I am in Zhengzhou.

則可以統計出有9個英語單詞、7個不同的英語單詞。

實驗二 小型詞法分析器的設計

一、實驗原理

1、詞法分析器

詞法分析器的功能輸入源程序，按照構詞規則分解成一系列單詞符號。單詞是語言中具有獨立意義的最小單位，包括關鍵字、標識符、運算符、界符和常量等。

(1) 關鍵字 是由程序語言定義的具有固定意義的標識符。例如，Pascal 中的begin，end，if，while都是保留字。這些字通常不用作一般標識符。

(2) 標識符 用來表示各種名字，如變量名，數組名，過程名等等。

(3) 常數? 常數的類型一般有整型、實型、布爾型、文字型等。

(4) 運算符 如+、-、*、/等等。

(5) 界符? 如逗號、分號、括號、等等。

2、詞法分析器設計目標

(1) 正確性

(2) 可讀性

(3) 健壯性

(4) 高時間效率

(5) 高空間效率

二、實驗要求和目的

1、理解詞法分析器的基本原理；

2、能夠根據詞法分析器的原理設計小型詞法分析器，該詞法分析器可以獲取單詞符號并判斷符號的類別。

三、實驗環境

環境不限。

四、作業要求

1、編寫一個詞法分析器，對于輸入的算術表達式，可以獲取該字符串中的所有運算數和運算符。

如，輸入25.6 + 1752.9e10 -62^ 3

則要求得到輸出如下，

25.6

+

17

*

52.9e10

6

*

2

^

3

2、編寫一個詞法分析器，對于輸入的一段程序，可以獲取該程序的單詞符號。單詞符號的類別有基本字、標識符、常數、算符和界符。關鍵字為基本字，由字母組成，如int、for和while；變量名和函數名為標識符，由字母和數字構成，如fun1和age；固定不變的數值為常數，如12、13.86和25e8(科學計數法)；算符如+、-、、/ 、%、&&；界符如 {、[、(、 ；和：等。

如，若輸出源程序如下，

public?static?void?main (String []?args)?{

???double sum5 = 0.0;

for ( int?i=1;i<=5;i++)?{

sum5=sum5+(i+10);

sum5=sum5+(i2);

???}

}

則要求得到輸出如下，

public 基本字

static?基本字

void?基本字

main 標識符

( 界符

String基本字

[ 界符

] 界符

args標識符

)? 界符

{ 界符

double基本字

sum5標識符

= 算符

0.0 常數

; 界符

for基本字

( 界符

int?基本字

i標識符

=算符

1常數

; 界符

i標識符

<=算符

5常數

; 界符

i標識符

++算符

)? 界符

{ 界符

sum5 標識符

= 算符

sum5 標識符

算符

(界符

i標識符

算符

10常數

) 界符

; 界符

sum5 標識符

= 算符

sum5 標識符

算符

(界符

i 標識符

算符

2常數

) 界符

;? 界符

}界符

}界符

作業步驟：

(1) 了解該語言的單詞符號

(2) 為單詞符號構造對應的狀態轉換圖。狀態轉換圖的構造可以參考課本P41(圖3.2)和P43(圖3.3)

(3) 根據狀態轉圖的結構進行計算機實現。

注：

數字52.9e10為一個數據，切記不可將其分開為52.9和10; <=為一個操作符，切記不可將其分開為< 和 =

作業二 (選做)

flex 是- fast lexical analyzer generator 的簡稱，即快速詞法分析器。

給出的“lex_實驗”是一個通過flex得到的詞法分析器及相關文件，該詞法分析器可以統計源程序的行數及字符數。

（一） 目錄介紹

參考 “lex_實驗”，在完成實驗后，實驗目錄中包括兩個子目錄。

1、子目錄 flex

它包含了 flex.exe, flex.hlp, libfl.lib 三個文件，另外還有一個例子文件 example.l 及該例子生成的 lex.yy.c。

2、子目錄 lex_yy

這個目錄是為 lex.yy.c 建立的一個項目（如，使用 VC6）。它包含有 lex.yy.c, libfl.lib （拷貝自目錄 flex），以及相關的項目文件。在debug 子目錄中是已經生成的 詞法分析器 lex.yy.exe, 利用它可以進行詞法分析。

（二）實驗示范

生成“lex_實驗”的各文件的步驟如下：

1、編寫 lex 程序，如 example.l 文件所示

2、調用 flex 以生成 lex.yy.c， DOS命令格式： flex < example.l

3、新建一個目錄（如 lex_yy）, 把lex.yy.c 及 libfl.lib 拷貝到該目錄下。

4、用VC6或其它的C語言集成開發環境，打開lex.yy.c，并生成一個新項目。

5、編譯并鏈接libfl.lib， 得到詞法分析器 debug/ley.yy.exe。

6、驗證詞法分析器的功能：

1）編寫一輸入文件（如lex_yy/debug/12.txt）

2) 調用 lex.yy.exe（DOS 命令格式 lex.yy.exe < 12.txt ）

3) 觀察輸出結果是否與預想的相符（實際是有點不相符的）。

注意：flex.exe, flex.hlp, libfl.lib 三個文件是flex工具，自帶的。

實驗三 小型語法分析器的設計

一、實驗原理

語法分析器通常是作為編譯器或解釋器的組件出現的，它的作用是進行語法檢查、并構建由輸入的單詞組成的數據結構（一般是語法分析樹、抽象語法樹等層次化的數據結構）。

語法分析器通常使用一個獨立的詞法分析器從輸入字符流中分離出一個個的“單詞”，并將單詞流作為其輸入。實際開發中，語法分析器可以手工編寫，也可以使用工具（半）自動生成

二、實驗要求和目的

1、加深對語法分析器工作過程的理解；

2、加強對遞歸下降法實現語法分析程序的掌握；

3、能夠采用一種編程語言實現簡單的語法分析程序；

4、能夠使用自己編寫的分析程序對簡單的程序段進行語法翻譯。

三、實驗環境

環境不限。

四、作業要求

在實驗2的基礎上，用遞歸下降分析法編制語法分析程序，語法分析程序的實現可以采用任何一種編程工具。

編寫的分析程序能夠進行正確的語法分析；對于遇到的語法錯誤，能夠做出簡單的錯誤處理，給出簡單的錯誤提示，保證順利完成語法分析過程；

給定文法

E E + T | E – T | T

T T * F | T / F | F

F (E) | i

取消左遞歸后，改為:

E TE’

E’ +TE’ | -TE’ |ε

T FT’

T’ *FT’ | /FT’|ε

F (E) | i

該文法為LL(1)方法。

請根據第4.4節的遞歸下降分析程序構造方法，為該文法構造程序，對于給定的輸入，程序按照先后順序將使用的產生式輸出。

如，輸入25.6 * 14.5 + 2, 首先經過詞法分析器，得到五個單詞符號 i * i + i

經過語法分析，則輸出

E TE’

T FT’

F i

T’*FT’

F i

T’ε

E’+TE’

T FT’

F i

T’ε

E’ε

提示:

(1) 該程序應該為每個非終結符( E、E’、T、T’、F)分別寫一個函數，寫函數時，需要考慮first集和follow集。

(2) 在驗證程序正確性時，要考慮語法正確的串和語法不正確的串。

如： 正確的串有 25.6 * 14.5 + 2 ( i * i + i)， 2 / 5.2 + 78 - 6 ( i / i + i - i)

錯誤的串有 2 / 5.2 + 78 – ( i / i + i - ) +56 * 7 ( + i * i)

對于給定的輸入，大家可以通過手寫推導過程，然后再核對計算機輸出的產生式順序的方法，檢驗程序寫的對錯。

實驗四 小型語法分析器的設計

一、實驗原理

1、語法分析器

語法分析器通常是作為編譯器或解釋器的組件出現的，它的作用是進行語法檢查、并構建由輸入的單詞組成的數據結構（一般是語法分析樹、抽象語法樹等層次化的數據結構）。

語法分析器通常使用一個獨立的詞法分析器從輸入字符流中分離出一個個的“單詞”，并將單詞流作為其輸入。實際開發中，語法分析器可以手工編寫，也可以使用工具（半）自動生成

2、算符優先分析

對于一個算符優先文法，只要能構造出它的算符優先表，就可以利用算符優先分析方法，分析一個句子是否符合這個文法的定義。在算符優先文法中，僅存在終結符號之間的優先關系，完全不考慮非終結符號。我們根據算符優先關系，給句型尋找一個被歸約的最左素短語。一旦發現最左素短語，即可規約。

二、實驗要求和目的

1、加深對語法分析器工作過程的理解；

2、加強對終結符之間的優先關系的掌握；

3、能夠采用一種編程語言實現簡單的算符優先分析過程。

三、實驗環境

環境不限。

四、作業要求

1、在實驗2的基礎上，用算符優先分析法編制語法分析程序，語法分析程序的實現可以采用任何一種編程工具。

編寫的分析程序能夠進行正確的語法分析；對于遇到的語法錯誤，能夠做出簡單的錯誤處理，給出簡單的錯誤提示，保證順利完成語法分析過程。

給定文法及其優先關系表，如下：

（1）輸入正確的表達式，則給出詳細的操作步驟。如，給出表達式T+T*F+i，則輸出

符號棧 優先關系 剩余輸入串 動作

T+T*F+i# 移進

#T < +TF+i# 移進

#T+ TF+i# 移進

#T+T > F+i# 移進

#T+T F+i# 移進

#T+TF > +i# 歸約TF

#T+N > +i# 歸約T+N

#N < +i# 移進

#N+ < i# 移進

#N+i > # 歸約i

#N+N > # 歸約N+N

#N = # 接受

（2）輸入錯誤的表達式，如 i+i *, 則報錯。

2、選做

請設計一個小型公式編輯器的上下文無關文法，并進行自上而下分析的實現。

實驗五 小型編譯程序的設計

一、實驗原理

(1) 詞法分析

(2) 語法分析

(3) 語義分析

二、實驗要求和目的

1、加深對詞法分析器的理解；

2、加深對語法分析器的理解；

3、加深對屬性文法的理解；

三、實驗環境

環境不限。

四、作業要求

1、請大家在實驗2和實驗3的基礎之上，利用翻譯模式制作可編程計算器，如圖1所示。要求：

圖1 可編程計算器界面

（1）點擊 25.6 * 14.5 + 2 這11個符號，按‘=’，可輸出結果373.2

（2）點擊2 / (5.2 + 78) – 6這12個符號, 按‘=’，可輸出結果 -5.97596

（3）若輸入語法錯誤的串，如2 / 5.2 + 78 –， 則需報錯。

（4）考慮整型和浮點型問題。對于浮點型，還需考慮精度問題。

（5）考慮除0問題。

（6）考慮鍵盤操作問題。

本題翻譯模式的提示如下，請補充以下三個空之后，參考圖2所示的代碼，寫出計算器。

E TE’{E.val = T.val + E’.val}

E’ +TE’ {E’.val = T.val + E’.val}

E’ -TE’ {undefined}

E’ ε {E’.val = 0}

T FT’{T.val = F.val * T’.val}

T’ *FT’ {T’.val = F.val * T’.val}

T’ /FT’ {}

T’ ε {_________________}

F (E) {F.val = E.val}

F i {F.val = i.lexval}

E TE’{E.val = T.val + E’.val}， 其代碼經過更改如下：

圖2 翻譯模式代碼

2、選做

請將語義分析納入到小型公式編輯器中，并將小型公式編輯器實現出來。

CSS 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。