項(xiàng)目1 手動(dòng)設(shè)計(jì)詞法分析器

一、?目的與要求：

項(xiàng)目1：

１）目的

?通過設(shè)計(jì)調(diào)試詞法分析程序，實(shí)現(xiàn)從源程序中分出各種單詞的方法；加深對課堂教學(xué)的理解；提高詞法分析方法的實(shí)踐能力。

?２）要求

• 掌握從源程序文件中讀取有效字符的方法和產(chǎn)生源程序的內(nèi)部表示文件的方法。?

• 掌握詞法分析的實(shí)現(xiàn)方法。

• 上機(jī)調(diào)試編出的詞法分析程序。

二、?說明：

1、?TINY語言的特證

1)?TINY語言無過程定義，無聲明語句，所有的變量都是整型。

2)?它只有兩個(gè)控制語句：if語句和repeat語句。if語句有一個(gè)可選的else部分且必須由關(guān)鍵字end結(jié)束。

3)?read和write完成輸入和輸出

4)?"{"和"}"中的語句為注釋，但注釋不能嵌套

Tiny語言的文法定義：

程序清單1是該語言的一個(gè)求階乘的編程示例。

程序清單1

?

{ Sample program

??in TINY language -

??computes factorial

}

read x; { input an integer }

if 0 < x then { don't compute if x <= 0 }

??fact := 1;

??repeat

????fact := fact * x;

????x := x - 1

??until x = 0;

??write fact ?{ output factorial of x }

end

?

2、?TINY語言的單詞的種類和詞法分析程序設(shè)計(jì)

2.1單詞種類為5類：關(guān)鍵字，運(yùn)算符，標(biāo)識(shí)符，常整數(shù)，界限符或不可見字符

1)?關(guān)鍵字: if, then, else, end, repeat, until, read, write.（所有的關(guān)鍵字都是保留字，且全部小寫）

2)?運(yùn)算符： + - * / = < ( ) := （這里只用了小于符號(hào)<，沒有使用大于符號(hào)> , :=為賦值符號(hào)）

3)?標(biāo)識(shí)符和常整數(shù)：ID和NUM, 通過下列正則表達(dá)式定義：

ID = [a-zA-Z_]+[a-zA-Z0-9_]* ???//注意：大寫和小寫有區(qū)別

NUM = ([1-9][0-9]*)|([0-9]) ??????//存疑，可改為[0-9]+

4)?不可見字符是由空白、制表符組成。它通常被忽略，但可以用來分開ID、NUM關(guān)鍵字。表達(dá)式結(jié)束符“;”是一種界限符，用來區(qū)分不同的語句。另外小括號(hào)在C語言中是一種界限符，用來區(qū)分句子的成分，但在Tiny語言中由于只用于表達(dá)式，不算作界限符。注釋用{...}圍起來，且不能嵌套，其中花括號(hào)也是界限符。

2.2 TINY語言詞法分析程序設(shè)計(jì)

所有單詞對應(yīng)的DFA:

?

?

PS：思考一下，這正確嗎？里面有沒有bug？

考慮下面問題：

問題1：應(yīng)設(shè)置多少種單詞？

理論上應(yīng)設(shè)置5類單詞（參見書或課件PPT），但為了方便起見，可以直接把if, then, else, end, repeat, until, read, write，+ ， - ， * ， / ， = ， < ， ( ， )， ; ， :=，ID，NUM分別當(dāng)做一類單詞，共20類。

?

問題2：在識(shí)別字母串構(gòu)成的單詞后，如何區(qū)分是標(biāo)識(shí)符還是保留字？

可以預(yù)設(shè)一張保留字表，通過查找保留字表來確定是保留字還是標(biāo)識(shí)符。

PS：思考一下，除了這個(gè)方法，還能怎么做？

答：超前搜索和預(yù)處理。

?

問題3：和語法分析程序用什么形式的接口，返回的信息應(yīng)包含什么？

詞法分析和語法分析的接口是函數(shù)接口，即詞法分析程序提供一個(gè)函數(shù)TokenType?getToken(void)提供給語法分析調(diào)用，此函數(shù)每調(diào)用一次識(shí)別出一個(gè)單詞，返回值為單詞種別碼，單詞屬性值放在全局變量char?tokenString[MAXTOKENLEN?+ 1]中。其中，除了標(biāo)識(shí)符和無符號(hào)整數(shù)外，其余單詞只有種別碼，沒有單詞屬性值，標(biāo)識(shí)符的單詞屬性值是字符串，無符號(hào)整數(shù)的單詞屬性值是整數(shù)值。

?

三、實(shí)驗(yàn)要求

（1）讀懂源代碼，添加注釋，補(bǔ)充空白處的代碼

（2）根據(jù)DFA設(shè)計(jì)單詞掃描程序，輸出單詞流。源代碼作為輸入舉例

例1： 源代碼一：求階乘

?

例2：?源代碼二：求最大公約數(shù)

?

填充代碼：

else if (c == '{')

{

//代碼一： 填充代碼

save = FALSE;

state = INCOMMENT; ? ? ? ? ?

}

?

case INASSIGN:

{

//代碼二：補(bǔ)充此代碼

if(c == '=')

{

state=DONE;

currentToken = ASSIGN;

}

else

{

state = DONE;

save = FALSE;

} ?

}

break;

?

需要修改的兩處bug：一處在START是’_’不被算入INID，另一處是在INID讀到’_’或數(shù)字不被算入INID

（1）第一處bug：

在case START中加入一下代碼

else if (c == '_') ? ?

state = INID;

?

（2）第二處bug：

case INID:

if (!isalpha(c))

{

if (isdigit(c))

state = INID;

else if (c == '_')

state = INID;

else

{

ungetNextChar();

save = FALSE;

state = DONE;

currentToken = ID;

}

}

?

求階乘的輸出結(jié)果如下：

?

?

求最大公約數(shù)的輸出結(jié)果如下：

?

?

?

項(xiàng)目2~3使用lex構(gòu)建詞法分析器

一、目的與要求?

?１）目的?

?通過lex工具構(gòu)建調(diào)試詞法分析程序，實(shí)現(xiàn)從源程序中分出各種單詞的方法；加深對課堂教學(xué)的理解；提高詞法分析方法的實(shí)踐能力。?

?２）要求?

• 掌握從源程序文件中讀取有效字符的方法和產(chǎn)生源程序的內(nèi)部表示文件的方法。?

• 掌握詞法分析的實(shí)現(xiàn)方法。

• 掌握lex代碼生成工具的使用

二、說明?

?2.1lex生成代碼的過程

?

2.2Lex輸入文件的格式

{

definition //定義集

1)必須插入的任何函數(shù)之外的代碼段(以%{, %}作為開始、結(jié)束標(biāo)記)，比如變量說明，常量說明等

2)正規(guī)式定義

}

%%

{

rules //規(guī)則集合

形如：{正規(guī)式} { 用C代碼表示的語義動(dòng)作}

?{line} {printf(“%5d%s”,lineno++,yytext);}

?

}

%%

{

auxiliary routines//輔助部分：在規(guī)則部分被調(diào)用且不在任何地方被定義的輔助程序

main()

{yylex();return(0)}

?

}

?

2.3Lex使用的幾點(diǎn)說明

（1）Lex 的常規(guī)表達(dá)式

（2）常規(guī)表達(dá)式舉例

?

（3）標(biāo)記聲明舉例

?

（4）lex常用變量和函數(shù)

?

三、實(shí)驗(yàn)要求

修改上面的文件內(nèi)容，完成單詞個(gè)數(shù)統(tǒng)計(jì)功能，例如對如下輸入：

?

{ Sample program

??in TINY language -

??computes factorial

}

read x; { input an integer }

if 0 < x then { don't compute if x <= 0 }

??fact := 1;

??repeat

????fact := fact * x;

????x := x - 1

??until x = 0;

??write fact ?{ output factorial of x }

end

輸出為：

if 1

then 1

else 0

end 1

repeat 1

until 1

read 1

write 1

ID 10

NUM 4

:= 3

= 1

< 1

+ 0

- 1

* 1

/ 0

( 0

) 0

; 5

ERROR 0

?

項(xiàng)目二：

補(bǔ)充代碼1：

"=" ? ?{ return EQ; }

補(bǔ)充代碼2：

{ "write", ?WRITE ??}

補(bǔ)充代碼3：

case LT: ?????????

printf("line%2d: ?%-6d%-10s%s\n",lineno, LT,"LT", "<");

break;

?

測試用例運(yùn)行結(jié)果如下：

Test1：

?

Test2：

項(xiàng)目三：

需要填的代碼的作用是記錄符號(hào)的個(gè)數(shù)，因此設(shè)置其對應(yīng)數(shù)量+1

":=" ? { ?count[ASSIGN]++; }

"=" ? ?{ ?count[EQ]++; }

"<" ? ?{ ?count[LT]++; }

"+" ? ?{ ?count[PLUS]++; }

"-" ? ?{ ?count[MINUS]++; }

"*" ? ?{ ?count[TIMES]++; }

"/" ? ?{ ?count[OVER]++; }

"(" ? ?{ ?count[LPAREN]++; }

")" ? ?{ ?count[RPAREN]++; }

";" ? ?{ ?count[SEMI]++; }

{num} ??????????{ ?count[NUM]++; ??}

. ? ?{ ?count[ERROR]++; }

?

測試用例運(yùn)行結(jié)果：

Test1：

Test2：