大家好,下面介绍的是我当时上编译原理所做的实验,主要内容就是根据已有的文法,构造文法的first集和follow集,然后再根据构造好的first集和follow集构造预测分析表,最后,设置一个栈,然后利用栈和预测分析表来对输入串进行分析,判断输入串是否是该文法的一个合适的语法范畴。用的是最基本的C语言写的,如有不足,欢迎大家批评指正!
一、实验目的通过预测分析算法的设计与实现,加深对自上而下语法分析方法的理解,尤其是对自上而下分析条件的理解。
二、实验内容输入文法及待分析的输入串,输出其预测分析过程及结果。
三、实验设计1)首先根据课本上的知识构造该文法的first集和follow集,对文法先进行简单的处理,便于后续 *** 作
2)根据first集和follow集构造预测分析表
3)设置一个栈,然后利用栈和预测分析表来对输入串进行分析,判断输入串是否是该文法的一个合适的语法范畴
运行效果,由于结果太长,我就把结果截取成了若干图片以便展示
代码由三个文件构成,如下图所示,其中,Hong.h中主要是对一下常用的变量进行宏定义,fun.h中是对各种方法的实现,main.c则是对fun.h中实现的方法的简单的调用,一些需要注意的地方都在代码中以注释的形式展现,话不多说,上代码!
Hong.h
#include#include #define STACK_INIT_SIZE 100 //存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 typedef char SElemType; typedef struct //定义栈的结构体 { SElemType *base; SElemType *top; int stacksize; } SqStack; int len_gram = 0; //产生式的句数 int len_ter = 0; //终结符数组的长度 int len_non_ter = 0; //非终结符数组的长度 int len_first = 0; //first集合的个数 int len_follow = 0; //follow集合的个数 int flag_first = 1; //作为first集不再扩大的标志 int flag_follow = 1; //作为follow集不再扩大的标志 char gramOldSet[200][200]; //原始文法的产生式 char terSymbol[200]; //终结符 char non_ter[200]; //非终结符 char allSymbol[400]; //所有符号 char firstSet[100][100]; //各产生式右部的first集合 char followSet[100][100]; //各产生式左部的follow集合 int M[200][200]; //分析表,里面存的都是在相应数组中的地址
fun.h
#include "Hong.h" //初始化 int InitStack(SqStack *S) { S->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if (!S->base) { printf("无法创建堆栈!n"); exit(0); } S->top = S->base; S->stacksize = STACKINCREMENT; return 1; } //获取栈顶元素 char GetTop(SqStack *S) { if (S->top == S->base) return ' '; return *(S->top - 1); } //将元素压入堆栈 int Push(SqStack *S, SElemType e) { if (S->top - S->base >= STACK_INIT_SIZE) { S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType)); if (!S->base) { printf("无法扩展堆栈n"); exit(0); } S->top = S->base + S->stacksize; S->stacksize += STACKINCREMENT; } *S->top++ = e; return 1; } //将栈顶元素d出 char Pop(SqStack *S) { if (S->top == S->base) return ' '; return *--S->top; } //区分是终结符还是非终结符 int check(char c) { if (c >= 'A' && c <= 'Z') return 1; //表示是非终结符 else if (c == '@' || c == '|' || c == ' ' || c == 'n' || c == 'r') return 0; //表示一些无关的元素 else return 2; //表示是终结符 } //判断数组中是否含有字符c int have_char(char str[], char c, int len) { for (int i = 0; i < len; i++) { if (c == str[i]) return 1; } return 0; } //从文件中读取产生式,并将产生式分解,区分终结符和非终结符 int Yu(char s[]) { FILE *fp; fp = fopen(s, "r"); char temp_gram[200]; int index_temp_gram = 3; int index_gram = 0; if (fp != NULL) { printf("文件中的产生式为n"); while (fgets(temp_gram, 200, fp) != NULL) { printf("%s", temp_gram); char gram_right = temp_gram[0]; //保存产生式左部的字符,用作扩展 index_temp_gram = 3; index_gram = 0; gramOldSet[len_gram][0] = gram_right; gramOldSet[len_gram][1] = '-'; gramOldSet[len_gram][2] = '>'; index_gram = 3; while (temp_gram[index_temp_gram] != '') { if (temp_gram[index_temp_gram] == 'n' || temp_gram[index_temp_gram] == 'r') { gramOldSet[len_gram][index_gram] = ''; //每个产生式都已''结尾,方便后面的遍历 len_gram++; break; } else if (temp_gram[index_temp_gram] == '|') //如果遇到或,说明该拆分了 { index_temp_gram++; gramOldSet[len_gram][index_gram] = ''; len_gram++; gramOldSet[len_gram][0] = gram_right; gramOldSet[len_gram][1] = '-'; gramOldSet[len_gram][2] = '>'; index_gram = 3; } gramOldSet[len_gram][index_gram] = temp_gram[index_temp_gram]; index_gram++; index_temp_gram++; } } gramOldSet[len_gram][index_gram] = ''; //遍历到最后,最后一个产生式还没有加上'' len_gram++; } else { printf("文件无法打开!"); } //显示处理过的产生式 printf("n处理过的产生式为n"); for (int i = 0; i < len_gram; i++) { printf("%sn", gramOldSet[i]); } //区分终结符和非终结符 for (int i = 0; i < len_gram; i++) { for (int j = 3; gramOldSet[i][j] != ''; j++) { char temp = gramOldSet[i][j]; int value_return = check(temp); if (value_return == 1) { if (!have_char(non_ter, temp, len_non_ter)) { non_ter[len_non_ter] = temp; len_non_ter++; } } else if (value_return == 2) { if (!have_char(terSymbol, temp, len_ter)) { terSymbol[len_ter] = temp; len_ter++; } } else { continue; } } } //显示终结符和非终结符 printf("终结符都有:n"); for (int i = 0; i < len_ter; i++) { printf("%c ", terSymbol[i]); } printf("n"); printf("非终结符都有:n"); for (int i = 0; i < len_non_ter; i++) { printf("%c ", non_ter[i]); } printf("n"); return 0; } //初始化first集 void init_first() { int temp = 0; while (temp < len_non_ter) { firstSet[len_first][0] = non_ter[temp]; firstSet[len_first][1] = ''; //结尾加上'',方便后面的遍历 temp++; len_first++; } temp = 0; while (temp < len_ter) { firstSet[len_first][0] = terSymbol[temp]; firstSet[len_first][1] = terSymbol[temp]; firstSet[len_first][2] = ''; temp++; len_first++; } } //初始化follow集 void init_follow() { int temp = 0; while (temp < len_non_ter) { followSet[len_follow][0] = non_ter[temp]; followSet[len_follow][1] = ''; temp++; len_follow++; } } //显示first集和follow集 void show() { printf("first集都有n"); for (int i = 0; i < len_first; i++) { printf("first(%c)= ", firstSet[i][0]); int j = 1; while (firstSet[i][j] != '') { printf("%c", firstSet[i][j]); printf(" "); j++; } printf("nn"); } printf("follow集都有n"); for (int i = 0; i < len_follow; i++) { printf("follow(%c)= ", followSet[i][0]); int j = 1; while (followSet[i][j] != '') { printf("%c", followSet[i][j]); printf(" "); j++; } printf("nn"); } } //定位first集和follow集的位置 int find_position(char c, char str[][100], int length) { for (int i = 0; i < length; i++) { if (str[i][0] == c) return i; } return -1; //说明没有找到 } //判断数组是否为空 int Is_empty(char str[]) { if (str[1] == '') return 1; return 0; } //将字符加入数组中,具有判重的功能 void add_element(char str[], char c) { int i = 0; while (str[i] != '') { if (str[i] == c) return; i++; } str[i] = c; i++; flag_first = 1; //first还在扩大的标志 flag_follow = 1; //follow集还在扩大的标志 str[i] = ''; } //判断是否是终结符或者空字 int is_ter(char c, char str[], int len) { for (int i = 0; i < len; i++) { if (str[i] == c || c == '@') return 1; } return 0; } //将str2数组合并到str1数组中 void merge_Set(char str1[], char str2[]) { int i = 1; while (str2[i] != '') { char t = str2[i]; add_element(str1, t); //具有判重功能 i++; } } //将str2数组中的空字去掉后加入str1数组 void merge_firstSet_null(char str1[], char str2[]) { int i = 1; while (str2[i] != '') { char t = str2[i]; if (t != '@') { add_element(str1, t); } i++; } } //判断是否含有空字 int have_null(char str[]) { int i = 0; while (str[i] != '') { if (str[i] == '@') return 1; i++; } return 0; } //构造first集 void creat_first() { init_first(); while (flag_first) //一直循环到标志符号位0 { flag_first = 0; //每次遍历前都要置0 for (int i = 0; i < len_gram; i++) { char right_gram = gramOldSet[i][0]; //获取产生式左部的符号 int index_first_right = find_position(right_gram, firstSet, len_first); //获取产生式左部符号所在的first集的位置 int j = 3; //指向产生式右部的第一个字符 while (gramOldSet[i][j] != '') //遍历产生式右部 { char left_gram = gramOldSet[i][j]; if (is_ter(left_gram, terSymbol, len_ter)) //如果第一个是终结符 { //加入到first集中,并结束遍历 add_element(firstSet[index_first_right], left_gram); break; } else { int index_first_left = find_position(left_gram, firstSet, len_first); //说明是非终结符,获取该非终结符在first集的位置 if (Is_empty(firstSet[index_first_left])) //如果它的first是空的结束遍历,查看下一个产生式 { break; } else //如果它的first集不是空的 { if (have_null(firstSet[index_first_left])) //判断它的first集中是否含有空字 { //如果含有空字,将他的first集出去空字加入,并且不跳出循环,继续遍历下一个字符 merge_firstSet_null(firstSet[index_first_right], firstSet[index_first_left]); } else //如果不含空字,将它的first集加入到产生式左部的first集中,并退出 { merge_Set(firstSet[index_first_right], firstSet[index_first_left]); break; } } } j++; } if (gramOldSet[i][j] == '') //说明前面while循环没有break,产生式右部都是非终结符,并且他们的first集中都含有空字 { add_element(firstSet[index_first_right], '@'); } } } } //获取产生式的长度 int length_gram(char str[]) { int i = 0; while (str[i] != '') { i++; } return i; } //构造follow集 void creat_follow() { init_follow(); //初始化follow集 add_element(followSet[find_position(gramOldSet[0][0], followSet, len_follow)], '#'); //将#加入开始符号的follow集中 while (flag_follow) //一直循环到follow集不再扩大为止 { flag_follow = 0; //每次遍历前都要置零 for (int i = 0; i < len_gram; i++) { char right_gram = gramOldSet[i][0]; //获取产生式左部的字符 A int index_firstSet = find_position(right_gram, firstSet, len_first); //获取A所在first集数组中的位置 int index_followSet_right = find_position(right_gram, followSet, len_follow); //获取A所在follow集数组中的位置 int length = length_gram(gramOldSet[i]); //获取该产生式的长度 for (int point_aim = 3; point_aim < length; point_aim++) //从产生式右部的第一个字符开始 { char head = gramOldSet[i][point_aim]; //接下来就是求它head的follow集 int index_followSet = find_position(head, followSet, len_follow); //获取head所在follow集数组中的位置 if (index_followSet != -1) //说明在follow集中找到了,也就是说head是一个非终结符 { if (point_aim == length - 1) { //如果head是最后一个元素,将A的follow集加入head的follow集中 merge_Set(followSet[index_followSet], followSet[index_followSet_right]); } else //如果head不是最后一个元素 { int next = point_aim + 1; //获取head后面的元素next int temp_flag = 0; while (next < length) { //获取next在first集的位置 int index_firstSet_temp = find_position(gramOldSet[i][next], firstSet, len_first); while (have_null(firstSet[index_firstSet_temp])) //一直到next的first集中没有空字为止 { merge_firstSet_null(followSet[index_followSet], firstSet[index_firstSet_temp]); //将next除去空字加入到head的follow集中 next++; if (next == length) { //如果遍历到最后一个元素,将next的follow集加入head的follow集中 int index_firstSet_temp = find_position(gramOldSet[i][next - 1], followSet, len_follow); merge_Set(followSet[index_followSet], followSet[index_firstSet_temp]); temp_flag = 1; //设置标志位,用于跳出循环 break; } index_firstSet_temp = find_position(gramOldSet[i][next], firstSet, len_first); } if (temp_flag) //如果遍历到最后一个字符了,就跳出循环 { break; } merge_firstSet_null(followSet[index_followSet], firstSet[index_firstSet_temp]); //如果在中间跳出上一个循环了,说明该next所指向的字符的first集没有空字,也要加到head的follow集中 break; } } } } } } } //初始化预测分析表 void init_forecastTable() { for (int i = 0; i <= len_non_ter; i++) { for (int j = 0; j <= len_ter; j++) { M[i][j] = -1; } } } //显示预测分析表 void show_table() { printf("nn预测分析表如下nn"); for (int i = 0; i <= len_non_ter; i++) { for (int j = 0; j <= len_ter; j++) { if (i == 0) { if (j == 0) { printf("0t"); } else printf("%ct", terSymbol[j - 1]); } else if (j == 0) { if (i == 0) { printf("0t"); } else printf("%ct", non_ter[i - 1]); } else { printf("%st", gramOldSet[M[i][j]]); } } printf("n"); } printf("n"); } //找到字符c在相应数组中的位置 int find_position_char(char c, char str[], int len) { for (int i = 0; i < len; i++) { if (c == str[i]) { return i; } } return -1; } //构造预测分析表 void creat_forecastTable() { //先将#加入终结符数组 terSymbol[len_ter] = '#'; len_ter++; init_forecastTable(); //遍历每一个产生式 for (int i = 0; i < len_gram; i++) { //获取产生式左部的字符,并获取它的位置,++的原因和构造表有关 char left_gram = gramOldSet[i][0]; int index_non = find_position_char(left_gram, non_ter, len_non_ter); index_non++; //求阿尔法的first集,也就是产生式右部的first集 char temp_first[100]; temp_first[0] = ''; //表示结束,方便后面的遍历 int j = 3; //指向产生式右部的第一个符号 while (gramOldSet[i][j] != '') //遍历产生式右部 { char left_gram = gramOldSet[i][j]; if (is_ter(left_gram, terSymbol, len_ter)) //如果第一个是终结符 { //加入到first集中,并结束遍历 add_element(temp_first, left_gram); break; } else { int index_first_left = find_position(left_gram, firstSet, len_first); //说明是非终结符,获取该非终结符在first集的位置 if (Is_empty(firstSet[index_first_left])) //如果它的first是空的结束遍历,查看下一个产生式 { break; } else //如果它的first集不是空的 { if (have_null(firstSet[index_first_left])) //判断它的first集中是否含有空字 { //如果含有空字,将他的first集出去空字加入,并且不跳出循环,继续遍历下一个字符 merge_firstSet_null(temp_first, firstSet[index_first_left]); } else //如果不含空字,将它的first集加入到产生式左部的first集中,并退出 { merge_Set(temp_first, firstSet[index_first_left]); break; } } } j++; } if (gramOldSet[i][j] == '') //说明前面while循环没有break,产生式右部都是非终结符,并且他们的first集中都含有空字 { add_element(temp_first, '@'); } //求完first阿尔法之后,判断first阿尔法是否含有空字 int k = 0; while (temp_first[k] != '') { if (temp_first[k] != '@') //除了空字,因为后面有专门对含有空字的处理 { int index_ter = find_position_char(temp_first[k], terSymbol, len_ter); index_ter++; M[index_non][index_ter] = i; } k++; } if (have_null(temp_first)) { int index_followSet = find_position(left_gram, followSet, len_follow); int t = 1; char c = followSet[index_followSet][t]; while (c != '') { int index_ter = find_position_char(c, terSymbol, len_ter); index_ter++; M[index_non][index_ter] = i; t++; c = followSet[index_followSet][t]; } } } } //总控程序 void control(char str[]) { printf("开始总控程序"); SqStack stack; InitStack(&stack); //将'#'压入堆栈 Push(&stack, '#'); //将开始符号压入堆栈 Push(&stack, gramOldSet[0][0]); int pointer = 0; //指向数组的指针 int flag = 1; int step = 1; while (flag) { printf("nn步骤%dn", step); //取栈顶元素 char top = GetTop(&stack); printf("栈顶元素为 %cn", top); //如果栈顶元素不是#,并且为终结符 if (top != '#' && is_ter(top, terSymbol, len_ter)) { if (top == str[pointer]) //如果和外面相同 { printf("栈顶元素%c和栈外元素%c一样,从堆栈弹出%c,指针指向下一个字符n", top, str[pointer], top); Pop(&stack); pointer++; } else //否则出错 { printf("ERROR 1n"); break; } } else if (top == '#') { //结束 if (top == str[pointer]) { printf("栈顶元素%c 和栈外元素%c一样n", top, str[pointer]); printf("接收完成n"); flag = 0; } else { //报错 printf("ERROR 2n"); break; } } else { int index_non = find_position_char(top, non_ter, len_non_ter); index_non++; int index_ter = find_position_char(str[pointer], terSymbol, len_ter); index_ter++; int index_gram = M[index_non][index_ter]; //判断表中是否有表达式 if (index_gram != -1) { //如果有,先弹出,再逆序压栈 printf("M(%c,%c)对应的产生式为%s,将%s压入堆栈n", top, str[pointer], gramOldSet[index_gram], gramOldSet[index_gram]); Pop(&stack); printf("将栈顶元素%c弹出n", top); if (gramOldSet[index_gram][3] != '@') { int length = length_gram(gramOldSet[index_gram]); for (int i = length - 1; i > 2; i--) { printf("将%c压入堆栈n", gramOldSet[index_gram][i]); Push(&stack, gramOldSet[index_gram][i]); } } } else { printf("ERROR 3n"); break; } } step++; } if (!flag) { printf("success!n"); } }
main.c
大家可以自行新建文本文件,只需要把对应的文件地址改一下即可,具体说明在注释中
#include "fun.h" int main() { Yu("E:\test\shiyan2\source.txt"); //从文件中读取产生式,并进行预处理 creat_first(); //生成first集 creat_follow(); //生成follow集 show(); //显示生成的first集和follow集 creat_forecastTable(); //生成预测分析表 show_table(); //显示预测分析表 control("(i+i)*i+i#"); //将输入字符串传给总控程序,由总控程序识别 return 0; }
source.txt文件中文法
E->TP P->+TP|@ T->FQ Q->*FQ|@ F->(E)|i
写在最后,如果大家觉得这篇文章对你有帮助的话,还请大家赞一下下啦 : )
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)