实验三词法分析与语法分析程序设计
实验日期: 2011 年11 月11日评分
批阅教师签字
一、实验目的
基本掌握计算机语言的词法分析程序和语法分析程序的设计方法
二、实验内容
实验要求：
1．根据以下的正规式，画出状态图；
标识符：<字母>(<字母>|<数字字符>)*
关键字：if then else while do
十进制整数：0 | （1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*
运算符和分隔符：+ - * / > < = ( ) ；
2．根据状态图，设计词法分析函数int scan( )，从键盘读入数据，分析出一个单词。
3．对于只含有+、*运算的算术表达式的如下文法，编写相应的语法分析程序，要求用LL(1)分析表实现，并以id+id*id为例进行测试：
E —＞TE′
E′—＞+TE′|ε
T —＞FT′
T′—＞*FT′|ε
F —＞（E）| id
实验步骤
1 根据状态图，设计词法分析算法
2 采用C++语言，实现该算法
3 调试程序：输入一组单词，检查输出结果。
4 编制给定文法的非递归的预测分析程序，并加以测试。
三、实验环境
计算机、Windows 操作系统、Visual C++ 程序集成环境。
四、实验原理（或程序框图）及步骤
LL(1)中的第一个L表示从左到右扫描输入，第二个L表示产生最右推导，而‘1’则表示在每一步中只需要向前看一个输入符号来决定语法分析动作。
构造一个预测分析表如下：
输入：文法G
输出：预测分析表M
方法：对于文法G的每个产生式A→α，进行如下处理：
1）：对于FIRST（α）中的每个终结符a，将A→α加入到M[A, α]中。
2）：如果ε在FIRST（α）中，那么对于FOLLOW（A）中的每个终结符b，将A→α加入到M[A, α]中。如果ε在FIRST（α）中，且$在FOLLOW（A）中，也将A→α加入到M[A, $]中。
完成上面操作之后，如果M[A, α]中没有产生式，那么将M[A, α]设置为error。五、程序源代码
词法分析函数：
struct key_kord {
char *word;
int id;
};
key_word keyword[]={
{"if",1},
{"then",2},
{"else",3},
{"while",4},
{"do",5},
{"integer",16}
};
void scan (FILE *ftp)
{
char temp_char;
int i,c;
while(!feof(ftp)){
temp_char=fgetc(ftp);
if(isalpha(temp_char)) {
TOKEN[0]=temp_char;
temp_char=fgetc(ftp);
i=1;
while(isalnum(temp_char)) {
TOKEN[i]=temp_char;
i++;
temp_char=fgetc(ftp);
}
TOKEN[i]='\0';
fseek(ftp,-1,1);
c=lookup(TOKEN);
if(c==0)
out (ID,TOKEN);
else
out (c," ");
}
else if(isdigit(temp_char)){ TOKEN[0]=temp_char;
temp_char=fgetc(ftp);
i=1;
while(isdigit(temp_char)){
TOKEN[i]=temp_char;
i++;
temp_char=fgetc(ftp);
}
TOKEN[i]='\0';
fseek(ftp,-1,1);
out(INT,TOKEN);
}
else
switch(temp_char){
case '<': temp_char=fgetc(ftp);
if(temp_char=='=')
out(LE," ");
else if(temp_char=='>')
out(NE," ");
else{
fseek(ftp,-1,1);
out(LT," ");
}
break;
case '=': out(EQ, " "); break; case '>': temp_char=fgetc(ftp); if(temp_char=='=')
out(GE," ");
else{
fseek(ftp,-1,1);
(GT," ");
}
break;
case ':': temp_char=fgetc(ftp); if(temp_char=='=')
out(FZ," ");
else{
fseek(ftp,-1,1);
report_error(temp_char); }
break;
case '/': temp_char=fgetc(ftp); if(temp_char=='/'){
do{
temp_char=fgetc(ftp);
}while(temp_char!='\n');
graphnum++;
}
else{
fseek(ftp,-1,1);
out(DEV," ");
}
break;
case ' ' : break;
case '\n': graphnum++; break; case ' ': break;
case -1 : break;
default : report_error(temp_char);
break;
}
}
return;
}
LL（1）算法实现：
#define MAXSYMBOL 30
temp_charar NT[]={'E','A','T','B','F'};
temp_charar TE[]={'i','+','*','(','(',')'};
temp_charar *analysisTable[MAXSYMBOL][3]={
{"E","i","TG"},{"E","+",""},{"E","*",""},{"E","(","TG"},{"E",")",""},{"E","#",""}, {"A","i",""},{"A","+","+TA"},{"A","*",""},{"A","(",""},{"A",")","$"},{"A","#","$"}, {"T","i","FB"},{"T","+",""},{"T","*",""},{"T","(","FB"},{"T",")",""},{"T","#",""}, {"B","i",""},{"B","+","$"},{"B","*","*FB"},{"B","(",""},{"B",")","$"},{"B","#","$"}, {"F","i","i"},{"F","+",""},{"F","*",""},{"F","(","(E)"},{"F",")",""},{"F","#",""},
};
int Stack_Count(HEADSTACK *head)
{
int count=0;
if(head->stackHead==NULL)
return 0;
TEMP_CHARARSTACK *currentNode=head->stackHead;
while(currentNode!=NULL)
{
currentNode=currentNode->nextNode;
count++;
}
return count;
}
HEADSTACK *Stack_Init()
{
HEADSTACK *headNode=(HEADSTACK *)malloc(sizeof(HEADSTACK)); headNode->stackHead=NULL;
return headNode;
}
void Stack_Push(HEADSTACK *head,temp_charar temp_char)
{
TEMP_CHARARSTACK *currentNode,*tail;
tail=(TEMP_CHARARSTACK *)malloc(sizeof(TEMP_CHARARSTACK)); tail->temp_char=temp_char;
tail->nextNode=NULL;
if(head->stackHead==NULL)
{
head->stackHead=tail;
return;
}
currentNode=head->stackHead;
while(currentNode->nextNode!=NULL)
{
currentNode=currentNode->nextNode;
}
currentNode->nextNode=tail;
currentNode=tail;
currentNode->nextNode=NULL;
}
TEMP_CHARARSTACK Stack_Pop(HEADSTACK *head)
{
TEMP_CHARARSTACK *currentNode,*tail,popNode;
if(head->stackHead==NULL)
{
printf("Error:The Stack does not has node\n");
return popNode;
}
currentNode=tail=head->stackHead;
if(tail->nextNode==NULL)
{
popNode.temp_char=tail->temp_char;
popNode.nextNode=NULL;
head->stackHead=NULL;
return popNode;
}
while (tail->nextNode!=NULL)
{
tail=tail->nextNode;
if(tail->nextNode==NULL)
{
currentNode->nextNode=NULL;
popNode.temp_char=tail->temp_char;
popNode.nextNode=tail->nextNode;
return popNode;
}
currentNode=currentNode->nextNode;
}
}
bool IsNT(temp_charar temp_char)
{
for(int i=0;i { if(temp_char==NT[i]) return true; } return false; } bool IsTE(temp_charar temp_char) { for(int i=0;i { if(temp_char==TE[i]) return true; } return false; } temp_charar* GetMatrixValue(temp_charar NT,temp_charar TE) { temp_charar nt[2],te[2]; nt[0]=NT; nt[1]='\0'; te[0]=TE; te[1]='\0'; for(int i=0;i { if((strcmp(nt,analysisTable[i][0])==0)&&(strcmp(te,analysisTable[i][1])==0)&&(analysisTable[i ][2]!=""))
相关主题
文本预览