《2013-2014编译原理考试.doc》由会员分享，可在线阅读，更多相关《2013-2014编译原理考试.doc（39页珍藏版）》请在金锄头文库上搜索。
1、编译程序是对高级语言程序进行翻译在规范规约中，用句柄来刻画可规约串动态存储分配是指在运行阶段为源程序的数据对象分配存储空间词法分析的输出结果是单词的种别编码和自身值正规式等价是指所识别的语言集相等优化可生成运行时间短且占内存少的代码程序【一】文法和语言编译程序和翻译程序的区别编译程序是整体编译完了，生成目标代码，再一次性执行。解释程序是一边解释，一边执行，并不形成目标程序。文法文法是描述语言的语法结构的形式规则（即语法规则）。文法G:定义为四元组（VN,VT,P,S）VN为非终结符号的集合， VT为终结符号的集合， P为产生式的集合， S为开始符号，是一个非终结符，至少要在一条规则中作为左部出
2、现。文法分类0型文法 短语文法 递归可枚举语言1型文法 上下文有关文法 上下文有关语言2型文法 上下文无关文法 上下文无关语言3型文法 正规文法 正规语言句型假定G是一个文法，S是它的开始符号。如果S*(表示从S出发，经0步或若干步可推出a），则称a是一个句型。句子仅含终结符号的句型是一个句子。语言由文法G生成的语言记为L(G),它是文法G的一切句子的集合所有的句子都是规范句型所有的句型不一定是规范句型推导 直接推导规约 直接规约直接推导：仅当A 是一个产生式，有v =A，w= ，A ，称v直接推导到w, 记作v w，也称w直接归约到v。最左推导又称为规范推导。 G：S0S1，S01 0S1
3、00S11 00S11 000S111 000S111 00001111 S 0S1语法树语法树的根结由开始符号所标记。随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结就产生了下一代新结。每个新结和其父亲结间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左至右排列起来就是一个句型。二义文法如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。也就是说，若一个文法存在某个句子，它有两个不同的最左（最右)推导，则这个文法是法是二义的。 文法的二义性证明：找出一个句子，它有两个不同的最左推导或最右推导题型：给出上下文无关文法句型，
4、写出最左或最右推导过程EE+E|E*E|(E)|,关于（i*i+i)的推导E (E) (E*E) (i*E) (i*E+E) (i*i+E) (i*i+i)E(E)(E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i)判断输入串是不是文法的句子例：文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子规约过程构造的推导： cAd cabd S cAd画出语法树EE+E|E*E|(E)|i,关于（i*i+i)的语法树短语语法树中一棵子树的所有叶子从左向右排列起来形成一个相对于子树根的短语。直接短语只有父子两代的短语为直接短语。句柄一个句型的分析树中，最左
5、边的只有父子两代的子树的叶子从左向右排列起来形成构成此句型的句柄。已知一上下文无关文法，对给定的句型，画出语法树，并求其短语，直接短语以及句柄。例：对于文法GS S ( L) | aS |a L L, S | S画出句型( S ,(a)的语法树，求某一句型的短语， 直接短语， 句柄. 短语：( S ,(a)；S ,(a)； (a)；a；S直接短语：S；a句柄： S已知语言写出描述该语言的文法试构造生成语言L=anbnci|n1, i 0的文法分析：anbnci可以进行分解让A生成anbn，B生成ci符号串anbnci是AB连接后的结果。n1所以A-aAb|ab ，i 0所以B-cB|也可写成B
6、-Bc|。解：S-AB A-aAb|ab B-cB|已知文法写出该文法所生成的语言.已知文法GA=(A,a,b,AbA|a,A)所生成的语言是什么？ bna|n=01、语言和文法的相互转换1） 已知文法写出该文法所生成的语言： 语言是有穷集：通过从开始符号的推导出所有的句子，所有句子的集合即为所求的语言 语言是无穷集：通过从开始符号的推导出几个的句子，总结句子的特点，将特点描述出来。例如G： S0S1， S01 S 01 S0S1 0011 S 0S1 00S11=000111 语言为01个数相等，并且0在前，1在后L（G）=0n1n|n=12) 已知语言写出描述该语言的文法一般所写的文法是上
7、下文无关文法和正规文法，用集合的形式表示语言 若是这一类的题目先记住几个基本的情况，若是复杂的都可以分解成基本的情况。 一般给定集合是无限集，文法都应是递归文法，可以是直接递归也可以是间接递归。基本的有： an 若生成多个a，用递归文法表示则为：A-aA，递归有结束的时候，结束的写法看n的值：若n为0，即有0个a，即为，A- 若n为1，即有1个a，即为a，A-a若n为2，即有2个a，即为aa，A-aaanbn生成n个a，n个b且a在b之前，则每一次推导都要产生一个a和一个b，才能保证ab的个数相等，若用A作为非终结符，右部A不能在ab之前A-Aab，或在ab之后A-abA，这样生成的符号串就是
8、abab,所以只能在ab之间。所以为：A-aAb，然后看n的值：若n为0，即有0个ab，即为，A- 若n为1，即有1个a,一个b，即为ab，A-ab rrt 若r是a,b*，rt是r的逆，第一位和最后一位相同，第二位和倒数第二位相同，。所以先生成第一个和最后一个，然后依次生成第二位和倒数第二位。因为第一位和最后一位相同，同为a或同为b，A-aAa|bAb,这样能保证从后部分是前部分的逆。递归结束看rt和r之间的符号，在这里没有为，所以为A-；若改为rart，rt和r之间为a，即为A-a其余的情况可分解成以上三种情形。例1： 试构造生成语言L=anbnci|n1, i 0的文法分析：anbnci
9、可以进行分解让A生成anbn，B生成ci符号串anbnci是AB连接后的结果。n1所以A-aAb|ab ，i 0所以B-cB|也可写成B-Bc|。解：S-AB A-aAb|ab B-cB|例2： 已知语言L=anbbn| n 1, 写出产生L的文法。 分析：先生成anbn，当n=1符号串为：abb解：S-aSb|abb例3：请给出描述语言=a2m+1 b m+1 | m=0a2m b m+2| m=0的文法分析：a2m+1 b m+1可以看成aa2m b mb,而a2m b m可以用A-aaAb生成，a2m b m+2可以看成a2m b mbb,而a2m b m也可以用A-aaAb生成，若m=
10、0，a2m b m为空串所以为A-，aa2m b mb 是aAb, a2m b mbb是Abb；解:s-aAb|Abb A-aaAb|例4：已知语言L=x | xa,b,c*,且x重复排列是对称的（aabcbaa,aabbaa,等） 写出该语言的文法。 分析：若符号串的长度为偶数，则后半部分是前半部分的逆，所以为S-aSa|bSb|cSc|若符号串的长度为奇数，则除中间的外，中间字符的后半部分是中间字符前半部分的逆，而中间的字符可以为a，b，c所以文法为：S-aSa|bSb|cSc|a|b|c 解: S-aSa|bSb|cSc|a|b|c| 用自然语言描述语言这种情况一般常根据经验来构造文法。
11、例：写一个文法，使其语言是奇数集，且每个奇数不以0开头。 N-A|MAM-B|MDA-1|3|5|7|9B-1|2|3|4|5|6|7|8|9D-0|B1.已知文法GA=(A,a,b,AbA|a,A)所生成的语言是什么？ bna|n=02.写一文法，使其语言是偶正整数的集合。 要求：(1) 允许0打头； (2)不允许0打头。答 ：(1)允许0开头的偶正整数集合的文法ENT|DTNT|DND|1|3|5|7|9D0|2|4|6|8(2)不允许0开头的偶正整数集合的文法ENT|D TFT|G ND|1|3|5|7|9D2|4|6|8FN|0GD|03.给出生成下述语言的上下文无关文法：（1） an
12、bnambm| n，m=0 （2） 1n0m 1m0n| n，m=0(3) a2n+1|n=0(4) a2n+1bnci|n0,i=0答： (1)SAA AaAb| (2) S1S0|A A0A1| (3) SaaS|a (4) SaAB AaaAb|aabBcB|4.已知语言L=x | xa,b,c*,且x重复排列是对称的（aabcbaa,aabbaa,等）写出该语言的文法。 SaSa|bSb|cSc|a|b|c|1:证明下述文法GE是二义的。Ea|(E)|EOE O+|-|*|/答：可为句子a+a*a构造两个不同的最右推导:最右推导1 EEOE EOa E* a EOE* a EOa *
13、aE+ a * a a + a * a最右推导2 EEOEEOEOEEOEO aEOE * a EOa * a E+ a * a a + a * a2：令文法GE为： ET|E+T|E-TTF|T*F|T/FF(E)|i 1： 试构造生成语言L=anbnci|n1, i 0的文法解：S-AB A-aAb|ab B-cB|2： 已知语言L=anbbn| n 1, 写出产生L的文法。 解：S-aSb|abb3： 已知文法G=(A,B,C,a,b,c,A,P)其中产生式P由以下组成： A abc A aBbc BbbB Bc Cbcc bC Cb aC aaB aC aa 问：此文法表式的语言是什么？ 解:该题通过推导到的句子的特点进行总结,语言为:anbncn|n=14 请给出描述语言=a2m+1 b m+1 | m=0a2m b m+2| m=0的文法 解:s-aAb|Abb A-aaAb| 5已知文法GS为： SdAB AaA|a BBb
