c实现消除文法左递归.doc

c实现消除文法左递归.doc

ID:49357058

大小:142.00 KB

页数:9页

时间:2020-02-29

c实现消除文法左递归.doc_第1页
c实现消除文法左递归.doc_第2页
c实现消除文法左递归.doc_第3页
c实现消除文法左递归.doc_第4页
c实现消除文法左递归.doc_第5页
资源描述:

《c实现消除文法左递归.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、编译原理实验报告实验名称消除文法的左递归实验时间2010.11.1院系计算机科学与技术班级2008学号JB084193姓名潘亚飞1.试验目的输入:任意的上下文无关文法。输出:消除了左递归的等价文法。2.实验原理1.直接左递归的消除消除产生式中的直接左递归是比较容易的。例如假设非终结符P的规则为P→Pα/β其中,β是不以P开头的符号串。那么,我们可以把P的规则改写为如下的非直接左递归形式:P→βP’P’→αP’/ε这两条规则和原来的规则是等价的,即两种形式从P推出的符号串是相同的。设有简单表达式文法G[E]:E→E+T/TT→T*F/FF→(E)/I经消除直接左递归

2、后得到如下文法:E→TE’E’→+TE’/εT→FT’T’→*FT’/εF→(E)/I考虑更一般的情况,假定关于非终结符P的规则为P→Pα1/Pα2/…/Pαn/β1/β2/…/βm其中,αi(I=1,2,…,n)都不为ε,而每个βj(j=1,2,…,m)都不以P开头,将上述规则改写为如下形式即可消除P的直接左递归:P→β1P’/β2P’/…/βmP’P’→α1P’/α2P’/…/αnP’/ε2.间接左递归的消除直接左递归见诸于表面,利用以上的方法可以很容易将其消除,即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。有些文

3、法虽然表面上不存在左递归,但却隐藏着左递归。例如,设有文法G[S]:S→Qc/cQ→Rb/bR→Sa/a虽不具有左递归,但S、Q、R都是左递归的,因为经过若干次推导有SQcRbcSabcQRbSabQcabRSaQcaRbca就显现出其左递归性了,这就是间接左递归文法。消除间接左递归的方法是,把间接左递归文法改写为直接左递归文法,然后用消除直接左递归的方法改写文法。如果一个文法不含有回路,即形如PP的推导,也不含有以ε为右部的产生式,那么就可以采用下述算法消除文法的所有左递归。消除左递归算法:(1)把文法G的所有非终结符按任一顺序排列,例如,A1,A2,…,An。

4、(2)for(i=1;i<=n;i++)for(j=1;j<=i-1;j++){把形如Ai→Ajγ的产生式改写成Ai→δ1γ/δ2γ/…/δkγ其中Aj→δ1/δ2/…/δk是关于的Aj全部规则;消除Ai规则中的直接左递归;}(3)化简由(2)所得到的文法,即去掉多余的规则。利用此算法可以将上述文法进行改写,来消除左递归。首先,令非终结符的排序为R、Q、S。对于R,不存在直接左递归。把R代入到Q中的相关规则中,则Q的规则变为Q→Sab/ab/b。代换后的Q不含有直接左递归,将其代入S,S的规则变为S→Sabc/abc/bc/c。此时,S存在直接左递归。在消除了S的

5、直接左递归后,得到整个文法为:S→abcS’/bcS'/cS'S’→abcS'/εQ→Sab/ab/bR→Sa/a可以看到从文法开始符号S出发,永远无法达到Q和R,所以关于Q和R的规则是多余的,将其删除并化简,最后得到文法G[S]为:S→abcS'/bcS’/cS'S'→abcS'/ε当然如果对文法非终结符排序的不同,最后得到的文法在形式上可能不一样,但它们都是等价的。例如,如果对上述非终结符排序选为S、Q、R,那么最后得到的文法G[R]为:R→bcaR'/caR'/aR’R'→bcaR'/ε容易证明上述两个文法是等价的。3..实验内容消除左递归算法:(1)把文法

6、G的所有非终结符按任一顺序排列,例如,A1,A2,…,An。(2)for(i=1;i<=n;i++)for(j=1;j<=i-1;j++){把形如Ai→Ajγ的产生式改写成Ai→δ1γ/δ2γ/…/δkγ其中Aj→δ1/δ2/…/δk是关于的Aj全部规则;消除Ai规则中的直接左递归;}(3)化简由(2)所得到的文法,即去掉多余的规则。利用此算法可以将上述文法进行改写,来消除左递归。4.实验代码//#include"stdafx.h"#include#includeusingnamespacestd;structWF//定义一个产

7、生式结构体{stringleft;//定义产生式的左部stringright;//定义产生式的右部};voidRemoving(WF*p,char*q,intn,intcount){intcount1=n;intflag=0;for(inti=0;i

8、f(p[i

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。