编译原理重点题型简答综合选择填空
?乔姆斯基把文法分成4种类型：0型也叫（短语文法）；1型也叫（上下文有关文法）；2型也叫（上下文无关文法）；3型也叫（正则文法）。
?自上而下分析方法一般需要消除（左递归）和回溯。
?一般而言，编译器的分析部分包括（词法分析），（语法分析），（语义分析）二综合部分包括（中间代码生成），（代码优化），（代码生成）。以上六个阶段都涉及到（符号表）管理和（出错）管理。
?任何NFA都存在一个与之等价的（DFA）。
?假设G是一个文法，S是文法开始符，若S x,则称x是句型。
?文法G产生的句子的全体是该文法描述的语言。
?LL(1)分析法中，第一个L的含义是从左到右分析，第二个L的含义是最左推导，“1”的含义是向前看一个符号。
?自下而上语法分析法的基本思想是：从待输入的符号串开始，利用文法的产生式步步向上进行归约，直至文法的开始符。
?算符优先分析法定义的可归约串叫做最左素短语，
? LR分析中定义的可归约串称为句柄。
?LR(1)分析法的名字中，“R”指的是最右推导逆过程。
?高级语言编译程序常用的语法分析方法中，递归下降分析法属于自上而下分析方法；
SLR分析法属于自下而上分析方法。
?LR分析法中，语法分析栈中存放的状态是识别规范句型活前缀的DFA的状态。
?编译过程中，每当扫描器识别出一个新名字，就将它填进符号表。
?确定的有穷自动机是一个五元组，通常表示为（S,Σ,δ,s0,F) 。
?已知文法G[S]：S→eT|RT
? T→DR|ε
? R→dR|ε
? D→a|bd
?则FIRST(S)= {a,b,d,e, ε} ，FOLLOW(R)= {a,b,#}
?在编译过程中：词法分析的常用方法有有穷自动机理论；语法分析常用的方法有自顶向下匹配和自底向上归约中间代码生成的常用方法有语法制导翻译方法；
?一个句型中的最左直接(简单)短语称为该句型的句柄。
短语：假定αβδ是文法G的一个句型，S是文法的开始符，若有：
S=*>αAδ且A=+>β ,则称β是句型αβδ相对于非终结符A的短语
直接短语：在短语定义的基础上，若有A=>β，则称β是句型αβδ相对于规则A→β的直接短语
句柄：一个句型的最左直接短语称为该句型的句柄
自上而下分析的主要分析方法：预测分析法
自下而上语法分析： (2)主要问题：
怎样判断栈顶符号串的可归约性，以及如何进行归约
不同的自下而上分析法主要区别自可归约串的不同定义
(3)主要分析方法：算符优先分析法、LR(k)分析法
三种LR文法的判别方法：
1) LR(0)文法是所有的LR(0)项目集中没有移进－归约冲突或归约－归约冲突(或LR(0)分析表中不含多重定义)
2) SLR(1)文法是LR(0)项目集中所有含冲突的项目集都能用SLR规则解决冲突(或SLR(1)分
析表中不含多重定义)
3) LR(1)文法是所有的LR(1)项目集中没有移进－归约冲突或归约－归约冲突(或LR(1)分析表中不含多重定义)
LR(0)项目集中可能的各种项目：归约项目、接受项目、移进项目、待约项目
1、语法分析通常采用语法制导翻译方法
2、语法制导翻译的基本思想是：
文法中的每个符号都有一些编译程序关心的信息，称为文法符号的属性；
为文法中的每个产生式给定一组计算相关属性的动作——语义动作
所谓语法制导翻译，是指在语法规则的制导下，通过计算语义规则，完成对输入符号串的翻译。
3、属性文法：为每个文法符号引进一组属性，且让该文法中的重写规则附加以语义规则时，称该上下文无关文法为属性文法
4、文法符号的属性有继承属性和综合属性两种
属性之间存在依赖关系，因而属性的计算有一定的顺序要求
若要一遍扫描完成翻译工作，则必须对文法进行修改，使得在计算每个属性之前，它所依赖的属性已全部计算出来
5、语义分析通常生成中间代码形式，常见的中间代码有逆波兰、四元式、三元式、三地址代码、抽象语法树等
6、语法制导翻译法和翻译方案（或称翻译模式）是属性文法的两种不同形式
语法制导翻译法：是在语法分析的过程中，依随分析的过程，在使用语法规则进行推导或归约的同时，根据每个产生式添加的语义动作进行翻译的方法。即：在语法规则的制导下，通过对语义规则的计算，完成对输入符号串的翻译
翻译方案/翻译模式：将属性文法中的语义规则用括号对{}括住，插在规则右部的任何地方，指明语义规则的计算次序，陈述一些实现细节，得到一种语义动作与语法分析交错的表示方法，以表达语义动作在语法分析过程中的执行时刻
1、编译过程中需要使用源程序中各种名字的相关信息，这些信息通常用一张或几张符号表保存起来。不同的名字需要保存在符号表中的信息各不相同
2、编译过程中，每当扫描器识别出一个名字后，就查看符号表，看该名字是否在其中。若是一个新名字就将它填进符号表。符号表的信息将在词法分析、语法分析-语义分析过程中陆续填入
3、符号表在整个编译期间的作用主要有两条：辅助语义的正确性检查、辅助代码生成
4、符号表的组织
每一表项包含两个部分：名字栏和信息栏，分别存放标识符的名字和相关属性
可按名字的不同种属使用不同的符号表，如：常量表、变量表、过程名表等等
5、符号表的数据结构和查找方法
符号表的数据结构可以是线性表、树结构、散列表等
查找算法很多：线性查找、折半法、杂凑技术等
6、过程嵌套结构的栈式符号表
采用栈符号表：新名字总是从栈顶填入，每进一层过程，要为在该层过程中新说明的标识符建立一张子符号表；而退出过程时，则要删除（释放）相应的子符号表，使现行符号表与进入此过程前的内容保持一致
引入一个显示层次关系表(DISPLAY)，称为过程的嵌套层次表。DISPLAY也是一个栈，其栈顶值总是指向当前正在处理的最内层过程的子符号表在栈符号表中的起始位置
在符号表中的查找范围由当前的DISPLAY栈顶值和当前的符号表栈顶值TOP控制
1、编译程序必须组织与分配目标程序运行时的数据空间
2、运行阶段的存储组织与分配是指编译程序在编译阶段为源程序中出现的用户定义的变量与常量、临时工作单元、过程或函数调用时需要的连接单元与返回地址等分配其在运行阶段的存储空间
3、运行阶段的存储组织与分配有两种方式：静态存储分配动态存储分配
4、几个相关概念
数据区：指一片连续的存储单元。在编译时，任何变量运行时的存储单元都可以由（数据区编号，位移）表示
过程的活动与活动记录：
一个过程的活动：指该过程的一次执行
过程的活动记录：使用一个连续的存储块记录某活动的相关信息，一般包括：连接数据、返回地址、动态链、静态链、形式单元、局部数据
5、非局部名字访问的实现：
静态链和活动记录：
在数据区中引入静态链指针，指向该过程直接外层过程的最新活动记录的起始地址
嵌套层次显示表和活动记录：
引进嵌套层次显示表（display）
假定现进入的过程的层数为i,在它的display表含有i+1个单元。此表本身是一个栈，自上而下依次存放现行层、直接外层…直至最外层（0层、主程序层）等每一层过程的最新活动记录的基地址
过程的层数可以静态确定，因而每个过程的display表的体积在编译时即可确定，将display 表作为活动记录的一部分
每当调用发生时，只需将调用者的display地址作为连接数据之一传送给被调用者，被调用者就可以建立起自己的display表——从调用者的display表中取i个（i为被调用者的静态层次数）单元，再加上被调用者的活动记录首地址即可
6．文法G[S]：S→aAa|aBb|bAb|bBa
A→d
B→d
判断该文法是LR(0)、SLR(1)文法吗？如是构造其分析表，并分析符号串adb是否是文法的句子拓广文法：
(0)S′→S
(1)S→aAa
(2)S→aBb
(3)S→bAb
(4)S→bBa
(5)A→d
(6)B→d
构造LR(0)项目集：
I0=CLOSURE({S′→·S })={S′→·S,S→·aAa, S→·aBb，S→·bAb, S→·bBa}
I1 =GO(I0,S)=CLOSURE({S′→S·})={S′→S·}
I2 =GO(I0,a)=CLOSURE({S→a·Aa, S→a·Bb })
={S→a·Aa, S→a·Bb , A→·d, B→·d }
I3 =GO(I2,d)= {A→d·, B→d·}
I3中含有多个归约项目，故该文法不是LR(0)文法
又：FOLLOW(A)=FOLLOW(B)={a,b}
因此该文法也不是SLR(1)文法
练习：写出下列程序段产生的中间代码
A:=1; B:=6; YES:=1;
WHILE (A BEGIN I:=1； WHILE(I<=100) DO BEGIN D[I ,100]:=I; IF (C>D) THEN BEGIN H:=H+D[I,J]; J:=J+1; END ELSE YES:=0; I:=I+1; END; END; ?下面的文法是否是左递归的？如果是，该如何消除？ E→E+T|T T→T*F|F F→(E)|id 答：存在。E->TE’ E’->FT’ T->FT’ T’->*FT’|ε F->(E)|id 1、文法G[S]：S→S*S|S+S|(S)|a，该文法是否有二义性？为什么？是该文法存在句子a=a*a；该句子存在两颗不同的语法数。 ?构造下面文法的LL(1)分析表 S→aBc|bAB A→aAb|b B→b|ε 构造其LL(1)分析表，并分析符号串baabbb是否是该文法的句子答：FIRST(S)={a,b} FIRST(A)={a,b} FIRST(B)={b,ε} FOLLOW(S)={#} FOLLOW(A)={b,#} FOLLOW(B)={c,#} LL(1)分析表： 分析符号串baabbb的过程： ?设有文法G[S]：S→CC (1) C→cC (2) C→d (3) 求：1）拓广文法 2）文法的LR(1)项目集规范族（识别活前缀的DFA） 3）构造规范LR分析表 4）给出句子cdd的LR(1)分析过程 1）拓广文法 S’→S(0) S→CC(1) C→cC(2) C→d(3) 2）LR(1)项目集规范族 I0={[S’→?S,#]，[S→?CC,#]，[C→?cC,c/d]，[C→?d,c/d]} I1=GO(I0,S)={[S’→S?,#]} I2=GO(I0,C)={[S→C?C,#]，[C→?cC,#]，[C→?d,#]} I3=GO(I0,c)=GO(I3,c)={[C→c?C,c/d]，[C→?cC,c/d]，[C→?d,c/d]} I4=GO(I0,d)=GO(I3,d)={[C→d?,c/d]} I5=GO(I2,C)={[S→CC?,#]} I6=GO(I2,c)=GO(I6,c)={[C→c?C,#]，[C→?cC,#]，[C→?d,#]} I7=GO(I2,d)=GO(I6,d)={[C→d?,#]} I8=GO(I3,C)={[C→cC?,c/d]} I9=GO(I6,C)={[C→cC?,#]} 14、给出下述文法对应的正规式： S→0A|1B A→1S|1 B→0S|0 分析与解析：将A，B产生式的右部代入S中 01S|01|10S|10=(01|10)S|(01|10) 所以，(01|10)*(01|10) 15、已知文法G[A]：A→B|AaB|AbB B→C|BcC|BdC C→fAg|e 给出符号串eceae的最右推导、语法树 16、设有文法G[S]=({S,A,B},{a,b},P,S)，其中P为： S→AB A→Aa|bB B→a|Sb 求句型baSb的全部短语、直接(简单)短语和句柄。 短语有：ba,Sb,a,baSb直接短语：a,Sb句柄：a 17、设有文法G[E]：E→EE+ E→EE* E→a (1) 构造该文法的LR(0)项目集规范族 (2) 该文法的LR(1)文法吗，请说明理由？若是请构造它的LR(1)分析表 解答：首先拓广文法如下： S→E E→EE+ E→EE* E→a (1)构造该文法的LR(0)项目集规范族： I0=CLOSOURE({S→·E})={ S→·E，E→·EE+， E→·EE*，E→·a } I1=GO(I0,E)= { S→E·，E→E·E+，E→E·E*，E→·EE+， E→·EE*，E→·a } I2=GO(I0,a)=GO(I1,a)= { E→a· } I3=GO(I1,E)=GO(I3,E)= { E→EE·+，E→EE·*，E→E·E+，E→E·E*，E→·EE+，E→·EE*，E→·a } I4=GO(I3,+)= { E→EE+·} I5=GO(I3,*)= { E→EE*· } (2)该文法是LR(1)文法，因为： 在LR(0)项目集规范族的每个项目子集中，都不存在移进－归约冲突和归约－归约冲突，所以该文法是LR(0)文法，自然也是SLR(1)文法和LR(1)文法，现构造LR(1)项目集族如下： I0=CLOSURE({[S→·E,#]})={ [S→·E,#]，[E→·EE+,#/a]， [E→·EE*,#/a]，[E→·a,#/a] } I1=GO(I0,E)= { [S→E·,#]，[E→E·E+,#/a]，[E→E·E*,#/a]， [E→·EE+,+/*/a]，[E→·EE*,+/*/a]，[E→·a,+/*/a] } I2=GO(I0,a)= { [E→a·,#/a] } I3=GO(I1,E)= { [E→EE·+,#/a]，[E→EE·*,#/a]， [E→E·E+,+/*/a]， [E→E·E*,+/*/a]，E→·EE+,+/*/a]， [E→·EE*,+/*/a]， [E→·a ,+/*/a] } I4=GO(I1,a)=GO(I3,a)=GO(I7,a)={ [E→a·,+/*/a]} I5=GO(I3,+)= { [E→EE+·,#/a] } I6=GO(I3,*)= { [E→EE*·,#/a] } I7=GO(I3,E)=GO(I7,E)={ [E→EE·+,+/*/a]，[E→EE·*,+/*/a]， [E→E·E+,+/*/a]， [E→E·E*,+/*/a]， [E→·EE+,+/*/a]， [E→·EE*,+/*/a]， [E→·a ,+/*/a] } I8=GO(I7,+)= { [E→EE+·,+/*/a] } I9=GO(I7,*)= { [E→EE*·,+/*/a] } 18、假设有以下算符优先文法：G[A]: A→A;D|D D→D(E)|F F→a|(A) E→E+A|A (1)给出该文法的算符优先关系表。(2)写出句子(a+a)的算符优先分析过程。 1.扫描器的任务是从源程序中识别出一个个单词符号 2．语法分析最常用的两类方法是自顶向下和___ 自底向上 ______分析法。 计算机执行用高级语言编写的程序主要有两种途径：___解释__和__编译___。 2．扫描器是__词法分析器___，它接受输入的__源程序___，对源程序进行___词法分析__并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。 3．自上而下分析法采用___移进__、归约、错误处理、___接受__等四种操作。 4．一个LR分析器包括两部分：一个总控程序和___一张分析表__。5．后缀式abc-/所代表的表达式是___a/(b-c)__。6．局部优化是在__基本块___范围内进行的一种优化。 5．编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。 6．编译器常用的语法分析方法有自底向上和自顶向下两种。 7．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。 8．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。 9．对编译程序而言，输入数据是源程序，输出结果是目标程序。 12.自下而上语法分析的基本实现方法是，该文法引进了一个符号栈来存放符号，按照扫描顺序把当前输 13.乔姆斯基把文法分成4种类型：0型也叫短语文法；1型也叫上下文有关文法；2型也叫上下文无关文法；3型也叫正则文法。 14.自上而下分析方法一般需要消除左递归和回溯。 15.一般而言，编译器的分析部分包括词法分析，语法分析，语义分析二综合部分包括中间代码生成，代码优化，代码生成。以上六个阶段都涉及到符号表管理和出错管理。 16..任何NFA都存在一个与之等价的DFA。 17. 算符优先分析法定义的可归约串叫做最左素短语，LR分析中定义的可归约串称为句柄。 18. LR(1)分析法的名字中，“R”指的是最右推导逆过程。 19 高级语言编译程序常用的语法分析方法中，递归下降分析法属于自上而下分析方法； SLR分析法属于自下而上分析方法。 20. 在编译过程中：词法分析的常用方法有有穷自动机理论；语法分析常用的方法有 自顶向下匹配和自底向上归约中间代码生成的常用方法有语法制导翻译方法； 21. 文法符号的属性有继承属性和综合属性两种 22. 语义分析通常生成中间代码形式，常见的中间代码有逆波兰、四元式、三元式、三地址代码、抽象语法树等 中间语言与语法制导翻译 重点与难点 重点：语法制导翻译的基本思想，属性文法，翻译模式，说明语句的翻译方案。 三地址码，各种语句的目标代码结构、属性文法与翻译模式。 难点：属性的意义，对综合属性，继承属性，固有属性的理解，属性计算，怎么通过属性来表达翻译。布尔表达式的翻译，对各种语句的目标代码结构、属性文法与翻译模式的理解。 基本要求 掌握语法制导翻译的基本思想，属性文法，综合属性，继承属性，固有属性，属性计算，S_属性文法，L_属性文法，说明语句的翻译方案，翻译模式、属性文法的实现掌握中间语言与语义分析的基本概念；熟练掌握语法（结构）树、三地址代码、赋值与控制语句的翻译、说明语句的翻译；掌握组合数据说明的翻译、过程调用翻译。 例题解析 例1 给定文法 E --> T { R.i := T.p } R { E.p := R.s } R --> addop T { R1.i := mknode( addop.val, R.i, T.p ) } R { R.s := R1.s } R --> { R.s := R1.s } T --> ( E ) { T.p := E.p } T --> id { T.p := mkleaf( id, id.entry ) } T --> num { T.p := mkleaf( num, num.val ) } (1) 指出文法中的各非终结符具有哪些综合属性和哪些继承属性 ⑵画出按本翻译模式处理表达式 a + 20 + ( b - 10 ) 时所生成的语法树 【解】 (1)E的综合属性 p，R的继承属性i，综合属性s；T的综合属性p (2) 处理表达式 a + 20 + ( b - 10 ) 时所生成的语法树如下 + （NUM, 20） - ( ID, b) (NUM, 10) 例2 定义一个计算器的属性文法,完成一个输入表达式值的计算和显示, 【解】计算器的文法 L → E * 编译原理复习题 一．简答题： 1) 什么是句子？ 什么是语言? 解答：句子——设G 是一个给定的文法，S 是文法的开始符号，如果S x （其中x ∈V T * ），则称x 是文法的一个句子。 语言——语言是句子的集合。 或——设G[S]是给定文法，则由文法G 所定义的语言L(G)可描述为：L(G)＝{x │ S x,x ∈V T * } 。 2) DFA 与NFA 有何区别 ? 解答:DFA 与NFA 的区别表现为两个方面:一是NFA 可以有若干个开始状态，而DFA 仅只有一个 开始状态。另一方面，DFA 的映象M 是从K ×∑到K ，而NFA 的映象M 是从K ×∑到K 的子集，即映象M 将产生一个状态集合（可能为空集），而不是单个状态。 3) 自顶向下的语法分析方法的基本思想是什么? 解答:从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接 推导，试图推导出文法的句子，使之与给定的输入串匹配。 4) 自底向上的语法分析方法的基本思想是什么? 解答:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图 归约到文法的开始符号。 5) 一个上下文无关文法G 包括哪四个组成部分？ 解答:一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。 6) 在自底向上的语法分析方法中，分析的关键是什么？ 解答:关键是寻找句柄。 7)在自顶向下的语法分析方法中，分析的关键是什么？ 解答:关键是选择候选式。 8）什么是属性文法？ 答：是在上下文无关文法的基础上，为每个文法符号(含终结符和非终结符)配备若干个属 性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则)。在语法分析过 程中，完成语义规则所描述的动作，从而实现语义处理。 一个属性文法形式的定义为一个三元组AG，AG=（G，V，E）。 其中G为一个上下文无关文法；V为属性的有穷集；E为一组语义规则。 9）语法制导翻译 语法制导翻译：定义翻译所必须的语义属性和语义规则，一般不涉及计算顺序。 语法制导翻译(Syntax-Directed Translations)： –一个句子的语义翻译过程与语法分析过程同时进行。 在文法中，文法符号有明确的意义，文法符号之间有确定的语义关系。属性描述语义信息， 语义规则描述属性间的的关系，将语义规则与语法规则相结合，在语法分析的过程中计算语义 属性值。 10）词法分析的主要任务是什么？ 解答:词法分析器的任务是对构成源程序的字符串从左到右逐个字符逐个字符地进行扫 描，依次把它们识别为一个一个具有独立意义的单词，并确定其属性，再转换为长度统一的属 11)图示运行时存储空间的划分（分为哪几个区）。 解答: 一般分为静态区和动态区： 程序代码区、静态数据区、栈区和堆区 12)常用的中间语言种类有哪几种？ 解答: 常用的中间语言种类有逆波兰表示、三元式、四元式和树形表示。 13）文法G所描述的语言是什么的集合？ 解答:是由文法的开始符号推出的所有终结符串的集合。或说是句子的集合。 14）乔姆斯基把文法分为四种类型，即0型、1型、2型、3型。其中2型文法叫什么？ 解答: 2型文法叫上下文无关文法。 15）常见的动态存贮分配策略有哪两种？ 解答:常见的两种动态存贮分配策略是栈式动态分配策略和堆式动态分配策略。 16）语法分析的任务是什么？ 一、填空题（每空2分，共20分） 1．编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。 2．编译器常用的语法分析方法有自底向上和自顶向下两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。 5．对编译程序而言，输入数据是源程序，输出结果是目标程序。 1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译。 2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。 3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。 4．一个LL（1）分析程序需要用到一张分析表和符号栈。 5．后缀式abc-/所代表的表达式是a/(b-c)。 二、单项选择题（每小题2分，共20分） 1．词法分析器的输出结果是__C。 A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 2．正规式 M 1 和 M 2 等价是指__C_。 A． M1和M2的状态数相等B． M1和M2的有向边条数相等 C． M1和M2所识别的语言集相等 D． M1和M2状态数和有向边条数相等 3．文法G：S→xSx|y所识别的语言是_C____。 A． xyx B． (xyx)* C．xnyxn(n≥0) D． x*yx* 4．如果文法G是无二义的，则它的任何句子α_A____。 A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握____D__。 A．源程序B．目标语言 C．编译方法 D．以上三项都是 6．四元式之间的联系是通过__B___实现的。 A．指示器B．临时变量C．符号表 D．程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。 A．┐AB∨∧CD∨B．A┐B∨CD∨∧C． AB∨┐CD∨∧ D．A┐B∨∧CD∨8. 优化可生成__D___的目标代码。 A．运行时间较短B．占用存储空间较小 C．运行时间短但占用内存空间大 D．运行时间短且占用存储空间小 9．下列___C___优化方法不是针对循环优化进行的。 A. 强度削弱 B．删除归纳变量C．删除多余运算 D．代码外提 10．编译程序使用_B_区别标识符的作用域。 A. 说明标识符的过程或函数名B．说明标识符的过程或函数的静态层次 C．说明标识符的过程或函数的动态层次 D. 标识符的行号 三、判断题（对的打√，错的打×，每小题1分，共10分） 2．一个有限状态自动机中，有且仅有一个唯一的终态。x 3．一个算符优先文法的每个非终结符号间都也可能存在优先关系。X 4．语法分析时必须先消除文法中的左递归。X 6．逆波兰表示法表示表达式时无须使用括号。R 9．两个正规集相等的必要条件是他们对应的正规式等价。 X 1．编译程序是对高级语言程序的编译执行。X 注:题目前带*号为很有疑问的。其余的也不是很对，总之答案仅供参考 1.扫描器的任务是从源程序中识别出一个个__单词符号____。 2．语法分析最常用的两类方法是自顶向下和___ 自底向上______分析法。 3．所谓语法制导翻译方法是____为每个产生式配上一个语义子程序，并在语法分析的同时执行这些程序 ___________。 4.源程序执行的途径有翻译和解释途径两类。 5．符号表的作用是语义检查的依据和辅助目标代码的生成。 6．词法分析的任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。 7．素短语是指至少含有一终结符除自身外不含其它素短语的短语。8．LL(1)分析法的文法须满足的条件是无回溯和无左递归。 9．DFA和NFA间的区别是后继状态是否唯一和匹配速度快慢。10．二义性的解决办法是修改编译算法和修改文法。 11．常用的两种动态存贮分配办法是栈式动态分配和__堆式___动态分配。 12．从功能上说，程序语言的语句大体可分为执行性语句和__说明性____语句两大类。13．一个上下文无关文法包含四个组成部分是一组终结符号、一组非终结符号、一个开始符号和一组产生式。 14．产生式是用于定义__ 语法成分___的一种书写规则。 15．动态存储分配实现的方式有栈式分配和堆式分配两种。 16．表达式a*(b+c)/d- (f+e)的逆波兰式表示是abc+*d/fe+- 。28．常见的中间语言的形式有三元式、四元式、逆波兰式和树表示。17．可用属性文法来说明源语言语义。属性文法由一个上下文无关文法和一系列附加在文法上的语义规则构成。 18．词法分析器的另一个名称为扫描程序。 19．代码优化可以分局部优化、全局优化和循环优化三类。 20．文法G[S]：S→aSb∣ε描述的语言L(G[S])是L(G[S])={(a^nb^n|n>=0} 。 21．素短语是指至少含有一终结符和除自身外不包含其它素短语的短语。 22．无环路有向图(DAG)是指如果有向图中任一通路都不是环路，则称庐有向图为无环路有向图，简称DAG 。 23．所谓优化是指加快运行速度和减少存储空间。 一、填空题（每空 2 分，共 30 分） 1、编译程序的整个过程可以从逻辑上划分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等几个阶段，另外还有两个重要的工 作是表格管理和出错处理 2、规范规约中的可归约串是句柄，算符优先分析中的可归约串是最左素短语。 3、语法分析方法主要可分为自顶向下和自底向上两大类。 4、 LR （ 0）文法的项目集中不会出现移进 -归约冲突和归约 -归约冲突。 5、数据空间的动存态储分配方式可分为栈式和堆式两种。 6、编译程序是指能将源语言程序翻译成目标语言程序的程序。 7、确定有穷自动机DFA 是NFA的一个特例。 8、表达式 (a+b)*c的逆波兰表示为ab+c*。 二、选择题（每题 2 分，共 20 分） 1、 L R 语法分析栈中存放的状态是识别B的 DFA 状态。 A 、前缀B、可归前缀C、项目 D 、句柄 2、D不可能是目标代码。 A 、汇编指令代码 B 、可重定位指令代码 C、绝对机器指令代码 D 、中间代码 3、一个控制流程图就是具有C的有向图 A 、唯一入口结点B、唯一出口结点C、唯一首结点 D 、唯一尾结点 4、设有文法G[S] ： S→ b|bB B → bS ，则该文法所描述的语言是C。 A 、 L （ G）={b i|i≥ 0}B、 L （G） ={b 2i |i≥0} C、 L （ G）={b 2i+1|i≥ 0} D 、 L （ G）={b 2i+1|i ≥1} 5、把汇编语言程序翻译成机器可执行的目标程序的工作是由 B完成的。 A 、编译器 B 、汇编器C、解释器D、预处理器6、在目标代码生成阶段，符号表用于D。 A 、目标代码生成 B 、语义检查C、语法检查D、预处理器地址分配0 7、规范归约是指B。 A 、最左推导的逆过程 B 、最右推导的逆过程C、规范推导D、最左归约逆过程 8、使用A可以定义一个程序的意义。 A 、语义规则B、词法规则C、语法规则D、左结合规则 9、经过编译所得到的目标程序是D。 A 、三元式序列B、四元式序列C、间接三元式 D 、机器语言程序或汇编语言程序 10、在一个基本块内进行的代码优化是B。 A 、全局优化B、局部优化C、循环优化D、代码外提 三、简答题（ 3 小题，共 30 分） 1、已知文法G[S]：S→Ac|aB A→ ab B→ bc 证明该文法具有二义性（本题 6 分） 证明：因为该文法的句型abc 存在如下两棵语法树： 所以，该文法具有二义性 一、填空题（每空 1分，共 20分） 1．编译过程一般分为、、中间代码生成、 和目标代码生成五个阶段。 2．语法分析最常用的两类方法是和分析法。 3．确定的有穷自动机是一个，通常表示为。 1、给出下面语言的相应文法。L1={a n b n c i|n≥1,i≥0} 从n，i的不同取值来把L1分成两部分：前半部分是anbn：A→aAb|ab后半部分是ci：B→Bc|ε所以整个文法G1[S]可以写为：G1(S):S→AB；A→aAb|ab；B→cB|ε 3、构造一个DFA，它接受 ={a，b}上所有包含ab的字符串。 （要求：先将正规式转化为NFA，再将NFA确定化，最小化） 4、对下面的文法G: E →TE ’ E ’→+E|ε T →FT ’ T ’→T|ε F →PF ’ F ’ →*F ’|ε P →(E)|a|b|∧ （1）证明这个文法是LL(1)的。 （2）构造它的预测分析表。 (1)FIRST(E)={(,a,b,^}FIRST(E')={+, ε}FIRST(T)={(,a,b,^}FIRST(T')={(,a,b,^,ε} FIRST(F)={(,a,b,^}FIRST(F')={*,ε}FIRST(P)={(,a,b,^}FOLLOW(E)={#,)} FOLLOW(E')={#,)}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#} FOLLOW(F')={(,a,b,^,+,),#}FOLLOW(P)={*,(,a,b,^,+,),#} (2)考虑下列产生式: '→+'→'→'→E E T T F F P E a b ||*|()|^||εεε FIRST(+E)∩FIRST(ε)={+}∩{ε}=φ FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ FIRST(*F')∩FIRST(ε)={*}∩{ε}=φ FIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ 《编译原理》练习 一、填空题 1、编译程序的总体结构分为词法分析、语法分析、语义分析和 中间代码、优化 和目标代码生成五部分。 2、构造一个编译程序的三要素是：___原程序_______ _____，__________目标语言_______，__编译方法__________________。 3、被编译的语言为A语言，编译的最终结果为B语言代码，编写编译程序的语言为C语言。那么，_____a__语言为源语言，___c__语言为宿主语言，_____b____语言为目标语言。 4、设文法G(S)： S→aS|Sb|a|b，则文法G(S)所识别语言的正规式为____a*（a|b）b*_____________________。5、设有文法G(S)： S→Sab|bR R→S|a G(S)的语言L(G(S))={_____________________}。 6、设文法G[V]： V→aaV|bc 该文法所对应的语言L(G)=_________________。 7、C语言中表达式a + + + + + + + = 1，词法分析后，能识别出的单词个数是_____6__。 8、设有文法G（S为开始符号）： S→Ap|Bq A→a|cA B→b|dB FIRST(Ap)=｛_______a c______｝。 9、设有文法G[S]: S→AB|bb|bAC A→ε|b B→ε|aC C→aS|c 则FIRST(S)=｛_____________｝,FOLLOW(A)=｛___________｝。 对给出的文法G[S]填写如下LL(1)分析表的内容： a b c ﹟ A ___________________ _____________ ________________ _______________ 10、一个LR分析器的逻辑结构包括___输入串____________、____总控程序____________ 编译原理复习题 一、选择题 1、编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行 2、(A)是一种典型的解释型语言。 A．BASIC B．C C．FORTRAN D．PASCAL 3、把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。 A. 编译器 B. 汇编器 C. 解释器 D. 预处理器 4、用高级语言编写的程序经编译后产生的程序叫(B) A．源程序 B．目标程序C．连接程序D．解释程序 5、(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序 C.设备管理程序 D.语法分析程序 6、通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。 A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器 7、编译程序绝大多数时间花在(D)上。 A．出错处理B．词法分析C．目标代码生成D．表格管理 8、源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 9、词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 10、词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 11、文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n (n≥0) 12、如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 1997年编译原理试题 1．（10分）某操作系统下合法的文件名为 device:name.extension 其中第一部分（device:）和第三部分（.extension）可缺省，若device, name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的确定有限自动机。 2．（20分） a. 下面的二义文法描述命题演算公式，为它写一个等价的非二义文法。 S—> S and S | S or S | not S | p | q | (S) b. 下面文法是否为LL(1)文法？说明理由。 S—> A B | P Q x A—> x y B—> b c P—> d P | εQ—> a Q | ε 3．（10分）某些语言允许给出名字表的一个属性表，也允许声明嵌在另一个声明里面，下面文法抽象这个问题。 D —> attrlist namelist | attrlist (D) namelist —> id, namelist | id attrlist —> A attrlist | A A —> decimal | fixed | float | real D —> attrlist namelist的含义是：在namelist中的任何名字有attrlist 中给出的所有属性。D—> attrlist (D) 的含义是：在括号中的声明提到的所有名字有attrlist 中给出的所有属性，而不管声明嵌套多少层。写一个翻译方案，它将每个名字的属性个数填入符号表。为简单起见，若属性重复出现，则重复计数。4．（10分）把表达式 -(a+b)*(c+d)+(a+b+c) 翻译成四元式。 5．（10分）由于文法二义引起的LR（1）分析动作冲突，可以依据消除二义的规则而得到LR（1）分析表，根据此表可以正确识别输入串是否为相应语言的句子。对于非二义非LR（1）文法引起的LR（1）分析动作的冲突，是否也可以依据什么规则来消除LR（1）分析动作的冲突而得到LR（1）分析表，并且根据此表识别相应语言的句子？若可以，你是否可以给出这样的规则？ 6．（5分）UNIX 下的C编译命令cc的选择项g和O的解释如下，其中dbx 的解释是“dbx is an utility for source-level debugging and execution of programs written in C”。试说明为什么用了选择项g后，选择项O便被忽略。 -g Produce additional symbol table information for dbx(1) and dbxtool(1) and pass -lg option to ld(1) (so as to include the g library, that is: 1、设正规式r= a(a|b)*, 将r转换为相应的正规文法。 令S为文法开始符，首先形成S →a(a|b)*,然后形成S →aA和A →(a|b)*,再变换成： S→aA A→ε A→(a|b)A， 进而变换成正规文法形式： S→aA A→ε A→aA A→bA 2、令文法G[S] S→cC,S→c,C→cC,C→dC,C→c,C→d， 将该文法转换为相应的正规式。 首先有S=cC|c， C=(cC|dC)|(c|d) =(c|d)C|(c|d) =(c|d)*|(c|d) =(c|d)+ 进一步有 S=c(c|d)+|c =c(c|d)* c(c|d)*即为该文法所对应的正规式 令文法G[S]为: S->S+A|A A->A*B|B B->(S)|a|b (1)分析说明a*a+b是该文法的一个句型； (2)指出该句型的所有短语、直接短语和句柄。（1）该字符串对应的语法树为： 所以a*a+b为该文法的句型。 （2）短语为：a,a,a*a,b,a*a+b； 直接短语为：a,a,b； 句柄为：最左边的a 令文法G[S]为: S->aCcDe C->b|Cb D->d (1)分析说明aCbcde是它的一个句型； (2)指出该句型的所有短语、直接短语和句柄。 （1）此句型对应语法树如下，故aCbcde为此文法的一个句型。 （2）短语为：aCbcde，Cb，d； 直接短语：Cb，d； 句柄: Cb。 构造正规式(a|b)*相应的最小化DFA。 1、首先构造对应的NFA： 2、将NFA确定化： 3、对其最小化： 设有非确定的有自限动机NFA M=({A，B，C}，{0，1}，δ，{A}，{C})，其中： δ(A，0)={C}， δ(A，1)={A，B}， δ(B，1)={C}， δ(C，1)={C}。 请画出状态转换距阵和状态转换图。 状态转换距阵为： 状态转换图为： <编译原理>历年试题及答案 一．（每项选择 2 分，共 20 分）选择题 1．将 编译程序分成若干个“遍”是为了_b__。 a.提 高程序的执行效率 b.使程序的结构更加清晰 c. 利用有限的机器内存并提高机器的执行效率 d. 利用有限的机器内存但降低了机器的执行效率 2．构造编译程序应掌握__d__。 a.源程序 b.目标语言 c.编译方 法 d.以上三项都是 3．变量应 当 c＿。 a.持有左值 b.持有右值 c.既持有左值又持有右值 d.既不持 有左值也不持有右值 4．编译程序绝大多数时间花在 _d___上。 a.出错处理 b.词法分析 c.目标代码 生成 d.管理表格 5．词法分析器的输 出结果是_c___。 a.单词的种别编码 b.单词在符号表中的位置 c.单词 的种别编码和自身值 d.单词自身值 6．正规式 MI 和 M2 等价是指__c__。 a. MI 和 M2 的状态数相等 b.Ml 和 M2 的有向弧条数相等。 C.M1 和 M2 所识别的语言集相等 d. Ml 和 M2 状态数和有向弧条数相等7．中间代码生成时所依据的是—c。 a．语法规则 b．词法规则c．语义规则 d．等价变换规则 8．后缀式 ab+cd+/可用表达式__b_来表示。 a． a+b/c+d b． (a+b)/(c+d) c． a+b/(c+d) d． a+b+c/d 9．程序所需 的数据空间在程序运行前就可确定，称为____c_＿管理技术。 a.动态存储 b.栈式存储 c.静态存储 d.堆式存储 10.堆式 动态分配申请和释放存储空间遵守___d____＿原则。 a.先请先放 b.先请后放 c.后请先放 d.任意 二（每小题 10 分，共 80 分）简答题 1.画出编译程序的 总体结构图，简述各部分的主要功能。 2. 已知文法 G[E]: E→ET+|T T→TF* | F F→F^ | a 试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄. 1-01.编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析，之间代码生成,代码优化等几个基本阶段,同时还会伴有表格处理和出错处理 . 1-02.若源程序是用高级语言编写的,目标程序是机器语言程序或汇编程序,则其翻译程序称为编译程序. 1-03.编译方式与解释方式的根本区别在于是否生成目标代码 . 1-04.翻译程序是这样一种程序,它能够将用甲语言书写的程序转换成与其等价的用乙语言书写的程序 . 1-05.对编译程序而言,输入数据是源程序,输出结果是目标程序. 1-06.如果编译程序生成的目标程序是机器代码程序,则源程序的执行分为两大阶段: 编译阶段和运行阶段 .如果编译程序生成的目标程序是汇编语言程序,则源程序的执行分 为三个阶段:编译阶段, 汇编阶段和运行阶段 . 1-07.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。 1-08.一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。其中，词法分析器用于识别单词。 1-09.编译方式与解释方式的根本区别为是否生成目标代码。 2-01.所谓最右推导是指：任何一步α?β都是对α中最右非终结符进行替换的。 2-02.一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。 2-03.产生式是用于定义语法成分的一种书写规则。 2-04.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│S x,x∈VT*} 。 2-05.设G是一个给定的文法，S是文法的开始符号，如果S x（其中x∈V*），则称x是文法的一个句型。 2-06.设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),则称x是文法的一个句子。 3-01.扫描器的任务是从源程序中识别出一个个单词符号。 4-01.语法分析最常用的两类方法是自上而下和自下而上分析法。 4-02.语法分析的任务是识别给定的终极符串是否为给定文法的句子。 4-03.递归下降法不允许任一非终极符是直接左递归的。 4-04.自顶向下的语法分析方法的关键是如何选择候选式的问题。 4-05.递归下降分析法是自顶向上分析方法。 4-06.自顶向下的语法分析方法的基本思想是：从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。 5-01.自底向上的语法分析方法的基本思想是：从给定的终极符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。 5-02.自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行直接归约，力求归约到文法的开始符号。 5-03.简单优先方法每次归约当前句型的句柄，算符优先方法每次归约当前句型的最左素短语，二者都是不断移进输入符号，直到符号栈顶出现可归约串的尾，再向前找到可归约串的头，然后归约。 5-04.在LR（0）分析法的名称中，L的含义是自左向右的扫描输入串，R 的含义是最左归约，0 的含义是向貌似句柄的符号串后查看0个输入符号。 5-05.在SLR（1）分析法的名称中，S的含义是简单的。 编译原理考试 ————————————————————————————————作者：————————————————————————————————日期： 一、判断对错：（对√；错 ；每小问2分共24分） <1>算符优先分析法是一种规范归约分析法。（ ） <2>若文法Gs中不含形如T→…BD…的产生式，T、B、D∈V N，则称Gs为算符文法。（√） <3>若一个语言是有穷集合，则定义该语言的文法一定是递归的。（ ） <4>若两个正规式所表示的正规集相同，则认为二者是等价的。（√） <5>LR分析法是一种规范归约分析法。（√） <6>一个LR(0)项目集I={B →α.bβ, P →aA.},则说I中含有“移进—归约”冲突。（√） <7>SLR(1)文法是无二义性文法。（√） <8>消除左递归后的文法一定是LL(1)文法。（ ） <9>对任何编译程序而言，代码优化是必不可少的。（ ） <10>编译程序与具体的机器无关。（ ） <11>在自动机的概念中，终态与非终态是可区别的。（√） <12>逆波兰式ab+cd+*所代表的中缀表达式是：(a+b)*(c+d)（√） 1. 一个语言有文法是不惟一的。（√） 2. 若一个语言是无穷集合，则定义该语言的文法一定是递归的。（√） 3. 紧跟在条件转移语句后面的语句是基本块的入口语句。（√） 4. 算符优先分析法是一种规范归约分析法。（ ） 5. 自下而上语法自导翻译的特点：当栈顶形成句柄时，在归约的同时执行其语义动作。（√） 6. LR(0)文法、SLR(1)文法都是无二义性文法。（√） 7．K、∑分别表示有限状态集和有穷字母表, DFA M的转换函数f是一个从K ?∑到K的单值映射。（√） 8. 对任何编译程序而言，代码优化是必不可少的。（ ） 9. 直接短语是某规则的右部，它对应简单子树叶结点从左到右排列形成的符号串。（√） 10. 两个有穷自动机等价是指它们的状态数和有向弧数相等。（ ） 11. 一个LR(0)项目集为：I={A→α.bβ, D→β.},则说I中含有“移进--归约”冲突。 （√） 12. 若两个正规式所表示的正规集相同，则认为二者是等价的。（√） 13. 无左递归的文法是LL(1)文法。（ ） 14. 逆波兰式abcde/+*+所代表的中缀表达式是：a+b*(c+d/e)（√） 15. 编译程序结构中，中间代码优化及目标代码生成两个阶段与具体的机器有关。（ ） 16. LALR分析法中，同心集的合并不会产生“移进--归约”冲突。（√） 中间语言与语法制导翻译重点与难点 重点：语法制导翻译的基本思想，属性文法，翻译模式，说明语句的翻译方案。 三地址码，各种语句的目标代码结构、属性文法与翻译模式。 难点：属性的意义，对综合属性，继承属性，固有属性的理解，属性计算，怎么通过属性来表达翻译。布尔 表达式的翻译，对各种语句的目标代码结构、属性文法与翻译模式的理解。 基本要求 掌握语法制导翻译的基本思想，属性文法，综合属性，继承属性，固有属性，属性计算，s_属性文法, L_属性文法，说明语句的翻译方案，翻译模式、属性文法的实现 掌握中间语言与语义分析的基本概念；熟练掌握语法(结构)树、三地址代码、赋值与控制语句的翻译、 说明语句的翻译；掌握组合数据说明的翻译、过程调用翻译。 例题解析 例1 给定文法E --> T { R.i := T.p } R { E.p := R.s } R --> addop T { R1.i := mknode( addop.val, R.i, T.p ) } R { R.s := R1.s } R --> : { R.s := R1.s } T --> ( E ) { T.p := E.p } T --> id { T.p := mkleaf( id, id.entry) } T --> num { T.p := mkleaf( n um, n um.val ) } (1) 指岀文法中的各非终结符具有哪些综合属性和哪些继承属性 ⑵ 画岀按本翻译模式处理表达式 a + 20 + ( b - 10 ) 时所生成的语法树 【解】 (1)E的综合属性p，R的继承属性i，综合属性s ; T的综合属性p ⑵处理表达式a + 20 + ( b - 10 ) 时所生成的语法树如下 例2定义一个计算器的属性文法，完成一个输入表达式值的计算和显示 【解】计算器的文法 L T E E T E1 + T | T T T T1 * F | F F T ( E ) | digit 一填空题 1．编译程序首先要识别出源程序中每个，然后再分析每个并翻译 其意义。 单词，句子 2．编译器常用的语法分析方法有和两种。 自底向上，自顶向下 2．通常把编译过程分为分析与综合两大阶段。词法、语法和语义 分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程 序的综合。 前端，后端 4．程序设计语言的发展带来了日渐多变的 运行时存储管理方案，主要分为两大 类，即方案和分配方案。 静态存储分配，动态存储 5．对编译程序而言，输入数据是，输出结果是。 源程序，目标程序 6．文法G包括四个组成部分：一组终结符号，一组非终结符号，一组，以 及一个开始符号。 产生式 7．文法按产生式的形式分为四种类型，它们是：0型文法，又称短语文法；1型 文法，又称上下文有关文法；2型文法， 又称；3型文法，又称。上下文无关文法，正规文法 8．最右推导称为，由规范推导产生的句型称为规范句型。 规范推导 9．设G是一个文法，S是它的开始符号，如果S=>*α，则称α是一个。 仅由终结符号组成的句型是一 个。 句型，句子 10 对于一个文法G而言，如果L(G)中存在 某个句子对应两棵不同，那么该 文法就称为是二义的。 语法树 11．通常程序设计语言的单词符号分为五种：基本字、、常数、算符、界 限符。 标识符 12．在自底向上分析法中，LR分析法把“可归约串”定义为。 句柄 13．编译中常用的中间代码形式有逆波兰式、三元式、和四元式等。 树代码 14．对中间代码优化按涉及的范围分 为，和全局优化。 局部优化，循环优化 15．局部优化主要包括、利用公共子表达式和删除无用赋值等内容。 合并已知量 16．为了构造不带回溯的递归下降分析程 1．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即方案和方案。 静态存储分配、动态存储分配 2．对编译程序而言，输入数据是，输出结果是。 源程序、目标程序 3.在语法分析中，最常见的两种方法一种是分析法，另一种是分析法。自上而上、自下而上 4.常用的两种动态存贮分配办法是_____动态分配和_____动态分配。 栈式、堆式 5.符号表中的信息栏中登记了每个名字的有关的性质，如____、_、__、地址等。类型、种属、所占单元大小 6.所谓最右推导是指：____。 任何一步αβ都是对α中最右非终结符进行替换的 7.语法分析最常用的两类方法是________和_________分析法。 自上而下、自下而上 8.一个上下文无关文法所含四个组成部分是_______________。 一组终结符号，一组非终结符号、一个开始符号、一组产生式 9.所谓语法制导翻译方法是_____________________。 为每个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序 10.从功能上说，程序语言的语句大体可分为_______语句和______语句两大类。执行性、说明性 11.扫描器的任务是从________中识别出一个个_______。 源程序、单词符号 12.所谓最右推导是指：_______。 任何一步αβ都是对α中最右非终结符进行替换的 13.语法分析最常用的两类方法是________和_________分析法。 自上而下、自下而上 14.文法中的终结符和非终结符的交集是。词法分析器交给语法分析器的文法符号一定是，它一定只出现在产生式的部。空集、终结符、右 15.最左推导是指每次都对句型中的非终结符进行扩展。最左 16.一个上下文无关文法所含四个组成部分是_______________。 一组终结符号，一组非终结符号、一个开始符号、一组产生式 南京工业大学继续教育学院编译原理期末考试试卷 (2012-2013学年) A卷 一、选择题（每题2分，共20分） 得分 1. 一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个_____，以及一组产生式。 A．字符串 B．运算符号 C．开始符号 D．文法 2.程序的基本块是指_____。 A．一个子程序 B．一个仅有一个入口和一个出口的语句 C．一个没有嵌套的程序段 D．一组顺序执行的程序段，仅有一个入口和一 个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于_____分析方法。 A．自左向右 B．自顶向下 C．自底向上 D．自右向左 4．经过编译所得到的目标程序是_____。 A．四元式序列 B．间接三元式序列 C．二元式序列 D．机器语言程序或汇编语言程序 5．运行阶段的存储组织与管理的目的是_____。 ①提高编译程序的运行速度②节省编译程序的存储空间 ③提高目标程序的运行速度④为运行阶段的存储分配做准备 A. ①② B. ②③ C. ③④ D. ④②6．词法分析器的输出结果是_____。 A．( ) 单词的种别编码B．( ) 单词在符号表中的位置C．( ) 单词的种别编码和自身值D．( ) 单词自身值 7．正规式M 1 和M 2 等价是指_____。 A．( ) M1和M2的状态数相等B．( ) M1和M2的有向边条数相等 C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等 8．文法G：S→xSx|y所识别的语言是_____。 A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 9．语言是_____。 A．句子的集合B．产生式的集合 C．符号串的集合D．句型的集合 10．编译程序前三个阶段完成的工作是 A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析 C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码优化 二、名词解释（每题2分，共20分） 得分 1.最左推导： 2.语法： 3.文法： 4.基本块： 5.语法制导翻译： 6.短语： 7.规范句型： 考试安排：7月13日（20周周三），15：00-17:00,20208 填空10X1分、选择10X2分、简答4X5分、大题5X10分 考试大题：循环优化 LL(1).定义之类的 算符优先算法 … 自下而上分析法（20分，选择、填空、大题） 第一章引论 一．编译程序(compiler): 把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序 二．编译程序的工作的五个阶段: 词法分析、语法分析、中间代码产生、优化、目标代码产生 1.词法分析 任务: 输入源程序， 符号。 依循的原则：构词规则 描述工具：有限自动机 保留字标识符等符整常数保留字整常数保留字 2.语法分析 任务:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。 依循的原则：语法规则 述工具：上下文无关文法 3.语义分析与中间代码产生 任务:对各类不同语法范畴按语言的语义进行初步翻译。（变量是否定义、类型是否正确等） 依循的原则：语义规则 中间代码:三元式，四元式，逆波兰记号，树形结构等。是一种独立于具体硬件的记号系统。 例：将Z:=X + 0.618 * Y 翻译成四元式为 (1) * 0.618 Y T1 (2) + X T1 T2 (3) := T2 _ Z 4. 优化 任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效 的目标代码。 依循的原则：程序的等价变换规则 FOR K:=1 TO 100 DO BEGIN M := I + 10 * K; N := J + 10 * K; END 4.目标代码产生 任务: 把中间代码变换成特定机器上的目标代码。 依赖于硬件系统结构和机器指令的含义 目标代码三种形式: a)绝对指令代码: 可直接运行 b)可重新定位指令代码: 需要连接装配 c)汇编指令代码: 需要进行汇编 三. 编译程序结构 编译程序总框 (简答题5分) 第二章高级语言及其语法描述 2.1.1语法 词法规则：单词符号的形成规则。 a)单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基 本字、算符、界符等。 b)描述工具：正规式和有限自动机 语法规则：语法单位的形成规则。 a) 语法单位通常包括：表达式、语句、分程序、过程、函数、程序等; c)描述工具：上下文无关文法 2.1.2语义 语义：一组规则，用它可以定义一个程序的意义。 描述方法： a)自然语言描述：隐藏错误、二义性和不完整性 b)形式描述： ?无二义性 ?完整性编译原理填空题
编译原理试题
编译原理复习题2017(含试卷)
编译原理期末考试题目及答案
编译原理填空集
编译原理考试试卷
编译原理复习整理(重点含答案)
编译原理练习题目
编译原理复习题
编译原理试题
编译原理考试重点题
编译原理试题及答案(期末复习版).pdf
编译原理填空集锦
编译原理考试
编译原理试题
编译原理试题库
编译原理填空
编译原理考试试卷
编译原理复习要点