項(xiàng)目4 使用遞歸下降法手動(dòng)構(gòu)建語法分析器

一、目的與要求 ?

??１）目的 ?

???通過設(shè)計(jì)、編制、調(diào)試一個(gè)確定的自頂向下語法分析程序，實(shí)現(xiàn)對(duì)詞法分析程序所提供的單詞序列進(jìn)行語法檢查和結(jié)構(gòu)分析，并建立相應(yīng)的語法樹，進(jìn)一步掌握常用的語法分析方法。?

??２）要求 ?

用遞歸下降法分析、設(shè)計(jì)和實(shí)現(xiàn)TINY語言源程序的語法分析程序。

輸入：?jiǎn)卧~序列

輸出：語法樹（語法正確），有語法錯(cuò)誤，則報(bào)錯(cuò)

二、語法分析說明 ?

TINY語言的文法：

中文描述：

文法的定義可以看出，TINNY語言有以下特點(diǎn)：

1)?程序共有5種語句：if語句，repeat語句，read語句，write語句和assign語句。

2)?if語句以end作為結(jié)束符號(hào)，if語句和repeat語句允許語句序列作為主體。

3)?輸入/輸出由保留字read和write開始。read語句一次只讀出一個(gè)變量，而write語句一次只寫出一個(gè)表達(dá)式。

三、語法樹的設(shè)計(jì)

1)?TINY有兩種基本的結(jié)構(gòu)類型：語句和表達(dá)式。語句共有5類：（if語句、repeat語句、assign語句、read語句和write語句），表達(dá)式共有3類（算符表達(dá)式、常量表達(dá)式和標(biāo)識(shí)符表達(dá)式）。因此，語法樹節(jié)點(diǎn)首先安裝它是語句還是表達(dá)式來進(jìn)行分類，接著根據(jù)語句或表達(dá)式的種類進(jìn)行再次分類。

2)?樹節(jié)點(diǎn)最大可有3個(gè)孩子的結(jié)構(gòu)（僅在帶有else部分的if 語句才用到）。同一級(jí)的語句通過同屬域而不是子域來排序，孩子則在一個(gè)標(biāo)準(zhǔn)連接表中自左向右連接到一起，這種連接稱作同屬連接,用于區(qū)別父子連接。?

（1）if 語句（帶有3個(gè)可能的孩子）如下所示：

（2）repeat 語句有兩個(gè)孩子。第1個(gè)是表示循環(huán)體的語句序列，第2個(gè)是一個(gè)測(cè)試表達(dá)式：

（3） assign 語句有一個(gè)表示其值是被賦予的表達(dá)式的孩子（被賦予的變量名保存在語句節(jié)點(diǎn)中）：

??

（4） write 語句也有一個(gè)孩子，它表示要寫出值的表達(dá)式：

?? ?

（5）Read語句，沒有孩子

?

（6）表達(dá)式有兩個(gè)孩子，它們表示左操作數(shù)表達(dá)式和右操作數(shù)表達(dá)式：

?

3)?一個(gè)Tiny語法樹節(jié)點(diǎn)的C聲明如下：

?

typedef enum {StmtK,ExpK} NodeKind;

typedef enum {IfK,RepeatK,AssignK,ReadK,WriteK} StmtKind;

?

/* ExpType is used for type checking */

typedef enum {Void,Integer,Boolean} ExpType;

?

#define MAXCHILDREN 3

?

typedef struct treeNode{

?struct treeNode * child[MAXCHILDREN];

?????struct treeNode * sibling;

?????int lineno;

?????NodeKind nodekind;

?????union { StmtKind stmt; ExpKind exp;} kind;

?????union {

TokenType op;

??????????????int val;

??????????????char * name; } attr;

???} TreeNode;

4)?下面畫出語法樹的結(jié)構(gòu)，用矩形框表示語句節(jié)點(diǎn)，用圓形框或橢圓形框表示表達(dá)式節(jié)點(diǎn)。仍然以Tiny語言的階乘為例，給出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

四、?用遞歸下降法進(jìn)行語法分析程序的設(shè)計(jì)實(shí)現(xiàn)

遞歸下降法的實(shí)現(xiàn)思想就是對(duì)應(yīng)文法中的每個(gè)非終結(jié)符，編寫一個(gè)遞歸過程，每個(gè)過程的功能是識(shí)別該非終結(jié)符推出的串。當(dāng)某個(gè)非終結(jié)符的產(chǎn)生式有多個(gè)候選時(shí)能夠按照LL（1）的形式唯一地確定選擇某個(gè)候選進(jìn)行推導(dǎo)。

構(gòu)造遞歸下降分析程序時(shí)，每個(gè)函數(shù)名是相應(yīng)的非終結(jié)符，函數(shù)體根據(jù)產(chǎn)生式規(guī)則右部符號(hào)串的結(jié)構(gòu)編寫，基本思路如下：

（1）?當(dāng)遇到終結(jié)符a時(shí)，則編寫語句：

If （當(dāng)前讀來的輸入符號(hào)==‘a(chǎn)’）讀入下一個(gè)輸入符號(hào)

（2）?當(dāng)遇到非終結(jié)符A時(shí)，則編寫語句調(diào)用A()

（3）?當(dāng)遇到A?e產(chǎn)生式規(guī)則時(shí)，則編寫語句：

If（當(dāng)讀來的輸入符號(hào)不屬于Follow(A)）error()

（4）?當(dāng)某個(gè)非終結(jié)符有多個(gè)候選產(chǎn)生式規(guī)則時(shí)，則：

if（當(dāng)前讀來的輸入符號(hào)屬于Select(ai)）則按規(guī)則A?ai進(jìn)行推導(dǎo)

?

1）對(duì)于產(chǎn)生式

< STMT-SEQUENCE > ?::= ??<STMT-SEQUENCE> ??;? ?<STATEMENT>

? ????| <STATEMENT>

?

產(chǎn)生的句型應(yīng)該是：??< STATEMENT >?;?<STATEMENT> ;?<STATEMENT> …..

產(chǎn)生的樹結(jié)點(diǎn)： ?

?

我們可以構(gòu)造出對(duì)應(yīng)的程序：

TreeNode* stmt_sequence(void)

{

TreeNode* t = statement();

TreeNode* p=t;

while(token==SEMI)

{

match(SEMI);

TreeNode* t1=statement();

p->sibling = t1;

p=t1;

}

return t;

}? ?

(2)???STATEMENT? ?:= ?<IF-STMT> ?| ?<REPEAT-STMT> ?

| <ASSIGN-STMT> | <READ-STMT>

| ?<WRITE-STMT>

?

?

static TreeNode* statement()

{

TreeNode * t = NULL;

switch (token)

{

case IF: t = if_stmt(); break;

case REPEAT: t = repeat_stmt(); break;

case ID: t = assign_stmt(); break;

case READ: t = read_stmt(); break;

case WRITE: t = write_stmt(); break;

default:

{

???char t[100];

???sprintf(t, "unexpected token： %s", tokenString);

???syntaxError(t);

}

}

return t;

}

< REPEAT-STMT > ::= repeat???<STMT-SEQUENCE> ?until ??<EXP>

?

?

< SIMPLE-EXP> ?::= ?<SIMPLE-EXP> ?+ - ??<TERM>

?| ?<TERM>

產(chǎn)生的句型：<TERM> + | - <TERM> + | -<TERM>

?

表達(dá)式：a+b-c+30

?

五、出錯(cuò)處理

錯(cuò)誤處理的任務(wù)：（1）報(bào)錯(cuò)，發(fā)現(xiàn)錯(cuò)誤時(shí)應(yīng)盡可能準(zhǔn)確指出錯(cuò)誤位置和錯(cuò)誤屬性（2）錯(cuò)誤恢復(fù)，盡可能進(jìn)行校正，使編譯工作可以繼續(xù)下去，提高程序調(diào)試的效率。為了簡(jiǎn)單，本語法分析程序的出錯(cuò)處理為報(bào)告出錯(cuò)的行數(shù)，程序退出。

本實(shí)驗(yàn)采用的出錯(cuò)處理簡(jiǎn)單的處理為：一旦發(fā)生錯(cuò)誤，就報(bào)錯(cuò)后編譯停止

四、實(shí)驗(yàn)內(nèi)容

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

（2）測(cè)試求階乘的編程示例s.tiny ,輸出語法樹

?

{ 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

（3）測(cè)試編譯gcd.tiny ，如果有語法錯(cuò)誤，請(qǐng)修改語法后，輸出語法樹

?

{

????求最大公約數(shù)

}

read m; { input an integer }

read n;

?

if m<n then { 將大數(shù)放入m中，小數(shù)放入n中}

t:=m;

m:=n;

n:=t;

end

?

repeat

q:=m/n;

r=m-q*n;

m:=n;

n:=r;

填充代碼1：

TreeNode* if_stmt() ?

{

? ? // ?【代碼1】 ?填充此代碼

????TreeNode?*t?=?newStmtNode(IfK);

????match(IF);

????t->child[0]?=?exp_stmt();

????match(THEN);

????t->child[1]?=?stmt_sequence();

????if(token==END)

????{

????????match(END);

????????return?t;

????}

????if(token==ELSE)

????{

????????match(ELSE);

????????t->child[2]?=?stmt_sequence();

????????match(END);

????????return?t;

????}

????return?NULL;

?}

TreeNode* read_stmt()

{

? ? // ?【代碼2】 ?填充此代碼

????TreeNode?*t?=?newStmtNode(?ReadK);

????match(READ);

????char*?idname=?copyString(tokenString);

????match(ID);

????t->attr.name=idname;

????return?t;

}

?

static TreeNode* term()

{

? ? // ?【代碼3】 ?填充此代碼

????TreeNode?*t?=?factor();

????while(token==TIMES||token==OVER)

????{

???????TreeNode?*p?=?newExpNode(OpK);

???????p->child[0]?=?t;

???????p->attr.op?=?token;

???????match(token);

???????TreeNode?*q?=?factor();

???????p->child[1]?=?q;

???????t=p;

????}

????return?t;

}

?

運(yùn)行結(jié)果

Test1：

?

Test2：