爱华网表达式语法分析设计
一、 实验目的：
熟悉并设计一个表达式的语法分析器
二、实验内容：
1．设计表达式的语法语法分析器算法
2．编写代码并上机调试运行通过
要求： 输入------------ 表达式
输出------------ 表达式语法是否正确
三、 设计概要：
运用算术表达式的LL(1) 分析算法来设计的表达式的语法分析器。
LL（1）文法是一种自上而下的语法分析方法，它是从文法的识别符号出发，生成句子的最左推导，从左到右扫描源程序，每次向前查看1个字符，便能确定当前应该选择的产生式。
LL（1）分析需要用到一个分析表M和一个符号栈S，分析表M是一个矩阵，它的元素可以存放一个非终结符的产生式，表明当符号栈S的栈顶元素非终结符遇到当前输入字符时，所应选择的产生式；M的元素还可以是存放一个出错标志，说明符号栈S的栈顶元素非终结符不应该遇到当前输入字符（终结符）。
重复调用LL（1）分析方法对每一个输入字符进行分析，直到输入栈为空为止。
四、源程序(包含注释)
“stack.h”//栈的定义
#define STACK_INIT_SIZE 10 // 存储空间初始分配量
#define STACKINCREMENT 2 //存储空间分配增量
typedef struct
{
char *base;
char *top;
int stacksize;
}SqStack; // 顺序栈
void InitStack(SqStack *S)
{ //构造一个空栈S
(*S).base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));
if(!(*S).base)
exit(-2); //存储分配失败
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
}
void Push(SqStack *S,char e)
{ //插入元素e为新的栈顶元素
if((*S).top-(*S).base>=(*S).stacksize)
{
(*S).base=(char*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(char));
if(!(*S).base)
exit(-2);
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
}
void Pop(SqStack *S,char *e)
{ //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if((*S).top==(*S).base)
printf("stack is empty!");
*e=*(--(*S).top);
}
int GetTop(SqStack S,char *e)
{ //若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
if(S.top>S.base)
{
*e=*(S.top-1);
return 1;
}
else
return 0;
}
“LL1.c”//LL（1）语法分析器
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"stack.h"
#define MAXLENGTH 50
typedef enum{E,G,T,S,F}nofinal;
typedef enum{i,add,mul,lp,rp,$}final;
char *M[5][6]={"E->TG","error","error","E->TG","error","error",
"error","G->+TG","error","error","G->#","G->#",
"T->FS","error","error","T->FS","error","error",
"error","S->#","S->*FS","error","S->#","S->#",
"F->i","error","error","F->(E)","error","error"};
SqStack Sq;
int isfinalsymbol(chartop)//是否为终结符
{
if ((top=='i')||(top=='+')||(top=='*')||(top=='(')||
(top==')')||(top=='$'))
return 1;
else
return 0;
}
void analyze(char *M[5][6],char *p) //作预测分析
{
char top; //记录栈顶元素
char *temp;
char *a;
nofinal nf;
final fl;
a=p;
GetTop(Sq,&top);//取栈顶元素
while(top!='$')
{
if(top=='#')//为空
{
Pop(&Sq,&top);
}
elseif(isfinalsymbol(top)||(top=='$')) //栈顶是终结符
{
if(top==*a)
{
Pop(&Sq,&top);
a++;
}
else
{
printf("表达式语法不正确!");
getchar();
exit(1);
}
}
else//栈顶不是终结符
{
if(top=='E')
nf=E;
else if(top=='G')
nf=G;
else if(top=='T')
nf=T;
else if(top=='S')
nf=S;
else if(top=='F')
nf=F;
if(*a=='i')
fl=i;
elseif(*a=='+')
fl=add;
else if(*a=='*')
fl=mul;
else if(*a=='(')
fl=lp;
elseif(*a==')')
fl=rp;
else if(*a=='$')
fl=$;
else
{
printf("表达式语法不正确,程序退出.");
getchar();
exit(1);
}
if(strcmp(M[nf][fl],"error")!=0)
{
Pop(&Sq,&top);
temp=strrev(strdup(M[nf][fl])); //反序进栈
while(*temp!='>')
{
Push(&Sq,*temp);
temp++;
}
}
else
{
printf("表达式语法不正确!");
getchar();
exit(1);
}
}
GetTop(Sq,&top);//取栈顶元素
}
}
int main()
{
nofinal n;
final f;
char exp[MAXLENGTH];
InitStack(&Sq);
Push(&Sq,'$');//进栈
Push(&Sq,'E');//进栈
list:
printf("输入一个表达式可以包含(+,*,(,),i)以$结束(不超过%d个字符):n",MAXLENGTH);
gets(exp);
if(strlen(exp)>MAXLENGTH||(strstr(exp,"$")==NULL))
{
printf("字符过长或者没有以$结束,请重新输入n");
goto list;
}
analyze(M,exp);
printf("表达式语法正确!");
getchar();
return 0;
}
五、 测试数据及运行结果：
略
六、 思考题：
语法分析的任务是什么？
答：语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，语法分析程序判断源程序在结构上是否正确。
