编译原理复习题(考试)

一、是非题

1．计算机高级语言翻译成低级语言只有解释一种方式。(×)

3．每个文法都能改写为 LL(1) 文法。 (×)

4．算符优先关系表不一定存在对应的优先函数。 (√)

5．LR分析方法是自顶向下语法分析方法。 (×)

6．“ 用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行 ”这种说法。(× )

7．一个句型的句柄一定是文法某产生式的右部。 (√)

8．仅考虑一个基本块，不能确定一个赋值是否真是无用的。 (√ )

9．在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。 (× )

10．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。(×)

11．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。(× )

12．递归下降分析法是自顶向下分析方法。(√ )

13．产生式是用于定义词法成分 的一种书写规则。 (×)

14．在 SLR(1)分析法的名称中，S的含义是简单的。(√)

15．综合属性是用于 “ 自上而下 ” 传递信息。(× )

16．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。 (×)

17．程序语言的语言处理程序是一种应用软件。 (×)

18．解释程序适用于 COBOL 和 FORTRAN 语言。 (×)

19．一个 LL(l)文法一定是无二义的。 (√)

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

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

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

22．逆波兰法表示的表达式亦称后缀式 。 (√ )

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

24．数组元素的地址计算与数组的存储方式有关。(√)

25．算符优先关系表不一定存在对应的优先函数。 (×)

26．编译程序是对高级语言程序的解释执行。(× )

27．一个有限状态自动机中，有且仅有一个唯一的终态。(×)

28．一个算符优先文法可能不存在算符优先函数与之对应。 (√ )

29．语法分析时必须先消除文法中的左递归 。 (×)

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

31．逆波兰表示法表示表达式时无须使用括号。 (√ )

32．静态数组的存储空间可以在编译时确定。 (√)

33．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。 (√)

34．两个正规集相等的必要条件是他们对应的正规式等价。 (√)

35．一个语义子程序描述了一个文法所对应的翻译工作。 (×)

36．设r和s分别是正规式，则有L(r|s)=L(r)L(s)。(×)

37．确定的自动机以及不确定的自动机都能正确地识别正规集。(√)

38．词法分析作为单独的一遍来处理较好。 (× )

39．构造LR分析器的任务就是产生LR分析表。 (√)

40．规范归约和规范推导是互逆的两个过程。 (√)

41．同心集的合并有可能产生新的“移进”/“归约”冲突。 (× )

42．LR分析技术无法适用二义文法。 (× )

43．树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。 (×)

44．程序中的表达式语句在语义翻译时不需要回填技术。 (√)

45．对中间代码的优化依赖于具体的计算机。 (× )

46．若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。(×)

47．在程序中标识符的出现仅为使用性的。(×)

48．削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。(×)

49．编译程序与具体的机器有关，与具体的语言无关。(×)

二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)

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． 文法分为四种类型，即0型、1型、2型、3型。其中3型文法是( B )。

　A.短语文法    　　　 B．正则文法        C．上下文有关文法　　 D．上下文无关文法

6． 通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括( C )。

　A．模拟执行器             B．解释器      C．表格处理和出错处理     D．符号执行器

7． 一个句型中的最左( B )称为该句型的句柄。

　A．短语         B．简单短语       　C．素短语          D．终结符号 

8． 文法 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．③ 

9． 词法分析器用于识别( C )。

　A．句子      　B．句型         C．单词         D．产生式 

10． 在自底向上的语法分析方法中，分析的关键是( A )。

　 A．寻找句柄         B．寻找句型       C．消除递归       D．选择候选式 

11． 文法 G 产生的( D )的全体是该文法描述的语言。

　A．句型 　　 B．终结符集 　　C．非终结符集 　　D．句子

12． 若文法 G 定义的语言是无限集，则文法必然是( A )。  

A．递归的   　 　B．前后文无关的        C．二义性的 　　 D．无二义性的

13． 四种形式语言文法中，1型文法又称为( C )文法。

　A．短语结构文法       B．前后文无关文法 　　C．前后文有关文法     D．正规文法 

14． 一个文法所描述的语言是( A )。

　A．唯一的 　   　B．不唯一的        C．可能唯一，好可能不唯一   　　D．都不对

15． ( B )和代码优化部分不是每个编译程序都必需的。

A．语法分析   　　　B．中间代码生成        C．词法分析      　 D．目标代码生成 

16．( B )是两类程序语言处理程序。 

A．高级语言程序和低级语言程序            B．解释程序和编译程序 

C．编译程序和操作系统                    D．系统程序和应用程序 

17． 数组的内情向量中肯定不含有数组的( D )的信息。

　A．维数 　　　　B．类型       　C．维上下界         D．各维的界差 

18. 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组( D )。 

　A．句子 　 　　B．句型        C．单词 　　　 D．产生式

19． 文法分为四种类型，即0型、1型、2型、3型。其中2型文法是( D )。

　A．短语文法    　B．正则文法     C．上下文有关文法　　　D．上下文无关文法

20．文法 G 所描述的语言是( C )的集合。 

A．文法 G 的字母表 V 中所有符号组成的符号串    B．文法 G 的字母表 V 的闭包 V* 中的所有符号串

C．由文法的开始符号推出的所有终极符串            D．由文法的开始符号推出的所有符号串

21．词法分析器用于识别( C )。  

　 A．字符串   　 　B．语句        C．单词　　　　　 D．标识符

22．文法分为四种类型，即0型、1型、2型、3型。其中0型文法是( A )。

　A．短语文法    　　　 B．正则文法     C．上下文有关文法　　 D．上下文无关文法

24．( A )是一种典型的解释型语言。  

　A．BASIC 　　B．C 　　C．FORTRAN  　　D．PASCAL

25．与编译系统相比，解释系统( D )。

A．比较简单 , 可移植性好 , 执行速度快 　　B．比较复杂 , 可移植性好 , 执行速度快

C．比较简单 , 可移植性差 , 执行速度慢 　　D．比较简单 , 可移植性好 , 执行速度慢 

26．用高级语言编写的程序经编译后产生的程序叫( B )。 

　A．源程序       B．目标程序      C．连接程序 　　D．解释程序

27．词法分析器用于识别( A )。   

　A．字符串       B．语句          C．单词        D．标识符 

28．编写一个计算机高级语言的源程序后 , 到正式上机运行之前，一般要经过( B )这几步:

　 (1) 编辑   (2) 编译   (3) 连接   (4) 运行 

　A．(1)(2)(3)(4)     B．(1)(2)(3)    C．(1)(3)     D．(1)(4)

29．把汇编语言程序翻译成机器可执行的目标程序的工作是由( B )完成的。

　A．编译器            B．汇编器           C．解释器            D．预处理器

31．词法分析器的输出结果是( C )。

　A．单词的种别编码 　　B．单词在符号表中的位置        C．单词的种别编码和自身值 　D．单词自身值

32． 正规式 M 1 和 M 2 等价是指( C )。  

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

C．M1和M2所识别的语言集相等        D．M1和M2状态数和有向边条数相等 

33． 文法G：S→xSx|y所识别的语言是( C )。

　A．xyx  　 B．(xyx)* C．     D．x*yx* 

34．如果文法G是无二义的，则它的任何句子α  ( A )。

　A．最左推导和最右推导对应的语法树必定相同 　　B．最左推导和最右推导对应的语法树可能不同

　C．最左推导和最右推导必定相同   　　D．可能存在两个不同的最左推导，但它们对应的语法树相同 

35．构造编译程序应掌握( D )。

　A．源程序   　　　B．目标语言        C．编译方法      D．以上三项都是

36．四元式之间的联系是通过( B )实现的。 

　A．指示器         　　B．临时变量        C．符号表             D．程序变量 

37．表达式(┐A∨B)∧(C∨D)的逆波兰表示为( B )。

　A．┐AB∨∧CD∨ 　　　　B．A┐B∨CD∨∧      C．AB∨┐CD∨∧         D．A┐B∨∧CD∨ 

38. 优化可生成( D )的目标代码。

A．运行时间较短                    B．占用存储空间较小

C．运行时间短但占用内存空间大     D．运行时间短且占用存储空间小

39．下列( C  )优化方法不是针对循环优化进行的。

　A．强度削弱    　　　 B．删除归纳变量     C．删除多余运算　  　 D．代码外提

40．编译程序使用( B )区别标识符的作用域。 

A．说明标识符的过程或函数名                B．说明标识符的过程或函数的静态层次

C．说明标识符的过程或函数的动态层次         D．标识符的行号

41．编译程序绝大多数时间花在( D )上。

　A．出错处理 　　　B．词法分析 　　C．目标代码生成 　　 D．表格管理

42． 编译程序是对( D )。  

　A．汇编程序的翻译   　 B．高级语言程序的解释执行　　C．机器语言的执行 　　D．高级语言的翻译 

43． 采用自上而下分析，必须( C )。

　A．消除左递归  　　　B．消除右递归        C．消除回溯  　　　D．提取公共左因子 

44．在规范归约中，用( B )来刻画可归约串。

　A．直接短语 　 　 　 　 　 B．句柄            C．最左素短语   　 　 　 　D．素短语 

45． 若a为终结符，则A->α · aβ为( B ) 项目。

　A．归约   　　　B．移进     　C．接受      　　D．待约 

46．间接三元式表示法的优点为( A )。 

A．采用间接码表，便于优化处理            B．节省存储空间，不便于表的修改

C．便于优化处理，节省存储空间         D．节省存储空间，不便于优化处理 

47．基本块内的优化为( B )。

A．代码外提，删除归纳变量            B．删除多余运算，删除无用赋值

C．强度削弱，代码外提                D．循环展开，循环合并

48. 在目标代码生成阶段，符号表用( D )。

　A．目标代码生成 　 　　B．语义检查            C．语法检查 　　　　D．地址分配

49．若项目集Ik含有A->α · ，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A->α · ”动作的一定是( D )。

　A．LALR文法    　B．LR(0)文法         C．LR(1)文法　　　D．SLR(1)文法

50．堆式动态分配申请和释放存储空间遵守( D )原则。 

　A．先请先放 　　　 　 B．先请后放        C．后请先放  　　　 　D．任意

三、填空题

1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有__表格处理___和 ___出错处理__。 

2．编译方式与解释方式的根本区别在于__是否生成目标代码___。

3．产生式是用于定义___语法成分__的一种书写规则。 

4．设G是一个给定的文法，S是文法的开始符号，如果S->x( 其中 x∈VT*), 则称 x是文法的一个__句子___。 

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

6．常用的参数传递方式有___传地址__，传值和传名。 

7．一个句型中的最左简单短语称为该句型的___句柄__。 

8．对于文法的每个产生式都配备了一组属性的计算规则，称为 __语义规则___ 。

9．一个典型的编译程序中，不仅包括__词法分析___、__语法分析___、__中间代码生成___、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。

10． 从功能上说，程序语言的语句大体可分为__执行性___语句和__说明性___语句两大类。

11． 扫描器的任务是从__源程序___中识别出一个个___单词符号__。 

12． 产生式是用于定义__语法范畴___的一种书写规则。

13．语法分析是依据语言的__语法___规则进行的，中间代码产生是依据语言的__语义___规进行的。

14．语法分析器的输入是__单词符号串___，其输出是__语法单位___。

15．一个名字的属性包括__类型___和__作用域___。

16．逆波兰式 ab+c+ d*e- 所表达的表达式为__(a+b+c)*d-e___ 。 

17．语法分析最常用的两类方法是__自上而下___和__自下而上___分析法。

18．计算机执行用高级语言编写的程序主要有两种途径：___解释__和__编译___。 

19．扫描器是__词法分析器___，它接受输入的__源程序___，对源程序进行___词法分析__并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。

20．自上而下分析法采用___移进__、归约、错误处理、___接受__等四种操作。

21．一个LR分析器包括两部分：一个总控程序和___一张分析表__。

22．后缀式abc-/所代表的表达式是___a/(b-c)__。 

23．局部优化是在__基本块___范围内进行的一种优化。

24．词法分析基于__正则___文法进行，即识别的单词是该类文法的句子。 

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

26．分析句型时，应用算符优先分析技术时，每步被直接归约的是__最左素短语___，而应用LR分析技术时，每步被直接归约的是___句柄__。

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

28．按Chomsky分类法，文法按照___规则定义的形式__进行分类。 

29．一个文法能用有穷多个规则描述无穷的符号串集合（语言）是因为文法中存在有___递归__定义的规则。

四、简答题

111. 写一文法，使其语言是偶正整数的集合,要求： 

   (1)允许0打头；

   (2) 不允许0打头。

解：(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S) 

P: 

S->PD|D

P->NP|N

D->0|2|4|6|8

N->0|1|2|3|4|5|6|7|8|9

(2)G[S]=({S,P,R,D,N,Q },{0,1,2,…,9},P,S) 

P: 

S->PD|P0|D

P->NR|N

R->QR|Q

D->2|4|6|8

N->1|2|3|4|5|6|7|8|9

Q->0|1|2|3|4|5|6|7|8|9

2. 构造正规式相应的 NFA : 1(0|1)*101 

解1(0|1)*101对应的NFA为 

3. 写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示和三元式序列。

逆波兰表示： 　　　　　abc*＋ab＋/d－

三元式序列：

① (*，b，c) 

② (＋，a，①)

③ (＋，a，b)

④ (/，②，③)

⑤ (－，④，d)

4. 已知文法 G[S] 为：

   S→dAB 

   A→aA|a

   B→Bb|ε

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

答：G[S]产生的语言是L(G[S])={ }。

5. 构造正规式相应的 DFA : 1(1010 * | 1(010) * 1) * 0。

解：1(1010 * | 1(010) * 1) * 0对应的NFA为：

6. 已知文法G(S) 

　　 S→a|∧|(T) 

　　 T→T，S|S 

　　写出句子((a，a)，a)的规范归约过程及每一步的句柄。

解：

句型　　　　　归约规则　　　　　  句柄 

((a，a)，a)        S→a                a

((S，a)，a)        T→S                S 

((T，a)，a)        S→a                a

((T，S)，a)        T→T，S　　　　　 T，S

((S)，a)             T→S                S

((T)，a)             S→S(T)                 (T)

(S，a)             T→S                S

(T，a)             S→a                a

(T，S)             T→T，S　　　　　 T，S

(T)                 S→(T)                 (T)

S　　　　　　　　　　　　

7. 写一个文法，使其语言是奇数集，且每个奇数不以0开头。

解：文法G(N)：

N→AB|B

A→AC|D

B→1|3|5|7|9

D→B|2|4|6|8

C→0|D

8. 设文法G(S)：

　　　　 S→(L)|a S|a 

　　　　 L→L，S|S 

   (1) 消除左递归和回溯；

   (2) 计算每个非终结符的FIRST和FOLLOW。

解：(1) 

S→(L)|aS' 

　 S'→S|ε

　 L→SL' 

　 L'→SL'|ε

　　 (2)

　　　 FIRST)S)＝{(，a}　　　　FOLLOW(S)＝{#，，)}

　　　 FIRST(S')＝{，a,ε}　　FOLLOW(S')＝{#，，)}

FIRST(L)＝{(，a}　　　　FOLLOW(L)＝{ )}

　　　 FIRST(L')＝{，ε}　　FOLLOW(L'〕＝{ )}

9. 已知文法G(E) 

　　 E→T|E＋T 

　　 T→F|T *F 

　　 F→(E)|i 

　　 (1)给出句型(T *F＋i)的最右推导；

　　 (2)给出句型(T *F＋i)的短语、素短语。

解：(1) 最右推导： E=>T->F=>(E)->(E＋T)=>(E＋F)->(E＋i)=>(T＋i)=>(T*F＋i)

(2) 短语：(T*F＋i)，T*F＋i，T*F，i

素短语：T*F,i 　

10. While　a＞0 ∨ b＜0　do 

　　　　 Begin 

　　　　　　 X：＝X＋1； 

　　　　　　 if a＞0 then a：＝a－1 

　　　　　　　　　　 else b：＝b＋1 

　　　　 End； 

　　　　 翻译成四元式序列。

解：

　　 (1) (j＞，a，0，5) 

　　 (2) (j，－，－，3) 

　　 (3) (j＜，b，0，5) 

　　 (4) (j，－，－，15) 

　　 (5) (＋，X，1，T1) 

　　 (6) (：＝，T1，－，X) 

　　 (7) (j≥，a，0，9)

　　 (8) (j，－，－，12)

　　 (9) (－，a，1，T2) 

　　 (10) (：＝，T2，－，a) 

　　 (11) (j，－，－，1) 

　　 (12) (＋，b，1， T3) 

　　 (13) (：＝，T3，－，b) 

　　 (14) (j，－，－，1) 

　　 (15)

11. 写出下列表达式的三地址形式的中间表示。

   (1) 5+6 *(a + b); 

   (2)for j:=1 to 10 do a[j + j]:=0。

答： (1)100: t1:=a+b 

101: t2:=6*t1 

102: t3:=5+t2 

(2)100: j:=1 

101: if j>10 goto NEXT

102: i:=j+j 

103: a[i]:=0

12. 设基本块p由如下语句构成： 

   T 0 : =3.14; 

   T 1 :=2*T 0 ; 

   T 2 :=R+r; 

   A:=T l *T 2 ； 

   B:=A; 

   T 3 :=2*T 0 ; 

   T 4 :=R+r; 

   T 5 :=T 3 *T 4 ; 

   T 6 :=R-r ； 

   B:=T 5 *T 6 ；

试给出基本块p的 DAG 。

解：基本块p的DAG图: 

13. 写出表达式(a+b)/(a-b-(a+b*c)的三元序列及四元序列。

解：（1）三元式：

①（＋，a，b）

②（－，a，b）

③（/，①，②）

④（*，b，c）

⑤（＋，a，④）

⑥（－，③，⑤）

（2）四元式：

①（＋，a，b，T1）

②（－，a，b，T2）

③（/，T1，T2，T3）

④（*，b，c，T4）

⑤（＋，a，T4，T5）

⑥（－，T3，T5，T6）

14. 写一个文法使其语言为偶数集，且每个偶数不以0开头。 

解：文法G（S）：

S→AB|B|A0 

A→AD|C 

B→2|4|6|8 

C→1|3|5|7|9|B 

D→0|C

15. 设文法 G （ S ）： 

   S→S ＋ aF|aF| ＋ aF 

   F→*aF|*a 

 （1）消除左递归和回溯；

 （2）构造相应的 FIRST 和 Follow 集合。

解：（1）

　　 S->aFS'|＋aFS' 

　　 S'->＋aFS'|ε 

　　 F->*aF'

　　 F'->F|ε

（2）

FIRST（S）＝｛a，+｝ 　 FOLLOW（S）＝｛＃｝

FIRST（S'）＝｛+，ε ｝ FOLLOW（S'）＝｛＃｝

FIRST（F）＝｛*｝ 　　 FOLLoW（F）＝（+，＃｝ 

FIRST（F'）＝｛*，ε｝ FOLLOW（+，＃｝

16. 简要说明语义分析的基本功能。

答：语义分析的基本功能包括: 确定类型、类型检查、语义处理和某些静态语义检 查。

17. 考虑文法 G[S]: 

S → (T) | a+S | a 

T → T,S | S 

消除文法的左递归及提取公共左因子。

解：消除文法G[S]的左递归：

S→(T) | a+S | a 

T→ST′ 

T′→,ST′| ε 

提取公共左因子： 

S→(T) | aS′ 

S′→+S | ε 

T→ST′ 

T′→,ST′| ε

18. 试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。

解： w a b + c d e 10 - / + 8 + * +

19. 按照三种基本控制结构文法将下面的语句翻译成四元式序列：

while (A{ 

if (A ≥ 1) C=C+1;

else while (A ≤ D)

A=A+2;

}。

解：该语句的四元式序列如下(其中E1、E2和E3分别对应A＜C∧B＜D、A≥1和A≤D，并且关系运算符优先级高)：

100 (j<,A,C,102)

101 (j,_,_,113) 

102 (j<,B,D,104)

103 (j,_,_,113) 

104 (j=,A,1,106) 

105 (j,_,_,108) 

106 (+, C, 1, C) 

107 (j,_,_,112) 

108 (j≤,A,D,110) 

109 (j,_,_,112) 

110 (+, A, 2, A) 

111 (j,_,_,108) 

112 (j,_,_,100)

113

20. 已知文法 G[S] 为 S → aSb|Sb|b ，试证明文法 G[S] 为二义文法。

证明：

由文法G[S]：S→aSb|Sb|b，对句子aabbbb对应的两棵语法树为：

因此，文法G[S]为二义文法。

21. 文法 G[S] 为： 

S->Ac|aB

A->ab

B->bc

写出 L(G[S]) 的全部元素。

解：S=>Ac=>abc

或S=>aB=>abc

所以L(G[S])={abc}

22. 构造正规式 1(0|1)*101 相应的DFA。

解：先构造NFA：

确定化： 

重新命名，令AB为B、AC为C、ABY为D得： 

所以，可得DFA为： 

23. 文法 

S->a|^|(T)

T->T,S|S

对 (a,(a,a) 和 (((a,a),^,(a)),a) 的最左推导。

解： 对(a,(a,a)的最左推导为： 

S=>(T) =>(T,S) =>(S,S) =>(a,S)

=>(a,(T)) =>(a,(T,S)) =>(a,(S,S))

=>(a,(a,S)) =>(a,(a,a))

对(((a,a),^,(a)),a) 的最左推导为： 

S=>(T) =>(T,S) =>(S,S) =>((T),S)

=>((T,S),S) =>((T,S,S),S) =>((S,S,S),S)

=>(((T),S,S),S) =>(((T,S),S,S),S) =>(((S,S),S,S),S)

=>(((a,S),S,S),S) =>(((a,a),S,S),S) =>(((a,a),^,S),S)

=>(((a,a),^,(T)),S) =>(((a,a),^,(S)),S) =>(((a,a),^,(a)),S)

=>(((a,a),^,(a)),a)

24. 文法： 

S->MH|a

H->LSo| ε 

K->dML| ε 

L->eHf

M->K|bLM

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

解：各符号的FIRST集和FOLLOW集为： 

预测分析表为：

由于预测分析表中无多重入口，所以可判定文法是LL(1)的。

25．叙述由下列正规式描述的语言

(a)0(0|1)*0

(b)((ε|0)1*)*

(c)(0|1)*0(0|1)(0|1)

(d)0*10*10*10*

(e)(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*

解：(a)以0开头、以0结尾的所有0和1的串。

(b)由0和1组成的串，包括空串。

(c)倒数第3个字符为0，由0和1组成的串。

(d)含有3个1的所有0和1的串。

(e)由偶数个0和偶数个1构成的所有0和1的串。

26．已知文法G[S]：

S→(L)|a

L→L,S|S

为句子(a,(a,a))构造最左推导和最右推导。

解：句子(a,(a,a))的最左推导为：

S=>(L)=>(L,S) =>(S,S)=>(a,S) =>(a,(L))=>(a,(L,S)) =(a,(S,S))=>(a,(a,S))=>(a,(a,a))

句子(a,(a,a))的最右推导为：

S=>(L)=>(L,S) =>(l,(L))=>(L,(L,S))=>(L,(L,a))=>(L,(S,a))=>(L,(a,a))=(S,(a,a))=(a,(a,a))

五.计算题

1．构造下述文法 G[S] 的自动机： 

S->A0

A->A0|S1|0

该自动机是确定的吗？若不确定，则对它确定化。

解：由于该文法的产生式S->A0，A->A0|S1中没有字符集VT的输入，所以不是确定的自动机。 要将其他确定化，必须先用代入法得到它对应的正规式。把S?A0代入产生式A?S1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入S->A0有该文法的正规式：0(0|01)*0，所以，改写该文法为确定的自动机为： 

由于状态A有3次输入0的重复输入，所以上图只是NFA，下面将它确定化：

下表由子集法将NFA转换为DFA: 

由上表可知DFA为：

2．对下面的文法 G ： 

　　 E->TE'

　　 E'->+E| ε

　　 T->FT'

　　 T' ->T| ε

　　 F-> PF'

　　 F'-> *F'| ε

　　 P->(E)|a|b|^

　　 (1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。 

　　 (2) 证明这个方法是 LL(1) 的。 

　　 (3) 构造它的预测分析表。 

解：（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。 

FIRST集合有： 

FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^}; 

FIRST(E')={+,ε} 

FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^}; 

FIRST(T')=FIRST(T)∪{ε}={(,a,b,^,ε}; 

FIRST(F)=FIRST(P)={(,a,b,^}; 

FIRST(F')=FIRST(P)={*,ε}; 

FIRST(P)={(,a,b,^}; 

FOLLOW集合有： 

FOLLOW(E)={),#}; 

FOLLOW(E')=FOLLOW(E)={),#}; 

FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,),#};//不包含ε 

FOLLOW(T')=FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,),#}; 

FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#};//不包含ε 

FOLLOW(F')=FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#}; 

FOLLOW(P)=FIRST(F')∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε 

(2)证明这个方法是LL(1)的。 

各产生式的SELECT集合有： 

SELECT(E->TE')=FIRST(T)={(,a,b,^};

SELECT(E'->+E)={+};

SELECT(E'->ε)=FOLLOW(E/)={),#}

SELECT(T->FT')=FIRST(F)={(,a,b,^};

SELECT(T'->T)=FIRST(T)={(,a,b,^};

SELECT(T'->ε)=FOLLOW(T/)={+,),#};

SELECT(F->PF')=FIRST(P)={(,a,b,^};

SELECT(F'->*F')={*};

SELECT(F'->ε)=FOLLOW(F')={(,a,b,^,+,),#};

SELECT(P->(E))={(}

SELECT(P->a)={a}

SELECT(P->b)={b}

SELECT(P->^)={^}

可见，相同左部产生式的SELECT集的交集均为空，所以文法G[E]是LL(1)文法。 

(3)构造它的预测分析表。 

文法G[E]的预测分析表如下： 

3．已知 NFA= （ {x,y,z},{0,1},M,{x},{z} ），其中：

M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x}, M(y,1)= φ ,M(z,1)={y}, 构造相应的DFA并最小化。 

解：根据题意有NFA图: 

下表由子集法将NFA转换为DFA： 

下面将该DFA最小化： 

(1) 首先将它的状态集分成两个子集：P1={A,D,E},P2={B,C,F} 

(2) 区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。有P21={C,F},P22={B}。 

(3) 区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11={A,E},P12={D}。 

(4) 由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。 

(5) 综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。所以最小化的DFA如下： 

 4． 已知文法为： 

  S->a|^|(T)

  T->T,S|S

  构造它的 LR(0)分析表。 

解：加入非终结符S'，方法的增广文法为： 

S'->S

S->a

S->^

S->(T)

T->T,S

T->S 下面构造它的LR(0)项目集规范族为： 

从上表可看出,不存在移进-归约冲突以及归约归约冲突，该文法是LR(0)文法。 

从而有下面的LR(0)分析表： 

5．已知文法 

A->aAd|aAb| ε

判断该文法是否是 SLR(1) 文法，若是构造相应分析表，并对输入串 ab# 给出分析过程。

解：增加一个非终结符S/后，产生原文法的增广文法有： 

S'->A

A->aAd|aAb|ε

下面构造它的LR(0)项目集规范族为： 

从上表可看出,状态I0和I2存在移进-归约冲突，该文法不是LR(0)文法。对于I0来说有：FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ，所以在I0状态下面临输入符号为a时移进，为b,d,#时归约，为其他时报错。对于I2来说有也有与I0完全相同的结论。这就是说，以上的移进-归约冲突是可以解决的，因此该文法是SLR(1)文法。 

其SLR(1)分析表为： 

对输入串ab#给出分析过程为：

6．已知文法 G[S] 为： 

S->a|^|(T)

T-> T,S|S

(1) 计算 G[S] 的 FIRSTVT 和 LASTVT 。 

(2) 构造 G[S] 的算符优先关系表并说明 G[S] 是否未算符优先文法。 

(3) 计算 G[S] 的优先函数。 

(4) 给出输入串 (a,a)# 的算符优先分析过程。

解：（1）各符号的FIRSTVT和LASTVT：

（2）算符优先关系表： 

（3）对应的算符优先函数为： 

（4）句子(a,a)#分析过程如下：