實作遞歸下降分析器
- 實驗内容
- 開發環境
- 資料結構
-
- 1 符号棧
- 2 分析過程
- 3 數組
- 實驗步驟
-
- 分析與設計
- 程式設計
-
- 1 全局變量
- 2 棧
- 3 數組
- 4 函數
- 5 僞代碼
- 運作與調試
- 運作結果
- 所遇問題與解決方案
-
- 1 E’和T’的壓棧
- 2 棧的實作
- 心得體會
- 實驗代碼
-
- 1 主函數main()
- 2 E()
- 3 E1()
- 4 T()
- 5 T1()
- 6 F()
- 7 print()
實驗内容
用進階語言實作課本3.2文法的遞歸下降分析程式。
要求：
可使用書上提供的輸入串i1*(i2+i3)，也可以是自己定義的其他符号串；輸出棧中所有内容，并給出分析結果。
開發環境
windows 10
visual studio 2019
資料結構
1 符号棧
棧是一種有存取限制的線性表，它隻允許在一端進行插入或删除操作。遵循“先進先出”原則。
遞歸下降分析法是一種自頂向下的分析方法，文法的每個非終結符對應一個遞歸過程（函數），可用棧來表示分析過程。
2 分析過程
| 序号 | 符号棧 | 待分析字元 | 表達式 |
|---|---|---|---|
| # | i*(i+i)# | ||
| 1 | #E | i*(i+i)# | E→TE’ |
| 2 | #E’T | i*(i+i)# | T→FT’ |
| 3 | #E’T’F | i*(i+i)# | F→i |
| 4 | #E’T’ | i*(i+i)# | T’→*FT’ |
| 5 | #E’T’F | i*(i+i)# | F→(E) |
| 6 | #E’T’E | i*(i+i)# | E→TE’ |
| 7 | #E’T’E’T | i*(i+i)# | T→FT’ |
| 8 | #E’T’E’T’F | i*(i+i)# | F→i |
| 9 | #E’T’E’T’ | i*(i+i)# | T’→ε |
| 10 | #E’T’E’ | i*(i+i)# | E’→+TE’ |
| 11 | #E’T’E’T | i*(i+i)# | T→FT’ |
| 12 | #E’T’E’T’F | i*(i+i)# | F→i |
| 13 | #E’T’E’T’ | i*(i+i)# | T’→ε |
| 14 | #E’T’E’ | i*(i+i)# | E’→ε |
| 15 | #E’T’ | i*(i+i)# | T’→ε |
| 16 | #E’ | i*(i+i)# | E’→ε |
| 17 | # |
3 數組
1、分析串數組char token[token_size]：存放待分析串。
2、符号棧char stack[10] = {’#’}：存放符号棧内容，初始壓入‘#’。
實驗步驟
分析與設計
教材上的例題已然分析地較詳細：
1、 已消除左遞歸。
2、 無回溯。
我們直接進行遞歸下降分析器的構造。
程式設計
1 全局變量
① token_len：int類型變量，存放待分析串的長度。
② step：int類型變量，記錄目前分析步數。
2 棧
① char stack[10] = {’#’}：char類型數組，存放符号棧内容，初始壓入‘#’。
② stack_top：int類型變量，為符号棧的棧頂指針。
3 數組
token[token_size]：cha類型數組，存放待分析串。
4 函數
① 非終結符表達式：
void E();
void E1();
void T();
void T1();
void F();
② 列印函數：void print()。
5 僞代碼
見《編譯原理教程（第四版）》P52-53
void match(token t){
if (lookahead == t)
lookahead = nexttoken;
else
error();
}
void E(){
T();
E();
}
void E'(){
if (lookahead == '+'){
match('+');
T();
E'();
}
}
void T(){
F();
T'();
}
void T'(){
if (lookahead == '*'){
match('*');
F();
T'();
}
}
void F(){
if (lookahead == 'i')
match('i');
else if (lookahead == '('){
match('(');
E();
if (lookahead == ')')
match(')');
else
error();
}
else
error();
}
運作與調試
根據調試情況進行相應的代碼修改。
運作結果
所遇問題與解決方案
1 E’和T’的壓棧
因為E’不屬于一個字元，在考慮存放的時候本來是準備實作字元串數組的，問題有點多，是以就直接按照’E’和’\’’兩個字元來存儲E’了，T’同理。
2 棧的實作
心得體會
對遞歸下降分析器的構造有了更深的了解，也更熟練地掌握了棧的實作。
實驗代碼
1 主函數main()
int main(void){
printf("請輸入字元串（以#結束）:"); //輸入待分析字元串
while (token[lookahead] != '#'){ //如果沒有按下#結束
char scan_char; //掃描字元
do{ //若沒有掃描到結束符#，就繼續掃描
scanf_s("%c", &scan_char,1);
token[token_len] = scan_char; //将掃描到的字元儲存到待分析串數組中
token_len++;
} while (scan_char != '#');
printf("\n");
printf("序号\t");
printf("符号棧\t\t");
printf("待分析字元\t");
printf("表達式\n");
print(); //列印目前步驟資訊
printf("\n"); //換行
stack[++stack_top] = 'E'; //将E()壓入棧中，開始分析
step++; //分析步數+1
E();
if (token[lookahead] == '#') //若待分析字元為#，說明符合文法
printf("\n分析成功，合法字元串!");
else
printf("\n分析失敗，非法字元串!");
}
return 0;
}
2 E()
/*****************************************************************************
*函數名稱：E()
*函數類型：void
*參數：void
*功能：分析文法，輸出資訊
*****************************************************************************/
void E(){
print(); //列印目前步驟資訊
printf("E->TE'\n"); //輸出表達式
stack[stack_top] = 'E'; //将産生式右→左壓棧
stack[++stack_top] = '\''; //代表E'
stack[++stack_top] = 'T';
step++; //分析步數+1
T();
E1();
}
3 E1()
/*****************************************************************************
*函數名稱：E1()
*函數類型：void
*參數：void
*功能：分析文法，輸出資訊
*****************************************************************************/
void E1(){
if (token[lookahead] == '+'){ //若待分析字元比對‘+’
print(); //列印目前步驟資訊
printf("E'->+TE'\n"); //輸出表達式
stack[--stack_top] = 'E'; //将産生式右→左壓棧
stack[++stack_top] = '\'';
stack[++stack_top] = 'T';
step++; //分析步數+1
lookahead++; //因為比對到一個終結符，是以分析下一個字元
T();
E1();
}
else{
print(); //列印目前步驟資訊
printf("E'->ε\n"); //輸出表達式
stack[stack_top--] = NULL; //出棧
stack[stack_top--] = NULL; //E'雖然為一個非終結符，但占兩個字元，T'同
step++; //分析步數+1
}
}
4 T()
/*****************************************************************************
*函數名稱：T()
*函數類型：void
*參數：void
*功能：分析文法，輸出資訊
*****************************************************************************/
void T(){
print(); //列印目前步驟資訊
printf("T->FT'\n"); //輸出表達式
stack[stack_top] = 'T'; //将産生式右→左壓棧
stack[++stack_top] = '\'';
stack[++stack_top] = 'F';
step++; //分析步數+1
F();
T1();
}
5 T1()
/*****************************************************************************
*函數名稱：T1()
*函數類型：void
*參數：void
*功能：分析文法，輸出資訊
*****************************************************************************/
void T1(){
if (token[lookahead] == '*'){ //若待分析字元比對‘*’
print(); //列印目前步驟資訊
printf("T'->*FT'\n"); //輸出表達式
stack[--stack_top] = 'T'; //将産生式右→左壓棧
stack[++stack_top] = '\'';
stack[++stack_top] = 'F';
step++; //分析步數+1
lookahead++; //因為比對到一個終結符，是以分析下一個字元
F();
T1();
}
else{
print(); //列印目前步驟資訊
printf("T'->ε\n"); //輸出表達式
stack[stack_top--] = NULL; //出棧
stack[stack_top--] = NULL;
step++; //分析步數+1
}
}
6 F()
/*****************************************************************************
*函數名稱：F()
*函數類型：void
*參數：void
*功能：分析文法，輸出資訊
*****************************************************************************/
void F(){
if (token[lookahead] == 'i'){ //若待分析字元比對‘i’
print(); //列印目前步驟資訊
printf("F->i\n"); //輸出表達式
stack[stack_top--] = NULL; //出棧
step++; //分析步數+1
lookahead++; //因為比對到一個終結符，是以分析下一個字元
}
else if (token[lookahead] == '('){ //若待分析字元比對‘(’
print(); //列印目前步驟資訊
printf("F->(E)\n"); //輸出表達式
stack[stack_top] = 'E'; //将産生式右→左壓棧
step++; //分析步數+1
lookahead++; //因為比對到一個終結符，是以分析下一個字元
E();
if (token[lookahead] == ')'){ //若待分析字元比對‘)’
lookahead++; //因為比對到一個終結符，是以分析下一個字元
}
else{
printf("沒有')'比對！\n");
return;
}
}
else{
printf("error\n");
return;
}
}
7 print()
/*****************************************************************************
*函數名稱：print()
*函數類型：void
*參數：void
*功能：列印資訊
*****************************************************************************/
void print(){
int i;
printf("%d\t", step); //列印分析第step步
for (i = 0; i <= stack_top; i++) //輸出分析棧中内容
printf("%c", stack[i]);
if (stack_top < 7) //每列對齊
printf("\t\t");
else
printf("\t");
for (i = 0; i < lookahead; i++){ //若字元已被分析，它的位置置空，保持列對齊
token[i] = ' ';
printf("%c", token[i]);
}
for (i = lookahead; i < token_len; i++) //輸出剩餘待分析字元
printf("%c", token[i]);
printf("\t"); //為輸出表達式做準備
}
點選下載下傳完整代碼