开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 多国语言处理 > 词法分析 > 查看源码
syntax.cpp
资源名称：ll(1)词法分析.rar　[点击查看]
上传用户：shyefeng
上传日期：2013-04-07
资源大小：80k
文件大小：17k
源码类别：

词法分析

开发平台：

Visual C++

syntax.cpp：源码内容
  1. /*******************************************
  2.  语法分析程序
  3.  作者：龚勋         刘栋         罗晓波
  4.  学号：200131500342 200131500350 200131500351
  5.  计科系 13班
  6. ********************************************/
  7. #include<stdlib.h>
  8. #include<stdio.h>
  9. #include<string.h>
  10. /*******************************************/
  11. int count=0;              /*分解的产生式的个数*/
  12. int number;               /*所有终结符和非终结符的总数*/
  13. char start;               /*开始符号*/
  14. char termin[50];          /*终结符号*/
  15. char non_ter[50];         /*非终结符号*/
  16. char v[50];               /*所有符号*/
  17. char left[50];            /*左部*/
  18. char right[50][50];       /*右部*/
  19. char first[50][50],follow[50][50];       /*各产生式右部的FIRST和左部的FOLLOW集合*/
  20. char first1[50][50];      /*所有单个符号的FIRST集合*/
  21. char select[50][50];      /*各单个产生式的SELECT集合*/
  22. char f[50],F[50];         /*记录各符号的FIRST和FOLLOW是否已求过*/
  23. char empty[20];           /*记录可直接推出^的符号*/
  24. char TEMP[50];            /*求FOLLOW时存放某一符号串的FIRST集合*/
  25. int validity=1;           /*表示输入文法是否有效*/
  26. int ll=1;                 /*表示输入文法是否为LL(1)文法*/
  27. int M[20][20];            /*分析表*/
  28. char choose;              /*用户输入时使用*/
  29. char empt[20];            /*求_emp()时使用*/
  30. char fo[20];              /*求FOLLOW集合时使用*/
  33. /*******************************************
  34.  判断一个字符是否在指定字符串中
  35. ********************************************/
  36. int in(char c,char *p)
  37. {
  38. int i;
  39. if(strlen(p)==0)
  40. return(0);
  41. for(i=0;;i++)
  42. {
  43. if(p[i]==c)
  44. return(1);       /*若在，返回1*/
  45. if(i==strlen(p))
  46.     return(0);       /*若不在，返回0*/
  47. }
  48. }
  50. /*******************************************
  51.  得到一个不是非终结符的符号
  52. ********************************************/
  53. char c()
  54. {
  55. char c='A';
  56.     while(in(c,non_ter)==1)
  57. c++;
  58. return(c);
  59. }
  61. /*******************************************
  62.  分解含有左递归的产生式
  63. ********************************************/
  64. void recur(char *point)
  65. {                     /*完整的产生式在point[]中*/
  66.     int j,m=0,n=3,k;
  67. char temp[20],ch;
  68. ch=c();           /*得到一个非终结符*/
  69. k=strlen(non_ter);
  70. non_ter[k]=ch;
  71. non_ter[k+1]='';
  72. for(j=0;j<=strlen(point)-1;j++)
  73. {
  74. if(point[n]==point[0])
  75. {                          /*如果‘|’后的首符号和左部相同*/
  76. for(j=n+1;j<=strlen(point)-1;j++)
  77. {
  78.     while(point[j]!='|'&&point[j]!='')
  79.     temp[m++]=point[j++];
  80. left[count]=ch;
  81. memcpy(right[count],temp,m);
  82. right[count][m]=ch;
  83. right[count][m+1]='';
  84. m=0;
  85. count++;
  86. if(point[j]=='|')
  87. {
  88. n=j+1;
  89. break;
  90. }
  91. }
  92. }
  93. else
  94. {                          /*如果‘|’后的首符号和左部不同*/
  95. left[count]=ch;
  96. right[count][0]='^';
  97. right[count][1]='';
  98. count++;
  99. for(j=n;j<=strlen(point)-1;j++)
  100. {
  101.     if(point[j]!='|')
  102.         temp[m++]=point[j];
  103.     else
  104. {
  105.     left[count]=point[0];
  106.     memcpy(right[count],temp,m);
  107.     right[count][m]=ch;
  108.     right[count][m+1]='';
  109. printf(" count=%d ",count);
  110. m=0;
  111.     count++;
  112. }
  113. }
  114.             left[count]=point[0];
  115.     memcpy(right[count],temp,m);
  116.     right[count][m]=ch;
  117.        right[count][m+1]='';
  118. count++;
  119.     m=0;
  120. }
  121. }
  122. }
  124. /*******************************************
  125.  分解不含有左递归的产生式
  126. ********************************************/
  127. void non_re(char *point)
  128. {
  129.     int m=0,j;
  130. char temp[20];
  131. for(j=3;j<=strlen(point)-1;j++)
  132. {
  133.     if(point[j]!='|')
  134.     temp[m++]=point[j];
  135. else
  136. {
  137.     left[count]=point[0];
  138.     memcpy(right[count],temp,m);
  139.     right[count][m]='';
  140. m=0;
  141. count++;
  142. }
  143. }
  144.     left[count]=point[0];
  145.     memcpy(right[count],temp,m);
  146.     right[count][m]='';
  147.     count++;
  148. m=0;
  149. }
  152. /*******************************************
  153.  读入一个文法
  154. ********************************************/
  155. char grammer(char *t,char *n,char *left,char right[50][50])
  156. {
  157. char vn[50],vt[50];
  158. char s;
  159. char p[50][50];
  160. int i,j,k;
  161. printf("请输入文法的非终结符号串：");
  162.     scanf("%s",vn);
  163. getchar();
  164.     i=strlen(vn);
  165.     memcpy(n,vn,i);
  166. n[i]='';
  167. printf("请输入文法的终结符号串：");
  168.     scanf("%s",vt);
  169. getchar();
  170.     i=strlen(vt);
  171.     memcpy(t,vt,i);
  172. t[i]='';
  173.     printf("请输入文法的开始符号：");
  174. scanf("%c",&s);
  175. getchar();
  176. printf("请输入文法产生式的条数：");
  177.     scanf("%d",&i);
  178. getchar();
  179.     for(j=1;j<=i;j++)
  180. {
  181. printf("请输入文法的第%d条（共%d条）产生式：",j,i);
  182. scanf("%s",p[j-1]);
  183.         getchar();
  184. }
  185.     for(j=0;j<=i-1;j++)
  186. if(p[j][1]!='-'||p[j][2]!='>')
  187. { printf("ninput error!");
  188.     validity=0;
  189. return('');
  190.         }            /*检测输入错误*/
  191.    for(k=0;k<=i-1;k++)
  192.    {                        /*分解输入的各产生式*/
  193.         if(p[k][3]==p[k][0])
  194.             recur(p[k]);
  195. else
  196.     non_re(p[k]);
  197. }
  198. return(s);
  199. }
  203. /*******************************************
  204.  将单个符号或符号串并入另一符号串
  205. ********************************************/
  206. void merge(char *d,char *s,int type)
  207. {                 /*d是目标符号串，s是源串，type＝1，源串中的‘ ^ ’一并并入目串；
  208.                type＝2，源串中的‘ ^ ’不并入目串*/
  209.     int i,j;
  210. for(i=0;i<=strlen(s)-1;i++)
  211. {
  212.         if(type==2&&s[i]=='^')
  213. ;
  214. else
  215. {
  216. for(j=0;;j++)
  217. {
  218.     if(j<strlen(d)&&s[i]==d[j])
  219.    break;
  220.                 if(j==strlen(d))
  221. {
  222.     d[j]=s[i];
  223.     d[j+1]='';
  224.     break;
  225. }
  226. }
  227. }
  228. }
  229. }
  233. /*******************************************
  234.  求所有能直接推出^的符号
  235. ********************************************/
  236. void emp(char c)
  237. {                   /*即求所有由‘ ^ ’推出的符号*/
  238. char temp[10];
  239. int i;
  240. for(i=0;i<=count-1;i++)
  241. {
  242. if(right[i][0]==c&&strlen(right[i])==1)
  243. {
  244. temp[0]=left[i];
  245. temp[1]='';
  246. merge(empty,temp,1);
  247. emp(left[i]);
  248. }
  249. }
  250. }
  252. /*******************************************
  253.  求某一符号能否推出‘ ^ ’
  254. ********************************************/
  255. int _emp(char c)
  256. {                  /*若能推出，返回1；否则，返回0*/
  257. int i,j,k,result=1,mark=0;
  258. char temp[20];
  259. temp[0]=c;
  260. temp[1]='';
  261. merge(empt,temp,1);
  262. if(in(c,empty)==1)
  263. return(1);
  264. for(i=0;;i++)
  265. {
  266. if(i==count)
  267.             return(0);
  268. if(left[i]==c)         /*找一个左部为c的产生式*/
  269. {
  270.             j=strlen(right[i]);    /*j为右部的长度*/
  271. if(j==1&&in(right[i][0],empty)==1)
  272.     return(1);
  273. else if(j==1&&in(right[i][0],termin)==1)
  274. return(0);
  275. else 
  276. {
  277.                 for(k=0;k<=j-1;k++)
  278.                     if(in(right[i][k],empt)==1)
  279. mark=1;
  280. if(mark==1)
  281. continue;
  282. else
  283.                 {
  284. for(k=0;k<=j-1;k++)
  285. {
  286. result*=_emp(right[i][k]);
  287. temp[0]=right[i][k];
  288. temp[1]='';
  289. merge(empt,temp,1);
  290. }
  291. }
  292. }
  293.     if(result==0&&i<count)
  294.     continue;
  295.     else if(result==1&&i<count)
  296.     return(1);
  297. }
  298. }
  299. }
  302. /*******************************************
  303.  判断读入的文法是否正确
  304. ********************************************/
  305. int judge()
  306. {
  307.     int i,j;
  308. for(i=0;i<=count-1;i++)
  309. {
  310. if(in(left[i],non_ter)==0)
  311. {                    /*若左部不在非终结符中，报错*/
  312. printf("nerror1!");
  313. validity=0;
  314. return(0);
  315. }
  316. for(j=0;j<=strlen(right[i])-1;j++)
  317. {
  318. if(in(right[i][j],non_ter)==0&&in(right[i][j],termin)==0&&right[i][j]!='^')
  319. {               /*若右部某一符号不在非终结符、终结符中且不为‘ ^ ’，报错*/
  320. printf("nerror2!");
  321. validity=0;
  322. return(0);
  323. }
  324. }
  325. }
  326. return(1);
  327. }
  329. /*******************************************
  330.  求单个符号的FIRST
  331. ********************************************/
  332. void first2(int i)
  333. {                     /*i为符号在所有输入符号中的序号*/
  334.     char c,temp[20];
  335. int j,k,m;
  336. c=v[i];
  337. char ch='^';
  338. emp(ch);
  339. if(in(c,termin)==1)       /*若为终结符*/
  340.     {
  341.         first1[i][0]=c;
  342.     first1[i][1]='';
  343. }   
  344. else if(in(c,non_ter)==1)       /*若为非终结符*/
  345. {
  346. for(j=0;j<=count-1;j++)
  347. {
  348.             if(left[j]==c)
  349. {
  350.                 if(in(right[j][0],termin)==1||right[j][0]=='^')
  351. {
  352.                     temp[0]=right[j][0];
  353.     temp[1]='';
  354. merge(first1[i],temp,1);
  355. }
  356. else if(in(right[j][0],non_ter)==1)
  357. {
  358. if(right[j][0]==c)
  359. continue;
  360. for(k=0;;k++)
  361. if(v[k]==right[j][0])
  362. break;
  363. if(f[k]=='0')
  364. {   
  365. first2(k);
  366.     f[k]='1';
  367. }
  368. merge(first1[i],first1[k],2);
  369.                     for(k=0;k<=strlen(right[j])-1;k++)
  370. {
  371. empt[0]='';
  372. if(_emp(right[j][k])==1&&k<strlen(right[j])-1)
  373. {
  374.                             for(m=0;;m++)
  375. if(v[m]==right[j][k+1])
  376. break;
  377. if(f[m]=='0')
  378. {
  379. first2(m);
  380. f[m]='1';
  381. }
  382. merge(first1[i],first1[m],2);
  383. }
  384. else if(_emp(right[j][k])==1&&k==strlen(right[j])-1)
  385. {
  386. temp[0]='^';
  387. temp[1]='';
  388. merge(first1[i],temp,1);
  389. }
  390. else 
  391. break;
  392. }
  393. }
  394. }
  395. }
  396. }
  397. f[i]='1';
  398. }
  400. /*******************************************
  401.  求各产生式右部的FIRST
  402. ********************************************/
  403. void FIRST(int i,char *p)
  404. {
  405. int length;
  406. int j,k,m;
  407. char temp[20];
  408. length=strlen(p);
  409. if(length==1)                  /*如果右部为单个符号*/
  410. {
  411. if(p[0]=='^')
  412.         {   
  413. if(i>=0)
  414.             {
  415.     first[i][0]='^';
  416.     first[i][1]='';
  417. }
  418. else
  419. {
  420. TEMP[0]='^';
  421. TEMP[1]='';
  422. }
  423. }
  424. else
  425. {
  426. for(j=0;;j++)
  427. if(v[j]==p[0])
  428. break;
  429. if(i>=0)
  430. {
  431.     memcpy(first[i],first1[j],strlen(first1[j]));
  432.     first[i][strlen(first1[j])]='';
  433. }
  434. else
  435. {
  436. memcpy(TEMP,first1[j],strlen(first1[j]));
  437. TEMP[strlen(first1[j])]='';
  438. }
  439.         }
  440. }
  441. else                      /*如果右部为符号串*/
  442. {
  443. for(j=0;;j++)
  444. if(v[j]==p[0])
  445. break;
  446. if(i>=0)
  447.             merge(first[i],first1[j],2);
  448. else
  449. merge(TEMP,first1[j],2);
  450. for(k=0;k<=length-1;k++)
  451. {
  452. empt[0]='';
  453. if(_emp(p[k])==1&&k<length-1)
  454. { 
  455.                 for(m=0;;m++)
  456. if(v[m]==right[i][k+1])
  457. break;
  458.                 if(i>=0)
  459.     merge(first[i],first1[m],2);
  460. else
  461. merge(TEMP,first1[m],2);
  462. }
  463.             else if(_emp(p[k])==1&&k==length-1)
  464. {
  465.                 
  466. temp[0]='^';
  467. temp[1]='';
  468. if(i>=0)
  469.     merge(first[i],temp,1);   
  470. else
  471. merge(TEMP,temp,1);
  472. }
  473. else if(_emp(p[k])==0)
  474. break;
  475. }
  476. }
  477. }
  479. /*******************************************
  480.  求各产生式左部的FOLLOW
  481. ********************************************/
  482. void FOLLOW(int i)
  483. {
  484. int j,k,m,n,result=1;
  485. char c,temp[20];
  486. c=non_ter[i];             /*c为待求的非终结符*/
  487. temp[0]=c;
  488. temp[1]='';
  489. merge(fo,temp,1);
  490. if(c==start)
  491. {                         /*若为开始符号*/
  492. temp[0]='#';
  493. temp[1]='';
  494. merge(follow[i],temp,1);
  495. }
  496.     for(j=0;j<=count-1;j++)
  497. {
  498. if(in(c,right[j])==1)     /*找一个右部含有c的产生式*/
  499. {
  500. for(k=0;;k++)
  501. if(right[j][k]==c)
  502. break;       /*k为c在该产生式右部的序号*/
  503.             for(m=0;;m++)
  504. if(v[m]==left[j])
  505. break;        /*m为产生式左部非终结符在所有符号中的序号*/
  506. if(k==strlen(right[j])-1)
  507. {              /*如果c在产生式右部的最后*/
  508. if(in(v[m],fo)==1)
  509. {
  510. merge(follow[i],follow[m],1);
  511. continue;
  512.                 }
  513. if(F[m]=='0')
  514. {
  515. FOLLOW(m);
  516. F[m]='1';
  517. }
  518. merge(follow[i],follow[m],1);
  519. }
  520. else 
  521. {              /*如果c不在产生式右部的最后*/
  522. for(n=k+1;n<=strlen(right[j])-1;n++)
  523. {
  524. empt[0]='';
  525. result*=_emp(right[j][n]);
  526. }
  527. if(result==1)
  528. {         /*如果右部c后面的符号串能推出^*/
  529.                     if(in(v[m],fo)==1)
  530. {           /*避免循环递归*/
  531. merge(follow[i],follow[m],1);
  532. continue;
  533. }
  534. if(F[m]=='0')
  535. {
  536.     FOLLOW(m);
  537.     F[m]='1';
  538. }
  539.     merge(follow[i],follow[m],1);
  540. }
  541. for(n=k+1;n<=strlen(right[j])-1;n++)
  542.                     temp[n-k-1]=right[j][n];       
  543. temp[strlen(right[j])-k-1]='';
  544. FIRST(-1,temp);
  545. merge(follow[i],TEMP,2);
  546. }
  547. }
  548. }
  549. F[i]='1';
  550. }
  552. /*******************************************
  553.  判断读入文法是否为一个LL(1)文法
  554. ********************************************/
  555. int ll1()
  556. {
  557.     int i,j,length,result=1;
  558. char temp[50];
  559. for(j=0;j<=49;j++)
  560. {                            /*初始化*/
  561. first[j][0]='';
  562.     follow[j][0]='';
  563. first1[j][0]='';
  564. select[j][0]='';
  565. TEMP[j]='';
  566. temp[j]='';
  567. f[j]='0';
  568. F[j]='0';
  569. }
  570. for(j=0;j<=strlen(v)-1;j++)
  571.     first2(j);                /*求单个符号的FIRST集合*/
  572. printf("nfirst1:");
  573. for(j=0;j<=strlen(v)-1;j++)
  574. printf("%c:%s  ",v[j],first1[j]);
  575.     printf("nempty:%s",empty);
  576. printf("n_emp:");
  577. for(j=0;j<=strlen(v)-1;j++)
  578.         printf("%d  ",_emp(v[j]));
  579. for(i=0;i<=count-1;i++)
  580.     FIRST(i,right[i]);          /*求FIRST*/
  581. for(j=0;j<=strlen(non_ter)-1;j++)
  582.     {                               /*求FOLLOW*/
  583. if(fo[j]==0)
  584. {
  585. fo[0]='';
  586.     FOLLOW(j);
  587. }
  588.     }
  589. printf("nfirst:");
  590. for(i=0;i<=count-1;i++)
  591.     printf("%s ",first[i]);
  592. printf("nfollow:");
  593.     for(i=0;i<=strlen(non_ter)-1;i++)
  594.     printf("%s ",follow[i]);
  595. for(i=0;i<=count-1;i++)
  596. {                          /*求每一产生式的SELECT集合*/
  597.         memcpy(select[i],first[i],strlen(first[i]));
  598.         select[i][strlen(first[i])]='';
  599. for(j=0;j<=strlen(right[i])-1;j++)
  600. result*=_emp(right[i][j]);
  601. if(strlen(right[i])==1&&right[i][0]=='^')
  602. result=1;
  603. if(result==1)
  604. {
  605. for(j=0;;j++)
  606. if(v[j]==left[i])
  607. break;
  608. merge(select[i],follow[j],1);
  609. }
  610. }
  611. printf("nselect:");
  612. for(i=0;i<=count-1;i++)
  613.     printf("%s ",select[i]);
  614. memcpy(temp,select[0],strlen(select[0]));
  615. temp[strlen(select[0])]='';
  616. for(i=1;i<=count-1;i++)
  617. {                 /*判断输入文法是否为LL(1)文法*/
  618.         length=strlen(temp);
  619. if(left[i]==left[i-1])
  620. {
  621. merge(temp,select[i],1);
  622. if(strlen(temp)<length+strlen(select[i]))
  623. return(0);
  624. }
  625. else
  626. {
  627. temp[0]='';
  628.     memcpy(temp,select[i],strlen(select[i]));
  629. temp[strlen(select[i])]='';
  630. }
  631. }
  632. return(1);
  633. }
  635. /*******************************************
  636.  构造分析表M
  637. ********************************************/
  638. void MM()
  639. {
  640.     int i,j,k,m;
  641. for(i=0;i<=19;i++)
  642. for(j=0;j<=19;j++)
  643. M[i][j]=-1;
  644.     i=strlen(termin);
  645.     termin[i]='#';     /*将#加入终结符数组*/
  646.     termin[i+1]='';
  647. for(i=0;i<=count-1;i++)
  648. {
  649.         for(m=0;;m++)
  650. if(non_ter[m]==left[i])
  651. break;      /*m为产生式左部非终结符的序号*/
  652. for(j=0;j<=strlen(select[i])-1;j++)
  653. {
  654. if(in(select[i][j],termin)==1)
  655. {
  656. for(k=0;;k++)
  657. if(termin[k]==select[i][j])
  658. break;        /*k为产生式右部终结符的序号*/
  659.                 M[m][k]=i;
  660. }
  661. }
  662. }
  663. }
  665. /*******************************************
  666.  总控算法
  667. ********************************************/
  668. void syntax()
  669. {
  670. int i,j,k,m,n,p,q;
  671.     char ch;
  672. char S[50],str[50];
  673.     printf("请输入该文法的句型：");
  674. scanf("%s",str);
  675. getchar();
  676. i=strlen(str);
  677. str[i]='#';
  678. str[i+1]='';
  679. S[0]='#';
  680. S[1]=start;
  681. S[2]='';
  682. j=0;
  683. ch=str[j];
  684.     while(1)
  685. {
  686. if(in(S[strlen(S)-1],termin)==1)
  687. {
  688.             if(S[strlen(S)-1]!=ch)
  689. {
  690. printf("该符号串不是文法的句型！");
  691.                 return;
  692. }
  693. else if(S[strlen(S)-1]=='#')
  694. {
  695.                 printf("该符号串是文法的句型.");
  696.                 return;
  697. }
  698. else
  699. {
  700.                 S[strlen(S)-1]='';
  701. j++;
  702. ch=str[j];
  703. }
  704. }
  705. else 
  706. {   
  707.             for(i=0;;i++)
  708. if(non_ter[i]==S[strlen(S)-1])
  709. break;
  710. for(k=0;;k++)
  711. {
  712. if(termin[k]==ch)
  713. break;
  714. if(k==strlen(termin))
  715. {
  716. printf("词法错误！");
  717. return;
  718. }
  719. }
  720. if(M[i][k]==-1)
  721. {
  722. printf("语法错误！");
  723. return;
  724. }
  725. else
  726. {
  727.                 m=M[i][k];
  728.                 if(right[m][0]=='^')
  729. S[strlen(S)-1]='';
  730. else
  731. {
  732.     p=strlen(S)-1;
  733.     q=p;
  734.     for(n=strlen(right[m])-1;n>=0;n--)
  735.                         S[p++]=right[m][n];
  736.     S[q+strlen(right[m])]='';
  737. }
  738. }
  739. }
  740.     printf("S:%s  str:",S);
  741. for(p=j;p<=strlen(str)-1;p++)
  742. printf("%c",str[p]);
  743. printf(" n");
  744. }
  745. }
  747. /*******************************************
  748.  一个用户调用函数
  749. ********************************************/
  750. void menu()
  751. {
  752. syntax();
  753. printf("n是否继续？(y or n):");
  754. scanf("%c",&choose);
  755. getchar();
  756. while(choose=='y')
  757. { 
  758. menu();
  759. }
  760. }
  762. /*******************************************
  763.  主函数
  764. ********************************************/
  765. void main()
  766. {
  767. int i,j;
  768. start=grammer(termin,non_ter,left,right);               /*读入一个文法*/
  769.     printf("count=%d",count);
  770. printf("nstart:%c",start);
  771. strcpy(v,non_ter);
  772. strcat(v,termin);
  773. printf("nv:%s",v);
  774. printf("nnon_ter:%s",non_ter);
  775.     printf("ntermin:%s",termin);
  776. printf("nright:");
  777. for(i=0;i<=count-1;i++)
  778.     printf("%s   ",right[i]); 
  779.     printf("nleft:");
  780. for(i=0;i<=count-1;i++)
  781. printf("%c   ",left[i]);            
  782.     if(validity==1)
  783.     validity=judge();
  784.     printf("nvalidity=%d",validity);
  785. if(validity==1)
  786. {
  787.         ll=ll1();
  788. printf("nll=%d",ll);
  789. if(ll==0)
  790. printf("n该文法不是一个LL1文法！");
  791. else
  792. {
  793.     MM();
  794.             printf("n");
  795.     for(i=0;i<=19;i++)
  796.         for(j=0;j<=19;j++)
  797.         if(M[i][j]>=0)
  798.         printf("M[%d][%d]=%d ",i,j,M[i][j]);
  799.     menu();
  800. }
  801. }
  802. }