给你实验报唯巧告
#include <stdio.h>
#include<dos.h>
#include<stdlib.h>
#include<string.h>
char a[50] ,b[50]
char ch
int n1,i1=0,n=5
int E()int T()int E1()int T1()int F()
void main() /*递归分析*/
{
int f,j=0
printf("请输入字符串(长度<50,以#号结束）\n")
do{
scanf("%c",&ch)
a[j]=ch
j++
}while(ch!='#')
n1=j
ch=b[0]=a[0]
f=E()
if (f==0) return
if (ch=='#') printf("accept\n")
else printf("error\n")
}
int E() // E→TE'
{ int f,t
f=T()
if (f==0) return(0)
t=E1()
if (t==0) return(0)
else return(1)
}
int T() // T→FT'
{ int f,t
f=F()
if (f==0) return(0)
t=T1()
if (t==0) return(0)
else return(1)
}
int E1()/*E’山山含*/ // E'→+TE'
{ int f
if(ch=='+') {
b[i1]=ch
ch=a[++i1]
f=T()
if (f==0) return(0)
E1()
return(1)
}
return(1)
}
int T1()/*T’*/逗笑 // T'→*FT'
{
int f,t
if(ch=='*') {
b[i1]=ch
ch=a[++i1]
f=F()
if (f==0) return(0)
t=T1()
if (t==0) return(0)
else return(1)}
a[i1]=ch
return(1)
}
int F() // F→(E)
{ int f
if(ch=='(') {
b[i1]=ch
ch=a[++i1]
f=E()
if (f==0) return(0)
if(ch==')') {
b[i1]=ch
ch=a[++i1]
}
else {
printf("error\n")
return(0)
}
}
else if(ch=='i') {
b[i1]=ch
ch=a[++i1]
}
else {printf("error\n")return(0)}
return(1)
}
前面所介绍的SLR(1)分析法是一种较实用的方法。其优点是状态数目少，造表算法简单，大多数程序设计语言基本上都可用SLR(1)文法来描述。然而，也的确存在这样的文法，其项目集的“移进归约”冲突不可能通过SLR(1)规则得到解决。试看下面的例子。
例4?8考察文法G[S′]=({S′,S,A,B,C,D}, {a,b},,P,S′)其中，P由如下的产生式组成：
0? S′→S4?B→C
1?S→CbBA5?B→Db
2?A→Aab6?C→a
3?A→ab7?D→a
识别此文法的全部活前缀的DFA见图418。其中项目集I10={S→CbBA·,A→A·ab}存在“移进归约”冲突，但因FOLLOW(S)={#}，故上述冲突可通过SLR(1)规则得到解决。然而，在项目集I8={C→a·,D→a·}中，由于FOLLOW(C)={a,b}，FOLLOW(D)={b}，即FOLLOW(C)∩FOLLOW(D)≠?，故用SLR(1)规则解决上述“归约归约”冲突无效。而且还可验证，对于任何K>0，上述文法也是非SLR(k)的，故不能通过任何SLR(k)规则使项目集I8中的“归约归约”冲突得到解决 [2]。因此，我们需要更强的LR分析法，即LR(1)分析方法来解决这一问题。
对SLR(1)规则稍作分析即可发现，它对某些文法失效的原因，在于当所给的文法出现冲突的分析动作时，SLR(1)规则仅孤立地考察输入符号是否属于与归约项目A→α·相关联的集合FOLLOW(A)，以确定是否应按产生式A→α进行归约，而没有考察符号串α所在规范句型的“环境”，即没有考察α在规范裤贺句型中的“上下文”，这就具有一定的片面性。因为一旦α出现在分析栈的顶部 (设分析栈当前所存放的符号串为#δα)，且当前的输入符号a也属于FOLLOW(A)，就贸然将α归约为A，此时分析栈中的符号串将变成#δA，但若文法中并不存在以δAa为前缀的规范句型，那么，这种归约无效。例如，对于上述文法中的规范句型Cbabab，当分析达到格局
I0I2I4I8[]#Cbabab(4?50)
时，如果仅根据当前输入符号b∈FOLLOW(C)，就将栈顶符号a按产生式C→a归约为C，则有如下的格局：
I0I2I4I6[]#CbCbab
但在该文法中，根本不存在以CbCb为前缀的规范句型，因此在执行下一动作将b移进之前，分析器将报告“出错”。由此可见，在分析过程中，当试图用某一产生式A→α归约栈顶符号串α时，不仅应查看栈中符号串δα，还应向前扫视一输入符号a (我们将a称为向前搜索符号)，只有当δAa的确构成文法某一规范句型的前缀时，才能用此产生式进行归约。为了指明上述事实，应当在原来的每一LR(0)项目[A→α·β]中放置一个向前搜索符号a，使之成为[A→α·β,a]的形式，我们将此种项目称为一个LR(1)项目。同时，为了使分析的每一步都能在栈中得到一个规范句型的活前缀，还应要求每一个LR(1)项目对相应的活前缀都是有效的 (其定义在下面给出)。此外，液纤为了克服分析动作的冲突，在必要时，我们还可将某些项目集进行分解，以便使每一个状态都能确切地指明： 当α已出现在栈顶，且面临哪些输入符号时，才能按产生式A→α将α归约为A。
所谓一个LR(1)项目[A→α·β，a]对活前缀γ=δα有效，是指存在规范推导
S?*δAy?δαβyy∈V*T
且满足下列条件：
(1) 当y≠ε时，a是y的首符号；
(2) 当y=ε时，a=#。
例如，对于例4?8所给文法，因有
S?CbBA?CbBab?CbDbab
其中，δ=Cb,α=D,β=b,y=ab,A=B，故LR(1)项目[B→D·b,a]对活前缀γ=CbD有效。又因
S?*CbDbab?Cbabab
其中，δ=Cb,A=D,α=a,β=ε,y=bab,故LR(1)项目[D→a·,b]对活前缀γ=Cba有效。由此也可看出，当分析器所处的格局为式(4?50)时，应当将栈顶符号a归为D，而不应将它归约为C。
与LR(0)文法的情况相类似，识别文法全部活前缀的DFA的每一个状态也是用一个LR(1)项目集来表示，而每一个项目集又是由若干个对相应活前缀有效的LR(1)项目组成。为了构造LR(1)项目集族，我们同样需要闹纯仿用到两个函数，即CLOSURE(I)及GO(I，X)。
对每一LR(1)项目集I，相应的CLOSURE(I)的定义如下：
(1) I中的任何LR(1)项目都属于CLOSURE(I)。
(2) 设项目[A→α·Bβ，a]∈CLOSURE(I)，并假设它对活前缀γ=δα有效，则对文法中所有形如B→η的产生式和每一个b∈FIRST(βa)，形如[B→·η,b]的全部项目也都对γ有效，故若[B→·η,b]原不在CLOSURE(I)中，则应将其放入。事实上，因为[A→α·Bβ，a]对γ=δα有效，则由定义我们有：
s?*δAy?δαBβyy∈V*T
且a∈FIRST(y)∪{#}，故可将上面的推导写成
S?*δAy?δαBβaωω∈V*T∪{#}
现设文法已经过化简，故不论β是否为ε，从βaω总能推出终结符号串，于是可假定
βaω?*bω′
又因a≠ε，有FIRST(βaω)=FIRST(βa)，从而就得到推导
S?*δαBbω′
由此可见，一切形如[B→·η,b]的项目也对活前缀γ=δα有效。
(3) 重复步骤(2)直到没有新的项目加入为止。
至于函数GO(I，X)，其中I为一LR(1)项目集，X为某一文法符号，与LR(0)文法类似，我们也将它定义为：
GO(I,X)=CLOSURE(J)
其中J是由这样的一些LR(1)项目组成： 对I中所有圆点在X左边形如[A→α·Xβ,a]的项目，其后继项目[A→αX·β,a]∈J。注意，每一LR(1)项目与其后继项目有相同的向前搜索符号。
有了上述CLOSURE(I)和GO(I，X)的定义之后，采用与LR(0)类似的方法，可构造出所给文法G的LR(1)项目集族C及状态转换图。例如，对于上述文法，其LR(1)项目集及状态转换图如图419所示。
对于给定的文法G，当相应的LR(1)项目集族C及GO函数构造出来之后，便可按如下的算法构造它的LR(1)分析表：
(1) 对于每个项目集Ii中形如[A→α·Xβ,b]的项目，若GO(Ii,X)=Ij，且当X为一终结符号a时，置ACTION[i,a]=sj。但若X为一非终结符号时，则置GOTO[i,X]=j。
(2) 若归约项目[A→α·,a]∈Ii，A→α为文法的第j个产生式，则置ACTION[i,a]=rj。
(3) 若项目[S′→S·,#]∈Ii，则置ACTION[i,#]=acc。
(4) 在分析表中，凡不能照上述规则填入信息的元素，均置为“出错”。
对于一个文法G来说，若按上述算法所构造的分析表不含有多重定义的元素，则称此分析表为G的LR(1)分析表。凡具有LR(1)分析表的文法称为LR(1)文法。例如，上述文法的LR(1)分析表见表416，所以它是一个LR(1)文法。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）