《编译原理》常见题型

一、填空题

1、编译程序的工作过程一般可以划分为 词法分析 ， 语法分析 ， 语义分析 ，中间代码生成 ， 目标代码生成 等几个基本阶段。

2、若源程序是用高级语言编写的，目标程序是 机器语言程序或汇编程序 ，则其翻译程序称为编译程序。

3、编译方式与解释方式的根本区别在于 是否生成目标代码 。

5、对编译程序而言，输入数据是 源程序 ，输出结果是 目标程序 。

7、若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为 编译程序 。

8、一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括 表格处理 和 出错处理 。其中，词法分析器用于识别 单词 。

10、一个上下文无关文法所含四个组成部分是 一组终结符号 、 一组非终结符号 、 一个开始符号 、 一组产生式 。

12、产生式是用于定义 语法成分 的一种书写规则。

13、设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为 L(G)＝{x│ S?x，x∈VT*} 。

14、设G是一个给定的文法，S是文法的开始符号，如果S?x（其中x∈V*），则称x是文法的一个 句型 。

15、设G是一个给定的文法，S是文法的开始符号，如果S?x (其中x∈VT*)，则称x是文法的一个 句子 。

16、扫描器的任务是从源程序中识别出一个个 单词符号 。

17、语法分析最常用的两类方法是 自上而下 和 自下而上 分析法。 18、语法分析的任务是识别给定的终结符串是否为给定文法的 句子 。 19、递归下降法不允许任一非终结符是直接 左 递归的。

20、自顶向下的语法分析方法的关键是 如何选择候选式 的问题。 21、递归下降分析法是自 顶向下 分析方法。

22、自顶向下的语法分析方法的基本思想是：从文法的 开始符号 开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的 句子 ，使之与给定的输入串匹配。

23、自底向上的语法分析方法的基本思想是：从给定的终结符串开始，根据文法的规则一步一步的向上进行 直接归约 ，试图 归约 到文法的 开始符号 。 24、自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行 直接归约 ，力求 归约 到文法的 开始符号 。

26、在LR（0）分析法的名称中，L的含义是 自左向右的扫描输入串 ，R的含义是 最左归约 ，0 的含义是 向貌似句柄的符号串后查看0个输入符号 。 31、终结符只有 综合属性 ，它们由词法分析器提供。 32、在使用高级语言编程时，首先可通过编译程序发现源程序的全部 语法 错误

***和 语义 部分错误。

34、一个句型中的最左简单短语称为该句型的 句柄 。 36、从功能上说，程序语言的语句大体可分为 执行性 语句和 说明性 语句两大类。

37、语法分析是依据语言的 语法 规则进行的，中间代码产生是依据语言的 语义 规则进行的。

38、语法分析器的输入是 单词符号 ，其输出是 语法单位 。 40、逆波兰式 ab+c+ d*e- 所表达的表达式为 (a+b+c)*d-c 。

41、计算机执行用高级语言编写的程序主要有两种途径： 解释 和 编译 。 42、自上而下分析法采用 移进 、归约、错误处理、 接受 等四种操作。 43、一个LR分析器包括两部分：一个总控程序和 一张分析表 。 44、后缀式abc-/所代表的表达式是 a/(b-c) 。

46、语法分析基于 上下文无关 文法进行，即识别的是该类文法的句子。语法分析的有效工具是 语法树 。

48、语义分析阶段所生成的与源程序等价的中间表示形式可以有 逆波兰 、 四元式表示 与 三元式表示 等。

51、自顶向下语法分析会遇到的主要问题有 左递归 和 回溯 。

52、已知文法G[E]：E→T|E+T；T→F|T*F；F→(E)|i该文法的开始符号是 E ，终结符号集合VT是 {+、*、（、）、i} ，非终结符号结合VN是 {E、T、F} 。

二、单选题

1、一个编译程序中，不仅包含词法分析，（ A ），中间代码生成，代码优化，目标代码生成等五个部分。

A、语法分析 B、文法分析 C、语言分析 D、解释分析 2、语法分析器则可以发现源程序中的（ D ）。

A、语义错误 B、语法和语义错误 C、错误并校正 D、语法错误 3、解释程序处理语言时 , 大多数采用的是（ B ）方法。 A、源程序命令被逐个直接解释执行

B、先将源程序转化为中间代码 , 再解释执行 C、先将源程序解释转化为目标程序 , 再执行 D、以上方法都可以 4、编译程序是一种（ B ）。

A、汇编程序 B、翻译程序 C、解释程序 D、目标程序 5、通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括（ C ）。

A、模拟执行器 B、解释器 C、表格处理和出错处理 D、符号执行器 6、一个句型中的最左（ B ）称为该句型的句柄。

A、短语 B、简单短语 C、素短语 D、终结符号 7、文法 G[E] ： E→T∣E＋T T→F∣T﹡F F→a∣(E)

该文法句型 E＋F﹡(E＋T)的简单短语是下列符号串中的（ B ）。 ①（E＋T） ② E＋T ③ F ④ F﹡(E＋T)

A、① 和 ③ B、② 和 ③ C、③ 和 ④ D、③ 8、词法分析器用于识别（ C ）。

A、句子 B、句型 C、单词 D、产生式 9、在自底向上的语法分析方法中，分析的关键是（ D ）。

A、寻找句柄 B、寻找句型 C、消除递归 D、选择候选式 10、文法 G 产生的（ D ）的全体是该文法描述的语言。

A、句型 B、终结符集 C、非终结符集 D、句子 11、若文法 G 定义的语言是无限集，则文法必然是（ A ）。

A、递归的 B、前后文无关的 C、二义性的 D、无二义性的 12、四种形式语言文法中，1型文法又称为（ C ）文法。

A、短语结构文法 B、前后文无关文法 C、前后文有关文法 D、正规文法 13、一个文法所描述的语言是（ A ）。

A、唯一的 B、不唯一的 C、可能唯一，好可能不唯一 D、都不对 14、（ B ）和代码优化部分不是每个编译程序都必需的。

A、语法分析 B、中间代码生成 C、词法分析 D、目标代码生成 15、（ B ）是两类程序语言处理程序。 A、高级语言程序和低级语言程序 B、解释程序和编译程序 C、编译程序和操作系统 D、系统程序和应用程序

16、一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组（ D ）。 A、句子 B、句型 C、单词 D、产生式

17、文法分为四种类型，即0型、1型、2型、3型。其中2型文法是（ D ）。 A、短语文法 B、正则文法 C、上下文有关文法 D、上下文无关文法 18、文法 G 所描述的语言是（ C ）的集合。 A、文法G的字母表V中所有符号组成的符号串 B、文法G的字母表V的闭包V*中的所有符号串 C、由文法的开始符号推出的所有终结符串 D、由文法的开始符号推出的所有符号串

19、文法分为四种类型，即0型、1型、2型、3型。其中0型文法是（ A ）。 A、短语文法 B、正则文法 C、上下文有关文法 D、上下文无关文法 20、（ A ）是一种典型的解释型语言。

A、BASIC B、C C、FORTRAN D、PASCAL 21、与编译系统相比，解释系统（ D ）。 A、比较简单，可移植性好，执行速度快 B、比较复杂，可移植性好，执行速度快 C、比较简单，可移植性差，执行速度慢 D、比较简单，可移植性好，执行速度慢

22、用高级语言编写的程序经编译后产生的程序叫（ B ）。

A、源程序 B、目标程序 C、连接程序 D、解释程序 23、编写一个计算机高级语言的源程序后，到正式上机运行之前，一般要经过（ B ）这几步:（1）编辑 （2）编译 （3）连接 （4）运行 A、（1）（2）（3）（4） B、（1）（2）（3） C、（1）（3） D、（1）（4） 24、把汇编语言程序翻译成机器可执行的目标程序的工作是由（ B ）完成的。 A、编译器 B、汇编器 C、解释器 D、预处理器

25、词法分析器的输出结果是（ C ）。

A、单词的种别编码 B、单词在符号表中的位置 C、单词的种别编码和自身值 D、单词自身值 26、正规式M1和M2等价是指（ C ）。

A、M1和M2的状态数相等 B、M1和M2的有向边条数相等

C、M1和M2所识别的语言集相等 D、M1和M2状态数和有向边条数相等 27、文法G：S→xSx|y所识别的语言是（ C ）。

A、xyx B、(xyx)* C、xnyxn(n≥0) D、x*yx* 28、如果文法G是无二义的，则它的任何句子α（ A ）。 A、最左推导和最右推导对应的语法树必定相同 B、最左推导和最右推导对应的语法树可能不同 C、最左推导和最右推导必定相同

D、可能存在两个不同的最左推导，但它们对应的语法树相同 29、构造编译程序应掌握（ D ）。

A、源程序 B、目标语言 C、编译方法 D、以上三项都是 30．四元式之间的联系是通过（ B ）实现的。

A、指示器 B、临时变量 C、符号表 D、程序变量 31、表达式(┐A∨B)∧(C∨D)的逆波兰表示为（ B ）。 A、┐AB∨∧CD∨ B、A┐B∨CD∨∧ C、AB∨┐CD∨∧ D、A┐B∨∧CD∨ 33、编译程序是对（ D ）。

A、汇编程序的翻译 B、高级语言程序的解释执行 C、机器语言的执行 D、高级语言的翻译 34、采用自上而下分析，必须（ C ）。

A、消除左递归 B、消除右递归 C、消除回溯 D、提取公共左因子 35、在规范归约中，用（ B ）来刻画可归约串。

A、直接短语 B、句柄 C、最左素短语 D、素短语 36、间接三元式表示法的优点为（ A ）。 A、采用间接码表，便于优化处理 B、节省存储空间，不便于表的修改 C、便于优化处理，节省存储空间 D、节省存储空间，不便于优化处理 37、在目标代码生成阶段，符号表用（ D ）。

A、目标代码生成 B、语义检查 C、语法检查 D、地址分配 38、下面关于解释程序的描述正确的是（ B ）。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于COBOL 和 FORTRAN 语言

(3) 解释程序是为打开编译程序技术的僵局而开发的

A、(1)(2) B、(1) C、(1)(2)(3) D、(2)(3) 39、解释程序处理语言时，大多数采用的是（ B ）方法。 A、源程序命令被逐个直接解释执行

B、先将源程序转化为中间代码，再解释执行 C、先将源程序解释转化为目标程序，在执行 D、以上方法都可以

40、用不同语言编写的程序产生（）后，可用（）连接在一起生成机器可执行的程序.在机器中真正执行的是（）。上面三空格对应的选项是（ A ）

a、源程序 b、目标程序 c、函数 d、过程 e、机器指令代码 f、模块 g、连接程序 h、程序库 A、b、g、e B、b、c、e C、e、g、f D、e、c、f 41、由于受到具体机器主存容量的限制，编译程序几个不同阶段的工作往往被组合成 （），诸阶段的工作往往是（）进行的. 上面两空格对应的选项是（ A ） a、过程 b、程序 c、批量 d、遍 e、顺序 f、并行 g、成批 h、穿插

A、d和h B、d和e C、a和h D、a和e 42、编译过程中，语法分析器的任务就是（ B ） （1）分析单词是怎样构成的

（2）分析单词串是如何构成语句和说明的 （3）分析语句和说明是如何构成程序的 （4）分析程序的结构 A、（2）（3） B、（2）（3）（4） C、（1）（2）（3） D、（1）（2）（3）（4） 43、编译程序必须完成的工作有（ A ）

（1）词法分析 （2）语法分析 （3）语义分析 （4）代码生成 （5）中间代码生成 （6）代码优化 A、(1)(2)(3)(4) B、(1)(2)(3)(4)(5) C、(1)(2)(3)(4)(5)(6) D、(1)(2)(3)(4)(6) 44、按逻辑上划分，编译程序第二步工作是（ C ）。

A、语义分析 B、词法分析 C、语法分析 D、代码优化 45、已知语言L={ xnyyn | n>=1}，则下述文法中，（ D ）可以产生语言L。 A 1、Z→xZy|xAy|y B 1、A→xAy 2、A→xAy|x 2、A→x C 1、Z→AyB D 1、Z→xAy 2、A→xA|x 2、A→xAy|y 3、B→yB|y

46、乔姆斯基（Chomsky）把文法分为四种类型，即0型、1型、2型、3型。其中3型文法是（ B ）。

A、短语文法 B、正则文法 C、上下文有关文法 D、上下文无关文法 48、设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈V*)，则称x是文法G的一个（ B ）。

A、候选式 B、句型 C、单词 D、产生式 49、若一个文法是递归的，则它所产生的语言的句子（ A ）。

A、是无穷多个 B、是有穷多个 C、是可枚举的 D、个数是常量 50、文法的二义性和语言的二义性是两个（ A ）的概念。

A、不同 B、相同 C、无法判断 D、不存在

51、在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是（ B ）。 A、非终结符集 B、终结符集 C、字母表 D、状态集 52、编译程序中语法分析器接收以（ A ）为单位的输入。

A、单词 B、表达式 C、产生式 D、句子

53、在LR分析法中，分析栈中存放的状态是识别规范句型（ C ）的DFA状态。 A、句柄 B、前缀 C、活前缀 D、LR(0)项目

三、是非题

(下列各题，你认为正确的，请在题干的括号内打“√”，错的打“×”。) （×）1、计算机高级语言翻译成低级语言只有解释一种方式。

（×）2、在编译中进行语法检查的目的是为了发现程序中所有错误。

（×）3、甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 （×）4、“用高级语言书写的源程序都必须通过编译，产生目标代码后才能投入运行”这种说法。

（√）5、正则文法其产生式为A?a，A?Bb，A，B∈VN，a、b∈VT。 （×）6、产生式是用于定义词法成分的一种书写规则。 （×）7、解释程序适用于COBOL和FORTRAN语言。

（√）8、正规文法产生的语言都可以用上下文无关文法来描述。

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

（×）10、编译程序是对高级语言程序的解释执行。

（×）11、一个有限状态自动机中，有且仅有一个唯一的终态。 （×）12、语法分析时必须先消除文法中的左递归。

（√）13、两个正规集相等的必要条件是他们对应的正规式等价。 （×）14、设r和s分别是正规式，则有L(r|s)=L(r)L(s)。

（√）15、确定的自动机以及不确定的自动机都能正确地识别正规集。 （×）16、词法分析作为单独的一遍来处理较好。 （√）17、构造LR分析器的任务就是产生LR分析表。

（×）18、编译程序与具体的机器有关，与具体的语言无关。 （×）19、每个文法都能改写为LL(1)文法。

（√）20、递归下降法允许任一非终结符是直接左递归的。 （√）21、递归下降分析法是自顶向下分析方法。 （√）22、一个 LL(l)文法一定是无二义的。

（×）23、算符优先关系表不一定存在对应的优先函数。

（×）24、自底而上语法分析方法的主要问题是候选式的选择。 （×）25、LR分析方法是自顶向下语法分析方法。

（×）26、简单优先文法允许任意两个产生式具有相同右部。 （×）27、若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。 （√）28、一个句型的句柄一定是文法某产生式的右部。 （√）29、在 SLR(1)分析法的名称中，S的含义是简单的。 （×）30、综合属性是用于 “ 自上而下 ” 传递信息。

（√）31、一个算符优先文法可能不存在算符优先函数与之对应。

（√）32、LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。

（√）33、规范归约和规范推导是互逆的两个过程。 （×）34、LR分析技术无法适用二义文法。

（√）35、逆波兰表示法表示表达式时无须使用括号。 （√）36、逆波兰法表示的表达式亦称后缀式。 （×）38、在程序中标识符的出现仅为使用性的。

（×）39、设∑为{a，b}，则a，ba，{∑}，Φ都是∑上的正规式。

（×）40、对于上下文无关文法G[S]，若 S?αAB?αβγ则A →γ一定是一条产生式规则，其中α,β,γ∈（VT∨VN）*。

（√）41、对于逆波兰后缀式，无论从哪头开始分析均可得到唯一正确的分解。 （√）42、LR（0）分析法是一种规范归约法。

（√）43、算符优先分析法只能用来分析算符优先文法。 （×）44、解释程序和编译程序一样，生成目标代码。 （×）45、编译程序生成的目标代码只能是机器语言。 （×）46、等价文法是指两个文法完全相同。 （√）47、对于字母表Σ上的任一NFA M'，必存在Σ上与NFA M' 等价的DFA M。 （×）48、每个文法都能改写为LL(1)文法。

（√）49、不存在正规文法能产生语言：L={anbn|n>=1}

四、简答题

1、什么是句子？ 什么是语言?

设G是一个给定的文法，S是文法的开始符号，如果S

x(其中x∈VT*),则称x

是文法的一个句子。 设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│Sx，x∈VT*}。

2、已知文法G[E]为： E→T|E+T|E-T T→F|T*F|T/F F→（E）|i

① 该文法的开始符号（识别符号）是什么？

② 请给出该文法的终结符号集合VT和非终结符号集合VN。 ③ 找出句型T+T*F+i的所有短语、简单短语和句柄。 ① 该文法的开始符号（识别符号）是E。 ② 该文法的终结符号集合VT={+、-、*、/、（、）、i}。

非终结符号集合VN={E、T、F}。

③ 句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i；

简单短语为i、T*F、第一个T； 句柄为第一个T。

3、已知文法G[S]为： S→dAB A→aA|a B→Bb|ε

① G[S]产生的语言是什么？

② G[S]能否改写为等价的正规文法？

① G[S]产生的语言是L(G[S])={danbm│n≥1，m≥0}。

② G[S]能改写为等价的正规文法，其改写后的等价的正规文法G[Sˊ]为：

Sˊ→dA

A →aA|aB|a B →bB|b

5、证明下面文法G[N]是二义性文法。

G[N]：N →SE∣E S →SD∣D E →0∣2∣10

D →0∣1∣2

10是文法G[N]的一个句子，并且有两个不同的最右推导。 （1）S=>E=>10

（2）S=>SE=>S0=>D0=>10 因此说明此文法有二义性。 7、简述DFA与NFA有何区别 ?

DFA与NFA的区别表现为两个方面:一是NFA可以若干个开始状态，而DFA仅只一个开始状态。另一方面，DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。

8、试给出非确定自动机的定义。

一个非确定的有穷自动机（NFA）M是一个五元组：M=（K，Σ，f，S，Z）。 其中:

1、K是一个有穷集，它的每个元素称为一个状态。

2、Σ是一个有穷字母表，它的每个元素称为一个输入符号。

3、f是一个从K×Σ*到K的全体子集的映像，即K×Σ*→2K，其中2K表示K的幂集。

4、S?K，是一个非空初态集。 5、Z?K，是一个终态集。

9、为正规式（a|b）*a(a|b) 构造一个等价的确定的有限自动机。

a,b ? 0 a 1 b a 2

10、构造正规式相应的NFA：1(0|1)*101

12、已知文法 G[S] 为： S→dAB A→aA|a B→Bb|ε

G[S] 产生的语言是什么？

G[S]产生的语言是L(G[S])={danbm│n≥1，m≥0}。

13、编译过程一般分为几个阶段？各阶段的输入输出分别为什么？

15、在LL(1)分析法中，LL分别代表什么含义?

第一个L代表从左到右的扫描，第二个L代表每次进行最左推导。 16、文法G为： S→aAB A→a

B→α|β|γ

则判断G为LL（1）文法的条件是： （1）文法G不含左递归

（2）对于每个非终结符，First（α）、First（β）、First（γ）两两不相交。 （3）对于每个非终结符，不含能推出ε的产生式，故不考虑非终结符的First集和Follow集相交的情况。

17、文法G=({A, B, S}, {a, b, c}, P, S)，其中P为：

S→Ac|aB A→ab B→bc

该文法是二义的吗？说明理由。

18、文法G=({E}，{+，*，i，(，)}，P，E)，其中P为：

E→i E→E+E E→E*E E→(E)

该文法是二义的吗？说明理由。

19、自顶向下分析思想是什么？

从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。如果全部匹配成功，则表示开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。

25、简单优先方法基本思想是什么？

简单优先方法基本思想是首先规定文法符号之间的优先关系和结合性质，然后再利用这种关系，通过比较两个相邻的符号之间的优先顺序来确定句型的“句柄”并进行归约。

28、语法制导翻译方法的基本思想是什么?

在语法分析过程中，每当使用一条产生式进行推导或归约时，就执行该产生式所对应的语义动作进行属性计算，完成对输入符号串的翻译。

33、给定下列中缀式，分别写出等价的后缀式和四元式(运算符优先级按常规理解)。

(1)(a＋b*c)/(a＋b)－d 后缀式：abc*+ab+/d-

四元式：①（*，b，c，t1）

② (+，a，t1，t2） ③ (+，a，b，t3） ④ (/，t2，t3，t4） ⑤ (-，t4，d，t5）

一、最左、最右推导及语法树 1、令文法为

E→T|E+T|E-T T→F|T*F|T/F F→（E）|i

（1）给出i+i*i的最左推导和最右推导； （2）给出i+i*i的最左推导语法树。

2、已知文法G：

<表达式>::=<项>|<表达式>+<项> <项>::=<因子>|<项>*<因子> <因子>::=(<表达式>)|i （1）给出i+i*i的最左推导和最右推导； （2）给出i+i*i的最左推导语法树。

3、下面的文法生成的是以x和y为操作数、二元运算符+、*和-为运算符的前缀表达式：E→+EE|*EE|-EE|x|y

（1）给出串+*-xyxy的最左推导和最右推导； （2）给出+*-xyxy的语法树。

4、一个上下文无关文法生成句子abbaa的推导树如下：

SAaBSSεBbBbAaa （1）给出该句子相应的最左推导，最右推导。 （2）该文法的产生式集合P可能有哪些元素？

二、自动机的确定和最小化

1、将下图中的自动机确定化并最小化。

aXε5bε1ab3b4aa2ε6bεY

2、将下图中的自动机确定化。

a,biε1ε2ab3b4a5εa,b6εf

3、试构造正规式(0|1)*1(0|1)相应的自动机，并将其确定化。

4、试构造正规式(a|b)*ab(a|b)*相应的自动机，并将其确定化和最小化。

三、FIRST和FOLLOW集合 1、考虑下面文法G1： S→a|?|(T) T→T，S|S

（1）消去G1的左递归；

（2）经改写后的文法是否是LL(1)的？给出它的预测分析表(要求写出详细过程，应先求出每个非终结符的FIRST和FOLLOW集合)。

2、判断下面文法是否为LL(1)文法，若是，请构造相应的预测分析表。 S→aD

D→Ste|ε T→bH|H H→d|ε

3、对文法G(S)： S→S?aT|aT|?aT T→?aT|?a （1）消除该文法的左递归和提取左公因子； （2）构造各非终结符的FIRST和FOLLOW集合；

（3）构造该文法的LL(1)分析表，并判断该文法是否是LL(1)的。

四、短语、直接短语、句柄和素短语 1、对于文法G（S）： S→(L)|aS|a L→L，S|S

（1）画出句型(S，(a))的语法树。

（2）写出上述句型的所有短语、直接短语、句柄和素短语。

2、文法G[S]为： S→V

V→T|ViT T→F|T+F F→)V*|(

（1）画出句型ViFi(的语法树。

（2）写出上述句型的所有短语、直接短语、句柄和素短语。

3、对于文法G(E)： E→T|E+T T→F|T*F F→(E)|i

（1）画出句型T*F+i*i的语法树。

（2）写出上述句型的短语，直接短语、句柄、素短语和最左素短语。

五、FIRSTVT集合和LASTVT集合，构造优先关系表 1、设文法G（S）： S→(A)|a A→A+S|S

（1）构造各非终结符的FIRSTVT集合和LASTVT集合。 （2）构造优先关系表。

2、设文法G3为： S→AaBc

A→Aa|a B→b

（1）构造各非终结符的FIRSTVT集合和LASTVT集合。 （2）构造优先关系表。

（3）求句型AaBc的最左素短语。

3、设文法G(S)： S→SiA|A A→A+B|B B→)A*|(

（1）构造各非终结符的FIRSTVT和LASTVT集合； （2）构造优先关系表。

六、LR分析

1、已知文法：A→aAd|aAb|ε

判断该文法是否是SLR(1)文法，若是构造相应分析表。

2、若有定义二进制数的文法如下： S→L·L|L L→LB|B B→0|1

试为该文法构造LR分析表，并说明属哪类LR分析表。

3、已知文法G[S]： S→MH|a H→LSo|ε K→dML|ε L→eHf M→K|bLM

判断G 是否是LL(1)文法，如果是，构造LL(1)分析表。

4、考虑文法： S→AS|b A→SA|a

（1）构造文法的LR(0)项目集规范族及相应的DFA。 （2）构造文法的SLR分析表。

FIRSTVT集构造方法：

（1）若有产生式P→a…或P→Qa…，则a∈FIRSTVT(P)

（2）若a∈FIRSTVT(Q)，且产生式P→Q…，则a∈FIRSTVT(P)

LASTVT集构造方法：

（1）若有产生式P→…a或P→…aQ，则a∈LASTVT(P)

（2）若a∈LASTVT(Q)，且产生式P→…Q，则a∈LASTVT(P)

FIRST集构造方法：

(1) 若X∈ＶT，则 FIRST(X)=X。

(2) 若X∈ＶN，有产生式X→a…，则将a加入FIRST(X)； 或有产生式X→ε，则将ε加入FIRST(X)。

(3) 若有产生式X→Y…，且Y∈ＶN，则 FIRST(Y)的非ε元素∈FIRST(X)；若X→Y1Y2…Yk是一个产生式，Y1，…，Yi-1都是非终结符，而且，对于任何j，1=

FOLLOW集构造方法：

（1）将#加入到 FOLLOW(S)。

（2）若A→αBβ，则将 FIRST(β)的非ε元素加入FOLLOW(B)

（3）如果A→αB或A→αBβ，且β==*>ε，A≠B，则将FOLLOW(A)的所有元素加入 FOLLOW(B)

优先关系表的构造方法：

（1）对形如P→…ab…或P→…aQb…的产生式，有a≡b

（2）对形如P→…aR…的产生式，有b∈FIRSTVT(R)，则a≮b （3）对形如P→…Rb…的产生式，有a∈LASTVT(R)，则a≯b

此外，若将语句括号#作为终结符对待，并设S是文法的开始符号，则有#≡#，#≮FIRSTVT(S)，LASTVT(S)≯#

预测分析表的构造方法：

（1）对于每一产生式A→α，作（2）和（3）

（2）对于FIRST（α）中的每一终结符a，将A→α填入M[A，a] （3）如果ε属于FIRST（α），则对任何b∈FOLLOW（A）把A→α填入M[A,b]；