学步园

清华大学计算机系列教材

编译原理第二版

张素琴，吕映芝等编著

P56  5.6 典型例题及解答 例题一为例，进行预测分析

tip:预测分析法和回归分析法都是自顶向下的方法，预测分析法只能分析满足LL1的文法

简单示例，为清楚原理

//课本P96 例1</p> <p>#include "stdafx.h"<br /> #include <stdio.h><br /> #include <iostream><br /> #define MAXLEN 100 //栈的最大容量<br /> using namespace std;</p> <p>int analysisStack[MAXLEN]={0,30};//分析栈</p> <p>//略过词法分析阶段<br /> //int shuru[MAXLEN]={1,1,1,2,3,0};//匹配<br /> //int shuru[MAXLEN]={1,1,2,3,0};//不匹配<br /> int shuru[MAXLEN]={1,3,0};//匹配</p> <p>int inputLength=0; //输入串的长度<br /> int leftString[MAXLEN]={};//剩余输入串</p> <p>//定义产生式，根据题意，7条BNF，共7个产生式。每条最大长度不超过10<br /> //右边的第一个符号为终结符<br /> int product[10][10]={<br /> {30,1,31,0},<br /> {31,1,32,3,0},<br /> {31,3,0},<br /> {32,1,32,2,0},<br /> {32,4,0},<br /> {32,0},<br /> {33,1,32,0},<br /> {33,4,0},<br /> };</p> <p>void setLeftString()//设置剩余输入串，即要分析的字符串，词法分析的结果<br /> {<br /> while (shuru[inputLength]!=0)<br /> {<br /> inputLength++;<br /> }<br /> int j=0;//指向分析串的指针，暂时的<br /> for (j=0;j<=inputLength;j++)<br /> {<br /> leftString[j]=shuru[inputLength-j];<br /> }<br /> }<br /> void outputAnalysis()//输出分析栈的内容<br /> {<br /> printf("/n分析栈的内容：");<br /> for (int i=1;i<MAXLEN;i++)<br /> {<br /> if (analysisStack[i]!=0)//打印非0元素<br /> {<br /> printf("%d,",analysisStack[i]);<br /> }<br /> }<br /> }<br /> void outputLeftString()//输出剩余串<br /> {<br /> printf("/n剩余输入串：");<br /> for (int i=1;i<MAXLEN;i++)<br /> {<br /> if (leftString[i]!=0)//打印非0元素<br /> {<br /> printf("%d,",leftString[i]);<br /> }<br /> }<br /> }</p> <p>int _tmain(int argc, _TCHAR* argv[])<br /> {<br /> setLeftString();</p> <p> int pointer1=1;//分析栈的指针<br /> int pointer2=inputLength;//待分析串的指针</p> <p> outputAnalysis();<br /> outputLeftString();</p> <p> int fenxicishu=0;//分析次数<br /> while(fenxicishu<=20)//最多分析次数<br /> {<br /> printf("/n/n第%d次分析结果：",fenxicishu+1);<br /> if (analysisStack[pointer1]==0 && leftString[pointer2]==0)//栈空，结束<br /> {<br /> printf("栈空/n");<br /> break;<br /> }<br /> else<br /> {<br /> if (analysisStack[pointer1]==leftString[pointer2])//分析栈起始符号和剩余输入串起始符号匹配<br /> {<br /> printf("/n匹配");<br /> analysisStack[pointer1]=0;<br /> pointer1--;<br /> leftString[pointer2]=0;<br /> pointer2--;<br /> fenxicishu++;<br /> }<br /> else<br /> {<br /> printf("/n不匹配，");<br /> for(int i=0;i<10;i++)//产生式个数<br /> {<br /> if(analysisStack[pointer1]==product[i][0])//左边匹配<br /> {<br /> if (pointer1-pointer2==1)<br /> {<br /> analysisStack[pointer1]=0;//选择产生式->e<br /> pointer1--;<br /> break;<br /> }<br /> int k=i;//左边相同的产生式<br /> while (analysisStack[pointer1]==product[k][0])//左边相同的产生式<br /> {<br /> if (leftString[pointer2]==product[k][1])//右边以匹配的终结符开始<br /> {<br /> break;<br /> }<br /> k++;<br /> }<br /> i=k;</p> <p> printf("找到产生式：%d->",product[i][0]);<br /> int productLength=0;//产生式的长度<br /> while(product[i][productLength]!=0)<br /> {<br /> productLength++;<br /> printf("%d ",product[i][productLength]);<br /> }</p> <p> for (int j=1;j<productLength;j++)//产生式的长度<br /> {<br /> analysisStack[j+pointer1-1]=product[i][productLength-j];<br /> }<br /> pointer1=pointer1+productLength-2;<br /> }<br /> }<br /> }<br /> outputAnalysis();<br /> outputLeftString();<br /> fenxicishu++;<br /> }<br /> }<br /> if(analysisStack[1]!=0 || leftString[1]!=0 )<br /> {<br /> printf("/n/n分析了%d次，仍没成功匹配/n/n",fenxicishu);<br /> }<br /> else<br /> {<br /> printf("/n/n成功匹配!!/n/n");<br /> }</p> <p> system("pause");<br /> return 0;<br /> }</p> <p>