东北大学编译原理实验报告

编译原理程序设计实验报告 表达式语法分析器的设计与实现 班级： 姓名： 学号： 实验目标： 用两种不同的方法设计一个表达式的语法分析器 实验内容： ① LL(1) 分析法 LL (1)文法是一种自上而下的语法分析方法，它是从文法的识别符号出 发，生成句子的最左推导，从左到右扫描源程序，每次向前查看 1 个字符，便能 确定当前应该选择的产生式。 LL ( 1)分析需要用到一个分析表 M和一个符号栈S,分析表M是一个矩 阵，它的元素可以存放一个非终结符的产生式， 表明当符号栈S的栈顶元素非终 结符遇到当前输入字符时，所应选择的产生式； M的元素还可以是存放一个出错 标志，说明符号栈S的栈顶元素非终结符不应该遇到当前输入字符(终结符)。 重复调用 LL (1)分析方法对每一个输入字符进行分析，直到输入栈为空 为止。 ②递归下降子程序 递归下降分析法，在判断一个表达式时首先进入 E然后调用T在调用F,判 断是否为“(”或字符或常数，如果不是报错，是“(”的话再进入 E,是字符 或常数的话跳出递归。然后进入 T 中下一步，判断是否为“ *”，是的话进入 T 子递归，不是的话跳出，进入 E 的下一步判断是否为“ +”，是的话进入 E 的子 递归，不是的话跳出回到主程序。当 ch 标识符为 #时结束。 入口

源程序代码：（加入注释） LL⑴分析算法：

#include #include using namespace std; #define STACKSIZE 50

主程宇 子甩宇

E： 开始 ・入口 I

子程宇F：

子理呼T： #define STACKINCREMENT 10 #define OK 1 #define error 0 #define overflow -1 typedef char SElemType; typedef int Status; typedef struct { SElemType *base; SElemType *top;

Int stacksize; }SqStack; Status InitStack(SqStack &S) { S.base = (SElemType * )malloc(STACKSIZE * sizeof(SElemType)); if (!S.base) exit(overflow);

S.top=S.base; S.stacksize=STACKSIZE; return OK; } Status Push(SqStack &S, SElemType e) { if (S.top - S.base >= S.stacksize) { S.base = (SElemType * )realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));

if (!S.base) exit(overflow); S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } (S.top)++; *(S.top) = e; return OK; } Status Pop(SqStack &S, SElemType &e) { if (S.top == S.base)

return error; e = *(S.top); S.top--;

return OK; } Status GrammerAnalysis(SqStack &S, char *ch, char c) { SElemType e; Push(S, '#');

Push(S, 'E'); while (!((*(S.top) == '#') && (c == '#'))){ Pop(S, e); if ((e == 'E') && (((c >= '0') && (c <= '9')) ||(c>='a'&&c<='z')|| (c == '('))) { Push(S , 'A'); Push(S , 'T');

} else if ((e == 'A') && (c == '+')) { Push(S , 'A'); Push(S , 'T'); ch++; c = *ch; } else if ((e == 'A') && ((c == ')')||(c == '#'))); else if ((e == 'T') && (((c >= '0') && (c <= '9')) ||(c>='a'&&c<='z')|| (c == '('))) Push(S , 'B'); Push(S , 'F'); } else if ((e == 'B') && (c == '*')) { Push(S , 'B'); Push(S , 'F'); ch++; c = *ch;

} else if ((e == 'B') && ((c == '+')||(c == ')')||(c == '#'))); else if ((e == 'F') && ((c>='0'&&c<='9')||(c>='a'&&c<='z'))) {

ch++; while (((c = *ch) >= '0') && (c <= '9')||(c>='a'&&c<='z')) ch++; } else if ((e == 'F') && (c == '(')) { Push(S, ')');

Push(S, 'E'); ch++; c = *ch;

} else if ((e == ')') && (c == ')')) {ch++;

c = *ch; } else return error; } return OK; } int main() { char str[50]; char c; system("color 0B"); SqStack S; InitStack(S); printf("| ----------------------------------------------- |\n"); printf("| 请输入表达式，以 #键结束 : |\n"); printf("| ----------------------------------------------- |\n"); scanf("%s", str); c = *str; if (GrammerAnalysis(S,str,c)) { printf(" 语法分析通过 \n"); printf(" 表达式正确 \n");

} else{

printf(" 语法分析未通过 \n"); printf(" 表达式错误 \n");} main(); return 0; }

递归下降

#include using namespace std; int a=1; char ch; int i=0; char str[80]; void T(void); void F(void); void E(void); void Error(void); if(ch==')') { i++; ch=str[i]; } else {Error();a=0;} } else if((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z')) { i++;

ch=str[i]; } else

{ Error(); a=0; } } void E(void){ // 子程序 E T();

if(ch=='+') { i++; ch=str[i];

void Error() // { cout<<" 语法错误 "<} void T(void) { F();

if(ch=='*') { i++; ch=str[i]; T();} }

// //

void F(void) { if(ch=='(') { i++;

// //

ch=str[i]; E(); //

出错函数

子程序 T

进入子程序 F

递归子程序 T

子程序 F

回到子程序 E } }

int main() // 主函数 {

system("color 0B"); cout<<"| ------------------------------------------------ |">str; ch=str[0]; while(ch!='#') { E();

if(!a) break; } if((ch=='#') && ( a != 0)) // 遇# 且 a 不等于零时语法正确

cout<<" 语法正确 "

程序运行结果： (截屏) LL(1) 分析法：

递归下降：

E(); // 递归子程序 E