2013-2014编译原理考试

资源描述

《2013-2014编译原理考试》由会员分享，可在线阅读，更多相关《2013-2014编译原理考试（39页珍藏版）》请在金锄头文库上搜索。

1、编译程序是对高级语言程序进行翻译在规范规约中，用句柄来刻画可规约串动态存储分配是指在运行阶段为源程序的数据对象分配存储空间词法分析的输出结果是单词的种别编码和自身值正规式等价是指所识别的语言集相等优化可生成运行时间短且占内存少的代码程序【一】文法和语言编译程序和翻译程序的区别编译程序是整体编译完了，生成目标代码，再一次性执行。解释程序是一边解释，一边执行，并不形成目标程序。文法文法是描述语言的语法结构的形式规则（即语法规则）。文法 G:定义为四元组（VN,VT,P,S）VN 为非终结符号的集合， VT 为终结符号的集合， P 为产生式的集合， S 为开始符号，是一个非终结符，至少要在一条规则

2、中作为左部出现。文法分类0 型文法短语文法递归可枚举语言1 型文法上下文有关文法上下文有关语言2 型文法上下文无关文法上下文无关语言3 型文法正规文法正规语言句型假定 G 是一个文法，S 是它的开始符号。如果 S*(表示从 S 出发，经 0 步或若干步可推出），则称是一个句型。句子仅含终结符号的句型是一个句子。语言由文法 G 生成的语言记为 L(G),它是文法 G 的一切句子的集合所有的句子都是规范句型所有的句型不一定是规范句型推导直接推导规约直接规约直接推导：仅当 A 是一个产生式，有 v =A，w= ，A ，称 v 直接推导到 w, 记作 v w，也称 w 直接归

3、约到 v。最左推导又称为规范推导。 G：S0S1，S010S1 00S1100S11 000S111000S111 00001111S 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 cAdA abA a识别输入串 w=cabd 是否为该文法的句子规约过程构造的推导： cAd cabd S cAd短语语法树中一棵子树的所有叶子从左向右排列起来形成一个相对于子树根的短语。直接短语只有父子两代的短语为直接短语。句柄一个句型的分析树中，最左边的只

5、有父子两代的子树的叶子从左向右排列起来形成构成此句型的句柄。已知一上下文无关文法，对给定的句型，画出语法树，并求其短语，直接短语以及句柄。例：对于文法 GSS ( L) | aS |aL L, S | S画出句型( S ,(a)的语法树，求某一句型的短语，直接短语，句柄. 短语：( S ,(a)；S ,(a)； (a)；a；S直接短语：S；a句柄： S画出语法树EE+E|E*E|(E)|i,关于（i*i+i)的语法树E(根 ) （ E ） E + E E * E i i i E(根 ) （ E ） E * E i E + E i i 已知语言写出描述该语言的文法试构造生成语言 L=anbn

7、例如 G： S0S1， S01S 01 S0S1 0011 S 0S1 00S11=000111 语言为 01 个数相等，并且 0 在前，1 在后 L（G）=0 n1n|n=12) 已知语言写出描述该语言的文法一般所写的文法是上下文无关文法和正规文法，用集合的形式表示语言若是这一类的题目先记住几个基本的情况，若是复杂的都可以分解成基本的情况。一般给定集合是无限集，文法都应是递归文法，可以是直接递归也可以是间接递归。基本的有：a n 若生成多个 a，用递归文法表示则为：A-aA，递归有结束的时候，结束的写法看 n 的值：若 n 为 0，即有 0 个 a，即为，A- 若 n 为 1，即有 1 个

8、 a，即为 a，A-a若 n 为 2，即有 2 个 a，即为 aa，A- aaa nbn生成 n 个 a，n 个 b 且 a 在 b 之前，则每一次推导都要产生一个 a 和一个 b，才能保证 ab 的个数相等，若用 A 作为非终结符，右部 A 不能在 ab 之前 A-Aab，或在 ab 之后A-abA，这样生成的符号串就是 abab,所以只能在 ab 之间。所以为：A-aAb，然后看 n的值：若 n 为 0，即有 0 个 ab，即为，A- 若 n 为 1，即有 1 个 a,一个 b，即为ab，A-ab rrt 若 r 是a,b*，r t 是 r 的逆，第一位和最后一位相同，第二位和倒数第二位

9、相同，。所以先生成第一个和最后一个，然后依次生成第二位和倒数第二位。因为第一位和最后一位相同，同为 a 或同为 b，A-aAa|bAb,这样能保证从后部分是前部分的逆。递归结束看 rt 和 r 之间的符号，在这里没有为，所以为 A-；若改为rar t，r t 和 r 之间为 a，即为 A-a其余的情况可分解成以上三种情形。例 1：试构造生成语言 L=anbnci|n1, i 0的文法分析：a nbnci 可以进行分解让 A 生成 anbn，B 生成 ci 符号串 anbnci 是 AB 连接后的结果。n1 所以 A-aAb|ab ，i 0 所以 B-cB| 也可写成 B-Bc|。解：S-A

10、B A-aAb|ab B-cB|例 2：已知语言 L=anbbn| n 1, 写出产生 L 的文法。分析：先生成 anbn，当 n=1 符号串为：abb解：S-aSb|abb例 3：请给出描述语言=a 2m+1 b m+1 | m=0a 2m b m+2| m=0的文法分析：a 2m+1 b m+1 可以看成 aa2m b mb,而 a2m b m 可以用 A-aaAb 生成，a 2m b m+2 可以看成 a2m b mbb,而 a2m b m 也可以用 A-aaAb 生成，若 m=0，a 2m b m 为空串所以为 A-，aa 2m b mb 是 aAb, a2m b mbb 是 Abb

11、；解:s-aAb|AbbA-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| 用自然语言描述语言这种情况一般常根据经验来构造文法。例：写一个文法，使其语言是奇数集，且每个奇数不以 0 开头。N-A|MAM-B|MD

12、A-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） a nbnambm| n，m=0 （2） 1 n0m 1m0n| n，

13、m=0(3) a2n+1|n=0(4) a2n+1bnci|n0,i=0答： (1)SAAAaAb| (2) S1S0|A A0A1|(3) SaaS|a(4) SaABAaaAb|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 E EOE EOa E* a EOE* a EOa * a E+ a * a a + a * a最右推导 2 E

展开阅读全文