コンパイラ原理実験二 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;
}