2023年语法分析器实验报告.docx

《2023年语法分析器实验报告.docx》由会员分享，可在线阅读，更多相关《2023年语法分析器实验报告.docx（30页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、语法分析器的设计实验报告一、实验内容语法分析程序用LL (1)语法分析方法。一方面输入定义好的文法书写文献(所用 的文法可以用LL ( 1)分析)，先求出所输入的文法的每个非终结符是否能推出 空，再分别计算非终结符号的FIR ST集合，每个非终结符号的F 0 LLOW集合, 以及每个规则的SELECT集合，并判断任意一个非终结符号的任意两个规则的S ELECT集的交集是不是都为空，假如是，则输入文法符合LL (1)文法，可以 进行分析。对于文法：GE:E- E+T I TT-T*F I FF-i|( E)分析句子i+i*i是否符合文法。二、基本思想1、语法分析器实现语法分析是编译过程的核心部分

2、，它的重要任务是按照程序的语法规则,从由词 法分析输出的源程序符号串中辨认出各类语法成分，同时进行词法检查，为语义分 析和代码生成作准备。这里采用自顶向下的LL(1)分析方法。语法分析程序的流程图如图5-4所示。/* * *判断个字符C是否在指定字符串p中* * * * */int i n( c har c,cha r *p)(aint i ；i f(s t rlc n (p) =0)r eturn(O);for( i =0； ； i +)。i f(pi=c)a r e t u m(I);/若在，返回 1o if(i= (int)st r 1 e n ( p )。rc t ur n (0)；/

3、 /若不在，返回 0)/*木* * *木* 木木* * * * *水*水*木* * *火* * * 火 *水火*将单个符号或符号串并入另一符号串* * * *木* * *木* * *木 * * * *木 /void m e r g e( c har * d,char *s,ini type)/是目的符号串,s是源串，type=l,源市中的& 一并并入目串;/type =2,源串中的&不并入目串i nt i. j ;f o r(i=0;i=(int)st r lcn(s)-l;i+ + )。if( t y pe=2&si=& );oo e 1 s e (gofor (j=0： ; j +)。i

4、f (j j;pr i ntf(”请输入文法的非终结符号串:)；sc a n f (% s , v n);get c h ar ();i= s t r len(vn);meme p y(n,vn, i);oni=z 0;叩r i ntf (请输入文法的终结符号串：);s c a n f( %s, v t);gelchar ();i= s tri e n (vt)；mem c py( t ,v t ,i)；ti=O/ ;print f (请输入文法的开始符号:)；。s can f (%c ,&s);gctc har()；叩rin t f(”请输入文法产生式的条数:“);scanf (%d ” ,

5、&i)；g e tchar();ocoii n t=i;fbr(j=l； j=i； j+) (。prin t f(请输入文法的第d条(共d条)产生式:，j,i)；sc anf(%s,pj-l)；gctch a r()；f o r (j= 0 ;j)/检测输入错误8 。oprintf(”n 输入错误！)aval i dity=O;oorcturnC 0 );retu r n(s);)/* * * * * * * * * * * * *判断读入的文法是否对的* * * * * */i nt judgc()(i nt i , j ；f o r ( i =0;i=co u nt-1 ;i+ +)(。

6、i f(i n(1 e f t i ,non_te r )=0)!若左部不在非终结符中，报错，。p r intf( n文法左部犯错!”)；validity=O；orcturn(O);00fo r ( j =0;j=(i nt) s tr 1 e n(righ t i )-1 ;j+)。 if(in(r i gh t i j , n on_ter) =0&in(rig h t li j , t erm i n)= 0 &righi j !+&)。(若右部某一符号不在非终结符、终结符中且不为心，报错。 print f(n文法右部犯错！)；ava 1 i di t y= 0 ；8 ret u r n

7、(0)；。)00 rcturn( 1);)/* * * * * * * * * * * * * * * * * *求所有能直接推出&的符号* * */void emp( char c )(c h ar t e m p 1 0 ；int i;for ( i =0； ia,a为终结符)。 c o ntinu e ；o e Ise。(f or(k=0； kAB)g。 ma r k=I ；。 )。if(m a r k= 1 )/ /找到的字符与当前字符相同(A- A B)g oco n tinu e ; /结束本次循环。沱Ise /(ma r k 等于 0)0000 00。 f o r(k=O； k

8、=j-l ； k+) (。-result *=_emp(righ t i k);/递归调用，查找右部符号是否可推出空字，把返回值赋给r e su 1 t。 a tempO= r ig h tij k ；a。 t e mp 1 = 0merge(em p t, t e mp,l);把当前符号加入到临时数组cmpt 里，标记已查找。i f(resu 1 t =0 &icount)假如当前字符不能推出空字且还没搜索完所有的产 生式，则跳出本次循环继续搜索下一条产生式cont i nue;1 se if(result=l&ic o u n t )当前字符可推出空字，返回1grc t urn(l);0

9、)* *木* * * * * * * * * * *求单个符号的FIRST* * * * * * */voi d fi r s t 2 (int i )/i为符号在所有输入符号中的序号ch a rc,temp20;o i n t j, k,m； c h ar ch=&；c= v lij；0emp (ch)； / /求所有能直接推出空字的符号，结果保存到em p ty 口中if(in (c,termin)=l)/ /若为终结符-c VT,则 F IRST(c) =c)f i rstliOl=c;若为非终结符else if( i n (c, n on_ t er)=l)for(j= 0 ; j =

10、count1； j+) /)为所有产生式中的序列00 |if(leftfj=c) /找一个左部为c的产生式2 (a。 if (in (rightfjl 0,termin)=l I I rig h t j 0 = &)，/若产生式右部第一个字符为终结符或空.一产生式X-a (aVT)或X一&,则把a或&加进FIRST(X)teni p 0=r i g h t|j 0 ;4 e mp 1 = 0。 mer g e(fi r stl i ,tem P ,1);00 一一-XfYlY2Yk的产生式，若Y 1 EVN,则把FIRST(YI)中的一切非空符号加进 F IRST(X)g e 1 se if(

11、in( r i ght|j 0,n o n _ter)= I)/ /产生式右部第一个字符为非终结符(。if(righljO=c) 产生式右部的第一个符号等于当前字符，则跳到下一条产生式进行查找。o oconli n ue;8。for(k=0;k+)0oif(vk= rig h t j 0) 求右部第一个字符在所有字符集中的位置k3 a。 brc a k;000000i f (fir s tflag k= O)。6 rst2(k)； 求其 FI RST 集，。 gf i r s tflagk:T;/标记其为查找状态000a。me r ge(firstl i , f irstlk, 2 )； 求得

12、结果并入到 X 的 FIRST 集. f o r(k=O； k (in t )st r 1 c n (rig h t j)： k+)000-oCmpt0=0, ; /存放到一个临时数组里，标记此字符已查找其是否可推出空字。if(_ e mp( r i g hl j k) = 1 &k ( i n t ) s t rlen(r i gh(j)-l)。/ /当前产生式右部符号可推出空字，且当前字符不是右部的最后一个字符a。f or (m=0： ;m+)ooo 。2 -if (vm =rightj k+1)/获取右部符号下一个字符在所有字符集中的位置 a 。b r e ak;ooa)。a。，if (

13、 f i rstfl a gm=)/假如此字符的FIRST集尚未查找，则找其FIRST集, 并标其杳找状态为100M08。 wfi r st2(m);。 。 first f 1 a g m=r；0000 |。 。 merge(f i rs t i rst 1把求得结果并入到 X 的 FI R S T集.00语法分析程序流程图该程序可分为如下几步：(1)读入文法(2)判断正误(3)若无误，判断是否为LLQ)文法(4)若是,构造分析表；(5 )由句型判别算法判断输入符号串是为该文法的句型。三、核心思想该分析程序有1 5部分组成：(1)一方面定义各种需要用到的常量和变量；(2)判断一个字符是否在指定

14、字符串中；(3)读入一个文法；(4 )将单个符号或符号串并入另一符号串；(5)求所有能直接推出&的符号；(6)求某一符号能否推出& ;(7)判断读入的文法是否对的；(8)求单个符号的F I RST；(9 )求各产生式右部的FIRS T;/一-产生式为X-YIY2Yk,若对一切lO;a 。 merg e (fir s tl i, t emp.l);/把空字加入到当前字符X的F I R S T集.000 |else。break;/不能推出空字则结束循环o 0 )4 i rstfl a gi=;/ /标记当前字符c已查找其F I R S T集 )/* 木*木* *木* * * * 木* * 木*木*

15、 木木求各产生式右部的FI RST木*木* * * *木*木木木* *大*木*木木木*木木* * * * * *木* * /void F IR ST(int i , c har * p )指针P指向右部符号串in t leng t h； / /标记右部符号串的长度aim j, k, m；c har tempi2 0 ;dength=strl e n(p);oif(i ength=l)/ /假如右部为单个符号s if(p(O = =&) /右部符号串字符为“&”空字 (。o i f(i=0) /i不为-1时是产生式的序号 (。firs=，&;/把加入到当前符号串的FIRST集。f i r s t

16、i 口=0；)。 e Is e / / i为-1时,表达求FOLLOW时用到的产生式右部的FIRST集,保存在 TEMP 口中00|ggTEMP0=&;。TEMP 1=0;8)，else / /右部符号串字符不为“&”空字 (. fo r(j=O;j+)000 8 i f(Vj=:p0)求右部符号的第一个字符P0在所有字符集中的位置j。 gbr e a k ;8(g m e mcp y (fi r s t i,f i rs t I j,slr 1 en(f i rst 1 j );/ 把 j 所指向的单个符 号的FIR S T集拷贝到该右部符号串的FIRST集a。f i r s t i Jls

17、trlen(fi r s t 1 lj)J= 0；。 ocls eU。 mem c p y(TEM P,first 1 j, str i e n (firstlj);。TEM P s tr 1 en(firstl j) =0;g)oclse/假如右部为符号串0 。 f o r (j= 0 ;； j+)if (Vj =p 0) /求右部符号的第一个字符p0在所有字符集中的位置j。 a b r e ak;。i f ( i = 0 )s me r ge(fir st i, fir s tlj ,2);。 elsewomerg e (TEM P,f i rst 1 j , 2 );for(k=O; k

18、 =lcng t h-1 ;k+ )g e mpt 0= 0；oooif(_emp(pk) = 1&kif(vm=righti k +1)break;0 (o i f( i =0)merge(firsl i , first 1 m ,2);s 。 e Is e。 me r ge(TEMP, firstl m,2);8)clse i f (_cm p (pk) = 1 &k= 1 en g t h-1)。/当前右部符号串可推出空且是右部符号串的最后一个字符g。t e mpl0=,。 ootempl 1 =0;。if ( i =0)g e rge( f irst i , temp, 1 );wis

19、emerge(TEM P , t em p ,1);)。 e 1 se i f (_ e mp (p k)=0)a。b rea k ;001)/* * * * *求各产生式左部的FOLLOW* * * * * * * * * * * * * * * * * /vo i d FO LLOW(int i) 参数i为该符号在非终结符中的位置ini j , k,m, n , res u lt= 1 ；char c,t e mp 2 0：c=non_t e市;/ c为待求的非终结符temp0= c ;4 e mpl=0/；omer g e(f o 1 1 , temp);/把当前字符放至lj一临时数组f

20、 o 11中，标记求已求其FOL L。W集.避免循环递归if ( c =s tart)/若为开始符号一一开始符号S, M#gfol LOW(S)Mem p 0-#;temp 1 =0;omerg e (follow i, temp, 1 );)fo r (j=0;j*&)的产生式for(k=0;； k+)i f( r i ght j k=c)。 b re a k;/k为c在该产生式右部的序号，如B在产生式A-a B中的位置 000 f o r(m=0;m+)。if(v m=left j )o obreak；m为产生式左部非终结符在所有符号中的序号00 /假如c在产生式右部的最后，形如产生式A-

21、a B,则FOLLOW(A)FOLL OW (B)。 i f(k=(int) strlen(right j )-1)0 g。if (in(vlm,fol 1 )=1)查找该非终结符是否已经求过其F OLLOW集.避免循环递归g 是则 FOLLOW(A) WFOLLOW(B)o emerge (fol 1 ow i ,follow m, 1);把c所在产生式的左部非终结符的 FOLLOW 集力口入至lj FOL LOW (c)中 c o ntinu e ； /结束本次循环，进入j+循环 )。 i f (f o 11 o wfl a gm=O)。假如该非终结符的FOLLOW未求过。FOLLOW(m

22、); 求之 FOLLOW。fo 1 1 owf 1 a g m=，1 ;标记为 1000 )0000emerge (fol 1 ow i, fo 1 1 o w m , 1); / / F O L LOW( A) G FOLLOW(B)elseelse。假如c不在产生式右部的最后，形如A- a B Bgf o r ( n =k+l ； n*&)贝 IFOL LOW (A)eFOLLOW(B)if (in (vm, f oll)= = 1)，。查找该非终结符是否已经求过其FOLLOW集.避免循环递归0nl erge(fo 1 1 ow i ,fol 1 o wm J ) ;/F O LLOW(A

23、)E FOLLOW(B) ooftwcon t inue;002 。i f( f o llowfla g m = O)a(。oFOL LOW(m);a。followf 1 ag m = 1,;6 1 me r ge (fol 1 owi,f o llowm, 1);02 /若Af a B B,其中 Be VN,a e(VT U VN)*、B e(VT U VN)+,则FIRST(B)- e F OLLOW(B);fb r (n=k+ 1 ;n=(i n t)str 1 en( r i g htj) -l;n+)t e mpn-k-l=ri g htjn；g tem p str 1 e n( r

24、 i g htj )-k-1 = 0 *;FIR ST(-1, temp) ;/ /求 FIRST(B)。 -me r g e(fo 1 1 ow il.TEMP, 2 );/把 F I R ST( B )中所有非空元素加入到 FOLLOW(B)中000 |g)fol 1 owf 1 ag i =r； /标记当前规定的非终结符的FOL LOW集已求过 )/* * * * * * * * * * * * * *判断读入文法是否为一个LL(1)文法* * * * * * * * * * * * * */int LL 1 () |i nt i , j , 1 e ngth， r e su 1 t=

25、1;c h ar t emp50J;for (j=0； j =4 9；j+)。初始化gfirs t j 0 = 0;fo 1 low j 0= 0;gf i rst1fj0=0;o s elec t j 0=0;TEMPjl=O,;。 t empj=O;fir s tfl a g j 0?/用来记录该字符的FIRST集是否己求过.1表达已求，0表达未求ofol 1 ow f lag j = ()； /用来记录该字符的FOLLOW集是否已求过.1表达已求,0表 达未求)f o r(j= 0 ;j= (i n t)strle n (v) 1 :j+)4ir s t2(j)；求单个符号的FIRST集

26、合，结果保存在firsll 口里opri n tf( n各非终结符推出的f i rst集： n ”)；ofo r (j =0;j=( i nt) s tri e n (v) -1； j+)pri n tf(%c： %s , vfj, firstljl); )P rinif( n能导空的非终结符集合:% s ”.empty);p r intf(un_emp：)；4o r( j =0 ;j=(in t ) s t rlen(v) l;j+)p r intf (%d ,_emp(v j );fb r ( i =0； i=co u nt-l ;i+)oFIRST (i,rig h t i );求 HR

27、STfbr(j=O;j= ( i nt)strlen (non_ t e r) l;j+)求 FOLLOWooi f (foil j=0)2foi i0= (y；FOLLOW。)；)printf(nfirst 集：);fo r (i=O;i=c o u n t-1 ； i+)printf (%s , first i );P rinif (nfollow 集合：);fo r ( i = 0 ;i=( i n t )strlen(n o n_ t er) 1 ； i+)。 p r intf(n%s ,fbl 1 ow i 1);for (i= 0 ； i =countl;i+)。/求每一产生式的S

28、 EL ECT集合memcpy(sel e c ti,fi r st i ,strle n (firsti )； /first存放的是各产生式右部的 F IRST 集sei e cti strlen(first i ) =0;for(j=0;j&。 re s u 1 t = 1;o if( r e su 1 t= 1 ) s for(j=0;； j+)oi f (vl j = = lefli)j为左部符号在所有字符集中的位置a。bre a k ;。 mcr g e (s e 1c c t i, f oliow j J)；(10)求各产生式左部的FOLLOW；(11)判断读入文法是否为一个LL

29、(1)文法；(12)构造分析表M;(1 3)句型判别算法；(14) 一个用户调用函数；(15)主函数；卜.面是其中几部分程序段的算法思想：1、求能推出空的非终结符集I、实例中求直接推出空的empt y集的算法描述如下：void em p (char c) 参数c为空符号char t empl 0 ;定义临时数组oint i ；for(i=0： i =coun t -l;i+)从文法的第一个产生式开始查找。i f产生式右部第一个符号是空符号并且右部长度为1,then将该条产生式左部符号保存在临时数组temp中将临时数组中的元素合并到记录可推出&符号的数组em p ty中。II、求某一符号能否推出

30、&i nt _cmp( c har c)若能推出&,返回1；否则，返回0i nt i ,j, k, r esult= l,mark=0;ch a r templ20J;4emp0=c;tcmp 1 = O;。存放到一个临时数组empt里，标记此字符已查找其是否可推出空字P rint f (nse 1 ec t 集合顺序是：);f o r( i =O;i p rintf(n% s , selecti);amem c p y(t e nip, s el e ct 0 ,s t r 1 en( s elect 0 J);t e mpstrlen( s e Ie c t 0)=,0；ofor(i=l;

31、 i =co u n t 1 ; i +)/ 女判断输入文法是否为LL(1)文法*/le n g t h=strl e n (temp);Mf(le f t i= 1 efti-l )( 0m e rge(temp. s e 1 ec t i ,1);woif (s t rle n (t e m p )return( 1 );)/*木*木* *木* * * * * *木* 火* *木*木木*构造分析表M木木木木木* *求* * *木*求*木木* * * * * * *木*木*木* * *水*/void MM ()int i, j ,k,m；fbr( i =0 ;i=l 9 ； i+)oforO

32、=0;j=19;j+) 初始化分析表，所有置为空(-1)。(2Mij=- 1 ；)i=st r 1 e n( t ermi n );t erm i nl i =# z ;/ /将#加入终结符数组t e r mini+l=0,;for (i=0： i=count-l; i +) / / 查看每个产生式的 SELE C T集 for (m= 0 ;m+)0 if(non_term =lcft i )。b r e a k; m为产生式左部非终结符的序号0 )f or (j=O;j=(i n t)str 1 en (selecti)-l; j +)/ / 对每个 S E LECT 集中的所有元素进行操

33、作00i f (in(s e 1 ecti j ,termin)=l)000f o r(k=O； ； k+)。 o if(termink=sel e c t i j)。 b reak;/ k为产生式右部终结符的序号00 I)，)/* * * * * * *判断符号串是否是该文法的句型* * * * * * * * * * * * * * * * */void s y n t ax()(ini i,j, k ,m,n,p q;c h ar c h ;charS 5 0, st r 5 0 ;pr i ntf(”请输入该文法的句型：);s c an f (%s,st r );getc h a r(

34、);i=strl e n(st r );stri=#ostri+lT0；3 s l=slarl；S2 =0;j=0;sch=strj：w h i 1 e( I )。 i f (in(S s trlcn(S) 1 , t erm i n)= 1 )00 i f(S st r len(S)-l!=c h )。p rintf(该符号串不是文法的句型巧：retur n;g2cl s e i f (S st rlcn(S)-l=-# )printf (该符号串是文法的句型.”)；r etum；8)elseOdd Sstrlen (S)-1 =10;8g j + ；。ch=str jj;。)1 sef or ( i =0;； i+)f (non_ter i =Sstrlen (S)-1 )。b rea k ；。fbr( k =0;k+) 。 if( t erm i nk =c h )o aabre a k;。 if (k=( i nt) s trlen ( t e rmin)。oprint f (词法错误！)；。o return;0000 )0。i f (M i