LL1語法分析報(bào)告報(bào)告材料程序?qū)嶒?yàn)報(bào)告材料

1、LL1語法分析報(bào)告報(bào)告材料程序?qū)嶒?yàn)報(bào)告材料LL1語法分析報(bào)告報(bào)告材料程序?qū)嶒?yàn)報(bào)告材料 實(shí)用標(biāo)準(zhǔn)文案LL1實(shí)驗(yàn)報(bào)告08計(jì)算機(jī)3班1.設(shè)計(jì)原理所謂LL（1）分析法，就是指從左到右掃描輸入串（源程序），同時(shí)采用最左推導(dǎo)，且對(duì)每次直接推導(dǎo)只需向前看一個(gè)輸入符號(hào)，便可確定當(dāng)前所應(yīng)當(dāng)選擇的規(guī)則。實(shí)現(xiàn)LL（1）分析的程序又稱為L(zhǎng)L（1）分析程序或LL1（1）分析器。我們知道一個(gè)文法要能進(jìn)行LL（1）分析，那么這個(gè)文法應(yīng)該滿足：無二義性，無左遞歸，無左公因子。當(dāng)文法滿足條件后，再分別構(gòu)造文法每個(gè)非終結(jié)符的FIRST和FOLLOW集合，然后根據(jù)FIRST和FOLLOW集合構(gòu)造LL（1）分析表，最后利用分析表，根

2、據(jù)LL(1)語法分析構(gòu)造一個(gè)分析器。LL（1）的語法分析程序包含了三個(gè)部分，總控程序，預(yù)測(cè)分析表函數(shù)，先進(jìn)先出的語法分析棧，本程序也是采用了同樣的方法進(jìn)行語法分析，該程序是采用了C+語言來編寫，其邏輯結(jié)構(gòu)圖如下：LL（1）預(yù)測(cè)分析程序的總控程序在任何時(shí)候都是按STACK棧頂符號(hào)X和當(dāng)前的輸入符號(hào)a做哪種過程的。對(duì)于任何（X，a），總控程序每次都執(zhí)行下述三種可能的動(dòng)作之一：（）若X = a =#，則宣布分析成功，停止分析過程。（）若X = a #，則把X從STACK棧頂彈出，讓a指向下一個(gè)輸入符號(hào)。（）若X是一個(gè)非終結(jié)符，則查看預(yù)測(cè)分析表M。若MA，a中存放著關(guān)于X的一個(gè)產(chǎn)生式，那么，首先把X彈

3、出STACK棧頂，然后，把產(chǎn)生式的右部符號(hào)串按反序一一彈出STACK棧（若右部符號(hào)為，則不推什么東西進(jìn)STACK棧）。若MA，a中存放著“出 精彩文檔實(shí)用標(biāo)準(zhǔn)文案錯(cuò)標(biāo)志”，則調(diào)用出錯(cuò)診斷程序ERROR。事實(shí)上，LL（1）的分析是根據(jù)文法構(gòu)造的，它反映了相應(yīng)文法所定義的語言的固定特征，因此在LL（1）分析器中，實(shí)際上是以LL（1）分析表代替相應(yīng)方法來進(jìn)行分析的。 2.分析 LL ( 1) 分析表是一個(gè)二維表，它的表列符號(hào)是當(dāng)前符號(hào)，包括文法所有的終結(jié)和自定義。的句子結(jié)束符號(hào)#，它的表行符號(hào)是可能在文法符號(hào)棧SYN中出現(xiàn)的所有符號(hào)，包括所有的非終結(jié)符，所有出現(xiàn)在產(chǎn)生式右側(cè)且不在首位置的終結(jié)符， 自

4、定義的句子結(jié)束符號(hào)#表項(xiàng)。為當(dāng)前棧符號(hào)與當(dāng)前符號(hào)匹配后，所要求的棧操作和輸入操作。表項(xiàng)表明了文法的終結(jié)符與非終結(jié)符是否可能相遇。其中 ， 棧操作包括兩種，一是彈棧;二是彈棧后，將符號(hào)串ABc反轉(zhuǎn)后壓棧;輸 入 操作 包 括 兩 種 ，一 是 讀 入下一符號(hào)，是保持當(dāng)前符號(hào)不變。具體的造算法為171。(1 ) 設(shè) A , B 為文法的非終結(jié)符，C為文法的終結(jié)符和非終結(jié)符組成的字符串，a為文法的終結(jié)符將所 有 產(chǎn) 生式分為四類:6)A-aB，則(A,a )項(xiàng)填寫為(B調(diào)向后壓棧，讀入下一個(gè)字符):(ii)A-a; A-a,則將A, a)項(xiàng)填寫為(彈棧，讀入下一個(gè)字符):(iii)A-BC，則將(A

5、,select(A-BC)項(xiàng)全部填寫為(將BC調(diào)向后壓棧，保持當(dāng)前字符不讀入):(iv)A-N，則將(A, follow(A)項(xiàng)全部填寫為(彈棧，保持 精彩文檔實(shí)用標(biāo)準(zhǔn)文案當(dāng)前字符不讀)。(2) 對(duì)表行和表列的所有字符進(jìn)行循環(huán)；(3) 如果當(dāng)前表行的字符是非終結(jié)符，它必有產(chǎn)生式，依據(jù)此產(chǎn)生式的類型，填寫表項(xiàng)。(4) 如果當(dāng)前表列的字符不在此產(chǎn)生式的選擇集合中，該項(xiàng)填寫為Eror。(5)對(duì) (# ，#)項(xiàng)填寫為OK；(6) 對(duì)當(dāng)前表行字符為終結(jié)符的，只有它與表列字符相同時(shí)，才填寫為(彈棧，讀入下一個(gè)字符)，否則填入Eror。 3.流程圖 開 讀入文法 有效？ 是 文法？LL(1)是 是 判斷句型

6、 報(bào)錯(cuò) 精彩文檔 結(jié)束 實(shí)用標(biāo)準(zhǔn)文案 數(shù)據(jù)結(jié)構(gòu)#includeiostream.h#include stdio.h#include malloc.h#include conio.hstruct Lcharchar char_ch;struct Lchar *next;Lchar,*p,*h,*temp,*top,*base;char curchar;char curtocmp;int right;int table58=1,0,0,1,0,0,0,1,0,0,1,1, 精彩文檔 實(shí)用標(biāo)準(zhǔn)文案1,0,0,1,0,0,0,1,1,0,1,1,1,0,0,1,0,0;int i,j;void pus

7、h(char pchar)temp=(struct Lchar*)malloc(sizeof(Lchar);temp-char_ch=pchar;temp-next=top;top=temp;void pop(void)curtocmp=top-char_ch;if(top-char_ch!=#)top=top-next;void doforpush(int t) 精彩文檔 實(shí)用標(biāo)準(zhǔn)文案switch(t)case 0:push(A);push(T);break;case 5:push(A);push(T);break;case 11:push(A);push(T);push(+);break;

8、case 20:push(B);push(F);break;case 23:push(B);push(F);break;case 32:push(B);push(F);push(*);break;case 40:push(i);break;case 43:push();push(E);push();void changchartoint()switch(curtocmp)case A:i=1;break;case B:i=3;break;case E:i=0;break; 精彩文檔 實(shí)用標(biāo)準(zhǔn)文案case T:i=2;break;case F:i=4;switch(curchar)case i:

9、j=0;break;case +:j=1;break;case *:j=2;break;case (:j=3;break;case ):j=4;break;case #:j=5;void dosome(void)int t;for(;)pop(); 精彩文檔 實(shí)用標(biāo)準(zhǔn)文案curchar=h-char_ch;printf(%ct%c,curchar,curtocmp);if(curtocmp=# curchar=#)break;if(curtocmp=A|curtocmp=B|curtocmp=E|curtocmp=T|curtocmp=F)if(curtocmp!=#)changchartoi

10、nt();if(tableij)t=10*i+j;doforpush(t);continue;elseright=0;break;else 精彩文檔 實(shí)用標(biāo)準(zhǔn)文案if(curtocmp!=curchar)right=0;break;elsebreak;elseif(curtocmp!=curchar)right=0;break;elseh=h-next;continue; 精彩文檔 實(shí)用標(biāo)準(zhǔn)文案void main(void)char ch;cout* 文件名稱: 語法分析endl;cout endl;cout/* 程序相關(guān)說明 */endl; cout-endl; cout-/* A=E B=

11、T */endl; cout-* 目 的: 對(duì)輸入LL(1)文法字符串，本程序能自動(dòng)判斷所給字符串是 -endl; cout-* 否為所給文法的句子，并能給出分析過程。 -endl; cout-*-endl; 潣瑵請(qǐng)?jiān)谙滦休斎胍治龅拇?#號(hào)結(jié)束)：endl; 精彩文檔 實(shí)用標(biāo)準(zhǔn)文案 right=1;base=(struct Lchar*)malloc(sizeof(Lchar);base-next=NULL;base-char_ch=#;temp=(struct Lchar*)malloc(sizeof(Lchar);temp-next=base;temp-char_ch=E;top=tem

12、p;h=(struct Lchar*)malloc(sizeof(Lchar);h-next=NULL;p=h;doch=getch();putch(ch);if(ch=i|ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=#)temp=(struct Lchar*)malloc(sizeof(Lchar);temp-next=NULL;temp-char_ch=ch;h-next=temp; 精彩文檔 實(shí)用標(biāo)準(zhǔn)文案h=h-next;elsetemp=p-next;printf(Input a wrong char!Input again:n);for(;)if (temp!=

13、NULL)printf(%c,temp-char_ch);elsebreak;temp=temp-next;while(ch!=#);p=p-next;h=p;dosome();if(right)printf(成功!n);else 精彩文檔 實(shí)用標(biāo)準(zhǔn)文案錯(cuò)誤printf( !n);getch();截圖： 預(yù)測(cè)分析程序 一、預(yù)測(cè)分析器的結(jié)構(gòu)（注是終結(jié)符或aa形式的矩陣。其中，A為非終結(jié)符，預(yù)測(cè)分析表是一個(gè)MA，雖然它不是文法的一部分，不是文法的終結(jié)符，我們總把它當(dāng)成輸入串的結(jié)束符。意，A中存放著一條關(guān)于MA，a但假定它的存在將有助于簡(jiǎn)化分析算法的描述）。矩陣元素中也可能存放一個(gè)“出aMA面臨輸入

14、符號(hào)a時(shí)所應(yīng)采用的候選。，A的產(chǎn)生式，指出當(dāng) 。根本不該面臨輸入符號(hào)錯(cuò)標(biāo)志”，指出Aa 精彩文檔 實(shí)用標(biāo)準(zhǔn)文案 STACK用于存放文法符號(hào)。分析開始時(shí)，棧底先放一個(gè)，然后，放進(jìn)文法棧開始符號(hào)。同時(shí)，假定輸入串之后也總有一個(gè)，標(biāo)志輸入串結(jié)束。 預(yù)測(cè)分析程序的總控程序在任何時(shí)候都是按STACK棧頂符號(hào)X和當(dāng)前的輸入符號(hào)a行事的。對(duì)于任何（X，a），總控程序每次都執(zhí)行下述三種可能的動(dòng)作之一：（1）若Xa，則宣布分析成功，停止分析過程。（2）若Xa 1，則把X從STACK棧頂逐出，讓a指向下一個(gè)輸入符號(hào)。（3）若X是一個(gè)非終結(jié)符，則查看分析表M。若MA，a中存放著關(guān)于X的一個(gè)產(chǎn)生式，那么，首先把X逐出STACK棧頂，然后，把產(chǎn)生式的右部符號(hào)串按反序一一推進(jìn)STACK棧（若右部符號(hào)為e，則意味不推什么東西進(jìn)棧）。在把產(chǎn)生式的右部符號(hào)推進(jìn)棧的同時(shí)應(yīng)做這個(gè)產(chǎn)生式相應(yīng)的語義動(dòng)作（目前暫且不管）。若MA，a中存放著“出錯(cuò)標(biāo)志”，則調(diào)用出錯(cuò)診察程序ERROR。預(yù)測(cè)分析器的結(jié)構(gòu)如圖所示輸入a + b #預(yù)測(cè)分析X棧輸出(采選用的產(chǎn)生式)控制程序YZ#分析表M 預(yù)測(cè)分析器的結(jié)構(gòu) 圖