编译原理词法分析及ll(1)文法判定.doc

武汉科技大学实验报告

课程名称 编译原理

专业班级
姓 名
学 号

实验一 词法分析器设计
【实验目的】
1．熟悉词法分析的基本原理，词法分析的过程以及词法分析中要注意的问题。
2．复习高级语言，进一步加强用高级语言来解决实际问题的能力。
3．通过完成词法分析程序，了解词法分析的过程。

【实验内容】
用C语言编写一个PL/0词法分析器，为语法语义分析提供单词，使之能把输入的字符串形式的源程序分割成一个个单词符号传递给语法语义分析，并把分析结果（基本字，运算符，标识符，常数以及界符）输出。

【实验步骤和要求】
1． 要求绘出词法分析过程的流程图。
2． 根据词法分析的目的以及内容，确定完成分析过程所需模块。
3． 写出每个模块的源代码。
4． 整理程序清单及所得结果。
【流程图】

【源代码】
//resource.h
#define IDD_MAINDLG 101
#define IDR_MENU 102
#define IDI_ICON 104
#define IDC_INPUT 1001
#define IDC_OUTPUT 1003
#define IDC_ERRPUT 1004
#define IDC_BUTTON1 1005
#define ID_START 40001
#define ID_ABOUT 40003
#define ID_OPEN 40005
#define ID_SAVE 40006
#define ID_LISTKEY 40007

// Next default values for new objects
//
#ifdef APSTUDIO_INVOKED
#ifndef APSTUDIO_READONLY_SYMBOLS
#define _APS_NEXT_RESOURCE_VALUE 105
#define _APS_NEXT_COMMAND_VALUE 40008
#define _APS_NEXT_CONTROL_VALUE 1007
#define _APS_NEXT_SYMED_VALUE 101
#endif
#endif
//getsym.h
#ifndef _GETSYM_H_
#define _GETSYM_H_

#include <stdlib.h> //For memset()
#include <string.h> //For strcpy()

#define ISLETTER(c) ((c)>='A'&&(c)<='Z'||(c)>='a'&&(c)<='z')
#define ISNUMBER(c) ((c)>='0'&&(c)<='9')
#define ISCHAR(c) ((c)>=33 &&(c)<=126)

#define MAX_SYM 32768 //最大符号量
#define MAX_SYMFORM 1024 //最大符号表长度
#define MAX_NUMFORM 4096 //最大常数表长度

#define MAX_SYMLEN 31 //最大符号长度
#define MAX_NUMLEN 10 //最大常数长度
#define MAX_BUFFER MAX_SYMLEN+1//最大缓冲长度

#define MAX_KEYWORD 27 //关键字数量
#define MAX_OPWORDA 8 //单字运算符数量
#define MAX_OPWORDB 4 //双字运算符数量
#define MAX_ENDWORD 8 //单字界符数量
#define MAX_ERROR 5 //错误类型数量

#define TYPE_KEYWORD 1 //关键字类型号
#define TYPE_SYMBOL 2 //符号类型号
#define TYPE_NUMBER 3 //常量类型号
#define TYPE_OPWORD 4 //运算符类型号
#define TYPE_ENDWORD 5 //界符类型号
#define TYPE_ERROR -1 //错误类型号

#define ERR_OVERSYMLEN 1 //以下是一般错误号
#define ERR_OVERNUMLEN 2
#define ERR_NUMBER 3
#define ERR_WRONGOP 4
#define ERR_OVERSYMFORM 10001 //以下是严重错误号
#define ERR_OVERNUMFORM 10002
#define ERR_OVERSYMNUM 10003
#define ERR_OVERERRNUM 10004

#ifdef __cplusplus
extern "C" {
#endif

struct SYM //符号描述结构体(含错误描述结构)
{
int type; //类型号(0:错误)
int id; //ID号(错误值)
int line; //所在行数
// int no; //SYM编号/列号
char name[MAX_SYMLEN+1]; //所取的词
};

struct FORM //表格结构体
{
int symnum;
int numnum;
struct SYMF //符号表项结构体
{
int id;
char name[MAX_SYMLEN+1];
}symf[MAX_SYMFORM];
struct NUMF //常量表项结构体
{
int id;
char name[MAX_NUMLEN+1];
}numf[MAX_NUMFORM];
};

struct SYMINFO //词法分析信息结构体
{
int num;
struct SYM sym[MAX_SYM];
struct FORM form;
};
//取词函数(返回读字符数量,如果是0则表示结束,lin表示当前行数)
int __stdcall getsym(const char *in,struct SYM *out,int *ln,struct FORM *form);
//取所有词函数(正常返回0,否则返回严重错误号)
int __stdcall getsyminfo(const char *in,struct SYMINFO *out);

#ifdef __cplusplus
}
#endif
#endif

#include "getsym.h"
//关键字[BASIC:13,EXTEND:14]
const char* const keytxt[MAX_KEYWORD]=
{
"procedure","call","begin","end","var","const",
"if","then","while","do","read","write","odd",
"program","type","function","array","integer",
"real","char","boobean","case","of","repeat",
"until","to","down"
};
//单字运算符
const char opatxt[MAX_OPWORDA]=
{
'+','-','*','/','=','#','<','>'
};
//双字运算符
const char* const opbtxt[MAX_OPWORDB]=
{
"<=",">=",":=","<>"
};
//单字界符
const char eoptxt[MAX_ENDWORD]=
{
'(',')',',',';','.','[',']',':'
};
//错误提示信息
const char* const errtxt[MAX_ERROR]=
{
"OK", //Not used.
"Too long symbol",
"Too long number",
"Mixed number and letter",
"Unkown operator",
};

int getsym(const char *in,struct SYM *out,int *ln,struct FORM *form)
{
char b[MAX_BUFFER]; //建符号缓冲区
int i,m=0,n=0,e=0; //序号/非字符数/字符数/出错标记
memset(out,0,sizeof(struct SYM));
while(!ISCHAR(*in)) //滤出前面的非字符
{
if(*in==10) (*ln)++;//换行时,ln++
if(*in++) m++; else return 0; //如果无字符则退出
}
out->line=*ln;
if(ISLETTER(*in)) //字母开头情况
{
while(ISLETTER(*in)||ISNUMBER(*in))
{
if(n<=MAX_SYMLEN) b[n]=*in;
n++; in++;
}
b[MAX_SYMLEN]=0; //符号结尾置0
if(n<MAX_SYMLEN) b[n]=0;
strcpy(out->name,b);
if(n>MAX_SYMLEN) //超出符号最大长度
{
out->type=TYPE_ERROR;
out->id=ERR_OVERSYMLEN;
}
else
{
for(i=0;i<MAX_KEYWORD;i++)
if(strcmp(b,keytxt[i])==0) break;
if(i<MAX_KEYWORD) //属于关键字
{
out->type=TYPE_KEYWORD;
out->id=i;
}
else //不属于关键字
{
for(i=0;i<form->symnum;i++)
if(strcmp(b,form->symf[i].name)==0) break;
if(i==form->symnum) //不在符号表中则添加
{
if(form->symnum>=MAX_SYMFORM)
{ //超出符号表范围产生严重错误
out->type=TYPE_ERROR;
out->id=ERR_OVERSYMFORM;
return m+n;
}
form->symf[i].id=i;
strcpy(form->symf[i].name,b);
form->symnum++;
}
out->type=TYPE_SYMBOL; //符号类型
out->id=i;
}
}
return m+n;
}
if(ISNUMBER(*in)) //数字开头情况
{
e=0;
while(ISNUMBER(*in)||ISLETTER(*in))
{
if(ISLETTER(*in)) e=1; //含字母则置出错标记
if(n<=MAX_NUMLEN) b[n]=*in;
n++; in++;
}
b[MAX_NUMLEN]=0; //数字尾置0
if(n<MAX_NUMLEN) b[n]=0;
strcpy(out->name,b);
if(e||n>MAX_NUMLEN) //有出错标记或超出数字最大长度
{
out->type=TYPE_ERROR;
if(e) //含字母情况
out->id=ERR_NUMBER;
else //超出数字最大长度情况
out->id=ERR_OVERNUMLEN;
}
else //无错情况
{
if(form->numnum>=MAX_NUMFORM)
{ //超出常量表范围产生严重错误
out->type=TYPE_ERROR;
out->id=ERR_OVERNUMFORM;
return m+n;
}
form->numf[form->numnum].id=form->numnum;
strcpy(form->numf[form->numnum].name,b);
out->type=TYPE_NUMBER;
out->id=form->numnum;
form->numnum++;
}
return m+n;
}
for(i=0;i<MAX_OPWORDB;i++) //双字运算符情况
if(*(short*)in==*(short*)(opbtxt[i])) break;
if(i<MAX_OPWORDB)
{
out->type=TYPE_OPWORD;
out->id=MAX_OPWORDA+i;
*(short*)out->name=*(short*)opbtxt[i];
out->name[2]=0;
return m+2;
}
out->name[0]=*in;
out->name[1]=0;
for(i=0;i<MAX_OPWORDA;i++) //单字运算符情况
if(*in==opatxt[i]) break;
if(i<MAX_OPWORDA)
{
out->type=TYPE_OPWORD;
out->id=i;
return m+1;
}
for(i=0;i<MAX_ENDWORD;i++) //单字界符情况
if(*in==eoptxt[i]) break;
if(i<MAX_ENDWORD)
{
out->type=TYPE_ENDWORD;
out->id=i;
return m+1;
}
out->type=TYPE_ERROR;
out->id=ERR_WRONGOP; //其他符号则出错
return m+1;
}

int getsyminfo(const char *in,struct SYMINFO *out)
{
int offset,ln=1; //每次取词偏移量/当前行数
memset(out,0,sizeof(struct SYMINFO));
while(1)
{
offset=getsym(in,&out->sym[out->num],&ln,&out->form);
if(offset==0) break; //完成取词则退出
if(out->num>=MAX_SYM) return ERR_OVERSYMNUM;//超出符号信息最大值
if(out->sym[out->num].type==TYPE_ERROR&&out->sym[out->num].id>=10000)
return out->sym[out->num].id;//有严重错误则退出
out->num++;
in+=offset;
}
return 0;
}
Test.Txt
program test;
procedure func(a:integer,b:char);
begin
var c:char;
read(c);
if c>=1234 then
b:=c*320;
b:=(a-b)/10000;
end;
begin
const s:=4444;
a:=b[333];
while s=a do
begin
call test;
end;
write(a);
end.

结果

实验二 LL（1）语法分析程序设计
【实验目的】
1．熟悉判断LL（1）文法的方法及对某一输入串的分析过程。
2．学会构造表达式文法的预测分析表。
【实验内容】
编写一个语法分析程序，对于给定的输入串，能够判断识别该串是否为给定文法的句型。
【实验步骤和要求】
1． 从键盘读入输入串，并判断正误；
2． 若无误，由程序自动构造FIRST、FOLLOW集以及SELECT集合，判断是否为LL（1）文法；
3． 若符合LL（1）文法，由程序自动构造LL（1）分析表；
4． 由算法判断输入符号串是否为该文法的句型。（可参考教材96页的例题1）
【源代码】
#include "stdio.h"
#include "stdlib.h"
#define MaxRuleNum 8
#define MaxVnNum 5
#define MaxVtNum 5
#define MaxStackDepth 20
#define MaxPLength 20
#define MaxStLength 50
struct pRNode /*产生式右部结构*/
{
 int rCursor; /*右部序号*/
 struct pRNode *next;
};
struct pNode /*产生式结点结构*/
{
 int lCursor; /*左部符号序号*/
 int rLength; /*右部长度*/
 /*注当rLength = 1 时，rCursor = -1为空产生式*/
 struct pRNode *rHead; /*右部结点头指针*/
};
char Vn[MaxVnNum + 1]; /*非终结符集*/
int vnNum;
char Vt[MaxVtNum + 1]; /*终结符集*/
int vtNum;
struct pNode P[MaxRuleNum]; /*产生式*/
int PNum; /*产生式实际个数*/
char buffer[MaxPLength + 1];
char ch; /*符号或string ch;*/
char st[MaxStLength]; /*要分析的符号串*/

struct collectNode /*集合元素结点结构*/
{
 int nVt; /*在终结符集中的下标*/
 struct collectNode *next;
};
struct collectNode* first[MaxVnNum + 1]; /*first集*/
struct collectNode* follow[MaxVnNum + 1]; /*follow集*/

int analyseTable[MaxVnNum + 1][MaxVtNum + 1 + 1];
/*预测分析表存放为产生式的编号，+1用于存放结束符，多+1用于存放#(-1)*/
int analyseStack[MaxStackDepth + 1]; /*分析栈*/
int topAnalyse; /*分析栈顶*/
/*int reverseStack[MaxStackDepth + 1]; /*颠倒顺序栈*/
/*int topReverse; /*倒叙栈顶*/

void Init();/*初始化*/
int IndexCh(char ch);
/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/
void InputVt(); /*输入终结符*/
void InputVn();/*输入非终结符*/
void ShowChArray(char* collect, int num);/*输出Vn或Vt的内容*/
void InputP();/*产生式输入*/
bool CheckP(char * st);/*判断产生式正确性*/
void First(int U);/*计算first集,U->xx...*/
void AddFirst(int U, int nCh); /*加入first集*/
bool HaveEmpty(int nVn); /*判断first集中是否有空(-1)*/
void Follow(int V);/*计算follow集*/
void AddFollow(int V, int nCh, int kind);/*加入follow集，
 kind = 0表加入follow集，kind = 1加入first集*/
void ShowCollect(struct collectNode **collect);/*输出first或follow集*/
void FirstFollow();/*计算first和follow*/
void CreateAT();/*构造预测分析表*/
void ShowAT();/*输出分析表*/
void Identify(char *st);/*主控程序,为操作方便*/
/*分析过程显示操作为本行变换所用，与教程的显示方式不同*/
void InitStack();/*初始化栈及符号串*/
void ShowStack();/*显示符号栈中内容*/
void Pop();/*栈顶出栈*/
void Push(int r);/*使用产生式入栈操作*/

#include "LL1.h"
void main(void)
{
 char todo,ch;
  Init();
 InputVn();
 InputVt();
 InputP();
 getchar();
 FirstFollow();
 printf("所得first集为：");
 ShowCollect(first);
 printf("所得follow集为：");
 ShowCollect(follow);
 CreateAT();
 ShowAT();
 todo = 'y';
 while('y' == todo)
 {
  printf("\n是否继续进行句型分析？(y / n):");
  todo = getchar();
  while('y' != todo && 'n' != todo)
  {
   printf("\n(y / n)? ");
   todo = getchar();
  }
  if('y' == todo)
  {
   int i;
   InitStack();
   printf("请输入符号串(以#结束) : ");
   ch = getchar();
   i = 0;
   while('#' != ch && i < MaxStLength)
   {
    if(' ' != ch && '\n' != ch)
    {
     st[i++] = ch;
    }
    ch = getchar();
   }
   if('#' == ch && i < MaxStLength)
   {
    st[i] = ch;
    Identify(st);
   }
   else
    printf("输入出错！\n");
  }
 }
 getchar();
}
void Init()
{
 int i,j;
 vnNum = 0;
 vtNum = 0;
 PNum = 0;
 for(i = 0; i <= MaxVnNum; i++)
  Vn[i] = '\0';
 for(i = 0; i <= MaxVtNum; i++)
  Vt[i] = '\0';
 for(i = 0; i < MaxRuleNum; i++)
 {
  P[i].lCursor = NULL;
  P[i].rHead = NULL;
  P[i].rLength = 0;
 }
 PNum = 0;
 for(i = 0; i <= MaxPLength; i++)
  buffer[i] = '\0';
 for(i = 0; i < MaxVnNum; i++)
 {
  first[i] = NULL;
  follow[i] = NULL;
 }
 for(i = 0; i <= MaxVnNum; i++)
 {
  for(j = 0; j <= MaxVnNum + 1; j++)
   analyseTable[i][j] = -1;
 }
}
/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/
int IndexCh(char ch) 
{
 int n;
 n = 0; /*is Vn?*/
 while(ch != Vn[n] && '\0' != Vn[n])
  n++;
 if('\0' != Vn[n])
  return 100 + n;
 n = 0; /*is Vt?*/
 while(ch != Vt[n] && '\0' != Vt[n])
  n++;
 if('\0' != Vt[n])
  return n;
 return -1;
}
/*输出Vn或Vt的内容*/
void ShowChArray(char* collect)
{
 int k = 0;
 while('\0' != collect[k])
 {
  printf(" %c ", collect[k++]);
 }
 printf("\n");
}
/*输入非终结符*/
void InputVn()
{
 int inErr = 1;
 int n,k;
 char ch;
 while(inErr)
 {
  printf("\n请输入所有的非终结符，注意：");
  printf("请将开始符放在第一位，并以#号结束:\n"); 
  ch = ' ';
  n = 0;
  /*初始化数组*/
  while(n < MaxVnNum)
  {
   Vn[n++] = '\0';
  }
  n = 0;
  while(('#' != ch) && (n < MaxVnNum))
  {
   if(' ' != ch && '\n' != ch && -1 == IndexCh(ch))
   {
    Vn[n++] = ch;
    vnNum++;
   }
   ch = getchar();
  }
  Vn[n] = '#'; /*以“#”标志结束用于判断长度是否合法*/
  k = n; /*k用于记录n以便改Vn[n]='\0'*/
  if('#' != ch)
  {
   if( '#' != (ch = getchar()))
   {
    while('#' != (ch = getchar()))
     ;
    printf("\n符号数目超过限制！\n");
    inErr = 1;
    continue;
   }
  }
  /*正确性确认，正确则，执行下下面，否则重新输入*/
  Vn[k] = '\0';
  ShowChArray(Vn);
  ch = ' ';
  while('y' != ch && 'n' != ch)
  {
   if('\n' != ch)
   {
    printf("输入正确确认?(y/n):");
   }
   scanf("%c", &ch);
  }
  if('n' == ch)
  {
   printf("录入错误重新输入！\n");
   inErr = 1;
  }
  else
  {
   inErr = 0;
  }
 }
}
/*输入终结符*/
void InputVt()
{
 int inErr = 1;
 int n,k;
 char ch;
 while(inErr)
 {
  printf("\n请输入所有的终结符，注意：");
  printf("以#号结束:\n"); 
  ch = ' ';
  n = 0;
  /*初始化数组*/
  while(n < MaxVtNum)
  {
   Vt[n++] = '\0';
  }
  n = 0;
  while(('#' != ch) && (n < MaxVtNum))
  {
   if(' '!= ch && '\n' != ch && -1 == IndexCh(ch))
   {
    Vt[n++] = ch;
    vtNum++;
   }
   ch = getchar();
  }
  Vt[n] = '#'; /*以“#”标志结束*/
  k = n; /*k用于记录n以便改Vt[n]='\0'*/
  if('#' != ch)
  {
   if( '#' != (ch = getchar()))
   {
    while('#' != (ch = getchar()))    
    printf("\n符号数目超过限制！\n");
    inErr = 1;
    continue;
   }
  }
  /*正确性确认，正确则，执行下下面，否则重新输入*/
  Vt[k] = '\0';
  ShowChArray(Vt);
  ch =' ';
  while('y' != ch && 'n' != ch)
  {
   if('\n' != ch)
   {
    printf("输入正确确认?(y/n):");
   }
   scanf("%c", &ch);
  }
  if('n' == ch)
  {
   printf("录入错误重新输入！\n");
   inErr = 1;
  }
  else
  {
   inErr = 0;
  }
 }
}
/*产生式输入*/
void InputP()
{
 char ch;
 int i = 0, n,num;
 printf("请输入文法产生式的个数：");
 scanf("%d", &num);
 PNum = num;
 getchar(); /*消除回车符*/
 printf("\n请输入文法的%d个产生式,并以回车分隔每个产生式：", num);
 printf("\n");
 while(i < num)
 {
  printf("第%d个：", i);
  /*初始化*/
  for(n =0; n < MaxPLength; n++)
   buffer[n] = '\0';
  /*输入产生式串*/
  ch = ' ';
  n = 0;
  while('\n' != (ch = getchar()) && n < MaxPLength)
  {
   if(' ' != ch)
    buffer[n++] = ch;    
  }
  buffer[n] = '\0';
/*  printf("%s", buffer);*/
  if(CheckP(buffer))
  {
   /*填写入产生式结构体*/
   pRNode *pt, *qt;
   P[i].lCursor = IndexCh(buffer[0]);
   pt = (pRNode*)malloc(sizeof(pRNode));
   pt->rCursor = IndexCh(buffer[3]);
   pt->next = NULL;
   P[i].rHead = pt;
   n = 4;
   while('\0' != buffer[n])
   {
    qt = (pRNode*)malloc(sizeof(pRNode));
    qt->rCursor = IndexCh(buffer[n]);
    qt->next = NULL;
    pt->next = qt;
    pt = qt;
    n++;
   }
   P[i].rLength = n - 3;
   i++;
   /*调试时使用*/
  }
  else
   printf("输入符号含非法在成分，请重新输入！\n");
 }
}
/*判断产生式正确性*/
bool CheckP(char * st)
{
 int n;
 if(100 > IndexCh(st[0]))
  return false;
 if('-' != st[1])
  return false;
 if('>' != st[2])
  return false;
 for(n = 3; '\0' != st[n]; n ++)
 {
  if(-1 == IndexCh(st[n]))
   return false;
 }
 return true;
}
/*====================first & follow======================*/
/*计算first集,U->xx...*/
void First(int U)
{
 int i,j;
 for(i = 0; i < PNum; i++)
 {
  if(P[i].lCursor == U)
  {
   struct pRNode* pt;
   pt = P[i].rHe