还剩9页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
第五章自顶向下语法分析方法•对文法1G[S]Sa|A|TTT,S|S给出和的最左推导1a,a,a a,a,A,a,a对文法进行改写,然后对每个非终结符写出不带回溯的递归子程序2G,经改写后的文法是否是的?给出它的预测分析表3LL1给出输入串的分析过程,并说明该串是否为的句子解4a,a#G的最左推导为1a,a,a ST T,S S,S a,T a,T,S a,S,a a,a,a的最左推导为a,a,A,a,aS T T,S S,a T,a T,S,a T,S,S,a S,A,T,a T,A,S a5T,S,A,a,a S,a,A,a,a a,a,A,a,a由于有的产生式,所以消除该产生式的左递归,增中一个非终结符有新的文法2TT,S UG[S]:Sa|A|TTSUU,SU|£分析子程序的构造方法对满足条件的文法按如下方法构造相应的语法分析子程序对于每个非终结号编写一个相应的子程序;1U,PU对于规则有一个关于的子程序按如下方法构造:2U::=x1|x2|..|xn,U PU,PUIF CH IN FIRSTx1THEN Px1ELSE IF CHIN FIRSTx2THEN Px2ELSE...IF CHIN FIRSTxn THENPx nELSE ERROR其中,存放当前的输入符号,是一个全程变量;一段处理出错信息的程序;为相应的CH ERROR1Pxj子程序⑶对于符号串的含义为x=y1y
2...y n;pxBEGIN;Py1Py2;;Py nEND如果是非终结符,则代表调用处理的子程序;yi Pyiyi如果是终结符,则为形如下述语句的一段子程序yi PyiIF CH=yi THEN READCH ELSE ERROR即如果当前文法中的符号与输入符号匹配,则继续读入下一个待输入符号到中,CH否则表明出错⑷如果文法中有空规则则算法中的语句U::=EPSILON,编译原理习题解答IF CHIN FIRSTxn THENPx n编译原理习题解答ELSEERROR改写为IFCHINFIRSTxn THENPx nELSEIFCHIN FOLLOWUTHEN RETURNERROR要分析一个应在该串的后面加上一个串括)开始,5OrgStr,号#,并从子程序为文法的开始符号PSS如果中途没有产生错误,并且最后则说明串合法,否则该串不合法CH=#,OrgStr对每个非终结符写出不带回溯的递归子程序如下〃存放当前的输入符号char CH;〃非终结符的子程序void P_S S产生式A,产生式A>产生式ifCH==aREADCH;//S aelse ifCH==READC Selse ifCH==S TREADCH;;P_TIF CH==THENREADCHelse ERRORelse ERR;〃非终结符的子程序void P_T S〃为的右部的集合iflslnCH,FIRST_SU FIRST_SU TSUFIRST;〃非终结符的子程序P_S P_U;void P_U U,产生式WCH==U,SU READCH;P_S;P-U;产生式else//U£为的集合iflslnCH,FOLLOW_U//FOLLOW_U UFOLLOW return;else ERR;⑶判断文法网是否为⑴文法G LL各非终结符的集合如下FIRST人,}FIRSTS={a,人,FIRSTT=FIRSTS={a,FIRSTU={,,£}各非终结符的哈如下FOLLOW编译原理习题解答FOLLOWS={#}U FIRSTUU FOLLOWTU FOLLOWU={#,,,}FOLLOWT={}FOLLOWU=FOLLOWT={}每个产生式的集合如下SELECTSELECTS a={a}SELECTS A={A}SELECTS={}SELECTT SU=FIRSTS={a,A,}SELECTU,SU={,}SELECTU=FOLLOWU={}E可见,相同左部产生式的集的交集均为空,所以文法是文法SELECT G[S]LL1文法的预测分析表如下G[S]#a AS aATT SU SUSU,suUE给出输入串的分析过程5a,a#步骤分析栈剩余输入串所用产生式1#S a,a#ST匹配2#T a,a#3#T a,a#TSU4#US a,a#Sa匹配5#Ua a,a#a6#U,a#U,SU,匹配7#US,,a#8#US a#Sa匹配9#Ua a#a10#U#UE匹配11##接受12##.对下面的文法2G:ETEE+E|ETFTTZT|EF PFP*R|EP E|a|bF⑴计算这个文法的每个非终结符的集和FIRST FOLLOWio⑵证明这个方法是的LL1构造它的预测分析表3构造它的递归下降分析程序4解计算这个文法的每个非终结符的集和集1FIRST FOLLOW集合有FIRSTFIRSTE=FIRSTT=FIRSTF=FIRSTP={,a,br};编译原理习题解答,FIRSTE={+,E}FIRSTT=FIRSTF=FIRSTP={,a,br};FIRSTTZ=FIRSTT U{E}={,a,b=E};FIRSTF=FIRSTP={,a,b,A};;FIRSTF=FIRSTP={*£}5FIRSTP={,a b,A;5集合有FOLLOWFOLLOWE={,#};Z;FOLLOW E=FOLLOWE={,#}〃不包含£ZFOLLOWT=FIRSTE UFOLLOWE={+,,#};FOLLOWT=FOLLOWT=FIRSTEU;FOLLOWE={+,,#}〃不包含£FOLLOWF=FIRSTT UFOLLOWT={,a,b,A,+,,#};FOLLOWF=FOLLOWF=FIRSTTU FOLLOWT={,a,b,A,+,,#};〃不包含£FOLLOWP=FIRSTF UFOLLOWF={*,,a,b,A,+,,#};⑵证明这个方法是⑴的LL各产生式的集合有SELECTSELECTE TE=FIRSTT={,a,br};SELECTE+E={+};SELECTE£=FOLLOWE={,#}十二SELECTT5FIRSTF={,a,b,A};SELECTT T=FIRSTT={,a,br};;SELECTT£=FOLLOWT={+,,#}SELECTF PF=FIRSTP={,a,br};={*};SELECTF*FSELECTF£=FOLLOWF={,a,b,A,+,,#};SELECTP E={}SELECTP a={a}SELECTP b={b}SELECTP A={,可见,相同左部产生式的集的交集均为空,所以文法是文法SELECT G[E]LL1构造它的预测分析表文法的预测分析表如下:3G[E]*A+a b#7E TETE TEPTE匚+E££FT FTFT FTTT£T£TTT£PF PF PFPF,FF Z£*F££££££P Ea bA构造它的递归下降分析程序4对每个非终结符写出不带回溯的递归子程序如下〃存放当前的输入符号char CH;非终结符的子程序void P_E//E〃为的右部的集合,产生式iflslnCH,FIRST_TEP FIRST_TEP ETEFIRST ETE;P_T P_EP;〃非终结符的子程序//产生式else ERR;void P_EP Uif CH==+U+EREADCH;;产生式zP_Eelse//E为的喋合iflslnCH,FOLLOW_EP//FOLLOW_EP EFOLLO return;else ERR;非终结符的子程序void P_T//T〃为〒的右部的集合,产生式iflslnCH,FIRST_FTP FIRST_FTP TFFIRST TFTP_F;;P_TPelse ERR;非终结符的子程序void P_TP//Fiflsl nCH,FIRST_T〃FIRST_T为产生式TT的右部的FIRST集合,产生式TT;P_T为的喋合〃T FOLLOiflsIn CH,FOLLOW_TP FOLLOW_TPreturn;else ERR;非终结符的子程序void P_F//F的右部的集合,产生式PF FIRSTFPF为iflslnCH,FIRST_PFP//FIRST_PFP F{;P_P P_FP;else ERR;非终结符的子程序void P_FP//P//产生式Zif CH==*R*FREADCH;P_FP;else//产生式R f为U的FOLLO喋合产生式V£else//〃非终结符的子程序void P_P PifCH==9{READCH;;P_EfifCH==READCHC H;elseERR;J,else ifCH==aREADCH;,,else ifCH==bREADCH;A,else ifCH==READCH;else ERR;•已知文法3G[S]:SMH|aH LSo|£KdML|£LeHfM K|bLM判断是否是文法,如果是,构造分析表解G LL1LL1首先求各非终结符的集合FIRSTFIRSTS={a}U FIRSTM U FIRSTH={a}U{b,d,}U{e,}={a,b,d,e,};£££;FIRSTH=FIRSTL U{}={e,£}£FIRSTK={d,£};;FIRSTL={e}FIRSTM=FIRSTK U{b}={b,d,£};然后求非终结符的合FOLLOWSFOLLOWS={o,#}〃不包含FOLLOWH=FOLLOWS{f}={f,o,#}FOLLOWK=FOLLOWM=FIRSTH FOLLOWS={e,o,#};£FOLLOWL=FIRSTS U{o}U FOLLOWKJFIRSTMU FOLLOWM={a,b,d,e,o,#}U〃不包含£FOLLOWM={a,b,d,e,o,#};〃不包含£最后求各产生式的集合FOLLOWM=FIRSTLU FIRSTHU FOLLOWS={e,o,#}SELECTSELECTS MH=FIRSTMH-{£}U FOLLOWS={b,d,e}U{o,#}={b,d,e,o,#};SELECTS a={a}SELECTH LSo={e}SELECTH£=FOLLOWH={f,o,#}SELECTK dML={d}SELECTK£=FOLLOWK={e,o,#}SELECTL eHf={e}SELECTM K=FIRSTK-{£}UFOLLOWM={d,e,o,#}SELECTM bLM={b}可见,相同左部产生式的集的交集均为空,所以文法是⑴文法SELECT G[S]LL文法的预测分析表如下G[E]a0d ef b#S aMH MH MHMHMHH£LSo££K£dML££L eHfMK KK bLMK.对于一个文法若消除了左递归,提取了左公共因子后是否一定为文法?试对下面方法进行改写,并对7LL1改写后的文法进行判⑴A baB|£B Abb|a⑵A aABe|a解对于一个文法若消除了左递归,提取了左公共因子后不一定为文法如果新的文法中无空产生式,B Bb|d LL1则一定为文法,如果有空产生式,则需要进行判断才能决定新方法是否一定是文法LL1LL1LL11由于两集合有交集,所以该文法不是⑴方法该文法已经消除了SELECTA baB={b},SELECTA=FOLLOWA={b,#},LL£左递归,与左公共因子,一般来说是不能再改写了但根据本文法的具体情况有以下改写用产生式八与分别替换528A£产生式有提取这两个新产生式的左公共因子有B AbbBbaBbb|bb,这样改写后文法网为BbBBaBbb|b,GA baB|zB bB|az每个产生式的集合为
①zB aBbb|b SELECTSELECTA baB={b}SELECTA£”SELECTB bB={b}SELECTB可见,相同左部产生式的集的交集均为空,所以文法a={a}SELECTB aBbb={a}SELECTB b={b}SELECT G[A]是⑴文法LL显然文法的第个产生式的右部具有左公共因子而产生工具有左递归,因此文法可改写为21,2a,BBbz zAaA AABe|£BdBz由于交集为空bB|£SELECTA ABe={a},SELECTA£=FOLLOWA=FOLLOWA=FIRSTB U{#}={d,#},而z1交集也为空SELECTB bB={b},SELECTB=FOLLOWB=FOLLOWB={e},而非终结符与都只有一个产生式,不存在求的交集问题A BSELECT所以改写后的方法为文法LL1。