编译原理实验报告语法分析程序的设计文档编制序号：[KK8UY-LL9IO69-TTO6M3-MTOL89-FTT688]实验5语法分析程序的设计（2）一、实验目的通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中算法优先分析方法。
二、实验内容设计一个文法的算法优先分析程序，判断特定表达式的正确性。
三、实验要求1、给出文法如下：G[E]E->T|E+T;T->F|T*F;F->i|(E);+*()i+*()i21）直接存放，2）为优先关系建立优先函数，这里由学生自己选择一种方式；1、给出算符优先分析算法如下：k:=1; S[k]:=‘#’;REPEAT把下一个输入符号读进a中；IF S[k]∈V T THEN j:=k ELSE j:=k-1;WHILE S[j] a DOBEGINREPEATQ:=S[j];IF S[j-1]∈V T THEN j:=j-1 ELSE j:=j-2UNTIL S[j] Q把S[j+1]…S[k]归约为某个N；k:=j+1;S[k]:=N;END OF WHILE;IF S[j] a OR S[j] a THENBEGINk:=k+1;S[k]:=aENDELSE ERRORUNTIL a=‘#’1、根据给出算法，利用适当的数据结构实现算符优先分析程序；2、利用算符优先分析程序完成下列功能：1）手工将测试的表达式写入文本文件，每个表达式写一行，用“；”表示结束；2）读入文本文件中的表达式；3）调用实验2中的词法分析程序搜索单词；4）把单词送入算法优先分析程序，判断表达式是否正确（是否是给出文法的语言），若错误，应给出错误信息；5）完成上述功能，有余力的同学可以对正确的表达式计算出结果。
四、实验环境PC微机DOS操作系统或 Windows 操作系统Turbo C 程序集成环境或 Visual C++ 程序集成环境五、实验步骤1、分析文法中终结符号的优先关系；2、存放优先关系或构造优先函数；3、利用算符优先分析的算法编写分析程序；4、写测试程序，包括表达式的读入和结果的输出；5、程序运行效果，测试数据可以参考下列给出的数据。
六、测试数据输入数据：编辑一个文本文文件，在文件中输入如下内正确结果：（1）10;输出：正确（2）1+2;输出：正确（3）(1+2)*3+(5+6*7);输出：正确（4）((1+2)*3+4输出：错误（5）1+2+3+(*4+5)输出：错误（6）(a+b)*(c+d)输出：正确（7）((ab3+de4)**5)+1输出：错误七、实验报告要求实验报告应包括以下几个部分：1、2、算符优先分析程序的算法和结构；程序从文本文件中逐行读取表达式，每行以“；”做标记。
调用词法分析程序将这行数据分析出由一个个的单词组成的表达式，再逐个分析单词。
另外，由于文法中没写入关于标识符和常数的产生式，所以在对单词符号进行语法分析时，会将标识符和常数自动规约为“i”。
数据结构：优先关系表R：二维数组，存储了终结符+、*、（、）、i、#的优先关系。
符号W：结构体，有四个成员，包括：ch：char类型，非终结符与终结符的字符标记；po：int类型，只对终结符有效，与在R中的位置有关，有词法分析器提供；对于非终结符，其po无效；val：string类型，综合属性；对终结符i，其值由词法分析器提供；对非终结符，其值由规约时对应的产生式的规则计算得到；对界符或运算符，val无效；type：int类型，标记属性值类型，0为标识符，不可计算；1为可计算的数值；由词法分析器提供；注意：程序内部数值的计算和标记一律使用十进制，文本中的表达式必须为十进制整数，即如果在文本中使用八进制或十六进制，词法分析器分析后不会添加至缓冲区，在表达式语法正确且其中不含标志符时，计算得到的结果一律使用十进制。
例：对于文本中十进制数字10，其对应的初始结构体成员的值ch=’i’，po=5，val=”10”，type=1。
符号栈S：符号结构体的一维数组。
算法：说明：G[E]E->T|E+T;T->F|T*F;F->i|(E);算符优先文法并未对非终结符定义优先关系，无法对单非产生式进行规约，所以实际上在规约时，上面的E->T，T->F基本没有使用，而且规约时并不严格按照产生式的右部规约，只要待规约项符合句型#N1a1N2a2…NnanNn+1#（每个ai都是终结符，Ni是可有可无的非终结符），并且相对产生式，在相同位置有相同的非终结符即可规约，这样算符优先文法规约很快，但有些语法错误将无法识别，在本实验中，只要在要规约的地方准确的判断可规约的项，即符合句型，在不严格要求非终结符相同而终结符位置符号相同时，存在可匹配文法的产生式，即可规约，例如：F * F 可以匹配T*F继而规约为T。
定义用W[ch]表示字符名为ch的符号；实际程序中关于终结符优先关系的比较是利用R获取优先关系标志的，算法中为了可读性，直接将结构体进行比较了。
从文本文件读入一行数据，反复调用scanP()得到符号集合，用符号结构体数组E存储；k = 1; i = 0; S[k] = W[#];Do {A = E[i++];if（S[k] 是终结符）j = k;elsej = k – 1;while(S[j] > A) {Do {Q = S[j];If(S[j - 1] 是终结符)j = j – 1;elsej = j – 2;}while(S[j] < Q);N = Statute(S,j + 1,k);k = j + 1；S[k] = N；}If(S[j] < A || S[j] == A) {k++;S[k] = A;}else error(S[j].po,;}while(A == W[#]);程序功能说明：程序从文本文件读入表达式，判断语法是否正确，正确则输出结果，其中有标识符的话，结果还是含有标识符的原表达式，语法错误的话，则输出错误信息。
源程序：程序中文本文件在桌面文件名为#include<iostream>#include<string>#include<>using namespace std;#define NULL 0#define MAXSIZE 30 h == 'i' && s == e) {= 'F';= S[s].val;= S[s].type;}else if (S[s].ch == '(' && !(checkVt(S[s + 1].ch)) &&S[e].ch == ')') {if (S[s + 1].type == 1) {= 'F';= S[s + 1].val;= S[s + 1].type;}else {= 'F';= '('+ S[s + 1].val + ')';= S[s + 1].type;}}else if (!(checkVt(S[s].ch)) && S[s + 1].ch == '+'&& !(checkVt(S[e].ch))) {= 'E';if (S[s].type == 1 && S[e].type == 1) {= 1;int v = atoi(S[s].()) + atoi(S[e].());char l[30];sprintf_s(l,30,"%d", v);= l;}else {= 0;= S[s].val + S[s + 1].ch + S[e].val;}}else if ((s != e) && !(checkVt(S[s].ch)) && S[s + 1].ch == '*' && !(checkVt(S[e].ch))) {= 'T';if (S[s].type == 1 && S[e].type == 1) {= 1;int v = atoi(S[s].()) * atoi(S[e].());char l[30];sprintf_s(l, 30,"%d", v);= l;}else {= 0;= S[s].val + S[s + 1].ch + S[e].val;}}else if(S[s].ch == 'T' && s == e){= 'E';= S[s].val;= S[s].type;}else {= '#';}= 4;return N;}void error(char errnum) { h)) o][] == '>') {do {Q = S[j];if (checkVt(S[j - 1].ch))j = j - 1;elsej = j - 2;} while (pre[S[j].po][] != '<');W N = Statute(S, j + 1, k);if == '#') {error('4');return 0;}k = j + 1;S[k] = N;}if (pre[S[j].po][] == '<' || pre[S[j].po][] == '=') { k++;S[k] = A;}else {error(pre[S[j].po][]);return 0;}} while != '#');if == '#') {printf("正确，结果为：%s\n\n", S[k - 1].());return 0;}}int main() {FILE* fp;errno_t err;if ((err =fopen_s(&fp,"C:\\Users\\Administrator\\Desktop\\", "r")) != NULL) { //以只读方式打开文件，失败则退出程序printf("file can not open!");exit(0);}int n = 0;printf("语法分析结果如下：\n\n");while (!feof(fp)) { //若不是文件尾则执行循环int num = 0;W E[MAXSIZE]; //存储一行表达式GetBC(fp);if (!feof(fp)) {n++;fseek(fp, -1L, 1);printf("(%d)", n);}else {break;}while (1) { //只读一行，行末标志为“；”int flag = scan(fp, E,num);if (flag == 0) break;num++;}printf("\n输出：");syntax(E,num);}fclose(fp); //关闭文件fp = NULL; //避免指向非法内存}Pascal的repeat…until与C语言的do…while并一样，实验时不注意会使程序出错，二者的循环条件是相反的。