一、实验目的
语法分析的设计方法和实现原理；LL（1）分析表的构造；LL(1)分析过程；LL(1)分析器 的构造；
二、实验内容
实现 LL(1)分析中控制程序（表驱动程序）；完成以下描述赋值语句的 LL(1) 文法的 LL(1)分析过程。
G[S]:S→V=E
E→TE′
E′→ATE′|ε
T→FT′
T′→MFT′|ε
F→ (E)|i
A→+|-
M→*|/
V→i
[设计说明] 终结符号 i 为用户定义的简单变量,即标识符的定义。
[设计要求]
（1）输入串应是词法分析的输出二元式序列，即某算术表达式“专题 1”的 输出结果。输出为输入串是否为该文法定义的算术表达式的判断结果；
（2）LL(1)分析过程 应能发现输入串出错；
（3）设计两个测试用例（尽可能完备，正确和出错），并给出测试结 果；
（4）考虑根据 LL(1)文法编写程序构造 LL（1）分析表，包括 FIRST 集合和 FOLLOW 集 合，并添加到你的 LL（1）分析程序中。
输出结果：
词法分析输入文件：
词法分析输出：
LL1文法分析结果：
先根据已知文法构造分析表：
读取文件进行LL1文法分析：
以下为实现该文法分析的全部代码，文件读取部分也可改为自行输入字符串，对主函数的like字符型数组进行更改即可。
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include <cassert>
#include<fstream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
#define max_size 100
char LL_1[100][100]= {
"S->V=E",
"E->Te",
"e->ATe|N", //E'用小e表示
"T->Ft", //T'用小t表示
"t->MFt|N",
"F->(E)|i",
"A->+|-",
"M->*|/",
"V->i"
};//文法数组
int num_ll = 9;//这里表示文法条数
//记录文法分析表格
char LL1[50][50][100];
char frist[100][100];//记录frist集数据
char follow[100][100];//记录follow集数据
char H[200]; //记录非终结符合
char L[200]; //记录终结符号
stack<char>cmp;//分析栈
char shizi[500], like[500];//从文件中读取字符串
int location_H(char c);//判断当前字符是否属于非终结符号
int location_L(char c);//判断当前字符是否属于终结符号
void add_HL(char ll[100][100]);//添加非终结符号与终结符号
int check(char l[100], char c);//在字符串中查找字符
void find_frist(char ll[100][100]);//第一遍寻找frist集的函数
void find_the_frist(int ll_index, char ll[100][100], int n_frist);//用作递归
void find_follow(char ll[100][100]);//用作寻找follow集
void make_table(char ll[100][100]);//用作构建表格
void print_table();//输出结果的函数
int findH(char a);//查找非终结符号
int findL(char b);//查找终结符号
int error(int i, int cnt, int len, char p[], char str[]);//出错处理
void analyze(char str[1000], int len);//LL1分析函数
void openthefile();//读取词法分析输出的函数
void LL_1table(char ll[100][100]) {
add_HL(ll);
find_frist(ll);
find_follow(ll);
make_table(ll);
print_table();//输出结果函数
}
int check(char l[100], char c) {
int temp = 0;
for(int i = 0; i < strlen(l); i++) {
if (c == l[i]) {
temp = 1;
break;
}
}
return temp;
}
void add_HL(char ll[100][100]) {
int H_index = 0;
int L_index = 0;
int temp = 0;
int temp1 = 0;
for (int i = 0; i < num_ll; i++) {//添加非终结符号
H[H_index] = ll[i][0];
H_index++;
}
for (int i = 0; i < num_ll; i++) {
for (int j = 3; j < strlen(ll[i]); j++) {
//由于文法开始前三个字符必定不为终结符号，所以从三号索引开始
temp = 0;
for (int k = 0; k < strlen(H); k++) {
if (ll[i][j] == H[k] || ll[i][j] == '|' || ll[i][j] == 'N') {
temp = 1;
break;
}
}
if (temp == 0) {
temp1 = 0;
for (int k = 0; k < strlen(L); k++) {
//判断该非终结符号是否已经存在
if (ll[i][j] == L[k]) {
temp1 = 1;
break;
}
}
if (temp1 == 0) {
L[L_index] = ll[i][j];//添加终结符号
L_index++;
}
}
}
}
L[strlen(L)] = '#';
}
int location_H(char c) {
int location = -1;
for (int i = 0; i < num_ll; i++) {
if (c == H[i]) {
location = i;
break;
}
}
return location;
}
int location_L(char c) {
int location = -1;
for (int i = 0; i < num_ll; i++) {
if (c == L[i]) {
location = i;
break;
}
}
return location;
}
void print_table() {
cout << "------------------20231048 马云霄-----------------------" << endl;
cout << "该文法的非终结符号集为：" << H << endl;
cout << "该文法的终结符号集为：" << L << endl;
cout << "-------------------------------------------------------" << endl;
cout << " frist集 follow集" << endl;
for (int i = 0; i < num_ll; i++) {
cout << " 符号 " << H[i] << " : " << frist[i]<<" " <<follow[i]<< endl;
}
cout << "-------------------------------------------------------" << endl;
cout << "当前LL(1)分析表格为：" << endl;
cout << " ";
for (int i = 0; i < strlen(L); i++) {
cout << L[i] << " ";
}
cout << endl;
for (int i = 0; i < num_ll; i++) {
cout << H[i] << ": ";
for (int j = 0; j < strlen(L); j++) {
if (strlen(LL1[i][j]) == 0) {
strcpy(LL1[i][j], "null");
}
cout.width(8);
cout.unsetf(ios::right);
cout.fill(' ');
cout <<LL1[i][j];
}
cout << endl;
}
cout << "-------------------------------------------------------" << endl;
}
void find_frist(char ll[100][100]) {
int temp;
int n_frist;//当前添加frist集元素位置
int if_the_frist_word;//判断当前符号是否为第一个符号
int location;//下次递归寻找的非终结符号的位置
for (int i = 0; i < num_ll; i++) {
n_frist = 0;
if_the_frist_word = 0;
for (int j = 3; j < strlen(ll[i]); j++) {
if (if_the_frist_word == 0) {//判断当前符号是否为第一个符号
temp = 0;//表示当前字符为非终结符号
location = 0;
for (int k = 0; k < strlen(H); k++) {
if (H[k] == ll[i][j]) {
location = k;
temp = 1;
break;
}
}
if (temp == 0) {//如果当前字符为终结符号
n_frist = strlen(frist[i]);
frist[i][n_frist] = ll[i][j];
}
else {
find_the_frist(location, ll, i);
}
}
if_the_frist_word = 1;
if (ll[i][j] == '|') {
if_the_frist_word = 0;//或符号的下一个符号要进行识别
}
}
}
}
void find_the_frist(int ll_index,char ll[100][100],int n_frist) {
int if_the_frist_word = 0;
int location;//表示当前找寻的非终结符号的位置
int temp;
int location_frist;
for (int j = 3; j < strlen(ll[ll_index]); j++) {
if (if_the_frist_word == 0) {//判断当前符号是否为第一个符号
temp = 0;//表示当前字符为非终结符号
location = 0;
for (int k = 0; k < strlen(H); k++) {
if (H[k] == ll[ll_index][j]) {
temp = 1;
location = k;
break;
}
}
if (temp == 0) {//如果当前字符为终结符号
location_frist = strlen(frist[n_frist]);
frist[n_frist][location_frist] = ll[ll_index][j];
}
else {
find_the_frist(location, ll, n_frist);//递归寻找
}
}
if_the_frist_word = 1;
if (ll[ll_index][j] == '|') {
if_the_frist_word = 0;//或符号的下一个符号要进行识别
}
}
}
void find_follow(char ll[100][100]) {
follow[0][0] = '#';//为开始符号添加终结符
int f_location;
int ff_location;
for (int i = 0; i < num_ll; i++) {
for (int j = 3; j < strlen(ll[i])-1; j++) {
if (location_H(ll[i][j]) != -1) {
if (location_H(ll[i][j + 1]) == -1&&ll[i][j+1]!='|') {
//如果后面字符为终结符，直接将其加入follow集
if (check(follow[location_H(ll[i][j])], ll[i][j + 1]) == 0) {
//判断当前字符是否已经存在
f_location = strlen(follow[location_H(ll[i][j])]);
follow[location_H(ll[i][j])][f_location] = ll[i][j + 1];
}
}
else {
//如果不是，则将其后面的非终结符号的frist集加入当前follow集
f_location = strlen(frist[location_H(ll[i][j+1])]);
for (int k = 0; k < f_location; k++) {
if (frist[location_H(ll[i][j + 1])][k] != 'N') {
//判断当前字符是否为空
if (check(follow[location_H(ll[i][j])], frist[location_H(ll[i][j + 1])][k]) == 0) {
ff_location = strlen(follow[location_H(ll[i][j])]);
follow[location_H(ll[i][j])][ff_location] = frist[location_H(ll[i][j + 1])][k];
}
}
}
}
}
}
}
for (int i = 0; i < num_ll; i++) {
for (int j = 3; j < strlen(ll[i]) - 1; j++) {
if (location_H(ll[i][j]) != -1) {
if (ll[i][j + 1] == '|') {
//如果该非终结符号后续没有符号
f_location = strlen(follow[location_H(ll[i][0])]);
for (int k = 0; k < f_location; k++) {
//判断当前字符是否为空
if (check(follow[location_H(ll[i][j])], follow[location_H(ll[i][0])][k]) == 0) {
ff_location = strlen(follow[location_H(ll[i][j])]);
follow[location_H(ll[i][j])][ff_location] = follow[location_H(ll[i][0])][k];
}
}
}
else if (location_H(ll[i][j + 1]) != -1) {
//如果后续为非终结符号
if (check(frist[location_H(ll[i][j + 1])], 'N') == 1) {
//该非终结符号可以推导出空
f_location = strlen(follow[location_H(ll[i][0])]);
for (int k = 0; k < f_location; k++) {
//判断当前字符是否为空
if (check(follow[location_H(ll[i][j])], follow[location_H(ll[i][0])][k]) == 0) {
ff_location = strlen(follow[location_H(ll[i][j])]);
follow[location_H(ll[i][j])][ff_location] = follow[location_H(ll[i][0])][k];
//该符号的follow集加上推原符号的follow集的内容
}
}
}
}
}
}
if (location_H(ll[i][strlen(ll[i]) - 1]) != -1) {
//如果该符号为该文法的最后一个符号且为非终结符号
f_location = strlen(follow[location_H(ll[i][0])]);
for (int k = 0; k < f_location; k++) {
//判断当前字符是否为空
if (check(follow[location_H(ll[i][strlen(ll[i]) - 1])], follow[location_H(ll[i][0])][k]) == 0) {
ff_location = strlen(follow[location_H(ll[i][strlen(ll[i]) - 1])]);
follow[location_H(ll[i][strlen(ll[i]) - 1])][ff_location] = follow[location_H(ll[i][0])][k];
}
}
}
}
}
void make_table(char ll[100][100]) {
int temp = 0;
int w = 2;
for (int i = 0; i < num_ll; i++) {
if (check(ll[i], '|') == 0) {
//当前检索文法中不含或
for (int j = 0; j < strlen(frist[i]); j++) {//遍历当前frist集
if (frist[i][j] == 'N') {
continue;
}
for (int k = 1; k < strlen(ll[i]); k++) {
LL1[i][location_L(frist[i][j])][k - 1] = ll[i][k];
}
}
}
else {
//当前文法中含或，则需要判断填入哪条文法
for (int j=0; j < strlen(frist[i]); j++) {
if (frist[i][j] == 'N') {
continue;
}
temp = 0;
for (int k = 3; k < strlen(ll[i]); k++) {
//遍历当前文法,由于前三个符号不使用,这里从3开始遍历
if (temp == 0) {
if (location_H(ll[i][k]) != -1) {
//判断当前符号为终结符号还是非终结符号
if (check(frist[location_H(ll[i][k])], frist[i][j]) == 1) {
//如果当前符号为frist集取自其文法中该符号的frist集
LL1[i][location_L(frist[i][j])][0] = '-';
LL1[i][location_L(frist[i][j])][1] = '>';
w = 2;//标记当前表格对应位置字符串长度
for (int r = k; r < strlen(ll[i]); r++) {
//将对应文法放入当前表格
LL1[i][location_L(frist[i][j])][w] = ll[i][r];
w++;
if (ll[i][r + 1] == '|')
break;
}
}
}
else if (ll[i][k] != 'N' && ll[i][k] == frist[i][j]) {
//当前符号为终结符号且不为空
LL1[i][location_L(frist[i][j])][0] = '-';
LL1[i][location_L(frist[i][j])][1] = '>';
w = 2;
for (int r = k; r < strlen(ll[i]); r++) {
LL1[i][location_L(frist[i][j])][w] = ll[i][r];
w++;
if (ll[i][r + 1] == '|')
break;
}
}
}
temp = 1;
if (ll[i][k] == '|') {
//只判断或符号后面的符号即可
temp = 0;
}
}
}
}
}
for (int i = 0; i < num_ll; i++) {
if (check(frist[i], 'N') == 1) {
for (int j = 0; j < strlen(follow[i]); j++) {
LL1[i][location_L(follow[i][j])][0] = '-';
LL1[i][location_L(follow[i][j])][1] = '>';
LL1[i][location_L(follow[i][j])][2] = '$';
}
}
}
}
int findH(char a)
{
for (int i = 0; i < strlen(H); i++)//找到对应行
{
if (a == H[i])
{
return i;
}
}
return -1;
}
int findL(char b)
{
for (int i = 0; i < strlen(L); i++)//找到对应列
{
if (b == L[i])
{
return i;
}
}
return -1;
}
int error(int i, int cnt, int len, char p[], char str[])
{
printf("%d\t\t%s\t\t", cnt, p);
for (int q = i; q < len; q++)
{
cout << str[q];
}
printf("\t\t报错\n");
return len;
}
void analyze(char str[1000], int len)
{
int cnt = 1;//输出Step专用
int i = 0;
int temp = 1;
char p[2000] = "#S";//输出stack专用
int pindex = 2;
printf("Step\t\tStack\t\tString\t\tRule\n");
while (i < len)
{
int x, y;
char ch = cmp.top();//读取栈顶元素
if (check(H,ch)==1)
{
cmp.pop();
x = findH(ch);//当前文法识别字符位置
y = findL(str[i]);//当前字符位置
if (x != -1 && y != -1)
{
int len2 = strlen(LL1[x][y]);
if (strcmp(LL1[x][y], "null") == 0)
{
i = error(i, cnt, len, p, str);
continue;
}
printf("%d\t\t%s\t\t", cnt, p);
if (p[pindex - 1] != '#' && pindex>0&&temp!=0 )
{
p[pindex] = '\0';
pindex--;
}
temp = 1;
if (LL1[x][y][2] != '$')
{
for (int q = len2 - 1; q > 1; q--)
{
p[pindex] = LL1[x][y][q];
cmp.push(LL1[x][y][q]);
pindex++;
}
}
if(pindex>0 && LL1[x][y][2] == '$')
{
p[pindex] = '\0';
pindex--;
temp = 0;
}
for (int q = i; q < len; q++)
{
cout << str[q];
}
printf("\t\t%c%s\n", ch, LL1[x][y]);
}
else
{
i = error(i, cnt, len, p, str);
continue;
///未找到，报错
}
}
else
{
if (ch == str[i])
{
cmp.pop();
printf("%d\t\t%s\t\t", cnt, p);
if (ch == '#' && str[i] == '#')
{
printf("#\t\t接受\n");
return;
}
for (int q = i; q < len; q++)
{
cout << str[q];
}
printf("\t\t%c匹配\n", ch);
p[pindex] = '\0';
pindex--;
i++;
}
else
{
i = error(i, cnt, len, p, str);
continue;
///报错
}
}
cnt++;
}
}
void openthefile() {
cout << "读取文件可知输入语句：" << endl;
FILE* fp;
char buf[1000];
if ((fp = fopen("E:\\desktop\\result.txt", "r")) != NULL) {
while (fgets(buf, 1000, fp) != NULL)
{
int len = strlen(buf);
printf("%s \n", buf);
int flag = 0;
for (int i = 0; i < len; i++) {
if (buf[i] == '(' && flag == 0) {
flag = 1;//识别符号
for (int j = i + 1; j < len; j++) {
if (buf[j] == ',') {
shizi[strlen(shizi)]= buf[j + 1];
if ((buf[j + 1] >= 'a' && buf[j + 1] <= 'z') ||
(buf[j + 1] >= 'A' && buf[j + 1] <= 'Z')) {
like[strlen(like)] += 'i';
}
else like[strlen(like)] = buf[j + 1];
i = j + 1;
break;
}
}
}
else if (flag == 1 && buf[i] == ')') {
flag = 0;
}
}
}
}
shizi[strlen(shizi)] = '#';
like[strlen(like)] = '#';
fclose(fp);
cout << "-------------------------------------------------------" << endl;
cout << "输入的语句为：" << shizi << endl;
cout << "将其转化为：" << like << endl;
cout << "-------------------------------------------------------" << endl;
}
int main()
{
LL_1table(LL_1);
openthefile();
int len = strlen(like);
cmp.push('#');
cmp.push('S');
analyze(like, len);
return 0;
}
文章出处登录后可见！
已经登录？立即刷新
