コンパイラ原理実験四 LR(1)解析法プログラム

第三回実験は逆ポーランド式が比較的簡単なので省略します。

ソースコードリポジトリ：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 << "エラー！" << "不正な文字が出現し、プログラムが異常終了しました" <<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' << "エラー！ プログラムが異常終了しました" << 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 << "エラー！" << "プログラムが異常終了しました" <<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;
}