广工编译原理
编译原理复习例题
2.设有文法G:S→S+S|S*S|i|(S)。 (1)对于输入串i+i*i 给出一个最左推导;
(2)该文法是否是二义性文法?请证明你的结论。 解:(1)i+i*i的最左推导:
S => S+S => i+S => i+S*S => i+i*S
=> i+i*i
(2)该文法是二义性的。因为对于句子
i+i*i可以画出两棵语法树(语法树略)。
3.给出语言{ambmcn|m≥1,n≥0}的上下文无关文法(2型)。 解: G: S→AB|A A→aAb|ab B→cB|c
4.给出语言{abc|k,m,n≥1}的正规文法(3型)。
解: G: A→aA|aB B→bB|bC C→cC|c
5.将文法G改写成等价的正规文法(3型)。
G: S→dAB A→aA|a B→bB|b 解: G: S→dA A→aA|aB B→bB|b
6.构造一文法产生任意长的a,b串,使得
|a|≤|b|≤2|a|
其中,“|a|”和“|b|”分别表示串中的字符a和b的个数。
解:b的个数在a的个数和其2倍之间,串
的结构形如aSBS和BSaS,其中B为1或2个b。故得文法 G: S→aSBS|BSaS|ε B→b|bb
kmn
7.设有字母表{a,b}上的正规式
R=(ab|a)*。
(1)构造R的相应有限自动机; 解:
(2)构造R的相应确定有限自动机;


a


(

3)构造R的相应最小确定有限自动机; 解:对(2)得到的DFA化简,合并状态0和2 为状态2:
a +
(4)构造与R等价的正规文法 解:令状态1和2分别对应非终结符B和A
G: A→aB|a|ε
B→aB|bA|a|b|ε 可化简为: G: A→aB|ε
- 1 -
广工编译原理练习题_工学_高等教育_教育专区。广工编译原理一.填空题: 1-01.编译程序的工作过程一般可以划分为_ __等几个基本阶段,同时还会伴有_ __ 和 . ...
广工编译原理练习题+答案_工学_高等教育_教育专区。广工编译原理一、填空题: 1-01.编译程序的工作过程一般可以划分为 词法分析,语法分析,语义分析,之间代码生成,...
广工编译原理期末试题(精选题集+必考大题_互联网_IT/计算机_专业资料。专门为广工妓院打造的习题集,更正了许多错误,里面有许多经典例题,弄懂了这些题目后考试根本...
广工编译原理复习_工学_高等教育_教育专区。广工编译原理编译原理复习——Always ...P185 编译原理复习 共 16 页第 13 页 ---By Always 麦 大题:1、构造...
广工编译原理试题_工学_高等教育_教育专区。广工...编译原理试题计算机学院___级 题号 一 满分 得分... 2015国家公务员考试备战攻略 2015国考行测模拟试题...
广工编译原理各章练习题_工学_高等教育_教育专区。广工编译原理第三章复习重点:1.文法与语言的对应关系 语言 L(G)=L(G’) 文法 G n {b n>0} B→bB...
广工编译原理真题_工学_高等教育_教育专区。广工编译原理编译原理一【 选择题】... 2014小学教师资格考试《... 2014年幼儿园教师资格考... 2014教师资格中学教育...
广工编译原理考试重点_理学_高等教育_教育专区 暂无评价0人阅读0次下载举报文档 广工编译原理考试重点_理学_高等教育_教育专区。编译原理考试...
广工编译原理试卷A_工学_高等教育_教育专区。广工编译原理编译原理试卷 A 一、 选择题(每空 2 分,共 20 分) 1.一个正规语言只能对应( B )? A 一个正规...
热门文档