《編譯原理(實驗部分)》實驗9_自底向上算符優(yōu)先分析法

1、編譯原理（實驗部分）實驗9_自底向上算符優(yōu)先分析法一、實驗目的加深對語法分析器工作過程的理解；加強對算符優(yōu)先分析法實現(xiàn)語法分析程序的掌握；能夠采用一種編程語言實現(xiàn)簡單的語法分析程序；能夠使用自己編寫的分析程序對簡單的程序段進行語法翻譯。二、實驗設備1、PC 兼容機一臺；操作系統(tǒng)為WindowsWindowsXP。2、Visual C+ 6.0 或以上版本， Windows 2000 或以上版本，匯編工具（在Software 子目錄下）。三、實驗原理先在算符棧置“”，然后開始順序掃描表達式，若讀來的單詞符號是操作數(shù)，這直接進操作數(shù)棧，然后繼續(xù)讀下一個單詞符號。分析過程從頭開始，并重復進行；若讀來

2、的是運算符2 則將當前處于運算符棧頂?shù)倪\算符1的入棧優(yōu)先數(shù)f與2的比較優(yōu)先函數(shù)g進行比較。四、實驗步驟1、定義目標語言的語法規(guī)則；2、求解預測分析方法需要的符號集和分析表；3、依次讀入實驗一的分析結果，根據(jù)預測分析的方法進行語法分析，直到源程序結束；4、對遇到的語法錯誤做出錯誤處理。源程序：#include "stdio.h"#include "stdlib.h"#include "iostream.h"char data2020; /算符優(yōu)先關系char s100; /模擬符號棧s char lable20; /文法終極符集char

3、 input100; /文法輸入符號串char string2010; /用于輸入串的分析int k; char a; int j; char q; int r; /文法規(guī)則個數(shù)int r1; int m,n,N; /轉化后文法規(guī)則個數(shù)char st1030; /用來存儲文法規(guī)則char first1010; /文法非終結符FIRSTVT集char last1010; /文法非終結符LASTVT集int fflag10=0; /標志第i個非終結符的FIRSTVT集是否已求出int lflag10=0; /標志第i個非終結符的LASTVT集是否已求出int deal(); /對輸入串的分析int

4、 zhongjie(char c); /判斷字符c是否是終極符int xiabiao(char c); /求字符c在算符優(yōu)先關系表中的下標void out(int j,int k,char *s); /打印s棧void firstvt(char c); /求非終結符c的FIRSTVT集void lastvt(char c); /求非終結符c的LASTVT集void table(); /創(chuàng)建文法優(yōu)先關系表void main()int i,j,k=0; printf("請輸入文法規(guī)則數(shù)：");scanf("%d",&r);printf("請

5、輸入文法規(guī)則：n");for(i=0;i<r;i+) scanf("%s",sti);/存儲文法規(guī)則，初始化FIRSTVT集和LASTVT集*/ firsti0=0; /*firsti0和lasti0分別表示sti0非終極符的FIRSTVT集和LASTVT集中元素的個數(shù)*/lasti0=0;for(i=0;i<r;i+) /判斷文法是否合法for(j=0;stij!='0'j+)if(sti0<'A'|sti0>'Z')printf("不是算符文法!n"); exit(-1

6、);if(stij>='A'&&stij<='Z') if(stij+1>='A'&&stij+1<='Z')printf("不是算符文法!n"); exit(-1); for(i=0;i<r;i+)for(j=0;stij!='0'j+)if(stij<'A'|stij>'Z')&&stij!='-'&&stij!='>'

7、;&&stij!='|')lablek+=stij;lablek='#'lablek+1='0' table();printf("每個非終結符的FIRSTVT集為：n"); /輸出每個非終結符的FIRSTVT集for(i=0;i<r;i+)printf("%c: ",sti0);for(j=0;j<firsti0;j+)printf("%c ",firstij+1);printf("n");printf("每個非終結符的LASTV

8、T集為：n"); /輸出每個非終結符的LASTVT集for(i=0;i<r;i+)printf("%c: ",sti0);for(j=0;j<lasti0;j+)printf("%c ",lastij+1);printf("n");printf("算符優(yōu)先分析表如下:n");for(i=0;lablei!='0'i+) printf("t%c",lablei);printf("n"); for(i=0;i<k+1;i+)printf

9、("%ct",lablei);for(j=0;j<k+1;j+)printf("%ct",dataij);printf("n");printf("請輸入文法輸入符號串以#結束:");scanf("%s",input); deal();void table()char text2010;int i,j,k,t,l,x=0,y=0;int m,n;x=0;for(i=0;i<r;i+)firstvt(sti0);lastvt(sti0);for(i=0;i<r;i+)textxy=

10、sti0;y+;for(j=1;stij!='0'j+)if(stij='|')textxy='0'x+;y=0;textxy=sti0;y+;textxy+='-'textxy+='>'elsetextxy=stij;y+;textxy='0'x+;y=0;r1=x;printf("轉化后的文法為:n");for(i=0;i<x;i+) /輸出轉化后的文法規(guī)則串printf("%sn",texti);for(i=0;i<x;i+) /*求每

11、個終結符的推導結果(去掉"->"后的轉化文法，用于最后的規(guī)約)*/stringi0=texti0;for(j=3,l=1;textij!='0'j+,l+)stringil=textij;stringil='0'for(i=0;i<x;i+)for(j=1;textij+1!='0'j+)if(zhongjie(textij)&&zhongjie(textij+1)m=xiabiao(textij);n=xiabiao(textij+1);datamn='='if(textij+2!

12、='0'&&zhongjie(textij)&&zhongjie(textij+2)&&!zhongjie(textij+1)m=xiabiao(textij);n=xiabiao(textij+2);datamn='='if(zhongjie(textij)&&!zhongjie(textij+1)for(k=0;k<r;k+)if(stk0=textij+1)break;m=xiabiao(textij);for(t=0;t<firstk0;t+)n=xiabiao(firstkt+

13、1);datamn='<'if(!zhongjie(textij)&&zhongjie(textij+1)for(k=0;k<r;k+)if(stk0=textij)break;n=xiabiao(textij+1);for(t=0;t<lastk0;t+)m=xiabiao(lastkt+1);datamn='>'m=xiabiao('#');for(t=0;t<first00;t+)n=xiabiao(first0t+1);datamn='<'n=xiabiao('#

14、');for(t=0;t<last00;t+)m=xiabiao(last0t+1);datamn='>'datann='='void firstvt(char c) /求FIRSTVT集int i,j,k,m,n;for(i=0;i<r;i+)if(sti0=c)break;if(fflagi=0)n=firsti0+1;m=0;doif(m=2|stim='|')if(zhongjie(stim+1)firstin=stim+1;n+;elseif(zhongjie(stim+2)firstin=stim+2;n+;

15、if(stim+1!=c)firstvt(stim+1);for(j=0;j<r;j+)if(stj0=stim+1)break;for(k=0;k<firstj0;k+)int t;for(t=0;t<n;t+)if(firstit=firstjk+1)break;if(t=n)firstin=firstjk+1;n+;m+;while(stim!='0');firstin='0'firsti0=-n;fflagi=1;void lastvt(char c) /求LASTVT集int i,j,k,m,n;for(i=0;i<r;i+)i

16、f(sti0=c)break;if(lflagi=0)n=lasti0+1;m=0;doif(stim+1='0'|stim+1='|')if(zhongjie(stim)lastin=stim;n+;elseif(zhongjie(stim-1)lastin=stim-1;n+;if(stim!=c)lastvt(stim);for(j=0;j<r;j+)if(stj0=stim)break;for(k=0;k<lastj0;k+)int t;for(t=0;t<n;t+)if(lastit=lastjk+1)break;if(t=n)las

17、tin=lastjk+1;n+;m+;while(stim!='0');lastin='0'lasti0=-n;lflagi=1;int deal()int i,j;int x,y;int z; /輸入串的長度k=1;sk='#' /棧置初值for(i=0;inputi!='0'i+); /計算輸入串的長度z=i-;i=0;while(a=inputi)!='0')if(zhongjie(sk)j=k;elsej=k-1;x=xiabiao(sj);y=xiabiao(a);if(dataxy='>&

18、#39;)out(1,k,s);printf("%c",a);out(i+1,z,input);printf("規(guī)約n");doq=sj;if(zhongjie(sj-1)j=j-1;else j=j-2;x=xiabiao(sj);y=xiabiao(q);while(dataxy!='<');int m,n,N;for(m=j+1;m<=k;m+)for(N=0;N<r1;N+)for(n=1;stringNn!='0'n+)if(!zhongjie(sm)&&!zhongjie(stringNn)if(zhongjie(sm+1)&&zhongjie(stringNn+1)&&sm+1=stringNn+1)sj+1=stringN0; break; elseif(zhongjie(sm)if(sm=stringNn)sj+1=stringN0; break; k=j+1;if(k=2&&a='#')out(1,k,s);printf("%c",a);out(i+1,z,input)