編譯原理詞法分析,語法分析實驗報告

1、編譯原理實驗報告一LL(1)文法分析1.設計要求 （1）對輸入文法，它能判斷是否為LL(1)文法，若是，則轉(zhuǎn)（2）；否則報錯并終止； （2）輸入已知文法，由程序自動生成它的LL(1)分析表； （3）對于給定的輸入串，應能判斷識別該串是否為給定文法的句型。2.分析 該程序可分為如下幾步：（1）讀入文法 （2）判斷正誤 （3）若無誤，判斷是否為LL(1)文法 （4）若是，構(gòu)造分析表；（5）由總控算法判斷輸入符號串是否為該文法的句型。有效？讀入文法開始3.流程圖是是LL(1)文法？結(jié)束報錯判斷句型是4.源程序/* 語法分析程序 作者：xxx 學號：xxx*/#include<stdlib.h&

2、gt;#include<stdio.h>#include<string.h>/*/int count=0; /*分解的產(chǎn)生式的個數(shù)*/int number; /*所有終結(jié)符和非終結(jié)符的總數(shù)*/char start; /*開始符號*/char termin50; /*終結(jié)符號*/char non_ter50; /*非終結(jié)符號*/char v50; /*所有符號*/char left50; /*左部*/char right5050; /*右部*/char first5050,follow5050; /*各產(chǎn)生式右部的FIRST和左部的FOLLOW集合*/char first

3、15050; /*所有單個符號的FIRST集合*/char select5050; /*各單個產(chǎn)生式的SELECT集合*/char f50,F50; /*記錄各符號的FIRST和FOLLOW是否已求過*/char empty20; /*記錄可直接推出的符號*/char TEMP50; /*求FOLLOW時存放某一符號串的FIRST集合*/int validity=1; /*表示輸入文法是否有效*/int ll=1; /*表示輸入文法是否為LL(1)文法*/int M2020; /*分析表*/char choose; /*用戶輸入時使用*/char empt20; /*求_emp()時使用*/c

4、har fo20; /*求FOLLOW集合時使用*/* 判斷一個字符是否在指定字符串中*/int in(char c,char *p)int i;if(strlen(p)=0)return(0);for(i=0;i+)if(pi=c)return(1); /*若在，返回1*/if(i=strlen(p) return(0); /*若不在，返回0*/* 得到一個不是非終結(jié)符的符號*/char c()char c='A' while(in(c,non_ter)=1)c+;return(c);/* 分解含有左遞歸的產(chǎn)生式*/void recur(char *point) /*完整的產(chǎn)

5、生式在point中*/ int j,m=0,n=3,k;char temp20,ch;ch=c(); /*得到一個非終結(jié)符*/k=strlen(non_ter);non_terk=ch;non_terk+1='0'for(j=0;j<=strlen(point)-1;j+)if(pointn=point0) /*如果|后的首符號和左部相同*/for(j=n+1;j<=strlen(point)-1;j+) while(pointj!='|'&&pointj!='0') tempm+=pointj+;leftcount=

6、ch;memcpy(rightcount,temp,m);rightcountm=ch;rightcountm+1='0'm=0;count+;if(pointj='|')n=j+1;break;else /*如果|后的首符號和左部不同*/leftcount=ch;rightcount0=''rightcount1='0'count+;for(j=n;j<=strlen(point)-1;j+) if(pointj!='|') tempm+=pointj; else leftcount=point0; mem

7、cpy(rightcount,temp,m); rightcountm=ch; rightcountm+1='0'printf(" count=%d ",count);m=0; count+; leftcount=point0; memcpy(rightcount,temp,m); rightcountm=ch; rightcountm+1='0'count+; m=0;/* 分解不含有左遞歸的產(chǎn)生式*/void non_re(char *point) int m=0,j;char temp20;for(j=3;j<=strlen(po

8、int)-1;j+) if(pointj!='|') tempm+=pointj;else leftcount=point0; memcpy(rightcount,temp,m); rightcountm='0'm=0;count+; leftcount=point0; memcpy(rightcount,temp,m); rightcountm='0' count+;m=0;/* 讀入一個文法*/char grammer(char *t,char *n,char *left,char right5050)char vn50,vt50;char

9、s;char p5050;int i,j,k;printf("n請輸入文法的非終結(jié)符號串："); scanf("%s",vn);getchar(); i=strlen(vn); memcpy(n,vn,i);ni='0'printf("請輸入文法的終結(jié)符號串："); scanf("%s",vt);getchar(); i=strlen(vt); memcpy(t,vt,i);ti='0' printf("請輸入文法的開始符號：");scanf("%c&q

10、uot;,&s);getchar();printf("請輸入文法產(chǎn)生式的條數(shù)："); scanf("%d",&i);getchar(); for(j=1;j<=i;j+)printf("請輸入文法的第%d條（共%d條）產(chǎn)生式：",j,i);scanf("%s",pj-1); getchar(); for(j=0;j<=i-1;j+)if(pj1!='-'|pj2!='>')printf("ninput error!"); vali

11、dity=0;return('0'); /*檢測輸入錯誤*/ for(k=0;k<=i-1;k+) /*分解輸入的各產(chǎn)生式*/ if(pk3=pk0) recur(pk);else non_re(pk);return(s);/* 將單個符號或符號串并入另一符號串*/void merge(char *d,char *s,int type) /*d是目標符號串，s是源串，type1，源串中的 一并并入目串； type2，源串中的 不并入目串*/ int i,j;for(i=0;i<=strlen(s)-1;i+) if(type=2&&si='&

12、#39;);elsefor(j=0;j+) if(j<strlen(d)&&si=dj) break; if(j=strlen(d) dj=si; dj+1='0' break;/* 求所有能直接推出的符號*/void emp(char c) /*即求所有由 推出的符號*/char temp10;int i;for(i=0;i<=count-1;i+)if(righti0=c&&strlen(righti)=1)temp0=lefti;temp1='0'merge(empty,temp,1);emp(lefti);/*

13、 求某一符號能否推出 */int _emp(char c) /*若能推出，返回1；否則，返回0*/int i,j,k,result=1,mark=0;char temp20;temp0=c;temp1='0'merge(empt,temp,1);if(in(c,empty)=1)return(1);for(i=0;i+)if(i=count) return(0);if(lefti=c) /*找一個左部為c的產(chǎn)生式*/ j=strlen(righti); /*j為右部的長度*/if(j=1&&in(righti0,empty)=1) return(1);else

14、if(j=1&&in(righti0,termin)=1)return(0);else for(k=0;k<=j-1;k+) if(in(rightik,empt)=1)mark=1;if(mark=1)continue;else for(k=0;k<=j-1;k+)result*=_emp(rightik);temp0=rightik;temp1='0'merge(empt,temp,1); if(result=0&&i<count) continue; else if(result=1&&i<count

15、) return(1);/* 判斷讀入的文法是否正確*/int judge() int i,j;for(i=0;i<=count-1;i+)if(in(lefti,non_ter)=0) /*若左部不在非終結(jié)符中，報錯*/printf("nerror1!");validity=0;return(0);for(j=0;j<=strlen(righti)-1;j+)if(in(rightij,non_ter)=0&&in(rightij,termin)=0&&rightij!='') /*若右部某一符號不在非終結(jié)符、終

16、結(jié)符中且不為 ，報錯*/printf("nerror2!");validity=0;return(0);return(1);/* 求單個符號的FIRST*/void first2(int i) /*i為符號在所有輸入符號中的序號*/ char c,temp20;int j,k,m;c=vi;char ch=''emp(ch);if(in(c,termin)=1) /*若為終結(jié)符*/ first1i0=c; first1i1='0' else if(in(c,non_ter)=1) /*若為非終結(jié)符*/for(j=0;j<=count-1

17、;j+) if(leftj=c) if(in(rightj0,termin)=1|rightj0='') temp0=rightj0; temp1='0'merge(first1i,temp,1);else if(in(rightj0,non_ter)=1)if(rightj0=c)continue;for(k=0;k+)if(vk=rightj0)break;if(fk='0') first2(k); fk='1'merge(first1i,first1k,2); for(k=0;k<=strlen(rightj)-1;k

18、+)empt0='0'if(_emp(rightjk)=1&&k<strlen(rightj)-1) for(m=0;m+)if(vm=rightjk+1)break;if(fm='0')first2(m);fm='1'merge(first1i,first1m,2);else if(_emp(rightjk)=1&&k=strlen(rightj)-1)temp0=''temp1='0'merge(first1i,temp,1);else break;fi='1

19、9;/* 求各產(chǎn)生式右部的FIRST*/void FIRST(int i,char *p)int length;int j,k,m;char temp20;length=strlen(p);if(length=1) /*如果右部為單個符號*/if(p0='') if(i>=0) firsti0='' firsti1='0'elseTEMP0=''TEMP1='0'elsefor(j=0;j+)if(vj=p0)break;if(i>=0) memcpy(firsti,first1j,strlen(fir

20、st1j); firstistrlen(first1j)='0'elsememcpy(TEMP,first1j,strlen(first1j);TEMPstrlen(first1j)='0' else /*如果右部為符號串*/for(j=0;j+)if(vj=p0)break;if(i>=0) merge(firsti,first1j,2);elsemerge(TEMP,first1j,2);for(k=0;k<=length-1;k+)empt0='0'if(_emp(pk)=1&&k<length-1) fo

21、r(m=0;m+)if(vm=rightik+1)break; if(i>=0) merge(firsti,first1m,2);elsemerge(TEMP,first1m,2); else if(_emp(pk)=1&&k=length-1) temp0=''temp1='0'if(i>=0) merge(firsti,temp,1); elsemerge(TEMP,temp,1);else if(_emp(pk)=0)break;/* 求各產(chǎn)生式左部的FOLLOW*/void FOLLOW(int i)int j,k,m,n,r

22、esult=1;char c,temp20;c=non_teri; /*c為待求的非終結(jié)符*/temp0=c;temp1='0'merge(fo,temp,1);if(c=start) /*若為開始符號*/temp0='#'temp1='0'merge(followi,temp,1); for(j=0;j<=count-1;j+)if(in(c,rightj)=1) /*找一個右部含有c的產(chǎn)生式*/for(k=0;k+)if(rightjk=c)break; /*k為c在該產(chǎn)生式右部的序號*/ for(m=0;m+)if(vm=leftj)

23、break; /*m為產(chǎn)生式左部非終結(jié)符在所有符號中的序號*/if(k=strlen(rightj)-1) /*如果c在產(chǎn)生式右部的最后*/if(in(vm,fo)=1)merge(followi,followm,1);continue; if(Fm='0')FOLLOW(m);Fm='1'merge(followi,followm,1);else /*如果c不在產(chǎn)生式右部的最后*/for(n=k+1;n<=strlen(rightj)-1;n+)empt0='0'result*=_emp(rightjn);if(result=1) /*如

24、果右部c后面的符號串能推出*/ if(in(vm,fo)=1) /*避免循環(huán)遞歸*/merge(followi,followm,1);continue;if(Fm='0') FOLLOW(m); Fm='1' merge(followi,followm,1);for(n=k+1;n<=strlen(rightj)-1;n+) tempn-k-1=rightjn; tempstrlen(rightj)-k-1='0'FIRST(-1,temp);merge(followi,TEMP,2);Fi='1'/* 判斷讀入文法是否為一

25、個LL(1)文法*/int ll1() int i,j,length,result=1;char temp50;for(j=0;j<=49;j+) /*初始化*/firstj0='0' followj0='0'first1j0='0'selectj0='0'TEMPj='0'tempj='0'fj='0'Fj='0'for(j=0;j<=strlen(v)-1;j+) first2(j); /*求單個符號的FIRST集合*/printf("nfi

26、rst1:");for(j=0;j<=strlen(v)-1;j+)printf("%c:%s ",vj,first1j); printf("nempty:%s",empty);printf("n:n_emp:");for(j=0;j<=strlen(v)-1;j+) printf("%d ",_emp(vj);for(i=0;i<=count-1;i+) FIRST(i,righti); /*求FIRST*/printf("n");for(j=0;j<=str

27、len(non_ter)-1;j+) /*求FOLLOW*/if(foj=0)fo0='0' FOLLOW(j); printf("nfirst:");for(i=0;i<=count-1;i+) printf("%s ",firsti);printf("nfollow:"); for(i=0;i<=strlen(non_ter)-1;i+) printf("%s ",followi);for(i=0;i<=count-1;i+) /*求每一產(chǎn)生式的SELECT集合*/ memcp

28、y(selecti,firsti,strlen(firsti); selectistrlen(firsti)='0'for(j=0;j<=strlen(righti)-1;j+)result*=_emp(rightij);if(strlen(righti)=1&&righti0='')result=1;if(result=1)for(j=0;j+)if(vj=lefti)break;merge(selecti,followj,1);printf("nselect:");for(i=0;i<=count-1;i+)

29、printf("%s ",selecti);memcpy(temp,select0,strlen(select0);tempstrlen(select0)='0'for(i=1;i<=count-1;i+) /*判斷輸入文法是否為LL(1)文法*/ length=strlen(temp);if(lefti=lefti-1)merge(temp,selecti,1);if(strlen(temp)<length+strlen(selecti)return(0);elsetemp0='0' memcpy(temp,selecti,st

30、rlen(selecti);tempstrlen(selecti)='0'return(1);/* 構(gòu)造分析表M*/void MM() int i,j,k,m;for(i=0;i<=19;i+)for(j=0;j<=19;j+)Mij=-1; i=strlen(termin); termini='#' /*將#加入終結(jié)符數(shù)組*/ termini+1='0'for(i=0;i<=count-1;i+) for(m=0;m+)if(non_term=lefti)break; /*m為產(chǎn)生式左部非終結(jié)符的序號*/for(j=0;j&l

31、t;=strlen(selecti)-1;j+)if(in(selectij,termin)=1)for(k=0;k+)if(termink=selectij)break; /*k為產(chǎn)生式右部終結(jié)符的序號*/ Mmk=i;/* 總控算法*/void syntax()int i,j,k,m,n,p,q; char ch;char S50,str50; printf("請輸入該文法的句型：");scanf("%s",str);getchar();i=strlen(str);stri='#'stri+1='0'S0='#

32、'S1=start;S2='0'j=0;ch=strj; while(1)if(in(Sstrlen(S)-1,termin)=1) if(Sstrlen(S)-1!=ch)printf("n該符號串不是文法的句型！"); return;else if(Sstrlen(S)-1='#') printf("n該符號串是文法的句型."); return;else Sstrlen(S)-1='0'j+;ch=strj;else for(i=0;i+)if(non_teri=Sstrlen(S)-1)bre

33、ak;for(k=0;k+)if(termink=ch)break;if(k=strlen(termin)printf("n詞法錯誤！");return;if(Mik=-1)printf("n語法錯誤！");return;else m=Mik; if(rightm0='')Sstrlen(S)-1='0'else p=strlen(S)-1; q=p; for(n=strlen(rightm)-1;n>=0;n-) Sp+=rightmn; Sq+strlen(rightm)='0' printf(&

34、quot;nS:%s str:",S);for(p=j;p<=strlen(str)-1;p+)printf("%c",strp);printf(" ");/* 一個用戶調(diào)用函數(shù)*/void menu()syntax();printf("n是否繼續(xù)？(y or n):");scanf("%c",&choose);getchar();while(choose='y') menu();/* 主函數(shù)*/void main()int i,j;start=grammer(termin,

35、non_ter,left,right); /*讀入一個文法*/ printf("count=%d",count);printf("nstart:%c",start);strcpy(v,non_ter);strcat(v,termin);printf("nv:%s",v);printf("nnon_ter:%s",non_ter); printf("ntermin:%s",termin);printf("nright:");for(i=0;i<=count-1;i+) p

36、rintf("%s ",righti); printf("nleft:");for(i=0;i<=count-1;i+)printf("%c ",lefti); if(validity=1) validity=judge();printf("nvalidity=%d",validity);if(validity=1) printf("n文法有效");ll=ll1();printf("nll=%d",ll);if(ll=0)printf("n該文法不是一個LL1

37、文法！");else MM(); printf("n"); for(i=0;i<=19;i+) for(j=0;j<=19;j+) if(Mij>=0) printf("M%d%d=%d ",i,j,Mij); printf("n"); menu();5.執(zhí)行結(jié)果（1）輸入一個文法（2）輸入一個符號串（3）再次輸入一個符號串，然后退出程序 二詞法分析一、 問題描述識別簡單語言的單詞符號識別簡單語言的基本字、標識符、無符號整數(shù)、運算符和界符。1.題目選擇計算機高級程序語言之一 C語言，運用恰當?shù)脑~法分析技術線

38、路，設計和實現(xiàn)其對應的詞法分析器。2. 要求 1). 給出一簡單語言單詞符號的種別編碼。單詞符號 種別編碼begin 1if 2then 3while 4do 5end 6l ( l | d ) * 10 dd * 11. . 2). 詞法分析程序的功能 輸入是源程序字符串,以# 結(jié)束。輸出是單詞符號的二元組。分析器輸出結(jié)果存入到磁盤文件中，具有出錯處理功能。3). 建議和提示：技術線路選擇如下兩種之一：正則式NFADFAmin DFA程序設計或 正則文法NFADFAmin DFA程序設計。二、 系統(tǒng)分析詞法分析器對應的正則文法表達如下：S 標示符或關鍵字|數(shù)字字符|運算符標示符或關鍵字 characterAA character|number| (標示符或關鍵字要以字母開頭)數(shù)字字符 number| (數(shù)字字符只能由數(shù)字組成)character a|b|c|y|z|A|B|C|Y|Znumber 0|1|2|3|4|5|6|7|8|9運算符 <>|<|<=|>|>=|:|:=|+