编译原理的复习提纲
1.编译原理=形式语言+编译技术
2.汇编程序：
把汇编语言程序翻译成等价的机器语言程序
3.编译程序：
把高级语言程序翻译成等价的低级语言程序
4.解释执行方式：
解释程序，逐个语句地模拟执行
翻译执行方式：
翻译程序，把程序设计语言程序翻译成等价的目标程序
5.计算机程序的编译过程类似，一般分为五个阶段：
词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成
词法分析的任务：
扫描源程序的字符串，识别出的最小的语法单位（标识符或无正负号数等）
语法分析是：
在词法分析的基础上的，语法分析不考虑语义。语法分析读入词法分析程序识别出的符号，根据给定的语法规则，识别出各个语法结构。
语义分析的任务是检查程序语义的正确性，解释程序结构的含义，语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。
语法分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序
代码优化的主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码
编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序
编译程序结构包括五个基本功能模块和两个辅助模块
6.编译划分成前端和后端。
编译前端的工作包括词法分析、语法分析、语义分析。编译前端只依赖于源程序，独立于目标计算机。前端进行分析
编译后端的工作主要是目标代码的生成和优化后端进行综合。独立于源程序，完全依赖于目标机器和中间代码。
把编译程序分为前端和后端的优点是：
可以优化配置不同的编译程序组合，实现编译重用，保持语言与机器的独立性。
7.汇编器把汇编语言代码翻译成一个特定的机器指令序列
第二章
1.符号，字母表，符号串，符号串的长度计算P18，子符号串的含义，符号串的简单运算XY，Xn，
2.符号串集合的概念，符号串集合的乘积运算，方幂运算，闭包与正闭包的概念P19，P20A0
={ε}
3.重写规则，简称规则。非xx（V
n），xx（V
t）的概念。
4.文法的概念。P23识别符号.P23文法的第一个重写规则的左部符号为识别符号。
BNF表示法P6
5.直接推导和直接规约，广义推导广义规约，P24最左推导，最右推导P62
6.句型和句子Ｐ26，短语，简单短语，句柄Ｐ２６，Ｐ２７
7.语言的定义Ｐ31
8.递归，左递归Ｐ32
9.文法的形式化定义Ｐ36定义重点是正则文法和上下文无关文法
0型文法，短语结构语言
１型文法，上下文有关文法CSG
2型文法，上下文无关文法CFG
3型文法，正则文法RG
3型语言类（2型语言类（1型语言类（0型语言类
但四种语言之间没有必然的包含关系P38
3型语言的定义有穷状态自动机P41
2型语言下推自动机
1型语言线性界限自动机
0型语言图灵机
10.消去规则左递归P51
11.语法分析树的构造，能够根据语法书来寻找短语，直接短语，句柄。
12.文法的二义性问题P58，文法的二义性是不可判定的
-------------------------------
第三章
1.词法分析的功能P69
2.词法分析器可以有两种实现模式：
完全融合模式（大多采用）和相对独立模式，完全独立方式P71
3.有穷状态自动机的概念，如何从正则文法构造有穷状态转换自动机P72
4.
5.
6.
7.如何从有穷状态转换自动机构造正则文法P75
确定有穷状态自动机DFA五元组（K，Σ，M，S，F），五个字母的含义。P75非确定有穷状态自动机NFA，如何将NFA转化为DFAP82
DFA的化简
8.属性字由符号类和符号值组成。特定符号类，一个符号类对应一个符号值：
关键字、括号，运算符。非特定符号类：
标示符，无符号整数。符号类识别不同类的符号，符号值识别同类的不同符号P90
9.字符表，符号机内表示对照表，标示符表，无符号整数表各自的定义和作用P93词法分析程序的大致思路
------------------------------
第四章自顶向下（重点是预测分析表的构造和应用预测分析表进行字符串分析）
1.带回溯的自顶向下分析方法P121（一般采用最左或者最右推导）
2.无回溯的自顶向下分析方法：
条件，无左递归性，无回溯性。
3.预测分析技术：
消去文法左递归P51；构造first集合和follow集合P138，构造预测分析表P139进行字符串分析P134
-------------------------------------
第五章自底向上（重点是构造算符优先矩阵并进行字符串的分析）
1.规范分析：
最右推导被称为规范推导，最左规约被称为规范规约。P145
2.分析需要解决的两个基本问题：
找出要被归约的短语u；确定归约到哪个非终结符号U
3.一个符号串的前缀是指该串的任一部分。一个规范句型的前缀若不含句柄之后的任何符号就称为活前缀
4.基本方法：
移入规约xxP147四个动作之一：
移进归约接受出错
5.算符优先分析技术：
P150定义
5.2构造算符优先关系表P151-154算符优先识别算法Ｐ１５５
6.LR(k)分析技术,要知道其中定义（为什么引入LR(K)）:
圆点在产生式最右端的项目称为可归约项，如E→E+T·；圆点后面是终结符的项目称为移进项，如E→E·+T；圆点后面是非终结符的项目称为待约项，如
E→E+·T。
项，项集，项集的闭包
--------------------------------------------
第六章（重点是四元式、逆波兰式、抽象语法分析树（三元式）)
1.语义分析的基本功能：
确定类型；类型检查；识别含义，作相应的语意处理；其他一些静态语义检查。P215
2.语义分析以语法分析部分的输出（语法分析树或其他等价内部中间表示）为输入，输出中间表示代码，甚至目标代码。P215
3.语义是上下文相关的
4.语法制导翻译技术
5.抽象语法树P297
6.逆xx式P300
7.四元组P306
-------------------------------------------------
第七章
1.代码优化的定义P348，代码优化进行的是等价变换，为优化进行努力是值得的。
2.基本块的概念，对基本块的优化：
合并常量计算，消除公共子表达式，消减计算强度，删除无用代码。对循环的优化：
循环不变表达式外提，归纳变量删除，计算强度消减。
3.代码优化的三个过程：
控制流分析，数据流分析，变化。P350各自的含义
4.代码优化是基于中间表示代码进行的
5.窥孔优化：
定义P395包括：
四种典型优化，各自的含义、
《编译原理》模拟试题一 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．计算机高级语言翻译成低级语言只有解释一种方式。(×) 2．在编译中进行语法检查的目的是为了发现程序中所有错误。(×) 3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 (√ ) 4．正则文法其产生式为 A->a ， A->Bb, A,B∈VN ， a 、b∈VT 。 (×) 5．每个文法都能改写为 LL(1) 文法。 (√) 6．递归下降法允许任一非终极符是直接左递归的。 (√) 7．算符优先关系表不一定存在对应的优先函数。 (×) 8．自底而上语法分析方法的主要问题是候选式的选择。 (×) 9．LR 法是自顶向下语法分析方法。 (×) 10．简单优先文法允许任意两个产生式具有相同右部。 (×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．一个编译程序中，不仅包含词法分析，_____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析B．( )文法分析C．( )语言分析D．( )解释分析 2．词法分析器用于识别_____。 A．( ) 字符串B．( )语句 C．( )单词 D．( )标识符 3．语法分析器则可以发现源程序中的_____。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正D．( ) 语法错误 4．下面关于解释程序的描述正确的是_____。
(1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1)C．( ) (1)(2)(3) D．( ) (2)(3) 5．解释程序处理语言时 , 大多数采用的是_____方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 6．编译过程中 , 语法分析器的任务就是_____。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4) C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 7．编译程序是一种_____。 A. ( ) 汇编程序B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 8．文法 G 所描述的语言是_____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 9．文法分为四种类型，即0型、1型、2型、3型。其中3型文法是_____。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法 10．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。 A．( ) 句子B．( ) 句型 C．( ) 单词 D．( ) 产生式 三、填空题(每空1分，共10分)
编译原理考试题及答案汇总 一、选择 1．将编译程序分成若干个“遍”是为了_B__。 A . 提高程序的执行效率 B.使程序的结构更加清晰 C. 利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2．正规式 MI 和 M2 等价是指__C__。 A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。 C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等 3．中间代码生成时所依据的是 _C_。 A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 4．后缀式 ab+cd+/可用表达式__B_来表示。 A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d 6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析 7．词法分析器用于识别__C___。 A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符 8．语法分析器则可以发现源程序中的___D__。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正 D．( ) 语法错误 9．下面关于解释程序的描述正确的是__B___。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3) 10．解释程序处理语言时 , 大多数采用的是__B___方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 11．编译过程中 , 语法分析器的任务就是__B___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4)C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 12．编译程序是一种___C__。 A. ( ) 汇编程序 B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 13．文法 G 所描述的语言是_C____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___B__。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __D___。 A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式 16．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_C____。
1.解释程序：不生成目标代码 编译程序：生成目标代码 2.编译程序组成：8个 分析< 前端>：(词法分析程序、语法分析程序、语义分析程序、中间代码生成程序) 综合< 后端>：（代码优化程序、目标代码生成程序） 贯穿始末：表格管理程序、出错处理程序 3.文法四元组： 终结符号集合Vt 、非终结符号集合Vn、产生式集合P、识别符号(开始符号)S V T∩V N＝Φ 文法-> 语言（推导、规约）唯一；语言-> 文法（凑规则）不唯一。 4.文法分类： 0型文法(短语结构文法)：左侧至少含有一个非终结符 1型文法(上下文有关文法)：左侧长度<= 右侧长度S->ε除外，S不能出现在右侧2型文法(上下文无关文法)：左侧只能有一个非终结符( 语法分析) 3型文法(正规文法)：A-> aB A->a 右线性；( 词法分析) A->Ba 或A->a 左线性（看非终结符位置） 5.A*＝A0 ∪A+ A0 ＝{ε} !={ } ＝Φ空集 A+ ＝AA* ＝A*A 6.句型：符号串x是从识别符号S推导出来的，x称为一个句型 句子：x仅由终结符号组成，仅含终结符号的句型是一个句子 短语：子树的末端（叶子）从左至右连成的串（包括整棵语法树） 简单子树：只含有单层分枝的子树 直接短语( 简单短语)：由简单子树的叶子组成 句柄：最左边的直接短语（不一定含终结符） 素短语：至少含有一个终结符的短语，并且除它自身之外不再含任何更小的素短语最左素短语：最左边的素短语 短语：P（相对于T、E）、P+T（相对于E）、i（相对于P、F）、P+T+i（相对于E）直接短语：P、i 句柄：P (最左边的直接短语) 素短语：P+T 、i （至少含有一个终结符的短语）最左素短语：P+T 7.二义性文法：有两个不同的最左推导或有两个不同的最右推导或能产生两棵语法树 8.文法产生式正规式 规则1 A→xB B→y A = xy
编译原理考试题及答案汇总一、选择 1．将编译程序分成若干个“遍”是为了_B__。 A . 提高程序的执行效率 B.使程序的结构更加清晰 C. 利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2．正规式 MI 和 M2 等价是指__C__。 A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。 C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等 3．中间代码生成时所依据的是 _C_。 A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 4．后缀式 ab+cd+/可用表达式__B_来表示。 A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d 6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析 7．词法分析器用于识别__C___。 A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符 8．语法分析器则可以发现源程序中的___D__。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正 D．( ) 语法错误 9．下面关于解释程序的描述正确的是__B___。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3) 10．解释程序处理语言时 , 大多数采用的是__B___方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 11．编译过程中 , 语法分析器的任务就是__B___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4)C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 12．编译程序是一种___C__。 A. ( ) 汇编程序 B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 13．文法 G 所描述的语言是_C____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___B__。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __D___。 A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式
一、填空题（每空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.汇编器把汇编语言代码翻译成一个特定的机器指令序列 第二章 1.符号，字母表，符号串，符号串的长度计算P18，子符号串的含义，符号串的简单运算XY，Xn， 2.符号串集合的概念，符号串集合的乘积运算，方幂运算，闭包与正闭包的概念P19，P20A0 ={ε} 3.重写规则，简称规则。非xx（V
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}。 请画出状态转换距阵和状态转换图。 状态转换距阵为： 状态转换图为：
二填空题 1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两 种：静态存储分配方案和动态存储分配方案，而后者又分为（1）和（2）。 2. 规范规约是最（3）规约。 3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4）、语义分析与中间代码生成，代码优化及（5）。另外还有（6）和出错处理。 4．表达式x+y*z/(a+b)的后缀式为（7）。 5．文法符号的属性有综合属性和（8）。 6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i，j]的地址计算公式为（9）。 7．局部优化是局限于一个（10）范围内的一种优化。 答案 (1) 栈式动态存储分配(2) 堆式动态存储分配 (3) 左(4) 语法分析(5) 目标代码生成 (6) 表格管理 (7) xyz*ab+/+ (8) 继承属性 (9) a+(i-1)*20+j-1 (10) 基本块 8 词法规则通常可以用____正规式________，正规文法、____自动机________描述；语法规则通常用___2型文法___来描述；语义规则通常用__属性文法_____来描述。
9 编译原理的工作过程一般划分为：词法分析、语法分析、语义分析、优化和目标代码生成五个阶段。 1.( )称为规范推导。 2.编译过程可分为（），（），（），（）和（）五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。 4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。 5.语法分析器的输入是（），其输出是（）。 6.扫描器的任务是从（）中识别出一个个（）。 7.符号表中的信息栏中登记了每个名字的有关的性质，如（）等等。 8.一个过程相应的DISPLAY表的内容为（）。 9.一个句型的最左直接短语称为句型的（）。 10.常用的两种动态存贮分配办法是（）动态分配和（）动态分配。 11.一个名字的属性包括( )和( )。 12.常用的参数传递方式有（），（）和（）。 13.根据优化所涉及的程序范围，可将优化分成为（），（）
1.解释程序：不生成目的代码 编译程序：生成目的代码 2.编译程序构成：8个 分析< 前端>：(词法分析程序、语法分析程序、语义分析程序、中间代码生成程序) 综合< 后端>：（代码优化程序、目的代码生成程序） 贯穿始末：表格管理程序、出错解决程序 3.文法四元组： 终结符号集合Vt 、非终结符号集合Vn、产生式集合P、辨认符号(开始符号)S V T∩V N＝Φ 文法-> 语言（推导、规约）唯一；语言-> 文法（凑规则）不唯一。 4.文法分类： 0型文法(短语构造文法)：左侧至少具有一种非终结符 1型文法(上下文关于文法)：左侧长度<= 右侧长度S->ε除外，S不能出当前右侧2型文法(上下文无关文法)：左侧只能有一种非终结符( 语法分析) 3型文法(正规文法)：A-> aB A->a 右线性；( 词法分析) A->Ba 或A->a 左线性（看非终结符位置） 5.A*＝A0 ∪A+ A0 ＝{ε} !={ } ＝Φ空集 A+ ＝AA* ＝A*A 6.句型：符号串x是从辨认符号S推导出来，x称为一种句型 句子：x仅由终结符号构成，仅含终结符号句型是一种句子 短语：子树末端（叶子）从左至右连成串（涉及整棵语法树） 简朴子树：只具有单层分枝子树 直接短语( 简朴短语)：由简朴子树叶子构成 句柄：最左边直接短语（不一定含终结符） 素短语：至少具有一种终结符短语，并且除它自身之外不再含任何更小素短语
最左素短语：最左边素短语 短语：P（相对于T、E）、P+T（相对于E）、i（相对于P、F）、P+T+i（相对于E）直接短语：P、i 句柄：P (最左边直接短语) 素短语：P+T 、i （至少具有一种终结符短语）最左素短语：P+T 7.二义性文法：有两个不同最左推导或有两个不同最右推导或能产生两棵语法树 8.文法产生式正规式 规则1 A→xB B→y A = xy 规则2 A→xA|y A = x*y 右线性 A→Ax|y A = yx* 左线性 规则3 A→x A→y A = x|y 9.DFA 初态唯一，转换函数为单值映射 表达方式：转移矩阵、状态转换图 状态转换图上若存在一条从初态到某一终态道路，且这条路上所有弧标记符连成字符串为t，则称t被DFA接受。 10.NFA初态可为各种，转换函数为多值映射 拟定化：与某一NFA等价DFA不唯一 1.状态集合Iε-闭包 2.move函数 最小化：消除多余状态和合并等价状态 多余状态：从自动机开始状态出发，任何输入串也不能到达那个状态；或者从这个状态没有通路到达终态。
一、选择题（每个选择题 2 分，共 20 分） 1 ．文法 G 产生的⑴ 的全体是该文法描述的语言。 A ．句型 B. 终结符集 C. 非终结符集 D. 句子 2 ．若文法 G 定义的语言是无限集，则文法必然是⑵ ： A ．递归的 B 前后文无关的 C 二义性的 D 无二义性的 3 ． Chomsky 定义的四种形式语言文法中， 0 型文法又称为⑶ 文法； 1 型文法又称为⑷ 文法； 2 型语言可由⑸ 识别。 A ．短语结构文法 B 前后文无关文法 C 前后文有关文法 D 正规文法 E 图灵机 F 有限自动机 G 下推自动机 4 ．一个文法所描述的语言是⑹ ；描述一个语言的文法是⑺ 。 A ．唯一的 B 不唯一的 C 可能唯一，好可能不唯一 5 ．数组的内情向量中肯定不含有数组的⑻ 的信息 A．维数 B.类型 C.维上下界 D.各维的界差 6 ．在下述的编译方法中，自底向上的方法有⑼ ，自顶向下的分析方法有⑽ 。 ①简单优先分析②算符优先分析③递归下降分析④预测分析技术⑤LR（K）分析 ⑥ SLR（k）分析⑦ LL（k）分析⑧LALR（K）分析 A.③④⑦ B. ③④⑧ C.①②⑧ D.③④⑤⑥⑦ E.①②⑤⑥⑦ F. ①②⑤⑥⑧ 二、简答题（每小题 5 分，共 20 分） 1 ． LL （ 1 ）分析法对文法有哪些要求？ 2 ．常见的存储分配策略有几种？它们都适合于什么性质的语言？ 3 ．常见循环优化都有哪些项目？ 4 ．什么是活动记录？它主要由哪些内容构成？ 五、（ 12 分）已给文法 G[S] ：S → SaP | Sf | P P → qbP | q 将 G[S] 改造成 LL （ 1 ）文法，并给出 LL （ 1 ）分析表。 七、（ 8 分）将下面的条件语句表示成逆波兰式和四元式序列： if a>b then x:=a+b*c else x:=b-a; 八、（ 8 分）给定基本块： A:=3*5 B:=E+F C:=A+12 D:=E+F A:=D+12 C:=C+1 E:=E+F 假定出基本块后，只有 A 、 C 、 E 是活跃的，给出用 DAG 图完成优化后的代码序列。参考答案： 一、⑴ D ⑵ A ⑶ A ⑷ C ⑸ G. ⑹ A ⑺ B ⑻ A ⑼ F ⑽ A 二、 1 ．对于 G 中的每个产生式A →γ 1 | γ 2 | … | γ m ，其各候选式均应满足：（1）不同的候选式不能推出以同一终结符号打头的符号串，即 FIRST( γ i ) ∩ FIRST( γ j )= φ（1 ≤ i ，j ≤ m ；i ≠ j ）
参考答案 一、单项选择题(共10小题，每小题2分，共20分) 1．语言是 A ．句子的集合 B ．产生式的集合 C ．符号串的集合 D ．句型的集合 2．编译程序前三个阶段完成的工作是 A ．词法分析、语法分析和代码优化 B ．代码生成、代码优化和词法分析 C ．词法分析、语法分析、语义分析和中间代码生成 D ．词法分析、语法分析和代码优化 3．一个句型中称为句柄的是该句型的最左 A ．非终结符号 B ．短语 C ．句子 D ．直接短语 4．下推自动机识别的语言是 A ．0型语言 B ．1型语言 C ．2型语言 D ．3型语言 5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即 A ． 字符 B ．单词 C ．句子 D ．句型 6．对应Chomsky 四种文法的四种语言之间的关系是 A ．L 0?L 1?L 2?L 3 B ．L 3?L 2?L 1?L 0 C ．L 3=L 2?L 1?L 0 D ．L 0?L 1?L 2=L 3 7．词法分析的任务是 A ．识别单词 B ．分析句子的含义 C ．识别句子 D ．生成目标代码 8．常用的中间代码形式不含 A ．三元式 B ．四元式 C ．逆波兰式 D ．语法树 9． 代码优化的目的是 A ．节省时间 B ．节省空间 C ．节省时间和空间 D ．把编译程序进行等价交换 10．代码生成阶段的主要任务是 A ．把高级语言翻译成汇编语言 B ．把高级语言翻译成机器语言 C ．把中间代码变换成依赖具体机器的目标代码 装 订 线
D．把汇编语言翻译成机器语言 二、填空题（本大题共5小题，每小题2分，共10分） 1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。2．编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静态存储分配)方案和(动态存储分配)方案。 5．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。 三、名词解释题(共5小题，每小题4分，共20分) 1．词法分析 词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则 从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位， 并转换成统一的内部表示(token)，送给语法分析程序。 2．LL(1)文法 若文法的任何两个产生式A →α | β都满足下面两个条件： （1）FIRST(α) ? FIRST(β ) = φ； （2）若β?* ε，那么FIRST(α) ? FOLLOW( A ) = φ。 我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左 向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步 动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一 些明显的性质，它不是二义的，也不含左递归。 3．语法树 句子的树结构表示法称为语法树(语法分析树或语法推导树)。 给定文法G=(V N，V T，P，S)，对于G的任何句型都能构造与之关联的 语法树。这棵树具有下列特征： (1)根节点的标记是开始符号S。 (2)每个节点的标记都是V中的一个符号。 (3)若一棵子树的根节点为A，且其所有直接子孙的标记从左向右的排列 次序为A1A2…A R，那么A→A1A2…A R一定是P中的一条产生式。
编译原理： 编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。编译原理是计算机专业设置的一门重要的专业课程。编译原理课程是计算机相关专业学生的必修课程和高等学校培养计算机专业人才的基础及核心课程，同时也是计算机专业课程中最难及最挑战学习能力的课程之一。编译原理课程内容主要是原理性质，高度抽象。 基本概念： 编译原理即是对高级程序语言进行翻译的一门科学技术, 我们都知道计算机程序由程序语言编写而成, 在早期计算机程序语言发展较为缓慢, 因为计算机存储的数据和执行的程序都是由0、1代码组合而成的, 那么在早期程序员编写计算机程序时必须十分了解计算机的底层指令代码通过将这些微程序指令组合排列从而完成一个特定功能的程序, 这就对程序员的要求非常高了。人们一直在研究如何如何高效的开发计算机程序, 使编程的门槛降低。 编译器： C语言编译器是一种现代化的设备, 其需要借助计算机编译程序, C语言编译器的设计是一项专业性比较强的工作, 设计人员需要考虑计算机程序繁琐的设计流程, 还要考虑计算机用户的需求。计算机的种类在不断增加, 所以, 在对C语言编译器进行设计时, 一定要增加其适用性。C语言具有较强的处理能力, 其属于结构化语言, 而且在
计算机系统维护中应用比较多, C语言具有高效率的优点, 在其不同类型的计算机中应用比较多。 C语言编译器前端设计 编译过程一般是在计算机系统中实现的, 是将源代码转化为计算机通用语言的过程。编译器中包含入口点的地址、名称以及机器代码。编译器是计算机程序中应用比较多的工具, 在对编译器进行前端设计时, 一定要充分考虑影响因素, 还要对词法、语法、语义进行分析。 1 词法分析 词法分析是编译器前端设计的基础阶段, 在这一阶段, 编译器会根据设定的语法规则, 对源程序进行标记, 在标记的过程中, 每一处记号都代表着一类单词, 在做记号的过程中, 主要有标识符、关键字、特殊符号等类型, 编译器中包含词法分析器、输入源程序、输出识别记号符, 利用这些功能可以将字号转化为熟悉的单词。 2 语法分析 语法分析是指利用设定的语法规则, 对记号中的结构进行标识, 这包括句子、短语等方式, 在标识的过程中, 可以形成特殊的结构语法树。语法分析对编译器功能的发挥有着重要影响, 在设计的过程中, 一定要保证标识的准确性。 3 语义分析 语义分析也需要借助语法规则, 在对语法单元的静态语义进行检查时, 要保证语法规则设定的准确性。在对词法或者语法进行转化
第一章引论 一.单项选择题 1. 如果一个编译程序能产生不同于其宿主机的机器代码，则称它为：___________________ 。 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. Lex是语法分析自动生成器 d. 解释程序属于编译程序 7. 目标代码生成阶段所生成的目标代码的形式不可能是____。 a. 绝对指令代码 b. 可充定位的指令代码。 c. 汇编指令代码 d. 三地址代码 8. 语义错误是指源程序中不符合语义规则的错误，不包括：____ a. 非法字符错误 b. 类型不一致错误。 c. 作用域错误 d. 说明错误
《编译原理》考试试题及答案（汇总） 一、是非题（请在括号，正确的划√，错误的划×）（每个2分，共20分） 1．编译程序是对高级语言程序的解释执行。(× ) 2．一个有限状态自动机中，有且仅有一个唯一的终态。(×) 3．一个算符优先文法可能不存在算符优先函数与之对应。(√ ) 4．语法分析时必须先消除文法中的左递归。(×) 5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。(√) 6．逆波兰表示法表示表达式时无须使用括号。(√ ) 7．静态数组的存储空间可以在编译时确定。(×) 8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。(×) 9．两个正规集相等的必要条件是他们对应的正规式等价。(× ) 10．一个语义子程序描述了一个文法所对应的翻译工作。(×) 二、选择题(请在前括号选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．词法分析器的输出结果是_____。 A．( ) 单词的种别编码B．( ) 单词在符号表中的位置 C．( ) 单词的种别编码和自身值D．( ) 单词自身值 2．正规式 M 1 和 M 2 等价是指_____。 A．( ) M1和M2的状态数相等 B．( ) M1和M2的有向边条数相等C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等
3．文法G：S→xSx|y所识别的语言是_____。 A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 4．如果文法G是无二义的，则它的任何句子α_____。 A．( )最左推导和最右推导对应的语法树必定相同 B．( ) 最左推导和最右推导对应的语法树可能不同 C．( ) 最左推导和最右推导必定相同 D．( )可能存在两个不同的最左推导，但它们对应的语法树相同 5．构造编译程序应掌握______。 A．( )源程序B．( ) 目标语言 C．( ) 编译方法 D．( ) 以上三项都是 6．四元式之间的联系是通过_____实现的。 A．( ) 指示器B．( ) 临时变量 C．( ) 符号表 D．( ) 程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为_____。 A. ( ) ┐AB∨∧CD∨B．( ) A┐B∨CD∨∧ C．( ) AB∨┐CD∨∧ D．( ) A┐B∨∧CD∨ 8. 优化可生成_____的目标代码。 A．( ) 运行时间较短B．( ) 占用存储空间较小C．( ) 运行时间短但占用存空间大D．( ) 运行时间短且占用存储空间小 9．下列______优化方法不是针对循环优化进行的。 A. ( ) 强度削弱 B．( ) 删除归纳变量 C．( ) 删除多余运算 D．( ) 代码外提
第一章概论 1.什么是编译器？输入输出？ 编译器是将一种语言翻译为另一种语言的计算机程序。 输入：源语言( source language) 编写的程序 输出：目标语言( target language ) 编写的程序。 2.汇编语言的优缺点 优点：汇编语言大大提高了编程的速度和准确度 缺点：编写起来也不容易,阅读和理解很难；而且汇编语言的编写严格依赖于特定的机器，所以为一台计算机编写的代码在应用于另一台计算机时必须完全重写。 3.什么是解释器？与编译器的区别？ 解释程序是如同编译器的一种语言翻译程序。 与编译器的区别：它立即执行源程序而不是生成在翻译完成之后才执行的目标代码。 4.乔姆斯基分类结构有几种文法？名称？相互关系？ 4种 名称： 0型无限制文法 1型上下文相关文法 2型上下文无关文法 3型正则文法 相互关系：其中的每一个都是其前者的专门化。 5.什么是扫描器？扫描器的功能是什么？ 扫描器就是语法分析程序。 功能：依据词法规则，分析由字符组成的源程序，把它分割为一个一个具有独立意义的最小语法单位，即单词。 6.什么是编辑器？IDE中编辑器的新功能 编译器通常接受由任何生成标准文件(例如ASCII 文件)的编辑器编写的源程序。 IDE 中编辑器的新功能：尽管编辑器仍然生成标准文件，但会转向正被讨论的程序设计语言的格式或结构。这样的编辑器称为基于结构的，且它早已包括了编译器的某些操作；因此，程序员就会在程序的编写时而不是在编译时就得知错误了。从编辑器中也可调用编译器以及与它共用的程序，这样程序员无需离开编辑器就可执行程序。
7.什么是调试器，与编译器的关系 调试程序是可在被编译了的程序中判定执行错误的程序。 运行一个带有调试程序的程序与直接执行不同，这是因为调试程序保存着所有的或大多数源代码信息(诸如行数、变量名和过程)。它还可以在预先指定的位置(称为断点)暂停执行，并提供有关已调用的函数以及变量的当前值的信息。为了执行这些函数，编译器必须为调试程序提供恰当的符号信息。 8.编译器有哪几个功能模块？各模块的功能及输入输出 目标代码
一、回答下列问题：(30分) 1．什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？ 解答： S-属性文法是只含有综合属性的属性文法。（2分） L-属性文法要求对于每个产生式A X1X2…Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该属性仅依赖于： （1）产生式Xj的左边符号X1,X2…Xj-1的属性； （2）A的继承属性。（2分） S-属性文法是L-属性文法的特例。（2分） 2．什么是句柄？什么是素短语？ 一个句型的最左直接短语称为该句型的句柄。（3分）素短语是这样的一个短语，它至少包含一个终结符并且不包含更小的素短语。（3分） 3．划分程序的基本块时，确定基本块的入口语句的条件是什么？ 解答： （1）程序第一个语句，或 （2）能由条件转移语句或无条件转移语句转移到的语句，或 （3）紧跟在条件转移语句后面的语句。 4．(6分)运行时的DISPLAY表的内容是什么？它的作用是什么？ 答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY 表可以访问其外层过程的变量。 5．(6分)对下列四元式序列生成目标代码： A:=B*C D:=E+F G:=A+D H:=G*2 其中，H是基本块出口的活跃变量，R0和R1是可用寄存器 答： LD R0，B MUL R0，C LD R1，E ADD R1，F ADD R0，R1 MUL R0，2 ST R0，H
编译原理试题及答案 <高级版> 一、对于文法 G[S] ： S → 1A | 0B | ε A → 0S | 1AA B → 1S | 0BB ⑴ (3 分 ) 请写出三个关于 G[S] 的句子； ⑵ (4 分 ) 符号串 11A0S 是否为 G [S] 的句型？试证明你的结论。 ⑶ (3 分 ) 试画出 001B 关于 G [S] 的语法树。 二、请构造一个文法，使其产生这样的表达式 E ：表达式中只含有双目运算符 + 、 * ，且 + 的优先级高于 * ， + 采用右结合， * 采用左结合，运算对象只有标识符 i ，可以用括号改变运算符优先级。要求给出该文法的形式化描述。 三、设有语言 L={ α | α∈ {0,1} + ，且α不以 0 开头，但以 00 结尾 } 。 ⑴试写出描述 L 的正规表达式； ⑵构造识别 L 的 DFA （要求给出详细过程，并画出构造过程中的 NDFA 、 DFA 的状态转换图，以及 DFA 的形式化描述 ) 。 四、给定文法 G[S] ： S → AB A → a B | bS | c B → AS | d ⑴ (6 分 ) 请给出每一个产生式右部的 First 集；
⑵ (3 分 ) 请给出每一个非终结符号的 Follow 集； ⑶ (8 分 ) 请构造该文法的 LL(1) 分析表； ⑷ (8 分 ) 什么是 LL(1) 文法？该文法是 LL(1) 文法吗？为什么？ 五、给定文法 G[S] ： S → SaA|a A → AbS|b ⑴请构造该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 。 ⑵请构造该文法的 LR(0) 分析表。 ⑶什么是 LR(0) 文法？该文法是 LR(0) 文法吗？为什么？ ⑷什么是 SLR(1) 文法？该文法是 SLR(1) 文法吗？为什么？ 六、给定下列语句： if a+b>c then x := a*(b-c) + (b*c-d)/e ⑴写出其等价的逆波兰表示； ⑵写出其等价的四元式序列。 七、已知下列 C 语言程序： int * f() { int a = 100; return &a; } main()