LL(1)語法分析程序?qū)嶒?yàn)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上LL1實(shí)驗(yàn)報(bào)告1. 設(shè)計(jì)原理 所謂LL（1）分析法，就是指從左到右掃描輸入串（源程序），同時(shí)采用最左推導(dǎo)，且對每次直接推導(dǎo)只需向前看一個(gè)輸入符號，便可確定當(dāng)前所應(yīng)當(dāng)選擇的規(guī)則。實(shí)現(xiàn)LL（1）分析的程序又稱為LL（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）分析表，最后利用分析表，根據(jù)LL(1)語法分析構(gòu)造一個(gè)分析器。LL（1）的語法分析程序包含了三個(gè)部分，總控程

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

3、號為，則不推什么東西進(jìn)STACK棧）。若MA，a中存放著“出錯(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è)二維表，它的表列符號是當(dāng)前符號，包括文法所有的終結(jié)和自定義。的句子結(jié)束符號#，它的表行符號是可能在文法符號棧SYN中出現(xiàn)的所有符號，包括所有的非終結(jié)符，所有出現(xiàn)在產(chǎn)生式右側(cè)且不在首位置的終結(jié)符， 自定義的句子結(jié)束符號#表項(xiàng)。為當(dāng)前棧符號與當(dāng)前符號匹配后，所要求的棧操作和輸入操作。表項(xiàng)表明了文法的終結(jié)符與

4、非終結(jié)符是否可能相遇。其中 ， 棧操作包括兩種，一是彈棧;二是彈棧后，將符號串ABc反轉(zhuǎn)后壓棧;輸 入 操作 包 括 兩 種 ，一 是 讀 入下一符號，是保持當(dāng)前符號不變。具體的造算法為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,select(A->BC)項(xiàng)全部填寫為(將BC調(diào)向后壓棧，保持當(dāng)前字

5、符不讀入):(iv)A->N，則將(A, follow(A)項(xiàng)全部填寫為(彈棧，保持當(dāng)前字符不讀)。(2) 對表行和表列的所有字符進(jìn)行循環(huán)；(3) 如果當(dāng)前表行的字符是非終結(jié)符，它必有產(chǎn)生式，依據(jù)此產(chǎn)生式的類型，填寫表項(xiàng)。(4) 如果當(dāng)前表列的字符不在此產(chǎn)生式的選擇集合中，該項(xiàng)填寫為Eror。(5)對 (# ，#)項(xiàng)填寫為OK；(6) 對當(dāng)前表行字符為終結(jié)符的，只有它與表列字符相同時(shí)，才填寫為(彈棧，讀入下一個(gè)字符)，否則填入Eror。有效？讀入文法開始3.流程圖是是LL(1)文法？結(jié)束報(bào)錯(cuò)判斷句型是數(shù)據(jù)結(jié)構(gòu)#include"iostream.h"#include &

6、quot;stdio.h"#include "malloc.h"#include "conio.h"struct 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,1,0,0,1,0,0,0,1,1,0,1,1,1,0,0,1,0,0;int i,j; void push(char pchar)temp=(struct

7、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)switch(t)case 0:push('A');push('T');break;case 5:push('A');push('T');break;case

8、 11:push('A');push('T');push('+');break; 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(

9、9;E');push('('); void changchartoint()switch(curtocmp)case 'A':i=1;break;case 'B':i=3;break;case 'E':i=0;break;case 'T':i=2;break;case 'F':i=4;switch(curchar)case 'i':j=0;break;case '+':j=1;break; case '*':j=2;break; case &#

10、39;(':j=3;break;case ')':j=4;break;case '#':j=5; void dosome(void)int t;for(;)pop();curchar=h->char_ch;printf("n%ct%c",curchar,curtocmp);if(curtocmp='#' && curchar='#')break;if(curtocmp='A'|curtocmp='B'|curtocmp='E'|cur

11、tocmp='T'|curtocmp='F')if(curtocmp!='#')changchartoint();if(tableij)t=10*i+j;doforpush(t);continue;elseright=0;break;elseif(curtocmp!=curchar)right=0;break;elsebreak;elseif(curtocmp!=curchar)right=0;break;elseh=h->next;continue; void main(void)char ch;cout<<"* 文

12、件名稱: 語法分析"<<endl;cout<<" "<<endl;cout<<"/* 程序相關(guān)說明 */"<<endl; cout<<"-"<<endl; cout<<"-/* A=E B=T */"<<endl; cout<<"-* 目 的: 對輸入LL(1)文法字符串，本程序能自動判斷所給字符串是 -"<<endl; cout<<"

13、;-* 否為所給文法的句子，并能給出分析過程。 -"<<endl; cout<<"-*-"<<endl; cout<<"表達(dá)式文法為："<<endl; cout<<" E->E+T|T"<<endl; cout<<" T->T*F|F"<<endl; cout<<" F->(E)|i"<<endl; cout<<"請

14、在下行輸入要分析的串(#號結(jié)束)："<<endl; 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=temp;h=(struct Lchar*)malloc(sizeof(Lchar);h->next=NULL;p=h;do ch=getch(

15、);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;h=h->next;elsetemp=p->next;printf("nInput a wrong char!Input a