- 1、本文档共88页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
B?(aBc|d)B?B??bcB?|εA?BbA?aB+消除文法中一切左递归的算法。对文法中一切左递归的消除要求文法中不含回路,即无A?A的推导。满足该文法的充分条件是:文法中不包含形如A?A的有害规则和A?ε的产生式。算法步骤*自顶向下语法分析方法*以某种顺序将文法非终结符排列A1,A2…An从A1开始消除左部为A1的产生式的直接左递归,然后把左部为A1的所有规则的右部逐个替换左部为A2右部以A1开始的产生式中的A1,并消除左部为A2的产生式中的直接左递归。继而以同样方式把A1,A2的右部代入左部为A3右部以A1或A2开始的产生式中,消除左部为A3的产生式之直接左递归,直到把左部为A1,A2,…An-1的右部替换左部为An的产生式中,从An中消除直接左递归。0102*自顶向下语法分析方法*(1)以某种顺序将文法非终结符排列A1,A2…An(2)fori:=1tondobeginforj:=1toi-1do 若Aj的全部产生式为: Aj??1|?2|…|?k 替代形如Ai?Ajr的产生式变为:Ai??1r|?2r|…|?krend消除Ai规则的一切直接左递归;end;(3)去掉无用产生式方法一:根据定义计算对于每一个文法符号x?V,计算first(x)的方法如下:若x?VT,则first(x)={x}若x?VN,且有x?a…,a?VT,则a?first(x)若x?VN,x??,则??first(x)若x?VN,y1,y2,…,yi都?VN,若有产生式x?y1y2…yn,当y1,y2,…yi-1都??时(1≤i≤n),则first(y1)-{?},first(y2)-{?},…,first(yi-1)-{?},first(yi)都包含在first(x)中。e)当上式中所有yi??(1≤i≤n),则first(x)=(first(y1)-{?})∪(first(y2)-{?})∪…∪(first(yn)-{?})∪{?}**first(S)=(first(A)-{?})∪(first(B)-{?})∪{?}∪{b}={a,b,?}first(A)={b}∪{?}={b,?}first(B)={?}∪{a}={a,?}first(C)=(first(A)-{?})∪first(D)∪first(b)={a,b,c}first(D)={a}∪{c}={a,c}S?AB|bCA?ε|bB?ε|aDC?AD|bD?aS|c一个文法符号串的first集合计算方法:如果文法符号串??V*,?=X1X2…Xn,1、当X1?ε,则first(?)=first(X1)2、当对任何j(1≤j≤i-1,2≤i≤n),ε?first(Xj)ε?first(Xi),则first(?)=(first(X1)-{ε})∪(first(X2)-{ε})∪…∪(first(Xi-1)-{ε})∪first(Xi)3、当first(Xj)都含有ε时(1≤j≤n),则first(?)=first(X1)∪first(X2)∪…∪first(Xj)∪{ε}*first(A)∪first(B)∪{ε}={a,b,ε}{b}{ε}{a}(first(A)-{ε})∪first(D)={a,b,c}{b}{a}{c}first(AB)=first(bC)=first(ε)=first(aD)=first(AD)=first(b)=first(aS)=first(c)=文法G[S]: S→AB|bC A→ε|b B→ε|aD C→AD|b D→aS|c方法二:由关系图法求文法符号的first集合每个文法符号对应图中的一个结点,终结符结点用符号本身标记,非终结符结点用first(A)标记。若文法中有A??X?,??ε,则从对应A的结点到对应X结点连一条箭弧。凡是从first(A)结点有路径可到达的终结符结点所标记的终结符都为first(A)的成员。根据判别步骤1)确定ε是否为某非终结符first的成员,若是则将ε加入该非终结符的first集中。*自顶向下语法分析方法*first(S)first(B)first(C)first(A)first(D)bac文法为:S?AB|bCA?ε
文档评论(0)