资源描述：
《2013-2014编译原理考试》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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
3、：S→0S1，S→010S1Þ00S1100S11Þ000S111000S111Þ00001111SÞ0S1语法树语法树的根结由开始符号所标记。随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结就产生了下一代新结。每个新结和其父亲结间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左至右排列起来就是一个句型。二义文法如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。也就是说，若一个文法存在某个句子，它有两个不同的最左（最右)推导，则这个文法是法是二义的。文法的二义性证明：找出一个句子，它有两个不同的最左推导
4、或最右推导题型：给出上下文无关文法句型，写出最左或最右推导过程E→E+E
5、E*E
6、(E)
7、ｉ, 关于（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ÞcabdSÞcAd画出语法树E→E+E
8、E*E
9、(E)
10、i, 关于（i*i+i)的语法树短语语法树中一棵子树的所有叶子从左向右排列起来形成一个相对于子树根的短语。直
11、接短语只有父子两代的短语为直接短语。句柄一个句型的分析树中，最左边的只有父子两代的子树的叶子从左向右排列起来形成构成此句型的句柄。已知一上下文无关文法，对给定的句型，画出语法树，并求其短语，直接短语以及句柄。例：对于文法G[S]S→(L)
12、aS
13、aL→L,S
14、S画出句型(S,(a))的语法树，求某一句型的短语，直接短语，句柄.短语：(S,(a))；S,(a)；(a)；a；S直接短语：S；a句柄：S已知语言写出描述该语言的文法试构造生成语言L={anbnci
15、n≥1,i≥0}的文法分析：anbnci可以进行分解让A生成anbn，B生成ci符号串anbnci是AB连接后的结果。n
16、≥1所以A-〉aAb
17、ab，i≥0所以B->cB
18、ε也可写成B->Bc
19、ε。解：S-〉ABA-〉aAb
20、abB->cB
21、ε已知文法写出该文法所生成的语言.已知文法G[A]=({A},{a,b},{A—>bA
22、a},A)所生成的语言是什么？{bna
23、n>=0}1、语言和文法的相互转换1）已知文法写出该文法所生成的语言：①语言是有穷集：通过从开始符号的推导出所有的句子，所有句子的集合即为所求的语言②语言是无穷集：通过从开始符号的推导出几个的句子，总结句子的特点，将特点描述出来。例如G：S→0S1，S→01SÞ01SÞ0S1Þ0011SÞ0S1Þ00S11=>000111语言为01
24、个数相等，并且0在前，1在后L（G）={0n1n
25、n>=1}2)已知语言写出描述该语言的文法一般所写的文法是上下文无关文法和正规文法，①用集合的形式表示语言若是这一类的题目先记住几个基本的情况，若是复杂的都可以分解成基本的情况。一般给定集合是无限集，文法都应是递归文法，可以是直接递归也可以是间接递归。基本的有：ⅰ{an}若生成多个a，用递归文法表示则为：A->aA，递归有结束的时候，结束的写法看n的值：若n为0，即有0个a，即为ε，A->ε若n为1，即有1个a，即为a，A->a若n为2，即有2个a，即为
