编译原理期末复习

1、编译原理期末复习编译原理期末复习第3-4章基本概念和考试模块出题方法（包括实验）考试方法考试方法 根据文法写出语言根据文法写出语言 根据语言写出文法（上下文无关文法或根据语言写出文法（上下文无关文法或正规文法，同时要消除有害规则和多余正规文法，同时要消除有害规则和多余规则）规则） 容易出错的地方：容易出错的地方： 文法的写法（和正规式的区别、大小写规定）文法的写法（和正规式的区别、大小写规定） 语言的写法（文字表述、集合）语言的写法（文字表述、集合）根据文法写出语言根据文法写出语言例：文法例：文法G G：S0S1， S01问：它的语言是什么？问：它的语言是什么？答：答：L(G)=0n1n|n1

2、点击看答案根据语言写出文法根据语言写出文法 已知语言为已知语言为 0n1n|n1，写出能生成该写出能生成该语言的一个上下文无关文法。语言的一个上下文无关文法。答：文法为：答：文法为：GSGS：S0S1S01点击看答案考试方法考试方法 根据正规式写出语言（正规集）根据正规式写出语言（正规集） 根据语言（正规集）写出正规式根据语言（正规集）写出正规式 根据根据DFA的状态图判断字符串能否被接受的状态图判断字符串能否被接受 根据正规式画出状态图根据正规式画出状态图 根据状态图写出正规式根据状态图写出正规式 将将NFA化为化为DFA（给出过程，要求完成最后一给出过程，要求完成最后一步）步） 将将DFA

3、化简（给出足够的提示）化简（给出足够的提示） 根据正规式或状态图查找字符串根据正规式或状态图查找字符串 根据根据DFA的转换函数或状态表画出状态图（反的转换函数或状态表画出状态图（反之亦可）之亦可）根据正规式写出语言根据正规式写出语言 例例. =l，d，正规式正规式r=l(l d) 定义的正定义的正规集是什么？规集是什么？答：正规集是答：正规集是: 以以l开头，后跟任意多个开头，后跟任意多个l和和d，组成的串的集合。组成的串的集合。（比较：（比较：l,ll,ld,ldd, （标识符）标识符）点击看答案根据语言写出正规式根据语言写出正规式 写出标识符的正规式，其中设字母为写出标识符的正规式，其中

4、设字母为l，数字为数字为d，标识符长度不受限制。标识符长度不受限制。点击看答案答：正规式为答：正规式为 l(l d) 根据DFA的状态图判断字符串能否被接受 例.字符串baab能否被下面的DFA接受bSUVQaaaba，bb点击看答案答：能被接受。根据正规式画出状态图 正规式正规式R= l(l d) 相应的状态图为：相应的状态图为：SQl,dl根据状态图写出正规式例：SQl,dl求正规式求正规式R答：答：R= l(l d) 点击看答案实验考试方法 课程设计有关问题的思考 程序的功能，主要函数 程序的设计方法文法和语言（例1）1.1. G G：S0S1， S012. G: S Ac|Ac|aBa

5、B, A, Aabab, B, Bbcbc3. G: S cAdcAd, A, Aabab, Aa, Aa4. GN: N D|ND, D0|1|2|D|ND, D0|1|2|9|95.5. G: EE+E,EE-E,EEG: EE+E,EE-E,EE* *E,E(E),EiE,E(E),Ei(i(i为数值为数值) )6.6. 略略上一页答案上一页答案1.L(G)=0n1n|n12.L(G)=abc3.L(G)=cabd, cad4.L(G)=由由0-9组成的数字串组成的数字串5.包含数值、加、减、乘、括号的表达式包含数值、加、减、乘、括号的表达式6.各种数的集合：各种数的集合：1.偶正偶数的

6、集合偶正偶数的集合(1)允许允许0开头开头;(2)不许不许0开头开头2.自然数、正整数、被自然数、正整数、被5等整除的数、某几位或位数等整除的数、某几位或位数确定的数、含有符号的数、小数等确定的数、含有符号的数、小数等文法和语言（例2） G(E):E ETP|TT TFM|FF a|b|cP +|-M *|/上一页答案上一页答案 以a,b,c为操作数，以+,-,*,/为操作符的表达式的逆波兰表示文法和语言（例3） anbnambm|n,m0 1n0m1m0n|n,m0 WaWr|W属于0|a*, Wr表示W的逆上一页答案上一页答案 GS:SABAaAb|BaBb|GS:S1S0SAA0A1|GS:S 0S0|aSa|a有穷自动机（例1） 已知DFA M=(S,U,V,Q,a,