编译原理实验报告5-语法分析程序的设计(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、 给定文法优先关系和存放方式； # + * ( ) i + * e1 ( e2 e2 ) e2 e2 i e4 # e3 引入“#”，将句型包含起来并填入出错标记。

使用二维数组将其存放。

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 可以匹

从文本文件读入一行数据，反复调用scanP()得到符号集合，用符号结构体数组E存储； k = 1; i = 0; S[k] = W[#]; Do {

A = E[i++];

if（S[k] 是终结符） j = k; else

j = k – 1;

while(S[j] > A) { Do {

Q = S[j];

If(S[j - 1] 是终结符) j = j – 1; else

j = 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,A.po); }while(A == W[#]); 程序功能说明：

程序从文本文件读入表达式，判断语法是否正确，正确则输出结果，其中有标识符的话，结果还是含有标识符的原表达式，语法错误的话，则输出错误信息。 源程序：

程序中文本文件在桌面文件名为expression.txt

#include

配T*F继而规约为T。

定义用W[ch]表示字符名为ch的符号；实际程序中关于终结符优先关系的比较是利用R获取优先关系标志的，算法中为了可读性，直接将结构体进行比较了。

#include #include using namespace std; #define NULL 0 #define MAXSIZE 30

//单行表达式的符号总数最

大值

typedef struct grammar_symbol

//文法符号

{ char ch; int po; string val; int type; }W;

char pre[6][6] = {

//优先关系表

{ '>', '<', '<', '>', '<','>' }, { '>', '>', '<', '>', '<', '>' }, { '<', '<', '<', '=', '<', '1' }, { '>', '>', '2', '>', '2', '>' }, { '>', '>', '2', '>', '2', '>' }, { '<', '<', '<', '3', '<', '=' }

};

char GetChar(FILE* fp) { //读取文件中的一个字符 char ch; ch = fgetc(fp); return ch; }

char GetBC(FILE* fp) {

//读取文件的字符直至

ch不是空白 char ch; do {

ch = GetChar(fp);

} while (ch == ' ' || ch == '\\t' || ch == '\\n'); return ch; }

void Concat(char ch, char strToken[]) { //将ch中的字符连接到strToken之后 char str[2];

int len = strlen(strToken); strToken[len] = ch; strToken[len + 1] = '\\0'; }