一.需求分析
1．问题的提出：
语法分析是编译过程的核心部分。他的任务是在词法分析识别单词符号串的基础上，分析并判断程序的的语法结构是否符合语法规则。语言的语法结构是用上下文无关文法描述的。因此语法分析器的工作的本质上就是按文法的产生式，识别输入符号串是否为一个句子。对于一个文法，当给你一串符号是，如何知道它是不是该文法的一个句子，这是这个课程设计所要解决的一个问题。
2．问题解决：
其实要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符号出发推导出这个输入串。语法分析可以分为两类，一类是自上而下的分析法，一类是自下而上的分析法。自上而下的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者说，为输入串寻找一个最左推倒，这种分析过程的本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程我主要是自上而下的过程。
3．解决步骤：
在自上而下的分析法中，主要是研究LL(1)分析法。它的解决步骤是首先接收到用户输入的一个文法，对文法进行检测和处理，消除左递归，得到LL(1)文法，这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST 和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈。
二.概要设计
1．设计原理：
所谓LL（1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。实现LL（1）分析的程序又称为LL（1）分析程序或LL1（1）分析器。
我们知道一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，该程序是采用了C++语言来编写，其逻辑结构图如下：
LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。对于任何（X，a），总控程序每次都执行下述三种可能的动作之一：
（１）若X = a =?#‘，则宣布分析成功，停止分析过程。
（２）若X = a ?#‘，则把X从STACK栈顶弹出，让a指向下一个输入符号。
（３）若X是一个非终结符，则查看预测分析表M。若M[A，a]中存放着关于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号为ε，则不推什么东西进STACK栈）。若M[A，a]中存放着―出错标志‖，则调用出错诊断程序ERROR。
事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，因此在LL （1）分析器中，实际上是以LL（1）分析表代替相应方法来进行分析的。
2．构造LL(1)分析表
考查文法G[E]：
E→E+T | T
T→T*F | F
F→( E ) | i | x | y
我们容易看出此文法没有左公因子也没有二义性，但却存在两个直接左递归，这里我们利用引入新非终结符的方法来消除它使方法满足要求，即：
对形如：U→Ux|y的产生式（其中x,y V+ ，y不以U开头），引入一个新的非终结符U‘后，可以等价地改写成为：
U→yU‘
U‘→x U‘|ε
显然改写后，U和U‘都不是左递归的非终结符。因此文法G［E］按上述方法消去左递归后可等价地写成：
E→TP
P→+TP | ε
T→FQ
Q→*FQ | ε
F→( E ) | i | x | y
在构造LL(1)预测分析表之前，首先要构造该文法的每个非终结符的FIRST和FOLLOW集合，按照下面描述的算法来构造这两个集合。
①FIRST集合的构造算法：
（1）若X∈VT，则FIRST（X）={X}。
（2）若X∈VN，且有产生式X→a……，则把a加入到FIRST(X)中；若X→ε也是一条产生式，则把ε也加到FIRST(X)中。
（3）若X→Y……是一个产生式且Y∈VN，则把FIRST(Y)中的所有非ε-元素都加到FIRST(X)中；若X→Y1Y2…Yk是一个产生式，Y1，…，Yi-1都是非终结符，而且，对于任何j，1≤j≤i-1，FIRST(Yj)都含有ε（即Y1…Yi-1* ε），则把FIRST(Yj)中的所有非ε-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有ε，j=1,2,…，k，则把ε加到FIRST(X)中。
连续使用上面的规则，直至每个集合FIRST不再增大为止。
②FOLLOW集合的构造算法：
（1）对于文法的开始符号S，置#于FOLLOW(S)中；
（2）若A→αBβ是一个产生式，则把FIRST(β)| {ε}加至FOLLOW(B)中；
（3）若A→αB是一个产生式，或A→αBβ是一个产生式而β ε（即ε∈FIRST(β)），则把FOLLOW(A)加至FOLLOW(B)中。
连续使用上面的规则，直至每个集合FOLLOW不再增大为止。
根据以上描述的算法，可以构造文法G［E］的FIRST和FOLLOW集合如下：
FIRST(E) = {( , i，x，y } FOLLOW(E) = { ) , # }
FIRST(P) = { + ,ε}FOLLOW(P) = { ) , # }
FIRST(T) = { ( , i，x，y } FOLLOW(T) = { + , ) , # }
FIRST(Q) = { * , ε}FOLLOW(Q) = { + , ) , # }
FIRST(F) = { ( , i，x，y } FOLLOW(F) = { * , + , ) , # }
现在来构造G［E］的LL（1）预测分析表。预测分析表M[A, a]是如下形式的一个矩阵。A为非终结符，a是终结符或?#‘。矩阵元素M[A, a]中存放这一条关于A的产生式，指出当A面临输入符号a 是所应采用的规则。M[A, a]也可能存放一条―出错标志‖，指出当A根本不该面临输入符号a。文法G［E］的LL(1) 预测分析表如下：
其中，E、P 、T、Q、F为方法G［E］的非终结符，i、+、x、y、*、(、)，为方法G［E］的终结符，值得注意的是，―＃‖不管有没有ε产生式，我们在构造分析表时都不能省去。
3.利用分析表进行预测分析的步骤
对于这个文法，假设输入串为i*i+i，利用分析表进行预测分析的步骤为：
三. 详细设计
1．程序流程图：
在对程序各个模块分析之前。先给出整个程序的流程图。以便于在分析过程中更好的对各个模块之间的联系进行了解。
程序的流程图如下：
2．消除左递归
1)消除左递归时主要经历以下步骤：
a)对文法按推导字母顺序的顺序排列，且将开始符置于数组最前部，这里采用冒泡算法。
b)查看文法是否含有左递归，如果没有，则终止。
c)准备两个字符串数组:tweenStrArr和tmpGrammerArr，tweenStrArr用以
存放每一个非终止符作为左侧推导项时临时分析结果，tmpGrammerArr则用以存放去除左递归后的文法。
接下来即可进行消除左递归的过程，核心算法框架如下：
FOR i: = 1 To n Do
BEGIN
FOR j:=1 To i–1 Do
把形如Pi?Pj γ的规则改写成：
Pid?1 γ |d2 γ |…|dk γ ，其中
Pjd?1|d2|…|dk是关于Pi的所有规则；消除关于Pi规则的直接左递归性END
2)消除左递归关键代码
void recur(char *point)
{ /*完整的产生式在point[]中*/
int j,m=0,n=3,k;
char temp[20],ch;
ch=c(); /*得到一个非终结符*/
k=strlen(non_ter);
non_ter[k]=ch;
non_ter[k+1]='\0';
for(j=0;j<=strlen(point)-1;j++)
{
if(point[n]==point[0])
{ /*如果?|‘后的首符号和左部相同*/
for(j=n+1;j<=strlen(point)-1;j++)
{
while(point[j]!='|'&&point[j]!='\0')
temp[m++]=point[j++];
left[count]=ch;
memcpy(right[count],temp,m);
right[count][m]=ch;
right[count][m+1]='\0';
m=0;
count++;
if(point[j]=='|')
{
n=j+1;
break;
}
}
}
else
{ /*如果?|‘后的首符号和左部不同*/ left[count]=ch;
right[count][0]='^';
right[count][1]='\0';
count++;
for(j=n;j<=strlen(point)-1;j++)
{
if(point[j]!='|')
temp[m++]=point[j];
else
{
left[count]=point[0];
memcpy(right[count],temp,m);
right[count][m]=ch;
right[count][m+1]='\0';
printf(" count=%d ",count);
m=0;
count++;
}
}
left[count]=point[0];
memcpy(right[count],temp,m);
right[count][m]=ch;
right[count][m+1]='\0';
count++;
m=0;
}
}
}
3．得到预测分析表
消除左递归之后，我们需要判断高文法是否为LL(1)文法，如果不是则结束程序，否则创建FIRST 和FOLLOW集合，然后根据FIRST和FOLLOW集合的到预测分析表
本模块的流程图如下：
1）创建FIRST和FOLLOW集合程序代码如下：
void First(int U)
{
int i,j;
for(i = 0; i < PNum; i++)
{
if(P[i].lCursor == U)
{
struct pRNode* pt;
pt = P[i].rHead;
j = 0;
while(j < P[i].rLength)
{
if(100 > pt->rCursor)
{
/*注:此处因编程出错,使空产生式时
rlength同样是1,故此处同样可处理空产生式*/
AddFirst(U, pt->rCursor);
break;
}
else
{
if(NULL == first[pt->rCursor - 100])
{
First(pt->rCursor);
}
AddFirst(U, pt->rCursor);
if(!HaveEmpty(pt->rCursor))
{
break;
}
else
{
pt = pt->next;
}
}
j++;
}
if(j >= P[i].rLength) /*当产生式右部都能推出空时*/
AddFirst(U, -1);
}
}
}
/*加入first集*/
void AddFirst(int U, int nCh) /*当数值小于100时nCh为Vt*/ /*当处理非终结符时,AddFirst不添加空项(-1)*/
{
struct collectNode *pt, *qt;
int ch; /*用于处理Vn*/
pt = NULL;
qt = NULL;
if(nCh < 100)
{
pt = first[U - 100];
while(NULL != pt)
{
if(pt->nVt == nCh)
break;
else
{
qt = pt;
pt = pt->next;
}
}
if(NULL == pt)
{
pt = (struct collectNode *)malloc(sizeof(struct collectNode));
pt->nVt = nCh;
pt->next = NULL;
if(NULL == first[U - 100])
{
first[U - 100] = pt;
}
else
{
qt->next = pt; /*qt指向first集的最后一个元素*/
}
pt = pt->next;
}
else
{
pt = first[nCh - 100];
while(NULL != pt)
{
ch = pt->nVt;
if(-1 != ch)
{
AddFirst(U, ch);
}
pt = pt->next;
}
}
}
/*判断first集中是否有空(-1)*/
bool HaveEmpty(int nVn)
{
if(nVn < 100) /*为终结符时(含-1)，在follow集中用到*/ return false;
struct collectNode *pt;
pt = first[nVn - 100];
while(NULL != pt)
{
if(-1 == pt->nVt)
return true;
pt = pt->next;
}
return false;
/*计算follow集,例：U->xVy,U->xV.(注：初始符必含#——"-1")*/
void Follow(int V)
{
int i;
struct pRNode *pt ;
if(100 == V) /*当为初始符时*/
AddFollow(V, -1, 0 );
for(i = 0; i < PNum; i++)
{
pt = P[i].rHead;
while(NULL != pt && pt->rCursor != V) /*注此不能处理：U->xVyVz的情况*/ pt = pt->next;
if(NULL != pt)
{
pt = pt->next; /*V右侧的符号*/
if(NULL == pt) /*当V后为空时V->xV，将左符的follow集并入V的follow集中*/ {
if(NULL == follow[P[i].lCursor - 100] && P[i].lCursor != V)
{
Follow(P[i].lCursor);
}
AddFollow(V, P[i].lCursor, 0);
}
else /*不为空时V->xVy,(注意：y->)，调用AddFollow加入Vt或y的first集*/ {
while(NULL != pt && HaveEmpty(pt->rCursor))
{
AddFollow(V, pt->rCursor, 1); /*y的前缀中有空时，加如first集*/
pt = pt->next;
if(NULL == pt) /*当后面的字符可以推出空时*/
{
if(NULL == follow[P[i].lCursor - 100] && P[i].lCursor != V) {
Follow(P[i].lCursor);
}
AddFollow(V, P[i].lCursor, 0);
}
else /*发现不为空的字符时*/
{
AddFollow(V, pt->rCursor, 1);
}
}
}
}
}
/*当数值小于100时nCh为Vt*/
/*#用-1表示,kind用于区分是并入符号的first集，还是follow集kind = 0表加入follow集，kind = 1加入first集*/
void AddFollow(int V, int nCh, int kind)
{
struct collectNode *pt, *qt;
int ch; /*用于处理Vn*/
pt = NULL;
qt = NULL;
if(nCh < 100) /*为终结符时*/
{
pt = follow[V - 100];
while(NULL != pt)
{
if(pt->nVt == nCh)
break;
else
{
qt = pt;
pt = pt->next;
}
}
if(NULL == pt)
{
pt = (struct collectNode *)malloc(sizeof(struct collectNode));
pt->nVt = nCh;
pt->next = NULL;
if(NULL == follow[V - 100])
{
follow[V - 100] = pt;
}
else
{
qt->next = pt; /*qt指向follow集的最后一个元素*/
}
pt = pt->next;
}
}
else /*为非终结符时，要区分是加first还是follow*/
{
if(0 == kind)
{
pt = follow[nCh - 100];
while(NULL != pt)
{
ch = pt->nVt;
AddFollow(V, ch, 0);
pt = pt->next;
}
}
else
{
pt = first[nCh - 100];
while(NULL != pt)
{
ch = pt->nVt;
if(-1 != ch)
{
AddFollow(V, ch, 1);
}
pt = pt->next;
}
}
}
}
2）构造预测分析表的程序代码如下：void CreateAT()
{
int i;
struct pRNode *pt;
struct collectNode *ct;
for(i = 0; i < PNum; i++)
pt = P[i].rHead;
while(NULL != pt && HaveEmpty(pt->rCursor)) {
/*处理非终结符，当为终结符时，定含空为假跳出*/ ct = first[pt->rCursor - 100];
while(NULL != ct)
{
if(-1 != ct->nVt)
analyseTable[P[i].lCursor - 100][ct->nVt] = i;
ct = ct->next;
}
pt = pt->next;
}
if(NULL == pt)
{
/*NULL == pt，说明xyz->,用到follow中的符号*/ ct = follow[P[i].lCursor - 100];
while(NULL != ct)
{
if(-1 != ct->nVt)
analyseTable[P[i].lCursor - 100][ct->nVt] = i;
else /*当含有#号时*/
analyseTable[P[i].lCursor - 100][vtNum] = i;
ct = ct->next;
}
}
else
{
if(100 <= pt->rCursor) /*不含空的非终结符*/
ct = first[pt->rCursor - 100];
while(NULL != ct)
{
analyseTable[P[i].lCursor - 100][ct->nVt] = i;
ct = ct->next;
}
}
else /*终结符或者空*/
{
if(-1 == pt->rCursor) /*-1为空产生式时*/
{
ct = follow[P[i].lCursor - 100];
while(NULL != ct)
{
if(-1 != ct->nVt)
analyseTable[P[i].lCursor - 100][ct->nVt] = i;
else /*当含有#号时*/
analyseTable[P[i].lCursor - 100][vtNum] = i;
ct = ct->next;
}
}
else /*为终结符*/
{
analyseTable[P[i].lCursor - 100][pt->rCursor] = i;
}
}
}
}
}
4．利用分析表进行预测分析
1）总程序的算法描述如下：
BEGIN
首先把?#‘然后把文法开始符号推进STACK栈；
把第一个输入符号读进a;
FLAG:=TRUE;
WHILE FLAG DO
BEGIN
把栈顶符号出栈到X中；
IF X?VT THEN
IF X =a THEN 把下一输入符号读进a
ELSE ERROR
ELSE IF X= ?#‘THEN
IF X=a THEN FLAG:=FALSE
ELSE ERROR
ELSE IF M[A, a]={X?x1x2…xk} THEN
把xk, xk–1,…, x1依次进栈
/*若x1, x2 …xk=e，则不进栈*/
ELSE ERROR
END OF WHILE;
STOP /*分析成功，过程结束*/
END
2）代码实现如下：
void Identify(char *st)
{
int current,step,r; /*r表使用的产生式的序号*/
printf("\n%s的分析过程：\n", st);
printf("步骤\t分析符号栈\t当前指示字符\t使用产生式序号\n"); step = 0;
current = 0; /*符号串指示器*/
printf("%d\t",step);
ShowStack();
printf("\t\t%c\t\t- -\n", st[current]);
while('#' != st[current])
{
if(100 > analyseStack[topAnalyse]) /*当为终结符时*/
{
if(analyseStack[topAnalyse] == IndexCh(st[current]))
{
/*匹配出栈，指示器后移*/
Pop();
current++;
step++;
printf("%d\t", step);
ShowStack();
printf("\t\t%c\t\t出栈、后移\n", st[current]);
}
else
{
printf("%c-%c不匹配！", analyseStack[topAnalyse], st[current]);
printf("此串不是此文法的句子！\n");
return;
}
}
else /*当为非终结符时*/
{
r = analyseTable[analyseStack[topAnalyse] - 100][IndexCh(st[current])];
if(-1 != r)
Push(r); /*产生式右部代替左部，指示器不移动*/
step++;
printf("%d\t", step);
ShowStack();
printf("\t\t%c\t\t%d\n", st[current], r);
}
else
{
printf("无可用产生式，此串不是此文法的句子！\n");
return;
}
}
}
if('#' == st[current])
{
if(0 == topAnalyse && '#' == st[current])
{
step++;
printf("%d\t", step);
ShowStack();
printf("\t\t%c\t\t分析成功！\n", st[current]);
printf("%s是给定文法的句子！\n", st);
}
else
{
while(topAnalyse > 0)
{
if(100 > analyseStack[topAnalyse]) /*当为终结符时*/
printf("无可用产生式，此串不是此文法的句子！\n");
return;
}
else
{
r = analyseTable[analyseStack[topAnalyse] - 100][vtNum];
if(-1 != r)
{
Push(r); /*产生式右部代替左部，指示器不移动*/
step++;
printf("%d\t", step);
ShowStack();
if(0 == topAnalyse && '#' == st[current])
{
printf("\t\t%c\t\t分析成功！\n", st[current]);
printf("%s是给定文法的句子！\n", st);
}
else
printf("\t\t%c\t\t%d\n", st[current], r);
}
else
{
printf("无可用产生式，此串不是此文法的句子！\n");
return;
}
}
}
}
}
《LL（1）分析器的构造》实验报告 一、实验名称 LL(1)分析器的构造 二、实验目的 设计、编制、调试一个LL(1)语法分析器，利用语法分析器对符号串的识别，加深对语法分析原理的理解。 三、实验内容和要求 设计并实现一个LL(1)语法分析器，实现对算术文法: G[E]:E->E+T|T T->T*F|F F->(E)|i 所定义的符号串进行识别，例如符号串i+i*i为文法所定义的句子，符号串ii+++*i+不是文法所定义的句子。 实验要求: 1、检测左递归，如果有则进行消除； 2、求解FIRST集和FOLLOW集； 3、构建LL(1)分析表； 4、构建LL分析程序，对于用户输入的句子，能够利用所构造的分析程序进行分析，并显示出分析过程。 四、主要仪器设备 硬件：微型计算机。 软件： Code blocks（也可以是其它集成开发环境）。 五、实验过程描述 1、程序主要框架 程序中编写了以下函数，各个函数实现的作用如下： void input_grammer(string *G);//输入文法G
//将文法G预处理得到产生式集合P，非终结符、终结符集合U、u， int eliminate_1(string *G,string *P,string U,string *GG);//消除文法G中所有直接左递归得到文法GG int* ifempty(string* P,string U,int k,int n);//判断各非终结符是否能推导为空 string* FIRST_X(string* P,string U,string u,int* empty,int k,int n)；求所有非终结符的FIRST集 string FIRST(string U,string u,string* first,string s)；//求符号串s=X1X2...Xn的FIRST集 string** create_table(string *P,string U,string u,int n,int t,int k,string* first)；//构造分析表 void analyse(string **table,string U,string u,int t,string s)；//分析符号串s 2、编写的源程序 #include 编译技术 班级网络0802 学号3080610052姓名叶晨舟 指导老师朱玉全2011年 7 月 4 日 一、目的 编译技术是理论与实践并重的课程，而其实验课要综合运用一、二年级所学的多门课程的内容，用来完成一个小型编译程序。从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解；培养学生对完整系统的独立分析和设计的能力，进一步培养学生的独立编程能力。 二、任务及要求 基本要求： 1．词法分析器产生下述小语言的单词序列 这个小语言的所有的单词符号，以及它们的种别编码和内部值如下表： 单词符号种别编码助记符内码值 DIM IF DO STOP END 标识符 常数（整）= + * ** ， （ ）1 2 3 4 5 6 7 8 9 10 11 12 13 14 $DIM $IF $DO $STOP $END $ID $INT $ASSIGN $PLUS $STAR $POWER $COMMA $LPAR $RPAR - - - - - - 内部字符串 标准二进形式 - - - - - - 对于这个小语言，有几点重要的限制： 首先，所有的关键字（如IF﹑WHILE等）都是“保留字”。所谓的保留字的意思是，用户不得使用它们作为自己定义的标示符。例如，下面的写法是绝对禁止的： IF（5）=x 其次，由于把关键字作为保留字，故可以把关键字作为一类特殊标示符来处理。也就是说，对于关键字不专设对应的转换图。但把它们（及其种别编码）预先安排在一张表格中（此表叫作保留字表）。当转换图识别出一个标识符时，就去查对这张表，确定它是否为一个关键字。 再次，如果关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔（此时，空白符不再是完全没有意义的了）。例如，一个条件语句应写为 . 编译原理实验专业：13级网络工程 语法分析器1 一、实现方法描述 所给文法为G【E】； E->TE’ E’->+TE’|空 T->FT’ T’->*FT’|空 F->i|(E) 递归子程序法： 首先计算出五个非终结符的first集合follow集，然后根据五个产生式定义了五个函数。定义字符数组vocabulary来存储输入的句子，字符指针ch指向vocabulary。从非终结符E函数出发，如果首字符属于E的first集，则依次进入T函数和E’函数，开始递归调用。在每个函数中，都要判断指针所指字符是否属于该非终结符的first集，属于则根据产生式进入下一个函数进行调用，若first集中有空字符，还要判断是否属于该非终结符的follow集。以分号作为结束符。 二、实现代码 头文件shiyan3.h #include #include int a=0; cout<<"按1结束程序"< #include 编译原理实验报告 实验名称：分析调试语义分析程序 TEST抽象机模拟器完整程序 保证能用！！！！！ 一、实验目的 通过分析调试TEST语言的语义分析和中间代码生成程序，加深对语法制导翻译思想的理解，掌握将语法分析所识别的语法范畴变换为中间代码的语义翻译方法。 二、实验设计 程序流程图 extern int TESTScan(FILE *fin,FILE *fout); FILE *fin,*fout; //用于指定输入输出文件的指针 int main() { char szFinName[300]; char szFoutName[300]; printf("请输入源程序文件名（包括路径）:"); scanf("%s",szFinName); printf("请输入词法分析输出文件名（包括路径）："); scanf("%s",szFoutName); if( (fin = fopen(szFinName,"r")) == NULL) { printf("\n打开词法分析输入文件出错！\n"); return 0; } if( (fout = fopen(szFoutName,"w")) == NULL) { printf("\n创建词法分析输出文件出错！\n"); return 0; } int es = TESTScan(fin,fout); fclose(fin); fclose(fout); if(es > 0) printf("词法分析有错，编译停止！共有%d个错误！\n",es); else if(es == 0) { printf("词法分析成功！\n"); int es = 0; 词法分析器实验报告 词法分析器设计 一、实验目的： 对C语言的一个子集设计并实现一个简单的词法分析器，掌握利用状 态转换图设计词法分析器的基本方法。利用该词法分析器完成对源程 序字符串的词法分析。输出形式是源程序的单词符号二元式的代码， 并保存到文件中。 二、实验内容： 1. 设计原理 词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。 理论基础：有限自动机、正规文法、正规式 词法分析器(Lexical Analyzer) 又称扫描器(Scanner)：执行词法分析的程序 2. 词法分析器的功能和输出形式 功能:输入源程序、输出单词符号 程序语言的单词符号一般分为以下五种：关键字、标识符、常数、运算符,界符 3. 输出的单词符号的表示形式: 单词种别用整数编码，关键字一字一种，标识符统归为一种，常数一种，各种符号各一种。 4. 词法分析器的结构 单词符号 5. 状态转换图实现 三、程序设计 1．总体模块设计 /*用来存储目标文件名*/ string file_name; /*提取文本文件中的信息。*/ string GetText(); /*获得一个单词符号,从位置i开始查找。并且有一个引用参数j，用来返回这个单词最后一个字符在str的位置。*/ string GetWord(string str,int i,int& j); /*这个函数用来除去字符串中连续的空格和换行 int DeleteNull(string str,int i); /*判断i当前所指的字符是否为一个分界符，是的话返回真，反之假*/ bool IsBoundary(string str,int i); /*判断i当前所指的字符是否为一个运算符，是的话返回真，反之假*/ bool IsOperation(string str,int i); C语言编译器的设计与实现 01计算机4班18号任春妍2号陈俊我们设计的编译程序涉及到编译五个阶段中的三个，即词法分析器、语法分析器和中间代码生成器。编译程序的输出结果包括词法分析后的二元式序列、变量名表、状态栈分析过程显示及四元式序列程序，整个编译程序分为三部分： (1) 词法分析部分 (2) 语法分析处理及四元式生成部分 (3) 输出显示部分 一．词法分析器设计 由于我们规定的程序语句中涉及单词较少，故在词法分析阶段忽略了单词输入错误的检查，而将编译程序的重点放在中间代码生成阶段。词法分析器的功能是输入源程序，输出单词符号。我们规定输出的单词符号格式为如下的二元式：(单词种别，单词自身的值) #define ACC -2 #define syl_if 0 #define syl_else 1 #define syl_while 2 #define syl_begin 3 #define syl_end 4 #define a 5 #define semicolon 6 #define e 7 #define jinghao 8 #define s 9 #define L 10 #define tempsy 11 #define EA 12 #define EO 13 #define plus 14 #define times 15 #define becomes 16 #define op_and 17 #define op_or 18 #define op_not 19 #define rop 20 #define lparent 21 #define rparent 22 #define ident 23 #define intconst 24 学号20102７９8 专业软件工程姓名薛建东 实验日期２013.04.０8 教师签字成绩实验报告 【实验名称】ＬL（1）语法分析 【实验目的】 通过完成预测分析法的语法分析程序,了解预测分析法和递归子程序法的区别和联系。使了解语法分析的功能，掌握语法分析程序设计的原理和构造方法,训练掌握开发应用程序的基本方法。 【实验内容】 ◆根据某一文法编制调试LL ( 1)分析程序，以便对任意输入的符号串进行分析。 ◆构造预测分析表,并利用分析表和一个栈来实现对上述程序设计语言的分析程序。 ◆分析法的功能是利用LＬ（１)控制程序根据显示栈栈顶内容、向前看符号以及LL(1) 分析表,对输入符号串自上而下的分析过程。 【设计思想】 （1）、LL(１)文法的定义 ＬL(1)分析法属于确定的自顶向下分析方法。LＬ（１)的含义是：第一个Ｌ表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式（规则)进行推导。 LL(1)文法的判别需要依次计算FIRＳT集、FOLＬＯW集和SELLＥＣT集,然后判断是否为LL（1)文法，最后再进行句子分析。 需要预测分析器对所给句型进行识别。即在LＬ(１)分析法中,每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符;当出现终结符时，判断其与剩余输入串的第一个字符是否匹配,如果匹配，则继续分析,否则报错。ＬＬ（1）分析方法要求文法满足如下条件：对于任一非终极符A的两个不同产生式Ａ→α，A→β,都要满足下面条件:ＳELEＣＴ(Ａ→α)∩SELＥCT（Ａ→β)＝? (2）、预测分析表构造 LL（1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推 词法分析 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 3.1 主程序示意图： 扫描子程序主要部分流程图 其他 词法分析程序的C语言程序源代码： // 词法分析函数: void scan() // 数据传递: 形参fp接收指向文本文件头的文件指针； // 全局变量buffer与line对应保存源文件字符及其行号，char_num保存字符总数。 void scan() { char ch; int flag,j=0,i=-1; while(!feof(fp1)) { ch=fgetc(fp1); flag=judge(ch); printf("%c",ch);//显示打开的文件 if(flag==1||flag==2||flag==3) {i++;buffer[i]=ch;line[i]=row;} else if(flag==4) {i++;buffer[i]='?';line[i]=row;} else if(flag==5) {i++;buffer[i]='~';row++;} else if(flag==7) continue; else cout<<"\n请注意，第"< 词法分析器实验报告 一、实验目的及要求 本次实验通过用C语言设计、编制、调试一个词法分析子程序，识别单词，实现一个C语言词法分析器，经过此过程可以加深对编译器解析单词流的过程的了解。 运行环境： 硬件：windows xp 软件：visual c++6.0 二、实验步骤 1.查询资料，了解词法分析器的工作过程与原理。 2.分析题目，整理出基本设计思路。 3.实践编码，将设计思想转换用c语言编码实现，编译运行。 4.测试功能，多次设置包含不同字符，关键字的待解析文件，仔细察看运行结果，检测该分析器的分析结果是否正确。通过最终的测试发现问题，逐渐完善代码中设置的分析对象与关键字表，拓宽分析范围提高分析能力。 三、实验内容 本实验中将c语言单词符号分成了四类：关键字key（特别的将main说明为主函数）、普通标示符、常数和界符。将关键字初始化在一个字符型指针数组*key[]中，将界符分别由程序中的case列出。在词法分析过程中，关键字表和case列出的界符的内容是固定不变的（由程序中的初始化确定），因此，从源文件字符串中识别出现的关键字，界符只能从其中选取。标识符、常数是在分析过程中不断形成的。 对于一个具体源程序而言，在扫描字符串时识别出一个单词，若这个单词的类型是关键字、普通标示符、常数或界符中之一，那么就将此单词以文字说明的形式输出．每次调用词法分析程序，它均能自动继续扫描下去，形成下一个单词，直到整个源程序全部扫描完毕，从而形成相应的单词串。 输出形式例如：void $关键字 流程图、程序流程图： 程序： #include 词法分析 #include ch=s[--p]; syn=10; for(n=0;n<6;n++) if(strcmp(token,r[n])==0) { syn=n+1; break; } } void digit(bool positive)//数字的判断{ len=sum=0; ch=s[p]; while(ch>='0' && ch<='9') { sum=sum*10+ch-'0'; ch=s[++p]; } if(ch=='.') { dsum=sum; ch=s[++p]; pos=0.1; while(ch>='0' && ch<='9') { dsum=dsum+(ch-'0')*pos; pos=pos*0.1; ch=s[++p]; } if(ch=='e') { index[len++]=ch; ch=s[++p]; if(ch=='-' || ch=='+') { index[len++]=ch; ch=s[++p]; } if(!(ch>='0' && ch<='9')) { syn=-1; } else 实习二语法分析－自上而下分析 一、实验目的 使用预测分析方法对输入的表达式进行分析，掌握其具体的使用并且学会去分析一个文法。 二、实验内容 1．设计表达式的语法分析器算法（使用预测分析） 2．编写一段代码并上机调试查看其运行结果 三、实验要求 使用LL（1）分析算法设计表达式的语法分析器 LL（1）文法是一个自上而下的语法分析方法，它是从文法的开始符号出发，生成句子的最左推导，从左到右扫描源程序，每次向前查看一个字符，确定当前应该选择的产生式。 实现LL（1）分析的另一种有效方法是使用一张分析表和一个栈进行联合控制。 预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前a的输入符号行事的。对于任何（X，a），总控程序每次都执行三种可能的动作之一。 1.若X＝a＝“#”，则宣布分析成功，停止分析过程 2.若X＝a≠“#”，则把X从STACK栈顶逐出，让a指向下一 个输入符号。 3.若X是一个非终结符，则查看分析表。 四、运行结果 （本程序只能对由'i','+','*','(',')'构成的以'#'结束的字符串进行分析） 五、源程序实现 /*LL(1)分析法源程序，只能在VC++中运行*/ #include 编译原理语法分析器实验报告 班级： 学号： 姓名： 实验名称语法分析器 一、实验目的 1、根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。 2、本次实验的目的主要是加深对自上而下分析法的理解。 二、实验内容 [问题描述] 递归下降分析法： 0.定义部分：定义常量、变量、数据结构。 1.初始化：从文件将输入符号串输入到字符缓冲区中。 2.利用递归下降分析法分析，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。 LL（1）分析法： 模块结构： 1、定义部分：定义常量、变量、数据结构。 2、初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体等）； 3、运行程序：让程序分析一个text文件，判断输入的字符串是否符合文法定义的规则； 4、利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式 符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示简 单的错误提示。 [基本要求] 1. 对数据输入读取 2. 格式化输出分析结果 2．简单的程序实现词法分析 public static void main(String args[]) { LL l = new LL(); l.setP(); String input = ""; boolean flag = true; while (flag) { try { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); System.out.println(); System.out.print("请输入字符串(输入exit退出)："); input = br.readLine(); } catch (Exception e) { e.printStackTrace(); } if(input.equals("exit")){ flag = false; }else{ l.setInputString(input); l.setCount(1, 1, 0, 0); l.setFenxi(); System.out.println(); System.out.println("分析过程"); System.out.println("----------------------------------------------------------------------"); System.out.println(" 步骤| 分析栈 | 剩余输入串| 所用产生式"); System.out.println("----------------------------------------------------------------------"); boolean b = l.judge(); System.out.println("----------------------------------------------------------------------"); if(b){ System.out.println("您输入的字符串"+input+"是该文法的一个句子"); }else{ System.out.println("您输入的字符串"+input+"有词法错误！"); 编译原理课程设计报告 题目： 学院： 教师： 姓名： 学号： 班级： 评分： 签字： 编译原理课程设计一：设计c语言的词法分析器 一、实验目的 了解高级语言单词的分类，了解状态图以及如何表示并识别单词规则，掌握状态图到识别程序的编程，加深对词法原理的理解。 二、实验要求 了解高级语言单词的分类，了解状态图以及如何表示并识别单词规则，掌握状态图到识别程序的编程。 三、实验设计 3.1．单词分类及表示 3.1.1 C语言的子集分类 （1）标识符：以字母开头的字母数字串 （2）整数或浮点型。 （3）保留字：for,while,do,else,if,static,int,sizeof,break,continue （4）运算符：+，-，*，/，%,>,<,=,!=,==,<=,>=,!,&,&&,||; （5）界符："(",")",",",":",";","{","}" 3.1.2单词二元组（单词分类号、单词自身值） 3.2 词法分析器的设计 3.2.1算法设计 3.2.1.1概要设计 从文件中逐个读取字符，只要这五大类的状态序列则继续读取，否则回退字符，在对应类别进行查找，输出单元二次组至另一文件夹。 3.2.1.2状态图设计 3.2.2输入输出设计 输入：通过文件指针从文件中一个一个读取字符 输出：输出单词二元组至文件。格式为（种别码，值） 3.2.3主要函数 void Getchar(FILE *fp ) //读入一个字符 void GetBC(FILE *fp)//读入一个非空字符 void contacat()//连接字符 int letter()//判断是否为字母 int digit()//判断是否为字母 void retract(FILE *fp,char *c)//回退 int reserve (char **k)//处理保留字 int sysmbol(identifier *id)//处理标识符，查找符号表并存放位置若没有则添加int constant(constnumber *con)//存入常数表，并返回它在常数表中的位置 语法分析器的设计实验报告 一、实验内容 语法分析程序用LL(1)语法分析方法。首先输入定义好的文法书写文件(所用的文法可以用LL(1)分析)，先求出所输入的文法的每个非终结符是否能推出空，再分别计算非终结符号的FIRST集合，每个非终结符号的FOLLOW集合，以及每个规则的SELECT集合，并判断任意一个非终结符号的任意两个规则的SELECT 集的交集是不是都为空，如果是，则输入文法符合LL(1)文法，可以进行分析。对于文法： G[E]: E->E+T|T T->T*F|F F->i|(E) 分析句子i+i*i是否符合文法。 二、基本思想 1、语法分析器实现 语法分析是编译过程的核心部分，它的主要任务是按照程序的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行词法检查，为语义分析和代码生成作准备。这里采用自顶向下的LL(1)分析方法。 语法分析程序的流程图如图5-4所示。 语法分析程序流程图 该程序可分为如下几步： （1）读入文法 （2）判断正误 （3）若无误，判断是否为LL(1)文法 （4）若是，构造分析表； （5）由句型判别算法判断输入符号串是为该文法的句型。 三、核心思想 该分析程序有15部分组成： （1）首先定义各种需要用到的常量和变量； （2）判断一个字符是否在指定字符串中； （3）读入一个文法； （4）将单个符号或符号串并入另一符号串； （5）求所有能直接推出&的符号； （6）求某一符号能否推出‘& ’； （7）判断读入的文法是否正确； （8）求单个符号的FIRST； （9）求各产生式右部的FIRST； （10）求各产生式左部的FOLLOW； （11）判断读入文法是否为一个LL(1)文法； （12）构造分析表M； （13）句型判别算法； （14）一个用户调用函数； （15）主函数； 下面是其中几部分程序段的算法思想： 1、求能推出空的非终结符集 Ⅰ、实例中求直接推出空的empty集的算法描述如下： void emp(char c){ 参数c为空符号 char temp[10];定义临时数组 int i; for(i=0;i<=count-1;i++)从文法的第一个产生式开始查找 { if 产生式右部第一个符号是空符号并且右部长度为1, then将该条产生式左部符号保存在临时数组temp中 将临时数组中的元素合并到记录可推出&符号的数组empty中。 } Ⅱ、求某一符号能否推出'&' int _emp(char c) { //若能推出&，返回1；否则，返回0 int i,j,k,result=1,mark=0; char temp[20]; temp[0]=c; temp[1]='\0'; 存放到一个临时数组empt里,标识此字符已查找其是否可推出空字 如果c在可直接推出空字的empty[]中,返回1 for(i=0;;i++) { if(i==count) return(0); 找一个左部为c的产生式 j=strlen(right[i]); //j为c所在产生式右部的长度 if 右部长度为1且右部第一个字符在empty[]中. then返回1(A->B,B可推出空) if 右部长度为1但第一个字符为终结符,then 返回0(A->a,a为终结符) else 语法分析器的设计实验报告 一、实验容 语法分析程序用LL(1)语法分析方法。首先输入定义好的文法书写文件(所用的文法可以用LL(1)分析)，先求出所输入的文法的每个非终结符是否能推出空，再分别计算非终结符号的FIRST集合，每个非终结符号的FOLLOW集合，以及每个规则的SELECT集合，并判断任意一个非终结符号的任意两个规则的SELECT 集的交集是不是都为空，如果是，则输入文法符合LL(1)文法，可以进行分析。对于文法： G[E]: E->E+T|T T->T*F|F F->i|(E) 分析句子i+i*i是否符合文法。 二、基本思想 1、语法分析器实现 语法分析是编译过程的核心部分，它的主要任务是按照程序的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行词法检查，为语义分析和代码生成作准备。这里采用自顶向下的LL(1)分析方法。 语法分析程序的流程图如图5-4所示。 语法分析程序流程图 该程序可分为如下几步： （1）读入文法 （2）判断正误 （3）若无误，判断是否为LL(1)文法 （4）若是，构造分析表； （5）由句型判别算法判断输入符号串是为该文法的句型。 三、核心思想 该分析程序有15部分组成： （1）首先定义各种需要用到的常量和变量； （2）判断一个字符是否在指定字符串中； （3）读入一个文法； （4）将单个符号或符号串并入另一符号串； （5）求所有能直接推出&的符号； （6）求某一符号能否推出‘& ’； （7）判断读入的文法是否正确； （8）求单个符号的FIRST； （9）求各产生式右部的FIRST； （10）求各产生式左部的FOLLOW； （11）判断读入文法是否为一个LL(1)文法； （12）构造分析表M； （13）句型判别算法； （14）一个用户调用函数； （15）主函数； 下面是其中几部分程序段的算法思想： 1、求能推出空的非终结符集 Ⅰ、实例中求直接推出空的empty集的算法描述如下： void emp(char c){ 参数c为空符号 char temp[10];定义临时数组 int i; for(i=0;i<=count-1;i++)从文法的第一个产生式开始查找 { if 产生式右部第一个符号是空符号并且右部长度为1, then将该条产生式左部符号保存在临时数组temp中 将临时数组中的元素合并到记录可推出&符号的数组empty中。 } Ⅱ、求某一符号能否推出'&' int _emp(char c) { //若能推出&，返回1；否则，返回0 int i,j,k,result=1,mark=0; char temp[20]; temp[0]=c; temp[1]='\0'; 存放到一个临时数组empt里,标识此字符已查找其是否可推出空字 如果c在可直接推出空字的empty[]中,返回1 for(i=0;;i++) { if(i==count) return(0); 找一个左部为c的产生式 j=strlen(right[i]); //j为c所在产生式右部的长度 if 右部长度为1且右部第一个字符在empty[]中. then返回1(A->B,B可推出空) if 右部长度为1但第一个字符为终结符,then 返回0(A->a,a为终结符) else 词法分析 一、实验目的 设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 二、实验要求 2.1 待分析的简单的词法 （1）关键字： begin if then while do end 所有的关键字都是小写。 （2）运算符和界符 ： = + - * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 2.2 各种单词符号对应的种别码： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 例如：对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列： (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 3.1 主程序示意图： 主程序示意图如图3-1所示。其中初始包括以下两个方面： ⑴关键字表的初值。 关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下： Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 图3-1 （2）程序中需要用到的主要变量为syn,token和sum 3.2 扫描子程序的算法思想： 首先设置3个变量：①token用来存放构成单词符号的字符串；②sum用来整型单词；③syn用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。 实验报告 姓名：孙岩 学号：1408080211 班级：惠普开发142 学校：青岛科技大学Mail: 电话：178******** 教师：宮生文 实验报告： 实验名称：LL(1)语法分析 实验目的和要求 编制一个能识别由词法分析给出的单词符号序列是否是给定文法的正确句子（程序），输出对输入符号串的分析过程。 实验内容和步骤： 一、实验内容 对于这个实验，总共用了三个函数，即主函数、输出分析栈函数、输出剩余串函数。在主函数中，还要构造预测分析表。 二、实验步骤 1、基于实验的内容，构造程序所需的模块 2、根据已建构的模块，写出各个模块的相应程序代码 3、在主函数中调用模块来完成所要得到的效果 在本程序中，首先使用了结构体类型定义来定义产生式，用字符串数组存放分析栈、剩余串、终结符和非终结符，用二维数组存放预测分析表，利用指针对栈中数据进行读取。在本程序中，总共用了三个函数，即主函数、输出分析栈函数、输出剩余串函数。在主函数中，还要构造预测分析表，对输入的字符串进行分析，调用另外两个函数。 实验代码如下： #include编译原理词法分析器语法分析器实验报告
编译原理实验报告(语法分析器)
c语言语法分析器详解
TEST语言 -语法分析,词法分析实验报告
词法分析器实验报告
C语言编译器的设计与实现.
编译原理LL(1)语法分析实验报告
编译原理词法分析和语法分析报告 代码(C语言版)
词法分析器实验报告
编译原理--词法分析,语法分析,语义分析(C语言)
语法分析(自上而下分析)实验报告
编译原理语法分析器实验报告
编译原理设计c语言的词法分析器
语法分析器实验报告
语法分析器实验报告
编译原理词法分析和语法分析报告+代码(C语言版)
LL(1)语法分析实验报告
相关主题
文本预览