编译原理练习(3-4章)含答案.ppt

编译原理练****br/>2
文法和语言
符号和符号串
文法的类型
文法和语言的形式化定义
句型分析
语法树
文法和语言的二义性
上下文无关文法
文法的定义
推导的定义
语言的定义
第三章
字母表和符号串
符号串的运算
集合的闭包运算
第三章
1、作业P48 第5题写一文法,使其语言是偶正整数的集合。要求: 允许 0 打头。
思路:首先根据集合的描述设计几个句子,然后从句子中找出规律(或共性),把它们的性质用产生式表示出来。
提示:(1)生成的偶正数应不包括,若干个0。
(2)将偶正数分为两类:一类为允许若干个0(0个数>=0)后跟不以0开头的偶正数;一类为允许若干个0后跟2|4|6|8的偶正数(如0002,即不允许只含有若干0 )。
2、为只包含数字、, 的表达式,例如 9  2  5等构造一个文法,使得和运算满足右结合, 的运算优先级高于。
提示:结合性和运算优先性可以根据语法树的层次考虑。进而思考左递归产生式与运算符的结合性的关系。
3、一个上下文无关文法生成句子 abbaa 的推导树如下:
(1)给出串 abbaa 最左推导、最右推导。
(2)该文法的终结符、非终结符、产生式集合 P 可能有哪些元素?
(3)找出该句子的所有短语、直接短语、句柄。
提示:知识点:语法树的构造,文法的组成,短语等概念。
4、给出生成下述语言的三型文法:{anbmck|n, k>=1,m>0 }
提示:(1)三型文法中产生式的特点
(2)可参考P49 第16题
词法分析
自动构造工具
{正规集}
正规式
有穷自动机(NFA DFA)
正规文法
第四章知识结构
①
⑤
⑥
②
③
④
1、已知正规式b(ab)*和(ba)*b
(1)分别构造上述两个正规式相应的DFA,
(2) 将(1)构造的DFA最小化,
(3)利用DFA证明b(ab)*=(ba)*b
(4)构造该语言的正规文法。
提示:
使用的知识点:正规式 NFA,NFADFA,DFA的最小化,DFA 正规文法。
由转化得到的相同的最小化DFA,进而证明两个正规式等价。
2、(1)由偶数个0和奇数个1构成的所有01串的DFA。
(2)写出由0和1的个数都是偶数的01串的正规式。
提示:见下页PPT