編譯原理實驗二 LL(1)分析法程序

源代碼倉庫：CompilePrincipleLearning/experiment_2 · yusixian/CompilePrincipleLearning (github.com)

一。實驗目的#

掌握 LL (1) 分析法的基本原理
掌握 LL (1) 分析表的構造方法
掌握 LL (1) 驅動程序的構造方法

二。實驗內容及要求#

編寫識別單詞的詞法分析程序。

根據某一文法編制調試 LL（1）分析程序，以便對任意輸入的符號串進行分析。本次實驗的目的主要是加深對預測分析 LL（1）分析法的理解。

例：對下列文法，用 LL（1）分析法對任意輸入的符號串進行分析：

（1）E->TG

（2）G->+TG|—TG

（3）G->ε

（4）T->FS

（5）S->*FS|/FS

（6）S->ε

（7）F->(E)

（8）F->i

輸出的格式如下：

(1) LL（1）分析程序，編制人：姓名，學號，班級

(2) 輸入一以 #結束的符號串 (包括 +*（）i#)：i*(i+i)+(i*i)#

(3) 輸出過程步驟如下：

步驟	分析棧	剩餘輸入串	所用產生式
1	E	i+i*i#	E->TG

(4) 輸入符號串為非法符號串 (或者為合法符號串)

備註：

(1) 在 “ 所用產生式 ” 一列中如果對應有推導則寫出所用產生式；如果為匹配終結符則寫明匹配的終結符；如分析異常出錯則寫為 “分析出錯”；若成功結束則寫為 “分析成功”。

(2) 在此位置輸入符號串為用戶自行輸入的符號串。

(3) 上述描述的輸出過程只是其中一部分的。

注意：1．表達式中允許使用運算符（+-*/）、分割符（括號）、字符 i，結束符 #；

2．如果遇到錯誤的表達式，應輸出錯誤提示信息（該信息越詳細越好）；

3．對學有餘力的同學，測試用的表達式事先放在文本文件中，一行存放一個表達式，同時以分號分割。同時將預期的輸出結果寫在另一個文本文件中，以便和輸出進行對照；

4．可採用的其它的文法

三。實驗過程#

1、採用的數據結構#

產生式類型定義為 type，左側為 origin，大寫字符，右側產生的字符

struct type { /*產生式類型定義      */
    char origin;   /*產生式左側字符 大寫字符  */
    string array; /*產生式右邊字符 */
    int length;    /*字符個數      */
    type():origin('N'), array(""), length(0) {}
    void init(char a, string b) {
        origin = a;
        array = b;
        length = array.length();
    }
};

初始化數據結構如下：

e.init('E', "TG"), t.init('T', "FS");
g.init('G', "+TG"), g1.init('G', "^");
s.init('S', "*FS"), s1.init('S', "^");
f.init('F', "(E)"), f1.init('F', "i");

2、頭文件聲明和全局變量定義#

如下

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
const string ExpFileName = "./exp.txt";
char analyeStack[20];                           /*分析棧*/
char restStack[20];                             /*剩余棧*/
const string v1 = "i+*()#"; /*終結符 */
const string v2 = "EGTSF";      /*非終結符   */
const string acceptStr = "i+*()#";   // 接受的字符串
int top, ridx, len; /*len為輸入串長度 */
struct type { /*產生式類型定義      */
    char origin;   /*產生式左側字符 大寫字符  */
    string array; /*產生式右邊字符 */
    int length;    /*字符個數      */
    type():origin('N'), array(""), length(0) {}
    void init(char a, string b) {
        origin = a;
        array = b;
        length = array.length();
    }
};
type e, t, g, g1, s, s1, f, f1; /* 產生式結構體變量 */
type C[10][10];                 /*  預測分析表 */

4、函數彙總#

（1）函數彙總表#

函數名稱	功能簡述
`readFile`	讀取文件函數，返回一個 string 動態數組，以行數分割
`init`	初始化函數，在該函數中進行分析棧、剩余棧的初始化
`print`	輸出當前分析棧和剩余棧
`isTerminator`	判斷當前字符 c 是否是終結符
`analyze`	分析字符串 s，輸出其分析步驟
`main`	主程序入口，從此進入，填充初始分析表及產生式初始化，調用讀取文件函數開始分析

（2）函數的調用關係#

function

5、實驗結果#

輸入#

文件 exp.txt

i*(i+i)+(i*i)#
i*i-i/1#
i+i*i+i*(i+i*i)#
i+*i(i)+i(i+i*i)#
i+i(i)#code.txt

輸出#

實驗結果

在這裡插入圖片描述

完整代碼#

/*
 * @Author: cos
 * @Date: 2022-04-12 23:03:36
 * @LastEditTime: 2022-04-13 01:32:58
 * @LastEditors: cos
 * @Description: 
 * @FilePath: \CS\experiment_2\main.cpp
 */
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
const string ExpFileName = "./exp.txt";
char analyeStack[20];                           /*分析棧*/
char restStack[20];                             /*剩余棧*/
const string v1 = "i+*()#"; /*終結符 */
const string v2 = "EGTSF";      /*非終結符   */
int top, ridx, len; /*len為輸入串長度 */
struct type { /*產生式類型定義      */
    char origin;   /*產生式左側字符 大寫字符  */
    string array; /*產生式右邊字符 */
    int length;    /*字符個數      */
    type():origin('N'), array(""), length(0) {}
    void init(char a, string b) {
        origin = a;
        array = b;
        length = array.length();
    }
};
type e, t, g, g1, s, s1, f, f1; /* 產生式結構體變量 */
type C[10][10];                 /*  預測分析表 */
void print() {/*輸出分析棧和剩余棧 */
    for(int i = 0; i <= top + 1; ++i)   /*輸出分析棧  */
        cout << analyeStack[i];
    cout << "\t\t";

    for(int i = 0; i < ridx; ++i) /*輸出對齊符*/
        cout << ' ';
    for(int i = ridx; i <= len; ++i)   /*輸出剩余串*/
        cout << restStack[i];
    cout << "\t\t\t";
}
// 讀文件
vector<string> readFile(string fileName) {
    vector<string> res;
    try {
        ifstream fin;
        fin.open(fileName);
        string temp;
        while (getline(fin, temp))
            res.push_back(temp);
        return res;
    } catch(const exception& e) {
        cerr << e.what() << '\n';
        return res;
    }
}
bool isTerminator(char c) { // 判斷是否是終結符
    return v1.find(c) != string::npos;
}
void init(string exp) {
    top = ridx = 0;
    len = exp.length();     /*分析串長度*/
    for(int i = 0; i < len; ++i)
        restStack[i] = exp[i];
}
void analyze(string exp) {  // 分析一個文法
    init(exp);
    int k = 0;
    analyeStack[top] = '#';
    analyeStack[++top] = 'E'; /*'#','E'進棧*/
    cout << "步驟\t\t分析棧 \t\t剩餘字符 \t\t所用產生式 " << endl;
    while(true) {
        char ch = restStack[ridx];
        char x = analyeStack[top--]; /*x為當前棧頂字符*/
        cout << ++k << "\t\t";
        if(x == '#') {
            cout << "分析成功！AC！\n" << endl; /*接受 */
            return;
        }
        if(isTerminator(x)) {
            if (x == ch) {  // 匹配上了
                print();
                cout << ch << "匹配" << endl;
                ch = restStack[++ridx]; /*下一个输入字符*/
            } else {             /*出錯處理*/
                print();
                cout << "分析出錯，錯誤終結符為" << ch << endl; /*輸出出錯終結符*/
                return;
            }
        } else {    /*非終結符處理*/
            int m, n;   // 非終結符下標， 终结符下標
            v2.find(x) != string::npos ? m = v2.find(x) : -1;   // m為-1則說明找不到該非終結符，出錯
            v1.find(ch) != string::npos ? n = v1.find(ch) : -1; // n為-1則說明找不到該終結符，出錯
            if(m == -1 || n == -1) { /*出錯處理*/
                print();
                cout << "分析出錯，錯誤非終結符為" << x << endl; /*輸出出錯非終結符*/
                return;
            }
            type nowType = C[m][n];/*用來接受C[m][n]*/
            if(nowType.origin != 'N') {/*判斷是否為空*/
                print();
                cout << nowType.origin << "->" << nowType.array << endl; /*輸出產生式*/
                for (int j = (nowType.length - 1); j >= 0; --j) /*產生式逆序入棧*/
                    analyeStack[++top] = nowType.array[j];
                if (analyeStack[top] == '^') /*為空則不進棧*/
                    top--;
            } else { /*出錯處理*/
                print();
                cout << "分析出錯，錯誤非終結符為" << x << endl; /*輸出出錯非終結符*/
                return;
            }
        }
    }
}
int main() {
    e.init('E', "TG"), t.init('T', "FS");
    g.init('G', "+TG"), g1.init('G', "^");
    s.init('S', "*FS"), s1.init('S', "^");
    f.init('F', "(E)"), f1.init('F', "i"); /*  結構體變量 */
    /*填充分析表*/
    C[0][0] = C[0][3] = e;
    C[1][1] = g; 
    C[1][4] = C[1][5] = g1;
    C[2][0] = C[2][3] = t;
    C[3][2] = s;
    C[3][4] = C[3][5] = C[3][1] = s1;
    C[4][0] = f1; C[4][3] = f;
    cout << "LL（1）分析程序分析程序，編制人：xxx xxx 計科xxxx班" << endl;
    cout << "提示:本程序只能對由'i','+','*','(',')'構成的以'#'結束的字符串進行分析，每行一個讀入的字符串" << endl;
    cout << "讀取的文件名為：" << ExpFileName << endl; 
    vector<string> exps = readFile(ExpFileName);
    int len = exps.size();
    for(int i = 0; i < len; i++) {
        string exp = exps[i];
        cout << "------------------待分析字符串" << i+1 << "："<< exp << "--------------------" << endl;
        bool flag = true;
        for(int j = 0; j < exp.length(); j++) {
            if(!isTerminator(exp[j])) {
                cout << "第"<< i+1 << "行輸入的字符串不合法，請重新輸入" << endl;
                flag = false;
                break;
            }
        }
        if(flag) {
            cout << "字符串" << i+1 << "：" << exp << endl;
            analyze(exp);
        }
    }
    return 0;
}