温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
人生在世、俯仰之间、 唯有追求卓越、但求尽其所能！^V^
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
特别写出这篇文章 ：一来总结一下这几天的收获。二来与君共勉。首先给出几个不好理解的概念(一直理解的都不好)：1、活前缀：不包含句柄右侧任一符号的规范句型的前缀称为该句型的活前缀。& & & & & & & & 例如：Bab是下面那个文法的一个句型，其中b是句柄。& & & & & & & & 那么针对这个句型的活前缀有：ε、B、Ba 和Bab& & & & & & & & （其实，LR分析器的工作过程实际上就是逐步产生规范句型的活前缀。& & & & & & & & &如果能构造出一个识别文法所有规范句型活前缀的确定有穷自动机即DFA，就能很方便的构造出LR分析表）2、LR(0)项目：右部某位置上标有圆点的产生式称为相应文法的一个LR(0)项目& & & & & & & & &注意：A --&&ε
只对应一个项目
(LR(0)项目描述了活前缀和句柄的不同识别状态）3、ε-可达：从&S' --& .S 出发，不必再识别任何符号就可以到达 S --& .BB，就称&S --& .BB是从& & & & & & & &&S' --& .S 出发&ε-可达的。4、项目集闭包：用Item0表示DFA的初始状态，对应分析的开始，并期待着逐步将输入符号串& & & & & & & & 归约为开始符号S‘。因此将S' --& .S 放到&Item0 中，意即等待归约出S，且目前尚未& & & & & & & & 得到S的任何符号。& & & & & & & &&Item0 = CLOSURE({S' --& .S}) = {S' --& .S，S --& .BB，B --& .aB，B --& .b}& & & & & & & & 该项目集合中所有的项目都是从S' --& .S 出发&ε-可达的，称为{S' --& .S}的项目集闭包& & & & & & & （每个项目集闭包对应着分析器的一个状态）5、后继项目：项目 A --&&αX.β & 称为&A --&&α.Xβ &的后继项目6、后继项目集：假定Item0是文法G的一个LR(0)项目集，& & & & & & & &则称 GO(Item0,X) = CLOSURE({A --&&αX.β}) &为&Item0 关于X的后继项目集。& & & & & & & &GO为项目集的转移函数。7、项目集规范族：项目集的全体& & & & & & & &&例子：文法：S --& BBB --& aBB --& b步骤：一、扩展文法S' --& SS --& BBB --& aBB --& b二、求出项目集规范族Item0 = CLOSURE({S' --& .S}) = {S' --& .S，S --& .BB，B --& .aB，B --& .b}Item1 =GO(Item0,S) = CLOSURE({S' --& S.}) = {S' --& S.}Item2 =&GO(Item0,B) = CLOSURE({S --& B.B}) = {S --& B.B，B --& .aB，B --& .b}Item3 =&GO(Item0,a) = CLOSURE({B --& a.B}) = {B --& a.B，B --& .aB，B --& .b}Item4 = GO(Item0,b) = CLOSURE({B --& b.}) = {B --& b.}至此Item0已经遍历完，开始遍历下一个，由于Item1圆点已经到达末尾，所以跳过Item1。Item5 = GO({Item2,B) = CLOSURE({S --& BB.}) = {S --& BB.}由于 GO(Item2,a) 和&GO(Item2,b) 重复，所以去掉。Item6 = GO(Item3,B) = CLOSURE({B --& aB.}) = {B --& aB.}由于 GO(Item3,a) 和&GO(Item3,b) 重复，所以去掉。至此，项目集闭包不再增加，所以项目集规范族构造完毕！三、构造DFA方法很简单，看一下结果就懂了，在这里就不赘述了。需要注意的是：要找到每个集合和其他集合所有的转移路径，容易遗漏！四、构造LR(0)分析表（根据自己画出的DFA图，将分析表填充）先说算法：--------------------------------------------------------------------------------------------------------输入：文法G的扩展文法G'输出：G'的LR(0)分析表（即 Action表和Goto表）步骤：1、本例中Item2 &--B--& &Item5，则在 &状态号为2的行，列名为B的格中填入状态5（转移条件为非终结符，填充Goto表，填入状态号，&转移条件为终结符，填充Action表，填入Sn，Sn表示移进，移进符号并且移进状态号n）Item2 &--a--& &Item3 ，则在状态号为2的行，列名为a的格填入S3。2、对于圆点在右部最右边：if &A --&&α.&∈ Itemk (0&k&n) &&&A --&&α 为G的第 j 个产生式，then for &任意 a&∈ T U {#} &doAction[k,a] &= &Rj（Rn表示归约，不移进符号，用第n个产生式的右部替换符号栈的X）3、if &S' --& S. &∈Itemk&(0&k&n) & &then Action[k,#] = acc.--------------------------------------------------------------------------------------------------------&
阅读(1771)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_',
blogTitle:'编译原理：LR(0)文法项目集规范族、DFA和分析表的构建实例',
blogAbstract:'最近在复习编译原理，考试之前以为自己懂了，眼高手低就没去实践。结果一考试出问题了。。。。学习就要脚踏实地，容不得半点模糊。凭着侥幸心理很危险的。以后要引以为戒啊。特别写出这篇文章 ：一来总结一下这几天的收获。二来与君共勉。首先给出几个不好理解的概念(一直理解的都不好)：1、活前缀：不包含句柄右侧任一符号的规范句型的前缀称为该句型的活前缀。& & & & & & & & 例如：Bab是下面那个文法的一个句型，其中b是句柄。& & & & & & & & 那么针对这个句型的活前缀有：',
blogTag:'',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:8,
publishTime:4,
permalink:'blog/static/',
commentCount:0,
mainCommentCount:0,
recommendCount:0,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'人生在世、俯仰之间、 唯有追求卓越、但求尽其所能！^V^',
hmcon:'0',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}An error occurred on the server when processing the URL. Please contact the system administrator.
If you are the system administrator please click
to find out more about this error.您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
第九章 编译原理习题.doc 8页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
你可能关注的文档：
··········
··········
1.已知文法G[A]，写出它定义的语言描述
A → 0B|1C
B → 1|1A|0BB
C → 0|0A|1CC
2.? 给出生成下述语言的上下文无关文法：
（1）{ anbnambm| n，m&=0}
(2) { 1n0m 1m0n| n，m&=0}
3.? 给出生成下述语言的三型文法：
(1){ anbm|n,m&=1 }
(2){anbmck|n,m,k&=0 }
文法G[E]为： E→E+T|T
　　　　　　　　　　T→T*F|F
　　　　　　　　　　F→(E)|i
试给出句型(E+F)*i的短语，简单(直接)短语,句柄。
一、判断题:
编译程序中的词法分析程序以字符形式的源程序作为输入，输出的单词符号常采用二元组的形式。
正规式的运算符“|”读作“或“。
若两个正规式所表示的正规集相同，则认为二者是等价的。
用l代表字母，d代表数字，Σ={l，d}，则正规式r=dd*定义了无符号整数单词。
一个确定的有穷自动机DFA M的转换函数f是一个从KⅹΣ到K 的子集的映像。
一个非确定的有穷自动机NFA N
的转换函数f是一个从KⅹΣ*到K 的映像。
一张状态转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。
终态与非终态是可区别的。
对任意一个右线性文法G，都存在一个NFA M，满足L（G）=L（M）。
对任意一个右线性文法G，都存在一个DFA M，满足L（M）=L（R）。
二、构造正规式1(0|1)*101相应的DFA.
一、判断题：
空符号串的集合{ε}={}=ф。
设A是符号串的集合，则A0=ε。
设G是一个文法，S是开始符号，如果S =& x且x∈VT*,则称x是文法G[S]的句型。
在形式语言中，最右推导的逆过程也称为规范归约。
一个语言的文法是唯一的。
若一个语言是无穷集合，则定义该语言的文法一定是递归的。
一个句型中出现某个产生式的右部，则此右部一定是此句型的句柄。
每个直接短语都是某规则的右部。
用二义性文法定义的语言也是二义性的。
文法的二义性与语言的二义性是两个不同的概念。
任何正规文法都是上下文无关文法。
正规文法对规则的限制比上下文无关文法对规则的限制要多一些。
二、选择题（从各题的4个答案中选出一个或多个正确的答案写在横线上）
（1） 一般程序设计语言的描述都涉及（
）3个方面。
D 基本符号的确定
（2）为了使编译程序能对程序设计语言进行正确的翻译，必须采用（　　　　）方法定义程序设计语言。
Ａ　非形式化　
Ｂ　自然语言描述问题　　　Ｃ　形式化　
D自然语言和符号体系相结合
（3） 设x是符号串的幂运算 x0=（
（4）设A是符号串的集合，则A*=（
A1∪A2∪…∪AN∪…
A0∪A1∪A2∪…∪AN∪…
（5）字母表中的元素可以是（
B字母和数字
D字母、数字和其他符号
（6） 文法用来描述语言的语法结构，它由如下4个部分组成：（
）和文法开始符号。
A文法终结符集合
B 文法规则的集合
C 文法非终结符集合
D字母数字串
（7）在规则中，符号“→”（：：=）表示（
（8）在规则中，符号“|”表示（
D 定引导开关参数
（9）设文法G[E]的规则如下：
A→A1|A0|Aa|Ac|a|b|c
,该文法的句子是下列符号串（
(10) 如果在推导过程中的任何一步α=&β,都是对α中的最右非终结符进行替换，则称这种推导为（
A．直接推导
B.最右推导 C. 最左推导
D.规范推导
（11）描述语言L={ambn|n≥m≥1}的文法为（
正在加载中，请稍后...LR分析法的LR(0)分析表的构造_百度知道
LR分析法的LR(0)分析表的构造
我有更好的答案
顾名思义，LR(0)分析就是LR(K)分析当K=0的情况，亦即在分析的每一步，只要根据当前的栈顶状态 (或者说根据当前分析栈中已移进或归约出的全部文法符号)就能确定应采取何种分析动作，而无须向前查看输入符号。为了给出构造LR分析表的算法，我们首先需要引入一些非常重要的概念和术语。 由例4?6对输入串“a,b,a”的分析过程容易看出，如果所分析的输入串没有语法错误，则在分析的每一步，若将分析栈中已移进和归约出的全部文法符号与余留的输入符号串拼接起来，就形成了所给文法的一个规范句型。换言之，也就是在分析的每一步，如输入串已被扫视的部分无语法错误，则当前分析栈中的全部文法符号应当是某一规范句型的前缀。而且还不难看出，此种规范句型的前缀决不会含有句柄右边的任何符号，这是因为一旦句型的句柄在栈的顶部形成，将会立即被归约之故。以后，我们将把规范句型具有上述性质 (即不含句柄之右的任何符号)的前缀称为它的活前缀。例如，对于文法G[L]的规范句型“E,b,a” (见表412分析过程第5步)，其句柄为“b”，栈中的符号串为“E，b”，此句型的活前缀为ε，“E”，“E，”，“E,b”等。由此可见，一个LR分析器的工作过程，实质上也就是一个逐步产生 (或识别)所给文法的规范句型之活前缀的过程。同时，在分析的每一步，分析栈中的全部文法符号 (如果输入串无语法错误)应是当前规范句型的活前缀，并且与此时的栈顶状态相关联。因此，我们自然会想到，如果能构造一个识别所给文法的所有活前缀的有限自动机，那么就能很方便地构造出相应的LR分析表来。稍后我们将讨论这一问题。 上面我们已经说过，在一个规范句型的活前缀中决不含有句柄右边的任何符号。因此，活前缀与句柄的关系不外下述三种情况：(1) 其中已含有句柄的全部符号 (句柄的最右符号即为活前缀的最右符号)；(2) 其中只含句柄的一部分符号 (句柄开头的若干符号与活前缀最右的若干个符号一致)；(3) 其中全然不含有句柄的任何符号。第一种情况表明，此时某一产生式A→β的右部符号串β已出现在栈顶，因此相应的分析动作应是用此产生式进行归约。第二种情况意味着形如A→β1β2的产生式的右部子串β1已出现于栈顶，正期待着从余留输入串中看到能由β2推出的符号串。而第三种情况则意味着期望从余留输入串中能看到由某一产生式A→α的右部，即α所推出的符号串。为了刻画在分析过程中，文法的一个产生式右部符号串已有多大一部分被识别，我们可在该产生式的右部的某处加上一个圆点“·”来指示位置。例如，对于上述三种情况，标有圆点的产生式分别为A→β·，A→β1·β2以及A→·α。我们把右部某位置上标有圆点的产生式称为相应文法的一个LR(0)项目。特别，对形如A→ε的产生式，相应的LR(0)项目为A→·。显然，不同的LR(0)项目反映了分析过程中栈顶的不同情况。下面我们就会看到，文法的全部LR(0)项目，将是构造识别其全部活前缀的有限自动机的基础。 在作出文法的全部LR(0)项目之后，现在用它们来构造识别全部活前缀的DFA。这种DFA的每一个状态由若干个LK(0)项目所组成的集合 (称为项目集)来表示。下面以例4?7所给出的文法为例来说明构造此种DFA的方法。首先，我们用I0表示这个DFA的初态，它预示着分析过程的开始，并且期待着将给定的输入符号串逐步归约为文法的开始符号S′。或者反过来说，我们所期待的是，从使用产生式S′→S开始，能够逐步推导出所给的输入符号串。因此，我们应将项目S′→·S列入状态I0中。换言之，也就是我们期待着将要扫视的输入串正好就是能由S推出的任何终结符号串。然而，由于不能从输入串中直接读出非终结符号S，因此我们也应当把项目S→·A以及S→·B列入到I0中。由于A和B同样是非终结符号，所以又应当将A→·aAb，A→·c和B→·aBb，B→·d列入I0中。由于最后列入I0的项目中，圆点之后都是终结符号，故I0已经“封闭”，构造项目集I0宣告结束。这样，表示初态的项目集I0由如下的项目组成：I0: S′→·SS→·AA→·aAbS→·BB→·aBbB→·dA→·c我们将项目S′→·S称为项目集I0的基本项目。上述从项目S′→·S出发构造项目集I0的过程，可用一个对其基本项目集{S′→·S}的闭包运算，即CLOSURE({S′→·S})来表示。一般地，设I为一项目集，则构造I的闭包CLOSURE(I)的算法如下：(1) I中每一项目都属于CLOSURE(I)；(2) 若形如A→α·Xβ的项目属于CLOSURE(I)，且X为非终结符号，则文法中任何X产生式的一切圆点在最左边的项目X→·γ也都属于CLOSURE(I)；(3) 重复上述过程，直至不再有新的项目加入CLOSURE(I)为止。有了初态I0之后，我们来说明如何确定从I0可能转移到的下一个状态。设X为一个文法符号 (终结符号或非终结符号)，若I0中有圆点位于X左边的项目A→α·Xβ (其中α可以为ε)，则当分析器从输入串识别出 (即移进或归约出)文法符号X后，分析器将进入它的下一个状态。设此状态为Ii，显然Ii中必含有全部形如A→αX·β的项目，我们将这样的项目称为A→α·Xβ的后继项目。对于每一文法符号X，如果存在这样的后继项目，则可能不止一个，设其组成的集合为J,J中的每个项目也就是项目集Ii的基本项目。因此，按照与上面构造项目集I0相类似的讨论，我们就有Ii=CLOSURE(J)为了指明Ii是“I0关于文法符号X的后继状态”这一事实，我们可定义一个状态转移函数GO(I,X)=CLOSURE(J)其中，I为当前状态，X为文法符号，J为I中所有形如A→α·Xβ的项目的后继项目所组成的集合，而CLOSURE(J)就是项目集I (即状态I)关于X的后继项目集 (即后继状态)。例如，对于上例，我们有：I1=GO(I0,S)=CLOSURE({S′→S·})={S′→S·}I2=GO(I0,A)=CLOSURE({S→A·})={S→A·}I3=GO(I0,B)=CLOSURE({S→B·})={S→B·}I4=GO(I0,a)=CLOSURE({A→a·Ab,B→a·Bb})={A→a·Ab, B→a·Bb, A→·aAb, B→·aBb, A→·c, B→·d}I5=GO(I0,c)=CLOSURE({A→c·})={A→c·}I6=GO(I0,d)=CLOSURE({B→d·})={B→d·}请注意，由于I0中无圆点在b之前的项目，故GO(I0,b)无定义。这样，我们求出了I0的全部后继项目集I1,I2,I3,I4,I5,I6。容易看出，由于I1,I2,I3,I5,I6诸项目集中的项目均无后继项目，因此它们都没有后继状态。对于项目集I4，我们再仿此求出它的后继状态，这些后继状态是：I7=GO(I4,A)=CLOSURE({A→aA·b})={A→aA·b}I9=GO(I4,B)=CLOSURE({B→aB·b})={B→aB·b}此外，由于GO(I4,a)=I4GO(I4,c)=I5GO(I4,d)=I6故它们均不产生新的项目集。最后，再求出I7,I9的后继项目集。它们分别是I8=GO(I7,b)=CLOSURE({A→aAb·})={A→aAb·}I10=GO(I9,b)=CLOSURE({B→aBb·})={B→aBb·}由于I8和I10已无后继项目集，所以至此我们已求出所给文法G[S]的全部项目集I0~I10，通常，我们将这些项目集的全体称为文法G[S]的LR(0)项目集规范族，并记为C={I0,I1,I2,I3,…,I10}于是，我们所要构造的识别文法G[S]全部活前缀的DFA为M=(C,V,GO,I0,C)其中： M的状态集也就是文法的LR(0)项目集规范族C={I0,I1,…,I10}；M的字母表也就是文法的字汇表V={S′，S，A，B，a,b,c,d}；M的映像也就是如上定义的状态转换函数GO；M的终态集也是C，这表明M的每一状态都是它的终态。对于上述文法G[S]，如上构造的识别其全部活前缀的DFA的状态转换图如图416所示。由于状态转换图416中的每一个状态都是终态，因此在上述DFA工作的过程中，从初态I0出发，沿着有向边所指示的方向前进，可以使DFA在所经历的任何状态上中止它的工作。当DFA到达某一状态时，我们把从初态I0出发，到达该状态所经过的全部有向边上的标记符号依次连接起来，就得到了DFA在到达该状态时，所识别出的某规范句型的一个活前缀。例如：当上述DFA处于初态I0时，它所识别的活前缀为ε；当M处于状态I3时，它所识别的活前缀为B；当M处于I4时，它所识别的活前缀为aa*；而达到I9时，它所识别的活前缀为aa*B等等。需要注意的是，对那些只含有归约项目的项目集，即M的I1,I2,I3,I5,I6,I8和I10，当M到达这些状态时，表明活前缀中已含有相应句柄的全部符号 (即句柄已在栈顶形成)，因此，我们将这些状态称为句柄识别状态。特别是当M处于状态I1时，M所识别的活前缀为S，这意味着已将所给的输入串归约为S，如果再按产生式S′→S归约一步，就得到了拓广文法G′的开始符号S′。因此，我们将状态I1称为“接受状态”，它预示着对输入串的分析已成功地完成。对于一个给定文法G的拓广文法G′，当识别它的全部活前缀的DFA作出之后，我们就可据此构造相应的LR(0)分析表了。然而，应当首先注意的是，用前述方法所构造的每一个LR(0)项目集，实质上表征了在分析过程中可能出现的一种分析状态；再根据前面对LR(0)项目的分类，项目集中的每一个项目又与某一种分析动作相关联，因此，我们自然会提出这样的要求，即每一项目集中的诸项目应当是相容的。所谓相容，是指在一个项目集中，不出现这样的情况：(1) 移进项目和归约项目并存；(2) 多个归约项目并存。如果一个文法G满足上述条件，也就是它的每个LR(0)项目集中都不含冲突项目，则称G为LR(0)文法。显然，只有当一个文法是LR(0)文法时，才能构造出不含冲突动作的LR(0)分析表来。从前面的讨论和分析，我们将不难得出构造LR(0)分析表的算法。为方便起见，我们用整数0，1，2，…表示状态I0,I1,…，而且如表411那样，也将GOTO子表中有关终结符号的各列并入ACTION子表相应的各列中去，此外，算法中形如sj和rj等记号的含义同前，此算法如下：(1) 对于每个项目集Ii中形如A→α·Xβ的项目，若GO(Ii,X)=Ij，且X为一终结符号a时，置ACTION[i,a]=sj。但若X为非终结符号时，则仅置GOTO[i,X]=j。(2) 若归约项目A→α·属于Ii，设A→α为文法的第j个产生式，则对文法的任何终结符号或句子的右界符# (将它们统一地记为a)，置ACTION[i,a]=rj。(3) 若接受项目S′→S·属于Ii，则置ACTION[i,#]=acc。(4) 在分析表中，凡不能按上述规则填入信息的元素，均置为“出错”。
为您推荐：
其他类似问题
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。