编译原理 上下文无关文法 语法分析习题(附答案)_东华大学 姚励

编译原理一、是非题(下列各题你认为正确的，请在题干的括号内打“√”，错的打“×”。

每题1分，共5分)l、一个LL( l)文法一定是无二义的。

…………………………………………… ( )2、逆波兰法表示的表达式亦称前缀式。

……………………………………………()3、目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

……………()4、正规文法产生的语言都可以用上下文无关文法来描述。

………………………()5、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。

……………………………………………………………………………………()二、填空题（每题2分，共5分）1、语法分析是依据语言的( )规则进行的，中间代码产生是依据语言的( )规进行的。

2、程序语言的单词符号一般可以分为( )等等。

3、语法分析器的输入是( )，其输出是( )。

4、所谓自上而下分析法是指( )。

5、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是( )。

6、对于文法G，仅含终结符号的句型称为( )。

7、逆波兰式ab十c＋d*e—所表达的表达式为( )。

8、一个名字的属性包括( )和( )。

9、对于数据空间的存贮分配，FORTRAN采用( )策略，PASCAL采用( )策略。

10、所谓优化是指( )。

三、名词解释题（每题2分，共10分）l、词法分析器：2、语法：3、最右推导：4、语法制导翻译：5、基本块：四、简述题（每题4分，共24分）l、考虑下面的程序：…………Var i：integer；a：array[1··2] of integer；prncedure Q( b)；Var b：integer；Begini：＝1；b：＝b十2；i：＝2；b：＝b＋3End；Begina[1]：＝5；a[2]：＝6；i：＝1；Q(a[i])；print(a[l]，a[2])End．试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出a[l]，a[2]的值是什么?2、画出识别pascal中实常数(可带正负号，但不含指数部分)的状态转换图。

第5章习题1. 设有文法G[S]:S→a | ε | ( T )T→T b S | S说明：其中，终结符号集= {a, b , ( , )}。

(1) 将文法G[S]改写为LL(1)文法。

(2) 构造改写后的文法的递归子程序(给出流程图即可) 。

解：(1) 改写的LL(1)文法为S→a | ε | ( T )T→S { b S}(2) 构造的文法的递归子程序（主程序略去，请参考课件）：2. 计算下列文法中每个产生式的select集，并判断文法是否是LL(1)文法，如果是，给出LL(1)分析表，并给出输入串aebdee# 的分析过程。

G[S]：S →a AbD e | dA → BSD | eB → SA c | c D |εD → S e | ε说明：其中，终结符号集= {a, b, c, d, e}。

解：文法式编号：S →a AbD e①| d ②A → BSD③| e④B → SA c⑤| c D ⑥|ε⑦D → S e⑧| ε⑨Select(1)=first(a AbD e)={a}Select(2)=first(d)={d}Select(3)=first(BSD)={a,c,d}Select(4)=first(e)={e}Select(5)=first(Sac)={a,d}Select(6)=first(cD)={c}Select(7)=follow(B)={a,d}Select(8)=first(Se)={a,d}Select(9)=follow(D)={a,b,c,d,e}select(5)∩select(7)={a,d}所以所以不是LL（1）文法3. 对下面的文法G[S]S-> Ua | TbT-> Sc | dU-> Ub | e(1) 构造文法的句柄识别器。

(2) 该文法是LR(0)文法吗？请说明理由。

(3) 该文法是SLR(1)文法吗？若是，构造它的SLR(1)分析表，并按下表给出的（3）该文法是SLR(1)文法吗？若是，构造它的SLR(1)分析表，并按下表给出不是LR(0)文法，在1状态处有移近规约冲突。

《编译原理》考试试题及答案（附录）一、判断题：1.一个上下文无关文法的开始符，可以是终结符或非终结符。

( X )2.一个句型的直接短语是唯一的。

( X )3.已经证明文法的二义性是可判定的。

（ X ）4.每个基本块可用一个DAG表示。

（√）5.每个过程的活动记录的体积在编译时可静态确定。

（√）6.2型文法一定是3型文法。

（ x ）7.一个句型一定句子。

( X )8.算符优先分析法每次都是对句柄进行归约。

(应是最左素短语) ( X )9.采用三元式实现三地址代码时，不利于对中间代码进行优化。

（√）10.编译过程中，语法分析器的任务是分析单词是怎样构成的。

( x )11.一个优先表一定存在相应的优先函数。

( x )12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

( )13.递归下降分析法是一种自下而上分析法。

( )14.并不是每个文法都能改写成LL(1)文法。

( )15.每个基本块只有一个入口和一个出口。

( )16.一个LL(1)文法一定是无二义的。

( )17.逆波兰法表示的表达试亦称前缀式。

( )18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

( )19.正规文法产生的语言都可以用上下文无关文法来描述。

( )20.一个优先表一定存在相应的优先函数。

( )21.3型文法一定是2型文法。

( )22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。

( )二、填空题：1.( 最右推导 )称为规范推导。

2.编译过程可分为（词法分析），（语法分析），（语义分析和中间代码生成），（代码优化）和（目标代码生成）五个阶段。

3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。

4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。

5.语法分析器的输入是（），其输出是（）。

6.扫描器的任务是从（）中识别出一个个（）。

编译原理试题及答案
编译原理是计算机科学中的一门重要课程，它涉及到程序设计语言的语法、语义分析以及编译器的设计与实现等内容。

下面我们将为大家提供一些编译原理的试题及答案，希望能够帮助大家更好地理解和掌握这门课程的知识。

1. 什么是编译原理？
编译原理是研究编译器的设计与实现的一门学科，它主要包括词法分析、语法分析、语义分析、中间代码生成、代码优化和代码生成等内容。

2. 什么是词法分析？
词法分析是编译原理中的一个重要内容，它主要负责将源程序转换成一个个的单词符号，也就是词法单元。

3. 什么是语法分析？
语法分析是编译原理中的另一个重要内容，它主要负责将词法单元序列转换成抽象语法树，以便进行后续的语义分析和中间代码生成。

4. 什么是语义分析？
语义分析是编译原理中的一个关键环节，它主要负责对源程序进行语义检查，以确保程序的正确性和合法性。

5. 什么是中间代码生成？
中间代码生成是编译原理中的一个重要环节，它主要负责将源程序转换成一种中间形式的代码，以便进行后续的代码优化和代码生成。

6. 什么是代码优化？
代码优化是编译原理中的一个关键环节，它主要负责对中间代码进行优化，以提高程序的执行效率和减少资源消耗。

7. 什么是代码生成？
代码生成是编译原理中的最后一个环节，它主要负责将优化后的中间代码转换成目标机器代码，以便计算机能够执行。

以上就是关于编译原理的一些试题及答案，希望能够帮助大家更好地理解和掌握这门课程的知识。

如果大家对编译原理还有其他疑问，可以随时向我们提问，我们将竭诚为大家解答。

程序设计语言与编译——语言的设计与实现（第2版）习题4答案4-5 解：上下文有关文法（1型文法），产生的语言L（G）{=a i b i c i | i≥1,i为整数} 4-6 解：3型文法，L（G）={a i | i≥1,i为奇数}4-7 解：2型文法，L（G）={a i b i | i≥1,i为整数}4-8 解：1型文法，L（G）={a i b i c i | i≥1,i为整数}4-9 解：1. 最左推导最右推导S⇒ (A) ⇒ (B) ⇒(SdB) S⇒ (A) ⇒ (B) ⇒ (SdB)⇒ ((A)dB) ⇒ ((B)dB) ⇒ (SdS) ⇒ (Sda)⇒ ((S)dB) ⇒ ((b)dB) ⇒ ((A)da ⇒ ((B)da)⇒ ((b)dS) ⇒ ((b)da) ⇒ ((s)da⇒ ((b)da)2. 语法树4-10解：1. 因为存在推导S ⇒ SbF ⇒ SbP ⇒ Sbc ⇒ Fbc ⇒ FaPbc所以FaPbc是文法G (S) 的一个句型。

2. 语法树4-11解：因为串aaabaa可有下列两棵不同的语法树所以文法G (S)是二义文法。

因为串i(*可有下列两棵不同的语法树9-2解：（1）消除文法G的②产生式直接左递归。

A→SeA' | fA' ③A'→dA' | ε④（2）消除间接左递归：按S.A排序，将S的①产生式代入③有A→AaeA' | AbeA' | ceA' | fA' ⑤（3）消除⑤的直接左递归有A→ceA'A" | fA'A" ⑥A"→aeA'A" | beA'A" | ε⑦（4）对S的①产生式提公因子有S→AB | c ⑧B→| a | b ⑨（5）最后，文法G提取公因子，消除左递归后的产生式由⑧, ⑨, ⑥, ⑦和④组成，无多余的产生式。

编译原理试题及答案
试题：
1. 解释编译原理的定义，同时给出编译器的作用。

2. 简要描述编译过程中的四个基本步骤。

3. 解释词法分析器的功能和作用。

4. 解释语法分析器的功能和作用。

答案：
1. 编译原理是研究如何将高级语言程序转化为等价机器语言程序的一门学科。

编译器是将高级语言文本转换成等价的机器语言的软件工具。

它负责将源代码转化为目标代码，以便计算机能够理解和执行。

2. (1) 词法分析：将源代码分解成一系列单词或标记。

(2) 语法分析：根据语法规则组织单词或标记形成语法树。

(3) 语义分析：分析语法树以检测语义错误。

(4) 代码生成：根据语法树生成目标代码。

3. 词法分析器的功能是将源代码分解成一系列单词或标记。

它将源代码读取为字符流，然后将这些字符组成单词，同时可以去除空格、注释等不具有实际意义的内容。

词法分析器的作用是为语法分析器提供正确的单词序列，为后续的语义分析和代
码生成步骤建立基础。

4. 语法分析器的功能是根据语法规则组织单词或标记形成语法树。

它通过构建语法树来分析源代码的语法结构，同时可以检测语法错误。

语法分析器的作用是为后续的语义分析和代码生成步骤提供一个结构化的表示形式，便于后续的处理和转换。

编译原理试题及答案一、选择题1. 下列哪个不是编译器所需的基本处理步骤？A. 词法分析B. 语法分析C. 语义分析D. 目标代码优化答案：D2. 编译器的主要功能是将高级语言程序翻译成什么形式？A. 汇编语言B. 机器语言C. 中间代码D. 高级语言答案：B3. 下列哪个不属于编译器的后端阶段？A. 代码优化B. 目标代码生成C. 词法分析D. 目标程序优化答案：C二、填空题1. 编译器的输入是源程序，输出是目标程序。

2. 目标代码生成阶段的任务是将中间代码翻译成汇编语言或机器语言。

3. 语法分析阶段的输出是抽象语法树。

三、简答题1. 请简述编译器的工作原理。

编译器的工作原理主要包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等阶段。

词法分析阶段将源程序分解成单词（也称为词法单元），语法分析阶段根据语法规则将词法单元组织成一个语法树，语义分析阶段对语法树进行语义检查，中间代码生成阶段将语法树转化为中间代码，代码优化阶段对中间代码进行优化，最后目标代码生成阶段将中间代码转化为机器语言或汇编语言。

2. 请说明词法分析的作用是什么，如何实现？词法分析的作用是将源程序中的字符序列转化为单词序列，也就是将一段代码切分成不同的词法单元。

实现词法分析可以通过有限状态自动机来处理输入字符序列，并根据一系列规则将字符序列划分为词法单元。

常用的方法有手写分析器和使用词法分析生成器等。

3. 简要介绍一下代码优化的目的和方法。

代码优化的目的是通过对程序的中间代码或目标代码进行调整，以达到提高程序性能、减小程序的空间占用或减小程序的执行时间等目的。

代码优化的方法主要包括局部优化和全局优化两种。

局部优化主要针对某个代码块进行优化，如常量折叠、公共子表达式消除等。

全局优化则考虑整个程序，对程序的整体结构进行优化，如循环优化、函数内联等。

总结：编译原理试题及答案主要涵盖了选择题、填空题和简答题三个部分。

其中选择题主要考察对编译器基本处理步骤和功能的理解。

上下文无关文法例题
【实用版】
目录
1.什么是上下文无关文法
2.上下文无关文法的特点
3.例题解析
4.上下文无关文法在自然语言处理中的应用
正文
一、什么是上下文无关文法
上下文无关文法（Context-Free Grammar，简称 CFG）是形式语言理论中的一种文法，用来描述由符号组成的字符串。

这种文法能够生成任意长度的字符串，且生成的字符串与上下文无关，即与符号出现的顺序无关。

二、上下文无关文法的特点
1.确定性：上下文无关文法能够生成的字符串是确定的，即给定一个符号串，可以通过文法生成唯一的字符串。

2.无歧义性：上下文无关文法生成的字符串中，任意一个符号的出现都取决于其前面的符号，而不受后面的符号影响，因此不存在歧义。

3.最小性：上下文无关文法生成的字符串是最小的，即生成的字符串长度最短。

三、例题解析
假设有一个上下文无关文法如下：
```
S → AB
A → a
B → b
```
根据该文法，可以生成如下字符串：
```
S → AB → A → a → B → b
```
可以看出，字符串 "ab" 是由该文法生成的，且 "a" 和 "b" 的顺序与上下文无关。

四、上下文无关文法在自然语言处理中的应用
上下文无关文法在自然语言处理中有广泛应用，例如在编译器、词性标注、句法分析等方面。

通过研究上下文无关文法，可以更好地理解和生成自然语言，从而提高自然语言处理的效果。

综上所述，上下文无关文法是一种描述符号串的文法，具有确定性、无歧义性和最小性等特点。

《编译原理》复习题集1.名词解释短语句柄文法上下文无关文法LL (1)文法LR (1)文法语法分析无环路冇向图(DAG) 后缀式语法制导翻译遍局部优化词法分析语法分析语义分析源语言源程序目标语言中间语言(中间表示)2.简答题(1)编译程序和高级语言有什么区别？(2)编译程序的工作分为那几个阶段？(3)简述自下而上的分析方法。

(4)口标代码有哪几种形式？生成口标代码吋通常应考虑哪几个问题?(5)何谓优化？按所涉及的程序范围可分为哪几级优化？(6)简述代码优化的目的和意义。

3.叙述下面的正规式描述的语言，并画岀接受该语言的最简DFA的状态转换图。

(1 101 )*0*4.Pascal语言无符号数的止规定义如卜•：num T digit (. digit) ? (E(+|—)? digit) ?其中digit表示数字，用状态转换图表示接受无符号数的确定有限自动机。

5.画出Pascal中实数(不带正负号，可带指数部分)的状态转换图。

6.用状态转换图表示接收(a|b)*aa的确定的冇限自动机。

7.处于/*和*/之间的串构成注解，注解屮间没有*/。

画出接受这种注解的DFA的状态转换图。

8.某操作系统下合法的文件名为device:name.extension其中第一部分(device:)和第三部分(.extension) 口J缺省,device, name和extension都是字母串，长度不限，但至少为1,画出识别这种文件名的确定有限自动机。

9.构造一个DFA,它接受Z={0, 1}± 0和1的个数都是偶数的字符串。

10.设有非确定的有自限动机NFAM二({A, B, C}, {0, 1}, 5, {A}, {C}),其中:5 (A, 0) = {C} 5(A, 1)二{A, B} 6 (B, 1) = {C} 5 (C, 1) = {C}。

请画出状态转换距阵和状态转换图。

11.设匕{a,b,c}*是满足下述条件的符号串构成的语言：(1)若出现a ,则其后至少紧跟两个c ；(2)若出现b，其后至少紧跟一个c o试构造识别L的最小化的DFA ,并给出描述L的正规表达式。

编译原理试题及答案编译原理是计算机科学中的重要基础课程，涉及到编程语言的设计、编译器的构建等内容。

为了帮助大家更好地掌握编译原理的知识，我整理了一些编译原理试题及答案，希望能够对大家的学习有所帮助。

1. 什么是编译原理？简要说明其作用和意义。

编译原理是研究如何将高级语言程序翻译成目标代码的一门学科。

它的作用和意义在于帮助人们理解程序设计语言的语法和语义，掌握程序设计语言的翻译方法和技术，从而更好地进行程序设计和编程工作。

2. 请简要描述编译器的基本工作原理。

编译器的基本工作原理包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等步骤。

其中，词法分析将源程序转换成单词流，语法分析将单词流转换成语法树，语义分析对语法树进行语义检查，中间代码生成将语法树转换成中间代码，代码优化对中间代码进行优化，目标代码生成将优化后的中间代码转换成目标代码。

3. 什么是文法？简要说明文法的分类及其特点。

文法是用于描述编程语言语法结构的形式化工具。

文法可以分为上下文无关文法和上下文相关文法两种，其中上下文无关文法的特点是产生式左部只能是一个非终结符，上下文相关文法的特点是产生式左部可以是一个非终结符和一个终结符的串。

4. 请简要说明语法分析的两种基本方法及其区别。

语法分析的两种基本方法是自顶向下分析和自底向上分析。

自顶向下分析是从文法的开始符号出发，采用推导或归纳的方法，逐步构造出推导树或语法树；自底向上分析是从输入串出发，采用规约或移进的方法，逐步构造出推导树或语法树。

5. 请简要说明语义分析的主要任务及其实现方法。

语义分析的主要任务是对源程序进行语义检查，确保程序具有正确的含义。

语义分析的实现方法包括类型检查、作用域检查、中间代码生成等步骤，其中类型检查用于检查表达式的类型是否匹配，作用域检查用于检查标识符的作用域是否正确，中间代码生成用于将语法树转换成中间代码表示形式。

以上就是我整理的编译原理试题及答案，希望对大家的学习有所帮助。