編譯原理何炎祥視頻

『壹』 武大計算機系考研參考書

這是武大研究生招生網上的信息

211 計算機學院

922 計算機基礎（含數據結構、計算機組成原理）：
李春葆：《數據結構教程》（第一版），清華大學出版社2005年版
王愛英：《計算機組成與結構》（第三版），清華大學出版社2001年版
916 計算機圖形學基礎：
唐澤聖、周嘉玉、李新友編著：《計算機圖形學基礎》，清華大學出版社
917 C語言程序設計：
唐浩強著：《C語言程序設計》，清華大學出版社

復試科目參考書目：
資料庫原理：
尹為民：《現代資料庫系統及應用教程》，武漢大學出版社2005年版
操作系統：
黃水松：《計算機操作系統》，武漢大學出版社2003年版

加試科目參考書目：
編譯原理：
何炎祥：《編譯原理》（第二版），華中科技大學出版社2005年版
離散數學：
劉玉珍：《離散數學》（第二版），武漢大學出版社2002年版

『貳』 循環語句的語法分析及語義分析程序設計

目 錄
1 課程任務書····································（2）
1問題描述·······································（3）
2文法及屬性文法的描述···························（3）
2.1 while-do循環語句的文法·····················（3）
2.2while-do循環語句的結構翻譯·················（3）
3語法分析及中間代碼形式的描述···················（4）
3.1 語法分析方法·······························（4）
3.2 中間代碼形式描述···························（4）
4簡要的分析與概要設計···························（5）
4.1詞法分析··································（5）
4.2遞歸下降翻譯器的設計·······················（5）
4.3語法制導翻譯·······························（5）
5 詳細的演算法描述································（6）
5.1 文法·······································（6）
5.2 查錯·······································（6）
6 測試方法和測試結果···························（9）
6.1測試方法··································（9）
6.2測試結果··································（10）
7 設計的特點、不足、收獲與體會·················（10）
7.1 設計的特點································（10）
7.2 不足、收獲與體會··························（11）
8 參考文獻·····································（11）

課程設計任務書
題 目: 循環語句的語法分析及語義分析程序設計（遞歸下降法）
1．目的
通過設計、編制、調試一個語法及語義分析程序，加深對語法及語義分析原理的理解。

2.設計內容及要求
WHILE〈布爾表達式〉DO〈賦值語句〉
其中
（1）學號29至32的同學按順序分別選擇遞歸下降法、LL（1）、算符優先分析法（或簡單優先法）、LR法完成以上任務，中間代碼選用四元式。
（2）如1題寫出符合分析方法要求的文法，給出分析方法的思想，完成分析程序設計。
（3）編制好分析程序後，設計若干用例，上機測試並通過所設計的分析程序。

3.課程設計報告書的內容應包括：
1.設計題目、班級、學號、姓名、完成日期；
2.給出語法分析方法及中間代碼形式的描述、文法和屬性文法的設計；或者詞法分析方法
3.及符號表和TOKEN代碼的設計。
4.簡要的分析與概要設計；
5.詳細的演算法描述；
6.源程序清單；
7.給出軟體的測試方法和測試結果；
8.設計的評價、收獲與體會。

4.時間安排：
第17周，周1-周4上午，周五全天

指導教師簽名： 年 月 日
系主任（或責任教師）簽名： 年 月 日

1問題描述
設計一個WHILE〈布爾表達式〉DO〈賦值語句〉循環語句的詞法﹑語法及語義分析程序，語法分析選擇遞歸下降法，採用用語法制導翻譯輸出中間代碼四元式。
2文法及屬性文法的描述。
2.1 while-do循環語句的文法
產生式為S-> while E do A，為便於語法制導翻譯將其改寫如下：
文法G(s)如下：
S-->WEDG （意思是while E do G）
G-->c=R
R-->dTe|d
T-->+|-|*|/
E-->aFb
F--> >|==|<

2.2 whlie-do循環語句的結構翻譯：

3.語法分析方法及中間代碼形式的描述
3.1語法分析方法
遞歸下降法的實現思想是為文法的每個非終結符號設計一個相對應的遞歸子程序，識別程序由一組這樣的子程序組成。
它的優點是簡單直觀，易於構造，很多編譯系統所實現
缺點是對文法要求很高，由於遞歸調用多，影響分析器的效率
其文法可以表示為：
E→T│E+T
T→F│T*F
F→i│（E）
可以用語法圖來表示語言的文法，如圖：

E

T

F

3.2中間代碼形式描述
中間代碼採用四元式輸出，一個四元式是一個帶有四個域的記錄結構，這四個域分別稱為op﹑arg1﹑arg2及result。域op包含一個代表運算符的內部碼。語句while a<b do a=a+b的四元式輸出形式如下：
100 ( <, a , b , 102 )
101 ( j , _ , _ , 105 )
102 ( + , a , b , n )
103 ( = , n , _ , a )
104 ( j , _ , _ , 100)
105
4．簡要的分析與概要設計
4.1詞法分析
詞法分析程序的任務是：從左至右逐個字元地對源程序進行掃描，產生一個個的單詞符號，把作為字元串的源程序改造成為單詞符號的中間程序。詞法分析檢查的錯誤主要是挑出源程序中出現的非法符號。所謂非法符號是指不是程序設計語言中允許出現的符號，就像自然語句中的錯字。
4.2遞歸下降翻譯器的設計
1.：對每個非終結符A構造一個函數過程，對A的每個繼承屬性設置一個形式參數，函數的返回值為A的綜合屬性，A對應的函數過程中，為出現在A的產生式中的每一個文法符號的每一個屬性都設置一個局部變數。非終結符A對應的函數過程中，根據當前的輸入符號決定使用哪個產生式候選。
2：每個產生式對應的程序代碼中，按照從左到右的次序，對於單詞符號，非3：終結符和語義動作分別做以下工作。
（1）對於帶有綜合屬性x的終結符X，把x的值存入為X，x設置的變數中。然後產生一個匹配X的調用，並繼續讀入一個輸入符號。
（2）對於每個非終結符號B，產生一個右邊帶有函數調用的賦值語句c=B(b1,b2,…，bk)
（3）對於語義動作，把動作的代碼抄進分析器中，用代表屬性的變數來代替對應屬性的每一次引用。
4.3語法制導翻譯
在語法分析過程中，隨著分析的步步進展，根據每個產生式所對應的語義子程序（或語義規則描述的語義動作）進行翻譯。屬性文法的每個符號有屬性，所以每個符號入棧時，必須連屬性一起入棧，這樣，棧符號就由文法符號及存放該符號屬性的域所組成。由於屬性類型不同，屬性域存放的內容就要根據屬性的類型來定。有的可能直接存放屬性值，也有的存放的是指向屬性值的指針。對於綜合屬性，其屬性域不存放其屬性值，而是存放一個指針，指向存貯該屬性值的單元。對於繼承屬性，其屬性域直接保存其屬性值。繼承屬性的屬性域剛入棧時為空，但是在該棧符號變成棧頂符號之前的某一時刻，它們必須接受相應的屬性值，即在成為棧頂時，繼承屬性的屬性域必須有值。
5詳細的演算法描述
5.1 文法
/*
文法G(s)
s-->WEDG
G-->c=R
R-->dTe|d
T -> +|-|*|/|%E-->aFb
F--> >|==|<
*/
5.2 查錯
按照遞歸下降法求Wa<bDa=a+b，程序的執行順序應該是S()W()EF()D()G()R()T()
S()
void S()
{
printf("%d\tS-->WEDG\n",total);total++;
W();
E();
}

W()
void W()
{
if(ch!='W')
{
printf("有非法字元%c請按回車返回!!",ch);
getchar();
getchar();
exit(1);
}
}

E()
void E()
{
ch=a[++i1];
if(ch!='a')
{
printf("有非法字元%c %c請按回車返回!!",ch);
getchar();
getchar();
exit(1);
}
printf("%d\tE-->aFb\n",total);total++;
F();
}

F()
void F()
{
int i;
ch=a[++i1];
i=i1+1;
if(a[i]!='b')
{
printf("有非法字元%c請按回車返回!!",a[i]);
getchar();
getchar();
exit(1);
}
switch(ch)
{
case '>':
printf("%d\tF-->>\n",total);total++;
break;
case '==':
printf("%d\tF-->==\n",total);total++;
break;
default:
printf("%d\tF--><\n",total);total++;
break;
}
D();
G();
}

D()
void D()
{
++i1;
ch=a[++i1];
if(ch!='D')
{
printf("有非法字元%c請按回車返回!!",ch);
getchar();
getchar();
exit(1);}
ch=a[++i1];
}

G()
void G()
{
int i=i1+1;
if(ch!='c'&&a[i]!='=')
{
printf("有非法字元%c %c請按回車返回!!",ch,a[i]);
getchar();
getchar();
exit(1);
}
printf("%d\tG-->c=R\n",total);total++;
R();
}

R()
void R()
{
int i;
i=i1+1;
i1=i1+2;
ch=a[i1];
if(a[i]!='='&&ch!='d')
{
printf("有非法字元%c %c請按回車返回!!",a[i],ch);
getchar();
getchar();
exit(1);
}
else
{
if((a[i1+1]=='+')||(a[i1+1]=='-')||(a[i1+1]=='*')||(a[i1+1]=='/'))
{
printf("%d\tR-->dTe\n",total);total++;
T();
}
else
{
printf("%d\tR-->d\n",total);total++;
W();
E();
}
}
}

T()
void T()
{
ch=a[++i1];
switch(ch)
{
case '+':
printf("%d\tT-->+\n",total);total++;
break;
case '-':
printf("%d\tT-->-\n",total);total++;
break;
case '*':
printf("%d\tT-->*\n",total);total++;
break;
default:
printf("%d\tT-->/\n",total);total++;
break;
}
ch='#';
}

6測試方法和測試結果
6.1測試方法
在C++環境下，設計幾個有代表的用例，進行測試，例如：輸入語句Wa<bDa=a+b#(其中d表示do ,w表示while)。若得出的不是預期的結果，那麼程序就出現問題。如果有問題的話就進行單步調試找到程序中出現的邏輯問題。

6.2測試結果
測試結果如下：

7設計的特點、不足、收獲與體會
7.1設計的特點
本次設計是採用遞歸下降的方法對輸入的while--do 循環語句進行語法，語義分析，並輸出四元式。因此程序中充分體現了遞歸下降的思想。

7.2設計的不足，收獲與體會
本次的設計的不足主要是我沒將程序一般化，實現不了用戶自動輸入代碼進行詞法分析的四元式輸出，此程序只能實現對Wa<bDa=a+b#的分析與四元式輸出，由於我所設計的棧中只能一個字元一個字元的存放，因此只能用D W分別表示do while；而且我對語法制導翻譯這一塊很不熟悉，因此我始終不能用程序實現語法制導翻譯輸出四元式，於是根據自己的理解，直接把四元式寫了出來。
本次課程設計鞏固了我所學習的關於遞歸下降法這一方面的知識，並且使我對WHILE—DO循環語句也有了更深刻的理解,提高了我的動手能力。

8 課程設計參考資料
1張幸兒 《編譯原理》（第二版）清華大學出版社
2何炎祥 《編譯原理》華中理工大學出版社
3陳火旺 《程序設計語言編譯原理》（第3版）國防工業出版社

本科生課程設計成績評定表
班級：軟體0701姓名：周璐萍學號：0120710680129
序號 評分項目 滿分 實得分
1 學習態度認真、遵守紀律 10
2 設計分析合理性 10
3 設計方案正確性、可行性、創造性 20
4 設計結果正確性 40
5 設計報告的規范性 10
6 設計驗收 10
總得分/等級
評語：

註：最終成績以五級分制記。優（90-100分）、良（80-89分）、中（70-79分）、
及格（60-69分）、60分以下為不及格
源程序
#include <stdio.h>
#include<dos.h>
#include<stdlib.h>
#include<string.h>

char a[50],g[50][50];
char ch;
int n1,i1=0,i2=0;
int total=0;

void S();
void D();
void G();
void W();
void E();
void R();
void T();
void F();

void main()
{
int j=0;

printf("文法G(s)為:\n");
printf("s-->DGWE\n");
printf("G-->c=R\n");
printf("R-->dTe|d\n");
printf("T-->+|-|*|/\n");
printf("E-->aFb\n");
printf("F--> >|==|<\n");

printf("請輸入while-do語句(D代表do,W代表while),並以#結束:\n");
do{
scanf("%c",&ch);
a[j]=ch;
j++;
}while(ch!='#');
n1=j;
ch=a[0];

S();
printf("\n");

if (ch=='#')
{ printf("輸出四元式為：\n");
printf("100 (<,a,b,102)\n");
printf("101 (j,_,_,105)\n");
printf("102 (+,a,b,n)\n");
printf("103 (=,n,_,a)\n");
printf("104 (j,_,_,100)\n");
printf("105 \n");

}

else {

printf("error\n");

printf("press any key to continue..\n");

getchar();getchar();

return;

}

printf("\n");

printf("press any key to continue..\n");

getchar();
getchar();
}

/*出錯情況分析*/

void S()
{
printf("%d\tS-->WEDG\n",total);total++;
W();
E();
}

void W()
{

if(ch!='W')
{
printf("有非法字元%c請按回車返回!!",ch);
getchar();
getchar();
exit(1);
}
}

void E()
{
ch=a[++i1];
if(ch!='a')
{
printf("有非法字元%c %c請按回車返回!!",ch);
getchar();
getchar();
exit(1);
}
printf("%d\tE-->aFb\n",total);total++;
F();
}

void F()
{
int i;
ch=a[++i1];
i=i1+1;
if(a[i]!='b')
{
printf("有非法字元%c請按回車返回!!",a[i]);
getchar();
getchar();
exit(1);
}
switch(ch)
{
case '>':
printf("%d\tF-->>\n",total);total++;

break;
case '==':
printf("%d\tF-->==\n",total);total++;

break;
default:
printf("%d\tF--><\n",total);total++;

break;

}
D();
G();
}

void D()
{ ++i1;
ch=a[++i1];
if(ch!='D')
{ printf("有非法字元%c請按回車返回!!",ch);
getchar();
getchar();
exit(1);}
ch=a[++i1];

}

void G()
{ int i=i1+1;

if(ch!='c'&&a[i]!='=')
{ printf("有非法字元%c %c請按回車返回!!",ch,a[i]);
getchar();
getchar();
exit(1);}
printf("%d\tG-->c=R\n",total);total++;
R();
}

void R()
{
int i;
i=i1+1;
i1=i1+2;
ch=a[i1];
if(a[i]!='='&&ch!='d')
{
printf("有非法字元%c %c請按回車返回!!",a[i],ch);
getchar();
getchar();
exit(1);
}
else
{
if((a[i1+1]=='+')||(a[i1+1]=='-')||(a[i1+1]=='*')||(a[i1+1]=='/'))
{
printf("%d\tR-->dTe\n",total);total++;

T();

}
else
{
printf("%d\tR-->d\n",total);total++;

W();
E();
}
}

}

void T()
{
ch=a[++i1];
switch(ch)
{
case '+':
printf("%d\tT-->+\n",total);total++;

break;
case '-':
printf("%d\tT-->-\n",total);total++;

break;
case '*':
printf("%d\tT-->*\n",total);total++;

break;

default:
printf("%d\tT-->/\n",total);total++;

break;
}
ch='#';

}

指導教師簽名：
2010 年月日

『叄』 我想報考東華大學的計算機應用技術，請各位給點意見

東華的優點在於地處上海，分數還比較低，一般都是國家線。