资源描述：
《编译原理复习(有解答)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一章引论1.编译过程的阶段由词法分析、语法分析、语义分析、中间代码生成、代码优化与目标代码生成六个阶段2.编译程序的概念3.编译程序的结构例：（B）不是编译程序的组成部分。A.词法分析器；B.设备管理程序C.语法分析程序；D.代码生成程序4.遍的概念对源程序(或其中间形式)从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。5.编译程序与解释程序的区别例：解释程序与编译程序是两类程序语言处理程序，它们的主要区别在于（D）。A.单用户与多用户的差别B.对用户程序的差错能力C.机器执
2、行效率D.是否生成目标代码第三章文法与语言文法的概念字母表、符号串与集合的概念及运算例：(ab
3、b)*c与下面的那些串匹配？（ACD）A.ababbc；B.abab；C.c；D.babc；E.aaabc例：ab*c*(a
4、b)c与后面的那些串匹配？（BC）A.acbbcB.abbcacC.abcD.acc例：(a
5、b)a+(ba)*与后面的那些串匹配?（ADE）A.baB.bbaC.ababaD.aaE.baa文法的定义（四元组表示）文法G定义为四元组（VN，VT，P，S）VN：非终结符集VT：终结符集P：
6、产生式（规则）集合S：开始符号（或识别符号）例：给定文法，A::=bA
7、cc，下面哪些符号串可由其推导出（①②⑤）。①cc②b*cc③b*cbcc④bccbcc⑤bbbcc什么是推导例：已知文法G：E->E+T
8、E-T
9、TT->T*F
10、T/F
11、FF->(E)
12、i试给出下述表达式的推导：i*i+i推导过程：E->E+T->T+T->T*F+T->F*F+T->i*F+T->i*i+T->i*i+F->i*i+il句型、句子的概念例：假设G一个文法，S是文法的开始符号，如果S=>*x，则称x是句型。例：对于文法
13、G，仅含终结符号的句型称为句子。l语言的形式定义例：设r=(a
14、b
15、c)(x
16、y
17、z)，则L(r)中元素为9个。例：文法G产生式为S→AB，A→aAb
18、e，B→cBd
19、cd，则B∈L(G)。A.ababcd；B.ccdd；C.ab；D.aabbl等价文法例：如果两个文法描述了同一个语言，则这两个文法是等价文法。l文法的类型0型：左边至少有一个非终结符1型：右边长度>=左边长度2型：左边有且仅有一个非终结符3型：形如：A->aB,A->a各类型文法都是逐级包含关系，例：文法S→abC
20、c，bC→d是几型文法？
21、0型例：文法S→abC，bC→ad是几型文法？1型例：文法G[A]：A→e，A→aB，B→Ab，B→a是几型文法？2型例：文法S→a
22、bC，C→d是几型文法？3型l最左（右）推导规范推导：最右推导被称为规范推导规范句型：由规范推导所得的句型称为规范句型规范归约:左归约为规范归约l二义性例：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。例：已知文法G1：P->PaP
23、PbP
24、cP
25、Pe
26、f，G1是（A）。A二义文法；B无二义的例：证明下述文法G[<表达式>]是二义的。<表达式>→a
27、(<
28、表达式>)
29、<表达式><运算符><表达式><运算符>→+
30、-
31、*
32、/答：可为句子a+a*a构造两个不同的最右推导:最右推导1〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉a〈表达式〉*a〈表达式〉〈运算符〉〈表达式〉*a〈表达式〉〈运算符〉a*a〈表达式〉+a*aa+a*a最右推导2〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉a〈表达式〉〈运算符〉〈表达式〉*a〈表达式〉〈运算符〉a*a〈表达式〉+a*aa+
33、a*al短语、句柄、直接短语例：令文法G[E]为:E->E+T
34、E-TT->T*F
35、T/F
36、FF->(E)
37、i证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语与句柄。例：已知文法G[S]S→aB
38、bAA→a
39、aS
40、bAAB→aBB
41、bS
42、b句型aabbAb的句柄是（D）A.aB.abC.bD.bA第四章词法分析l词法输出的token表示法l词法记号、模式、词法单元的概念l词法输出的token表示：二元式表示（单词种别，单词自身的值）例：扫描器的任务是从源程序中识别出一个个单词。l正规式的概念及
43、其代数性质词法分析中的单词符号的描述工具正规式代表的集合例：请描述下面正规式定义的串，字母表S={0,1}。1(0
44、1)*0答：必须以1开头0结尾的串例：为下边所描述的串写正规式，字母表是{0,1}。以01结尾的所有串答：(0
45、1)*01l正规文法与正规式相互转换正规文法到正规式的转换规则：正规文法正规式A®xB,B®y转换成：A=xyA®xA½y转换成：A=x*yA®x,A®y转换成：A=x½y例：给出下述文法
