编译原理头歌实验：实验4《算符优先分析法设计与实现》（C语言版）

任务描述

本关任务：加深对语法分析器工作过程的理解；加强对算符优先分析法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。

相关知识

为了完成本关任务，你需要掌握：用算符优先法编制语法分析程序。

自下而上的语法分析器

语法分析在编译中是一个重要的环节，语法分析可以分为自上而下分析和自下而上分析两种方式。

自下而上分析法是一种“移进－归约”法。这种方法的大意是，用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分替换成（归约为）该产生式的左部符号。

对于自下而上的分析法，边输入单词符号（移进符号栈），边归约。也就是在从左到右移进输入串的过程中，一旦发现栈顶呈现可归约串就立即进行归约。

在该类方法中有以下的几个处理：

• 移进：指把输入串的一个符号移进栈。

• 归约：指发现栈顶呈可归约串，并用适当的相应符号去替换这个串（这两个问题都还没有解决）。

• 接受：指宣布最终分析成功，这个操作可看作是“归约”的一种特殊形式。

• 出错处理：指发现栈顶的内容与输入串相悖，分析工作无法正常进行，此时需调用出错处理程序进行诊察和校正，并对栈顶的内容和输入符号进行调整。

算符优先法

算符优先分析法(Operator Precedence Parse)是一种移动归约分析方法，它是仿效四则运算的计算过程而构造的一种语法分析方法。算符优先分析法的关键是比较两个相继出现的终结符的优先级而决定应采取的动作。

算法优先关系构造的构造遵循以下的步骤：

首先对于优先关系进行如下定义：

• a的优先级低于b
a < b： 文法中有形如A→…aB…的产生式而B+b…或B+Cb…
• a的优先级等于b
  a = b： 文法中有形如A→…ab…或者A→…aBb…的产生式
• a的优先级高于b
  a > b： 文法中有形如A…Bb…的产生式,而B+…a或B+…aC
• 算符的优先关系是有序的
  如果a > b，不能推出b < a
  如果a > b，有可能b > a
  如果a > b， b > c，不一定a > c
  根据这个大小关系的定义，我们知道为了确定两个终止符的优先关系，我们需要知道它的在所有的产生式中和前后非终止符的关系，那么我们做一个如步骤二的预处理。

定义并构造FIRSTVT和LASTVT两个集合

FIRSTVT(P)={a∣P⇒+a⋯或P⇒+Qa⋯}

LASTVT(P)={a∣P⇒+⋯a0​P⇒+…aQ}

1. FIRSTVT(P)直接根据定义递归的构造即可:

• 若有产生式 P→a⋯ 或 p→Qa⋯，则 a∈FIRSTVT(P)
• 若有产式 P→Q⋯，若 a∈FIRSTVT(Q)，则 a∈FIRSTVT(P)

1. LASTVT(P)直接根据定义递归的构造即可：

• 若有产生式 P→⋯ 或 p→⋯⋅a 则 a∈LASTVT(P)
• 若有产式 P→⋯, 若 a∈LASTVT(Q) 则 a∈LASTVT(P)

利用FIRSTVT和LASTVT集合构造算法优先关系表:

1. FOR 每个产生式 P->X1 X2 ……Xn
2. DO FOR i:=1 TO n-1 DO
3. IF X[i]和X[i+1]均为终结符
4. THEN 置 X[i]=X[i+1]
5. IF X[i]和X[i+2]均为终结符,X[i+1]为非终结符,i≤n-2,
6. THEN 置 X[i]=X[i+2]
7. IF X[i]为终结符, 但X[i+1]为非终结符
8. THEN FOR FIRSTVT(X[i+1])中的每个a
9. DO 置 X[i]<a
10. IF Xi为非终结符, 但X i+1 为终结符
11. THEN FOR LASTVT(X i )中的每个a
12. DO 置 a>X[i+1]

实验步骤

1. 对语法规则有明确的定义；
   该部分需要我们对输入文法进行构造，然后定义出算符之间的优先级，构造算符优先关系表，表的构造过程如上。
2. 编写的分析程序能够对测试用例进行正确的语法分析；
   该部分需要我们对于输入的字符串进行逐一判断，并给出相应的解析过程，该过程是一个移进，归约，接受及出错处理的操作过程。
3. 对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程；

编程要求

根据提示，在右侧编辑器补充代码，运行程序，进行结果对比。

测试说明

平台会对你编写的代码进行测试.

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <stack>
#include <iomanip>
using namespace std;
string V[100][2]; //存储拆分后的文法
int vi = 0; //存储拆分后有多少行
int t = 0;
int s = 0;
int l;
int r;
string FIRSTVT[20][2]; //存储firstvt集
string LASTVT[20][2]; //存储lastvt集
string str; //存储输入文法
string str_a = "#"; // 下堆栈
string str_b; // 剩余输入串
string analysis_table[100][5]; // 文法分析过程
char table[100][100]; // 算符优先关系表
void init_string(string &a) // 删除字符串的第一个元素
{
    for (int i = 1; i <= a.length(); ++i)
    {
        a[i - 1] = a[i];
    }
}
bool is_CHAR(char c) // 判断是否为大写字母
{
    if (c >= 'A' && c <= 'Z')
    {
        return true;
    }
    else
    {
        return false;
    }
}
bool is_in(int i, string x) // 判断从字符串x从最好一个开始算起连续的i个字符是否含有非大写字母
{
    bool flag = false;
    for (int j = 0; j < i; j++)
    {
        if (!is_CHAR(x[x.length() - j - 1]))
        {
            flag = true;
        }
    }
    return flag;
}
void split(string a) // 拆分文法，使其不含有｜
{
    for (int i = 3; i < a.length(); ++i)
    {
        V[vi][0] = a[0];
        while (a[i] != '|' && i < a.length())
        {
            V[vi][1] += a[i];
            i++;
        }
        vi++;
    }
}
void read_file(string file_path) //按行读取文件
{
    fstream f(file_path);
    vector<string> words;
    string line;
    while (getline(f, line))
    {
        words.push_back(line);
    }
    cout << "输入文法:" << endl;
    for (int i = 0; i < words.size(); i++)
    {
        cout << words[i] << endl;
        split(words[i]);
    }
}
int find_index(char a) //寻找字符a在firstvt或者lastvt中的位置
{
    for (int i = 0; i < t; ++i)
    {
        if (FIRSTVT[i][0][0] == a)
        {
            return i;
        }
    }
    return -1;
}
int find_table_index(char a) //寻找字符a在算符优先关系表中的位置
{
    for (int i = 0; i <= s; ++i)
    {
        if (table[i][0] == a)
        {
            return i;
        }
    }
    return -1;
}
void get_start() //获取非终结符
{
    for (int i = 0; i < vi; ++i)
    {
        bool flag = true;
        for (int j = 0; j < t; ++j)
        {
            if (FIRSTVT[j][0] == V[i][0])
            {
                flag = false;
            }
        }
        if (flag)
        {
            FIRSTVT[t][0] = V[i][0];
            LASTVT[t][0] = V[i][0];
            t++;
        }
    }
}
/********Beign********/
/*构造firstvt,lastvt*/
void add_firstvt(string b, int a) //判断字符串b是否在序号为a的firstvt中，没有则加入
{
    for (int s = 0; s < b.length(); ++s)
	{
		bool flag = true;
		char c = b[s];
		if (c <= 'Z' && c >= 'A')
		{
			continue;
		}
		for (int i = 0; i < FIRSTVT[a][1].length(); ++i)
		{
			if (c == FIRSTVT[a][1][i])
			{
				flag = false;
			}
		}
		if (flag)
		{
			FIRSTVT[a][1] += c;
		}
	}
}
void add_firstvt(char c, int a) //判断字符c是否在序号为a的firstvt中，没有则加入
{
    bool flag = true;
	for (int i = 0; i < FIRSTVT[a][1].length(); ++i)
	{
		if (c <= 'Z' && c >= 'A')
		{
			continue;
		}
		if (c == FIRSTVT[a][1][i])
		{
			flag = false;
		}
	}
	if (flag)
	{
		FIRSTVT[a][1] += c;
	}
 
}
void add_lastvt(string b, int a) //判断字符串b是否在序号为a的lastvt中，没有则加入
{
    for (int s = 0; s < b.length(); ++s)
	{
		bool flag = true;
		char c = b[s];
		if (c <= 'Z' && c >= 'A')
		{
			continue;
		}
		for (int i = 0; i < LASTVT[a][1].length(); ++i)
		{
			if (c == LASTVT[a][1][i])
			{
				flag = false;
			}
		}
		if (flag)
		{
			LASTVT[a][1] += c;
		}
	}
}
void add_lastvt(char c, int a) //判断字符串c是否在序号为a的lastvt中，没有则加入
{
    bool flag = true;
	for (int i = 0; i < LASTVT[a][1].length(); ++i)
	{
		if (c <= 'Z' && c >= 'A')
		{
			continue;
		}
		if (c == LASTVT[a][1][i])
		{
			flag = false;
		}
	}
	if (flag)
	{
		LASTVT[a][1] += c;
	}
}
string get_cur_firstvt(char c, int a) //获取当前字符的firstvt，并放入序号为a的firstvt中
{
    string temp;
	for (int i = 0; i < vi; ++i)
	{
		if (c == V[i][0][0])
		{
			if (!(V[i][1][0] <= 'Z' && V[i][1][0] >= 'A'))
			{
				add_firstvt(V[i][1][0], a);
			}
			else
			{
				if (c != V[i][1][0])
				{
					temp = get_cur_firstvt(V[i][1][0], find_index(V[i][1][0]));
					add_firstvt(temp, a);
				}
				if (V[i][1].length() > 2)
				{
					if (!(V[i][1][1] <= 'Z' && V[i][1][1] >= 'A'))
					{
						add_firstvt(V[i][1][1], a);
					}
				}
			}
		}
	}
	return FIRSTVT[a][1];
}
string get_cur_lastvt(char c, int a) //获取当前字符的lastvt，并放入序号为a的lastvt中
{
    string temp;
	for (int i = 0; i < vi; ++i)
	{
		int s = V[i][1].length();
		if (c == V[i][0][0])
		{
			if (!(V[i][1][s - 1] <= 'Z' && V[i][1][s - 1] >= 'A'))
			{
				add_lastvt(V[i][1][s - 1], a);
			}
			else
			{
				if (c != V[i][1][s - 1])
				{
					temp = get_cur_lastvt(V[i][1][s - 1], find_index(V[i][1][0]));
					add_lastvt(temp, a);
				}
				if (V[i][1].length() > 2)
				{
					if (!(V[i][1][s - 2] <= 'Z' && V[i][1][s - 2] >= 'A'))
					{
						add_lastvt(V[i][1][s - 2], a);
					}
				}
			}
		}
	}
	return LASTVT[a][1];
}
/*********End*********/
void get_firstvt() //获取所有文法的firstvt
{
    for (int i = 0; i < t; i++)
    {
        get_cur_firstvt(FIRSTVT[i][0][0], i);
    }
}
void get_lastvt() //获取所有文法的lastvt
{
    for (int i = 0; i < t; i++)
    {
        get_cur_lastvt(LASTVT[i][0][0], i);
    }
}
void print_firstvt(string t, string a) //打印非终极符为t的firstvt
{
    cout << "FIRSTVT(" << t << ") = {";
    for (int i = 0; i < a.length(); ++i)
    {
        if (i == a.length() - 1)
        {
            cout << "\"" << a[i] << "\"";
        }
        else
        {
            cout << "\"" << a[i] << "\"" << ", ";
        }
    }
    cout << "}" << endl;
}
void print_lastvt(string t, string a) //打印非终结符为t的lastvt
{
    cout << "LASTVT(" << t << ") = {";
    for (int i = 0; i < a.length(); ++i)
    {
        if (i == a.length() - 1)
        {
            cout << "\"" << a[i] << "\"";
        }
        else
        {
            cout << "\"" << a[i] << "\"" << ", ";
        }
    }
    cout << "}" << endl;
}
/********Beign********/
/*构造算符优先表*/
 
void init_table() //初始化算符优先关系表
{
    table[0][0] = '\\';
	for (int i = 0; i < vi; ++i)
	{
		for (int j = 0; j < V[i][1].length(); ++j)
		{
			bool flag = true;
			for (int k = 0; k < s + 1; ++k)
			{
				if (table[k + 1][0] == V[i][1][j] || (V[i][1][j] <= 'Z' && V[i][1][j] >= 'A'))
				{
					flag = false;
				}
			}
			if (flag)
			{
				table[s + 1][0] = V[i][1][j];
				table[0][s + 1] = V[i][1][j];
				s++;
			}
		}
	}
	for (int l = 1; l < s + 1; ++l)
	{
		for (int i = 1; i < s + 1; ++i)
		{
			table[l][i] = ' ';
		}
	}
}
 
void get_table() //生成算符优先关系表
{
    for (int i = 0; i < vi; ++i)
	{
		for (int j = 0; j < V[i][1].length(); ++j)
		{
			//ab
			if (!(V[i][1][j] <= 'Z' && V[i][1][j] >= 'A') && !(V[i][1][j + 1] <= 'Z' && V[i][1][j + 1] >= 'A') &&
				j + 1 < V[i][1].length())
			{
				table[find_table_index(V[i][1][j])][find_table_index(V[i][1][j + 1])] = '=';
			}
			//aQb
			if ((!(V[i][1][j] <= 'Z' && V[i][1][j] >= 'A')) && (V[i][1][j + 1] <= 'Z' && V[i][1][j + 1] >= 'A') &&
				(!(V[i][1][j + 2] <= 'Z' && V[i][1][j + 2] >= 'A')) && j + 2 < V[i][1].length())
			{
				table[find_table_index(V[i][1][j])][find_table_index(V[i][1][j + 2])] = '=';
			}
			//aQ
			if ((!(V[i][1][j] <= 'Z' && V[i][1][j] >= 'A')) && (V[i][1][j + 1] <= 'Z' && V[i][1][j + 1] >= 'A') &&
				j + 1 < V[i][1].length())
			{
				for (int k = 0; k < FIRSTVT[find_index(V[i][1][j + 1])][1].length(); ++k)
				{
					table[find_table_index(V[i][1][j])][find_table_index(
							FIRSTVT[find_index(V[i][1][j + 1])][1][k])] = '<';
				}
			}
			//Qa
			if ((V[i][1][j] <= 'Z' && V[i][1][j] >= 'A') && !(V[i][1][j + 1] <= 'Z' && V[i][1][j + 1] >= 'A') &&
				j + 1 < V[i][1].length())
			{
				for (int k = 0; k < LASTVT[find_index(V[i][1][j])][1].length(); ++k)
				{
					table[find_table_index(LASTVT[find_index(V[i][1][j])][1][k])][find_table_index(
							V[i][1][j + 1])] = '>';
				}
			}
		}
	}
}
/*********End*********/
void print_table() //打印算符优先关系表
{
    for (int i = 0; i < s + 1; ++i)
    {
        for (int j = 0; j < s + 1; ++j)
        {
            cout << table[i][j] << " ";
        }
        cout << endl;
    }
}
char get_relationship(char a, char b) //获取终结符a，b的优先关系
{
    return table[find_table_index(a)][find_table_index(b)];
}
bool is_reduce() //判断是否可以规约
{
    for (int i = 0; i < vi; ++i)
    {
        int count = 0;
        int f = str_a.length() - 1;
        for (int j = V[i][1].length() - 1; j >= 0 && f >= 0; j--, f--)
        {
            if (is_in(V[i][1].length(), str_a))
            {
                if (is_CHAR(str_a[f]) && is_CHAR(V[i][1][j]))
                {
                    count++;
                }
                else if (str_a[f] == V[i][1][j])
                {
                    count++;
                }
            }
            else
            {
                continue;
            }
        }
        if (count == V[i][1].length())
        {
            r = i;
            return true;
        }
    }
    return false;
}
void analyze_input_string() // 生成算符优先文法的分析过程
{
    analysis_table[0][0] = "步骤";
    analysis_table[0][1] = "下堆栈";
    analysis_table[0][2] = "优先关系";
    analysis_table[0][3] = "剩余输入串";
    analysis_table[0][4] = "移进或规约";
    str_b = str;
    char relationship;
    l = 1;
    int x;
    stringstream ss;
    while (true)
    {
        ss << l;
        int index = str_a.length() - 1;
        analysis_table[l][0] = ss.str();
        analysis_table[l][3] = str_b;
        analysis_table[l][1] = str_a;
        ss.clear();
        ss.str("");
        if (is_CHAR(str_a[index]))
        {
            for (int i = str_a.length() - 1; i >= 0; i--)
            {
                if (!is_CHAR(str_a[i]))
                {
                    index = i;
                    break;
                }
            }
        }
        relationship = get_relationship(str_a[index], str_b[0]);
        analysis_table[l][2] = relationship;
        if (relationship == '=')
        {
            if (str_a[index] == '#' && str_b[0] == '#')
            {
                analysis_table[l][4] = "完成";
                break;
            }
            else
            {
                analysis_table[l][4] = "移进";
                str_a += str_b[0];
                analysis_table[l + 1][1] = str_a;
                init_string(str_b);
            }
        }
        else if (relationship == '<')
        {
            analysis_table[l][4] = "移进";
            str_a += str_b[0];
            analysis_table[l + 1][1] = str_a;
            init_string(str_b);
        }
        else if (relationship == '>')
        {
            if (is_reduce())
            {
                analysis_table[l][4] = "规约";
                str_a[str_a.length() - V[r][1].length()] = V[r][0][0];
                str_a.erase(str_a.length() - V[r][1].length() + 1, V[r][1].length() - 1);
            }
            else
            {
                cout << "输入串非法" << endl;
                exit(-1);
            }
        }
        l++;
    }
}
void print_analyze_process() //打印算符优先文法的分析过程
{
    cout << "算符优先分析过程" << endl;
    cout << setw(12) << analysis_table[0][0] << setw(16) << analysis_table[0][1] << setw(16) << analysis_table[0][2]
         << setw(24)
         << analysis_table[0][3] << setw(20)
         << analysis_table[0][4] << endl;
    for (int i = 1; i <= l; ++i)
    {
        cout.width(10);
        cout << analysis_table[i][0];
        cout.width(12);
        cout << analysis_table[i][1];
        cout.width(10);
        cout << analysis_table[i][2];
        cout.width(20);
        cout << analysis_table[i][3];
        cout << analysis_table[i][4];
        cout << endl;
    }
}
int main(int argv, char *arg[])
{
    cout.setf(std::ios::left);
    read_file("/data/workspace/myshixun/in.txt");
    cout << "拆分后文法:" << endl;
    for (int i = 0; i < vi; ++i)
    {
        cout << V[i][0] << "->" << V[i][1] << endl;
    }
    cout << "非终结符:" << endl;
    get_start();
    for (int j = 0; j < t; ++j)
    {
        cout << FIRSTVT[j][0] << endl;
    }
    cout << "FIRSTVT:" << endl;
    get_firstvt();
    for (int k = 0; k < t; ++k)
    {
        print_firstvt(FIRSTVT[k][0], FIRSTVT[k][1]);
    }
    cout << "LASTVT:" << endl;
    get_lastvt();
    for (int k = 0; k < t; ++k)
    {
        print_lastvt(LASTVT[k][0], LASTVT[k][1]);
    }
    cout << "算符优先关系表" << endl;
    init_table();
    get_table();
    print_table();
    cout << "请输入文法并以#结束:" << endl;
    cin >> str;
    analyze_input_string();
    print_analyze_process();
    return 0;
}