- 1、本文档共10页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
可编辑版
PAGE
Word完美格式
一、填空题|(每题4分,共20分)
1. 乔母斯基定义的3型文法(线性文法)产生式形式 A?Ba|a,或A?aB|a,A,B∈Vn,a,b∈Vt 。
2.语法分析程序的输入是 单词符号,其输出是 语法单位 。
3 型为 B ? .aB 的LR(0)项目被称为 移进 项目,型为 B ? a.B 的LR(0)项目被称为 待约 项目,
4.在属性文法中文法符号的两种属性分别为 继承属性 和 综合属性 。
5、运行时存贮管理方案有 静态存储分配、动态存储分配 和 堆式存储分配 和方案。
二.已知文法 G(S)
(1) E ? T | E+T
(2) T ? F | F*F
(3) F ? (E)| i
(1)写出句型(T*F+i)的最右推到并画出语法树。(4分)
(2)写出上述句型的短语,直接短语和句柄。(4分)
答:(1)最右推到(2分)
E == T == F == (E) == (E+T) == (E+F) == (E+i) == (T+i) == (T*F+i)
(2) 语法树(2分)
(3)(4分)
短语: (T*F+i) ,T*F+i ,T*F , i
直接短语:T*F , i
句柄:T*F
三. 证明文法 G(S) : S ? SaS |ε 是二义的。(6分)
答:句子 aaa对应的两颗语法树为:
因此,文法是二义文法
四.给定正规文法G(S):
(1) S ? Sa | Ab |b
(2) A ? Sa
请构造与之等价的DFA。(6分)
答:对应的NFA为: (6分)
状态转换表:
a
b
{F}
Φ
{S}
{S}
{S,A}
Φ
{S,A}
{S,A}
{S}
五. 构造识别正规语言b*a(bb*a)*b* 最小的DFA(要求写出求解过程)。(15分)
答:(1)对应的NFA(5分)
(2)将(1)所得的NFA确定化:(5分)
a
b
{0}
{1,3}
{0}
{1,3}
Φ
{2,3}
{2,3}
{1,3}
{2,3}
(5分)
六. 已知文法 G(S) :
(1) S ? ^ | a | (T)
(2) T ? T,S | S
试:(1)消除文法的左递归;(4分)
(2)构造相应的first 和 follow 集合。(6分)
答:(1)消除文法的左递归后文法 G’(S)为:
(1) S ? ^ | a | (T)
(2) T ? ST’ | S
(3) T’ ? ,ST’ |ε (4分)
(2)(6分)
first
follow
S
a ^ (
# , )
T
a ^ (
)
T’
, ε
)
七. 已知文法 G(S) :
(1) S ? SiA | A
(2) A ? A+B | B
(3) B ? A* | (
试构造非终止符的firstVT和lastVT集合。(10分)
答:(10分)
firstVT
lastVT
S
i , + , * , (
i , + , * , (
A
+ , * , (
+ , * , (
B
* , (
* , (
FollowS#
Follow
S
#
B
a,b,#
(1) S ? B B
(2) B ? a B
(3) B ? b
的follow集合如表:
试:(1)给出该文法的LR(0)项目集规范族划分;
(2)填写相应的SLR(1)的分析表。(15分)
答:(1)LR(0)项目集规范族划分(8分)
I
I0
S’? .S
S ? .BB
B ? .aB
B ? .b
? I1
? I2
--? I3
--? I4
S
B
a
b
I1
S’? S.
I2
S ? B.B
B ? .aB
B ? .b
? I5
--? I3
--? I4
B
a
b
I3
B ? a.B
B ? .aB
B ? .b
? I6
--? I3
--? I4
B
a
b
I4
B ? b.
I5
S ? BB.
I6
B ? aB.
(2) SLR(1)分析表(7分)
状态
Action
Goto
a
b
#
S
B
0
S3
S4
1
2
1
Acc
2
S3
S4
5
3
S3
S4
6
4
R3
R3
R3
5
R1
6
R2
R2
R2
九.设某语言的not-then-else 语句的语法形式为:S ? not E then S1
其语义解释为:
针对自上而下的语法分析器,
(1) 分段产生式;(3分)
(2) 写出每个产生式对应的语义动作。(7分)
答:(1)分段产生式(3分)及
您可能关注的文档
最近下载
- 上海市外籍人口空间分布历史变迁研究.pdf
- 至为芯科技IP5356规格书资料.pdf
- 学习党的二十届三中全会精神应知应会知识测试题AB卷(附答案).docx VIP
- 进位制-(公开课).ppt VIP
- 船舶电气作业安全操作规程.docx
- DB37T5267-2023钢丝网架(片)板现浇混凝土复合保温体系应用技术标准 .docx VIP
- 2024安全生产标准化管理体系新旧版本对比汇总版.docx
- 国家电网计算机类笔试学习资料-计算机网络.pdf VIP
- 人教版初中数学第十四章《整式的乘法与因式分解》解答题提高训练 (39)(含答案解析).docx VIP
- 公务员考试常识习题(带答案).doc VIP
文档评论(0)