編譯原理實驗四 LR(1)分析法程序

第三次實驗因為逆波蘭式比較簡單所以略過 x

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

在 demo 文件夾中～

一。實驗目的#

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

二。實驗內容及要求#

構造 LR (1) 分析程序，利用它進行語法分析，判斷給出的符號串是否為該文法識別的句子，了解 LR（K）分析方法是嚴格的從左向右掃描，和自底向上的語法分析方法。

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

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

（0）S’->E

（1）E->E+T

（2）E->T

（3）T->T*F

（4）T->F

（5）F->(E)

（6）F->i

輸出的格式如下：

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

(2) 輸入一以 #結束的符號串 (包括 +-*/（）i#)：在此位置輸入符號串

(3) 輸出過程如下：

步驟	狀態棧	符號棧	剩餘輸入串	動作
1	0	#	i+i*i#	移進

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

注意：

表達式中允許使用運算符（+|*）、分割符（括號）、字符 i，結束符 #；
如果遇到錯誤的表達式，應輸出錯誤提示信息（該信息越詳細越好）；
對學有餘力的同學，測試用的表達式事先放在文本文件中，一行存放一個表達式，同時以分號分割。同時將預期的輸出結果寫在另一個文本文件中，以便和輸出進行對照；
可採用的其它的文法，但是必須是 LR1 分析方法。

三。實驗過程#

1、構造識別 LR（1）文法活前綴的 DFA#

如圖：新標籤頁打開，不糊的。

LR1_DFA.drawio.png

action 表和 goto 表如下：

2、採用的數據結構#

// ACTION表
// + * ( ) i #
string action[12][6];
// goto表
// a b #
int _goto[12][3];
string vt = "+*()i#";      // 終結符表
string vn = "ETF";        // 非終結符表
string LR[6] = { "E->E+T", "E->T", "T->T*F", "T->F", "F->(E)", "F->i" };   // 存放產生式
stack<char> chars;  // 符號棧
stack<int> state;   // 狀態棧

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

如下。

#include <iostream>
#include <string>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
const string ExpFileName = "./exp.txt";
const string GotoFileName = "./goto.txt";
const string ActionFileName = "./action.txt";
const int Null = -1;
// ACTION表
// + * ( ) i #
string action[12][6];
// goto表
// a b #
int _goto[12][3];
string vt = "+*()i#";      // 終結符表
string vn = "ETF";        // 非終結符表
string LR[6] = { "E->E+T", "E->T", "T->T*F", "T->F", "F->(E)", "F->i" };   // 存放產生式

4、函數彙總#

（1）函數彙總表#

函數名稱	功能簡述
`readFile`	讀取文件函數，返回一個 string 動態數組，以行數分割
`init`	初始化函數，在該函數中進行 goto 表和 action 表的初始化
`printActions / printGotos`	輸出 goto 表與 action 表
`isTerminator`	判斷當前字符 c 是否是終結符
`findTerminator`	返回終結符所處下標
`findNonTerminator`	返回非終結符所處下標
`s2string`	將棧轉換為字符串返回，方便輸出步驟
`analyzeLR1`	利用 LR1 分析法分析字符串 exp，輸出其分析步驟
`main`	主程序入口，調用讀取文件函數開始分析

（2）函數的調用關係#

function4.drawio.png

（3）流程圖#

main.drawio.png

5、實驗結果#

輸入#

action.txt 文件

N	N	s4	N	s5	N
s6	N	N	N	N	acc
r2	s7	N	r2	N	r2
r4	r4	N	r4	N	r4
N	N	s4	N	s5	N
r6	r6	N	r6	N	r6
N	N	s4	N	s5	N
N	N	s4	N	s5	N
s6	N	N	s11	N	N
r1	s7	N	r1	N	r1
r3	r3	N	r3	N	r3
r5	r5	N	r5	N	r5

goto.txt 文件

1	2	3
N	N	N
N	N	N
N	N	N
8	2	3
N	N	N
N	9	3
N	N	10
N	N	N
N	N	N
N	N	N
N	N	N

exp.txt 文件

i+(i*i)*(i+i)#
i*i+i*i#
i+i*i+i*(i+i*i)#
i+*(i)+i(i+i*i)#
i+i(i)#

輸出#

完整代碼#

/*
 * @Author: cos
 * @Date: 2022-04-30 14:20:51
 * @LastEditTime: 2022-05-01 02:34:12
 * @LastEditors: cos
 * @Description: 實驗4 LR(1) 分析法
 * @FilePath: \CompileTheory\experiment_4\demo\main.cpp
 */
#include <iostream>
#include <string>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
const string ExpFileName = "./exp.txt";
const string GotoFileName = "./goto.txt";
const string ActionFileName = "./action.txt";
const int Null = -1;
// ACTION表
// + * ( ) i #
string action[12][6];
// goto表
// a b #
int _goto[12][3];
string vt = "+*()i#";      // 終結符表
string vn = "ETF";        // 非終結符表
string LR[6] = { "E->E+T", "E->T", "T->T*F", "T->F", "F->(E)", "F->i" };   // 存放產生式
// 讀文件
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;
    }
}
void printActions() {
    cout << "-----------------ACTION表------------------" << endl;
    cout << "+\t*\t(\t)\ti\t$" << endl;
    for (int i = 0; i < 12; ++i) {
        for (int j = 0; j < 6; ++j)
            cout << action[i][j] << "\t";
        cout << endl;
    }
}
void printGotos() {
    cout << "-----------------GOTO表------------------" << endl;
    cout << "E\tT\tF" << endl;
    for (int i = 0; i < 12; ++i) {
        for (int j = 0; j < 3; ++j)
            cout << _goto[i][j] << "\t";
        cout << endl;
    }
}
void init() {
    vector<string> actions = readFile(ActionFileName);
    for (int i = 0; i < 12; ++i) {
        int cnt = 0;
        string row = actions[i];
        int len = actions[i].length();
        for (int j = 0; j < len; ++j) {
            string temp = "";
            while (j < len && row[j] != ' ' && row[j] != '\t') {
                temp += row[j];
                ++j;
            }
            while (j < len && (row[j] == ' ' || row[j] == '\t'))
                ++j;
            --j;
            action[i][cnt++] = temp;
        }

    }
    printActions();
    vector<string> gotos = readFile(GotoFileName);
    for (int i = 0; i < 12; ++i) {
        int cnt = 0;
        string row = gotos[i];
        int len = row.length();
        for (int j = 0; j < len; ++j) {
            string temp = "";
            while (j < len && row[j] != ' ' && row[j] != '\t') {
                temp += row[j];
                ++j;
            }
            while (j < len && (row[j] == ' ' || row[j] == '\t'))
                ++j;
            --j;
            _goto[i][cnt++] = (temp == "N") ? Null : stoi(temp);
        }
    }
    printGotos();
}
bool isTerminator(char c) {
    return vt.find(c) != string::npos;
}
int findTerminator(char c) { // 返回終結符所處下標
    return vt.find(c);
}
int findNonTerminator(char c) { // 返回非終結符的下標
    return vn.find(c);
}
// 將棧轉換為字符串返回
string s2string(stack<int> s) {
    string str = "";
    while(!s.empty()) {
        str += to_string(s.top()) + " ";
        s.pop();
    }
    return str;
}
// 輸出剩余輸入串
void printRestInput(string exp, int start, int len) {
    for(int i = start; i < len; ++i) 
        cout << exp[i];
    cout << '\t';
}
void analyzeLR1(string exp) {  // 分析一個表達式
    int len = exp.length();
    stack<char> chars;  // 符號棧
    stack<int> state;   // 狀態棧
    state.push(0);  // 初始狀態為0
    chars.push('#');  // 初始符號為#
    string charsStr = "#";
    stack<int> copyState;
    copyState.push(0);
    int cnt = 0;    // 序號
    int idx = 0;  // 當前輸入指針
    cout << "序號\t\t狀態棧\t\t符號棧\t\t輸入串\t\t描述" << endl;
    cout << cnt++ << '\t' << s2string(copyState) << '\t' << charsStr << '\t' << exp << '\t' << " 初始狀態 " << endl;
    while(1) {
        int nowState = state.top();
        char nowChar = exp[idx];    // 當前輸入字符
        int isT = findTerminator(nowChar);
        if(isT == Null) {   // 非終結符
            cout << "Error!" << "出現非法字符，程序錯誤退出" <<endl;
            return;
        }
        string actionStr = action[nowState][isT];
        if(actionStr == "acc") {
            cout << cnt++ << '\t' << s2string(copyState) << '\t' << charsStr << '\t' << exp << '\t' << " accept 接受！ " << endl;
            return;
        } else if(actionStr == "N") {
            cout << cnt++ << '\t' << s2string(copyState) << '\t' << charsStr << '\t' << exp << '\t' << "Error! 程序異常退出" << endl;
            return;
        } else if(actionStr[0] == 'r') {   // 归约
            int num = stoi(actionStr.substr(1));    // 選用第幾個產生式歸約
            int len = LR[num-1].length()-3;
            while(len--) {
                chars.pop();        // 出棧，歸約
                state.pop();
                charsStr = charsStr.substr(0, charsStr.length()-1);
                copyState.pop();   // 便於輸出
            }
            chars.push(LR[num-1][0]);   // 產生式左部入符號棧
            charsStr += LR[num-1][0];

            int nowState = state.top();
            int gidx = findNonTerminator(LR[num-1][0]);
            int newState = _goto[nowState][gidx];
            state.push(newState);
            copyState.push(newState);

            cout << cnt++ << '\t' << s2string(copyState) << '\t' << charsStr  << '\t';
            printRestInput(exp, idx, len);
            cout << '\t' << " 歸約 " << LR[num-1] << endl;
        } else if(actionStr[0] == 's') {    // 移進
            int newState =  stoi(actionStr.substr(1));
            state.push(newState);
            copyState.push(newState);

            chars.push(nowChar);
            charsStr += nowChar;
            ++idx;  // 輸入指針後移

            cout << cnt++ << '\t' << s2string(copyState) << '\t' << charsStr << '\t';
            printRestInput(exp, idx, len);
            cout << '\t' << actionStr << " 移進 " << endl;
        } else {
            cout << "Error!" << "程序異常退出" <<endl;
            return;
        }
    }
}
int main() {
    cout << "LR（1）分析程序，編制人：xxx xxxxxxxx xxxx班" << endl;
    cout << "提示:本程序只能對由'i','+','*','/','(',')'構成的以'#'結束的表達式進行分析，每行讀入一個表達式" << endl;
    cout << "讀取的文件名為：" << ExpFileName << endl; 
    init();
    vector<string> exps = readFile(ExpFileName);
    int len = exps.size();
    for (int i = 0; i < len; i++) {
        string exp = exps[i];
        cout << "\n------------------待分析表達式" << 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;
            analyzeLR1(exp);
        }
    }
    return 0;
}

編譯原理 實驗四 LR(1)分析法程序