首页 > 试题广场 >

考虑左递归文法S-Aab A-AcSde，消除左递

[单选题]

考虑左递归文法S->Aa|b A->Ac|Sd|e，消除左递归后应该为（）？

S->Aa|b			
 A->bdA’|A’			  
 A'->cA’|adA’|e

S->Ab|a
A->bdA’|A’
A’->cA’|adA’|e

S->Aa|b			
A->cdA’|A’			  
 A’->bA’|adA’|e

S->Aa|b
A->bdA’|A’
A’->caA’|dA’|e

推荐

小小

e 为空集,消除左递归,即消除有 A->A*的情况,消除做递归的一般形式为

U = Ux1 | U x2 |y1|y2

U = y1U' |y2 U' U' = x1

U'|x2U'|e

A = Ac|Aad|bd|e

A =bdA'|A'

A'= cA'|adA'|e

编辑于 2015-09-05 13:20:12 回复(0)

justalittlenoob

S->Aa | b

A->Ac | Sd | e

将S带入A：

A->Ac | Aad | bd | e

直接消除左递归：

A->bdA' | A'

A'->cA' | adA'|e

结果等于上面俩，再算上S,其实e应该是希腊字母ε，这出题的人也够糊弄的

发表于 2015-09-05 19:56:54 回复(0)

何文婷

http://www.cnblogs.com/nano94/p/4020775.html

很详细的解析

发表于 2015-09-06 00:41:26 回复(0)

skyskyuuu

为什么是S->Ab|a，而不是S->Aa|b,求解释

发表于 2015-09-07 21:44:59 回复(0)

提交观点

问题信息

编译和体系结构腾讯

来自：腾讯2013研发工程师笔试题

上传者：星野

难度：

4条回答 555收藏 19613浏览

扫一扫，把题目装进口袋