当前位置：文档之家 › 编译原理(清华大学第2版)课后习题答案

编译原理(清华大学第2版)课后习题答案

  • 格式：doc
  • 大小：679.00 KB
  • 文档页数：37

下载文档原格式

  / 37

合集下载

编译原理第二版课后习答案教学文稿

编译原理第二版课后习答案教学文稿

编译原理第二版课后习答案《编译原理》课后习题答案第一章第 1 章引论第 1 题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。

（2）源程序：源语言编写的程序称为源程序。

（3）目标程序：目标语言书写的程序称为目标程序。

（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。

通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。

（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。

（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

第 2 题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

答案：一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。

中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。

目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

表格管理程序：负责建立、填写和查找等一系列表格工作。

编译原理课后答案-第二版

编译原理课后答案-第二版

第三章1、L(G[S])={ abc }2、L(G[N])={ n位整数或空字符串| n>0 }3、G[E]：E—>E+D | E-D | DD—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 94、L(G[Z])={ a n b n | n>0 }5、(1) 考虑不包括“0”的情况G[S]：S—>0S | ABC | 2 | 4| 6 | 8A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B—>AB | 0B | εC—>0 | 2 | 4 | 6 | 8考虑包括“0”的情况：G[S]：S—>AB | CB—>AB | CA—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C—>0 | 2 | 4 | 6 | 8(2)方法1：G[S]：S—> ABC | 2 | 4 | 6 | 8A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B—>AB | 0B | εC—>0 | 2 | 4 | 6 | 8方法2：G[S]：S—>AB | CB—> AB | 0B | C | 0A—> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C—>2 | 4 | 6 | 86、设<表达式>为E，<项>为T，<因子>为F，注：推导过程不能省略，以下均为最左推导(1) E => T => F => i(4) E => E+T => T+T => T*F+T => F*F+T => i*F+T => i*i+T => i*i+F => i*i+i(6) E => E+T => T+T => F+T => i+T => i+T*F => i+F*F => i+i*F => i+i*I7、<表达式><表达式>*<表达式><表达式>+<表达式>i i i<表达式><表达式>+<表达式>i <表达式>*<表达式>i i8、是有二义性的，因为句子abc 有两棵语法树（或称有两个最左推导或有两个最右推导）最左推导1：S => Ac => abc 最左推导2：S => aB => abc 9、(1)(2) 该文法描述了变量a 和运算符+、*组成的逆波兰表达式10、(1) 该文法描述了各种成对圆括号的语法结构(2) 是有二义性的，因为该文法的句子()()存在两种不同的最左推导： 最左推导1：S => S(S)S => (S)S => ()S => ()S(S)S => ()(S)S => ()()S => ()()最左推导2：S => S(S)S => S(S)S(S)S => (S)S(S)S=> ()S(S)S => ()(S)S => ()()S => ()()11、(1) 因为从文法的开始符E 出发可推导出E+T*F ，推导过程如下：E => E+T =>E+T*F ，所以E+T*F 是句型。

最新编译原理[张素琴]第2版-答案-清华大学出版社

最新编译原理[张素琴]第2版-答案-清华大学出版社

《编译原理》课后习题第 1 章引论第1 题解释下列术语：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。

（2）源程序：源语言编写的程序称为源程序。

（3）目标程序：目标语言书写的程序称为目标程序。

（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。

通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。

（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。

（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

第2 题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

答案：一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。

中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。

目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

表格管理程序：负责建立、填写和查找等一系列表格工作。

表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。

清华大学编译原理第二版课后习答案

清华大学编译原理第二版课后习答案

Lw.《编译原理》课后习题答案第一章第1章引论第1题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。

（2）源程序：源语言编写的程序称为源程序。

（3）目标程序：目标语言书写的程序称为目标程序。

（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。

通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。

（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。

（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

第2题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

答案：一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。

中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。

盛威网（）专业的计算机学习网站1《编译原理》课后习题答案第一章目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

表格管理程序：负责建立、填写和查找等一系列表格工作。

编译原理第二版课后习答案

编译原理第二版课后习答案

编译原理第二版课后习答案编译原理是计算机科学领域中的一门重要学科，它主要研究程序的自动翻译技术，将高级语言编写的程序转换为机器能够执行的低级语言。

编译原理的基本概念和技术是计算机专业学生必须学会的知识之一，而编译原理第二版课后习题则是帮助学生更好地理解课程内容和提高编译器开发能力的重要资源。

本篇文章将对编译原理第二版课后习题进行分析和总结，并提供一些参考答案和解决问题的思路。

一、词法分析词法分析是编译器的第一步，它主要将输入的字符流转换为有意义的词法单元，例如关键字、标识符、常量和运算符等。

在词法分析过程中，我们需要编写一个词法分析程序来处理输入的字符流。

以下是几道词法分析相关的习题：1. 如何使用正则表达式来表示浮点数？答案：[+|-]?(\d+\.\d+|\d+\.|\.\d+)([e|E][+|-]?\d+)?这个正则表达式可以匹配所有的浮点数，包括正负小数、整数和指数形式的浮点数。

2. 什么是语素？举例说明。

答案：语素是构成单词的最小承载语义的单位，例如单词“man”，它由两个语素“ma”和“n”组成。

“ma”表示男性，“n”表示名词。

3. 采用有限状态自动机(Finite State Automata)实现词法分析的优点是什么？答案：采用有限状态自动机(Finite State Automata)实现词法分析的优点是运行速度快，消耗内存小，易于编写和调试，具有可读性。

二、语法分析语法分析是编译器的第二步，它主要检查词法分析生成的词法单元是否符合语法规则。

在语法分析过程中，我们需要编写一个语法分析器来处理词法单元序列。

以下是几道语法分析相关的习题：1. 什么是上下文无关文法？答案：上下文无关文法(Context-Free Grammar, CFG)是一种形式语言，它的语法规则不依赖于上下文，只考虑规则左边的非终结符号。

EBNF是一种常见的上下文无关文法。

2. LR分析表有什么作用？答案：LR分析表是一种自动机，它的作用是给定一个输入符号串，判断其是否符合某个文法规则，并生成语法树。

清华大学编译原理第二版课后习答案

清华大学编译原理第二版课后习答案

《编译原理》课后习题答案第一章第 4 题对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代码生成）报告的。

（1） else 没有匹配的if（2）数组下标越界（3）使用的函数没有定义（4）在数中出现非数字字符答案：（1）语法分析（2）语义分析（3）语法分析（4）词法分析《编译原理》课后习题答案第三章第1 题文法G＝({A,B,S},{a,b,c},P,S)其中P 为：S→Ac|aBA→abB→bc写出L(G[S])的全部元素。

答案：L(G[S])={abc}第2 题文法G[N]为：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？答案:G[N]的语言是V+。

V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD.... =>NDDDD...D=>D......D或者：允许0 开头的非负整数？第３题为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。

答案：G[S]:S->S+D|S-D|DD->0|1|2|3|4|5|6|7|8|9第4 题已知文法G[Z]：Z→aZb|ab写出L(G[Z])的全部元素。

答案：Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbbL(G[Z])={anbn|n>=1}第5 题写一文法，使其语言是偶正整数的集合。

要求：(1) 允许0 打头；(2)不允许0 打头。

答案：(1)允许0 开头的偶正整数集合的文法E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8(2)不允许0 开头的偶正整数集合的文法E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|0第6 题已知文法G：<表达式>::=<项>｜<表达式>＋<项><项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i试给出下述表达式的推导及语法树。

编译原理第二版课后习答案

《编译原理》课后习题答案第一章第?1?章引论第?1?题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）?编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。

（2）?源程序：源语言编写的程序称为源程序。

（3）?目标程序：目标语言书写的程序称为目标程序。

（4）?编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。

通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。

（5）?后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。

（6）?遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

第?2?题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

答案：一个典型的编译程序通常包含?8?个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。

中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。

目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

表格管理程序：负责建立、填写和查找等一系列表格工作。

编译原理(第二版)清华大学张桂琴,吕映芝著答案


4
5. 写文法，使其语言是偶正整数的集合。要求 （1）允许0打头 （2）不允许0打头
答： （1） S→XYZ | 2 | 4 | 6 | 8|0S X→1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Z→0 | 2 | 4 | 6 | 8 Y→YX | Y0 |ε
5.1 允许0打头的非负偶数 S→DS |0 | 2 | 4 | 6 | 8 D→ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
a
*
a
11
10. 文法：S→S(S)S |ε （1）该文法生成的语言是什么？ （2）是二义的吗？
答： L（G）={α|α为空串或可任意嵌套的配对的左右圆括号序列 } S S S（ S ）S S ε ε S（ S ）S ε ε ε ε S（ S ）S ε ε ε S （ S ）S ε
第3章 作业 P3.8
G=({A,B,S},{a,b,c},P,S) P: S→Ac|aB A→a b B→b c 写出L(G[S])的全部元素。
1.
S
A c a b
答： {abc}
1
2. 文法G[N]为： N→D|ND D→0|1|2|3|4|5|6|7|8|9 写出L(G[N])。
N
N D N D 0 D 4

给出生成下述语言的文法。 1.语言L={aibj|i≠j, i,j>0} 思路：该语言可视为两个语言的并集： L1={aibj| i>j>0}， L2={aibj| j>i>0} 参考答案 (1) SAC|CB AaA|a
BbB|b
CaCb|ab
（ C: a、b个数相等） ）
18
句子()()有两棵不同的语法树,所以该文法是二义的.

编译原理课后答案-第二版

第三章1、L(G[S])={ abc }2、L(G[N])={ n位整数或空字符串| n>0 }3、G[E]：E—>E+D | E-D | DD—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 94、L(G[Z])={ a n b n | n>0 }5、(1) 考虑不包括“0”的情况G[S]：S—>0S | ABC | 2 | 4| 6 | 8A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B—>AB | 0B | εC—>0 | 2 | 4 | 6 | 8考虑包括“0”的情况：G[S]：S—>AB | CB—>AB | CA—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C—>0 | 2 | 4 | 6 | 8(2)方法1：G[S]：S—> ABC | 2 | 4 | 6 | 8A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B—>AB | 0B | εC—>0 | 2 | 4 | 6 | 8方法2：G[S]：S—>AB | CB—> AB | 0B | C | 0A—> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C—>2 | 4 | 6 | 86、设<表达式>为E，<项>为T，<因子>为F，注：推导过程不能省略，以下均为最左推导(1) E => T => F => i(4) E => E+T => T+T => T*F+T => F*F+T => i*F+T => i*i+T => i*i+F => i*i+i(6) E => E+T => T+T => F+T => i+T => i+T*F => i+F*F => i+i*F => i+i*I7、<表达式><表达式>*<表达式><表达式>+<表达式>i i i<表达式><表达式>+<表达式>i <表达式>*<表达式>i i8、是有二义性的，因为句子abc 有两棵语法树（或称有两个最左推导或有两个最右推导）最左推导1：S => Ac => abc 最左推导2：S => aB => abc 9、(1)(2) 该文法描述了变量a 和运算符+、*组成的逆波兰表达式10、(1) 该文法描述了各种成对圆括号的语法结构(2) 是有二义性的，因为该文法的句子()()存在两种不同的最左推导： 最左推导1：S => S(S)S => (S)S => ()S => ()S(S)S => ()(S)S => ()()S => ()()最左推导2：S => S(S)S => S(S)S(S)S => (S)S(S)S=> ()S(S)S => ()(S)S => ()()S => ()()11、(1) 因为从文法的开始符E 出发可推导出E+T*F ，推导过程如下：E => E+T =>E+T*F ，所以E+T*F 是句型。

编译原理 第二版 第三章课后答案

第三章作业第三章作业答案P47 练习1、文法G=({A,B,S},{a,b,c},P,S),其中P为：S->Ac|aB A->ab B->bc写出L（G [S]）的全部元素。

S=>Ac=>abc或S=>aB=>abc所以L(G[S])={abc}2、文法G[N]为：N->D|NDD->0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？【解】N=>ND=>NDD.... =>NDDDD...D=>D......DG[N]的语言是V+。

V={0,1,2,3,4,5,6,7,8,9}或：解: N ND n-1D n{0,1,3,4,5,6,7,8,9}+∴L(G[N])= {0,1,3,4,5,6,7,8,9}+5.写一文法，使其语言是偶正数的集合。

要求：(1)允许0打头(2)不允许0打头【解】(1)允许0开头的偶正整数集合的文法E->NT|G|SFMT->NT|GN->D|1|3|5|7|9D->0|GG->2|4|6|8S->NS|εF->1|3|5|7|9|GM->M0|0(2)不允许0开头的偶正整数集合的文法E->NT|DT->FT|GN->D|1|3|5|7|9D->2|4|6|8F->N|0G->D|09.考虑下面上下文无关文法：S→SS*|SS+|a(1) 表明通过此文法如何生成串aa+a*，并为该串构造推导树。

(2) 该文法生成的语言是什么？【解】(1) S=>SS*=>SS+S*aa+a*该串的推导树如下：(2) 该文法生成的语言是只含+、*的算术表达式的逆波兰表示。

11.令文法G[E]为：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
G=( {0},{1,2,3,4,5} )
{1,2,3,4,5}a={1,3,0,5}
{1,2,3,4,5}b={4,3,2,5}
由于{4}a={0} {1,2,3,5}a={1,3,5}
因此应将{1,2,3,4,5}划分为{4},{1,2,3,5}
G=({0}{4}{1,2,3,5})
{1,2,3,5}a={1,3,5}
0
1
{z}
{x}
{Z}*
{X,z}
{y}
{X,z}*
{X,z}
{X,y}
{y}
{X,y}
{X,y}
{X,y,z}
{x}
{X,y,z}*
{X,y,z}
{X,y}
其中0表示初态，*表示终态
用0，1，2，3，4，5分别代替{X} {Z}{X,z}{y} {X,y} {X,y,z}
得DFA状态图为：
3．解：构造DFA矩阵表示
构造DFA的矩阵表示
0
1
{S}0
{V,Q}
{Q,U}
{V,Q}
{Z,V}
{Q,U}
{Q,U}
{V}
{Q,U,Z}
{Z,V}*
{Z}
{Z}
{V}
{Z}
{Q,U,Z}*
{V,Z}
{Q,U,Z}
{Z}
{Z}
{Z}
其中0表示初态，*表示终态
替换后的矩阵
0
1
00
1
2
1
3
2
2
4
5
3*
6
6
4
6
5*
3
5
6
6
6
构造DFA状态转换图（略）
1
6
5*
1
4
6
3
4
化简：
G={(0,1,3,4,6),(2,5)}
{0,1,3,4,6}a={1,3}
{0,1,3,4,6}b={2,3,4,5,6}
所以将{0,1,3,4,6}划分为{0,4,6}{1,3}
G={(0,4,6),(1,3),(2,5)}
{0,4,6}b={3,6,4}所以 划分为{0},{4,6}
(1,2,3,4,5,8)d=(3,8)
所以应将(1,2,3,4,5,8)分为(1,2,5,8), (3,4)
G={(1,2,5,8),(3,4),(6,7)}
11. 推导:E=>E+T=>E+T*F
语法树:
短语: T*F E+T*F
直接短语: T*F
句柄: T*F
12．
短语：<T><F><MOP> <E><T><F><MOP><POP>
直接短语：<T><F><MOP>
句柄： <T><F><MOP>
13.(1)最左推导：S=> ABS => aBS =>aSBBS => aBBS
4．（1）解
构造状态转换矩阵：
a
b
{0}0*
{0,1}
{1}
{0,1}*
{0,1}
{1}
{1}
{0}
转换为
a
b
0*
1
2
1*
1
2
2Байду номын сангаас
0
{2，3} {0，1}
{2，3}a={0,3}
{2},{3},{0,1}
{0,1}a={1,1} {0,1}b={2,2}
（2）解：首先把M的状态分为两组：终态组{0}，和非终态组{1，2，3，4,5}此时
因为 {2}a={1} {3}a={3} 所以{2,3}应划分为{2}{3}
所以化简后为G＝（ {0},{2},{3},{4},{1,5}）
7.去除多余产生式后，构造NFA如下
确定化，构造DFA矩阵
a
b
S
A
Q
A
A
B,Z
B,Z
Q
D
Q
Q
D,Z
D
A
B
D,Z
A
D
B
Q
D
变换为
a
b
00
1
3
1
1
2
2*
3
4
3
3
5
4
=>i+<因子>=>i+(<表达式>)=> i+(<表达式>+<项>)
=> i+(<因子>+<因子>)
=>i+(i+i)
(6) <表达式> => <表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项>
=>i+<项>*<因子>=>i+<因子>*<因子>=i+i*i
第7题
第9题
语法树
推导: S=>SS*=>SS+S*=>aa+a*
G={(0),(4,6),(1,3),(2,5)}
不能再划分，分别用 0，4，1，2代表各状态，构造DFA状态转换图如下；
8．代入得
S = 0(1S|1)| 1(0S|0)
= 01(S|ε) | 10(S|ε)
= (01|10)(S|ε)
= (01|10)S | (01|10)
= (01|10)*(01|10)
第三章
N=>D=> {0,1,2,3,4,5,6,7,8,9}
N=>ND=>NDD
L={a |a(0|1|3..|9)n且 n>=1}
(0|1|3..|9)n且 n>=1
{ab,}
anbnn>=1
第6题.
(1) <表达式>=><项>=><因子>=>i
(2) <表达式> => <项>=><因子>=>(<表达式>)=>(<项>)
构造NFA
由NFA可得正规式为(01|10)*(01|10)=(01|10)+
9.状态转换函数不是全函数,增加死状态8,
G={(1,2,3,4,5,8),(6,7)}
(1,2,3,4,5,8)a=(3,4,8) (3,4)应分出
(1,2,3,4,5,8)b=(2,6,7,8)
(1,2,3,4,5,8)c=(3,8)
=>(<因子>)=>(i)
(3) <表达式> =><项>=><项>*<因子>=><因子>*<因子>=i*i
(4) <表达式> => <表达式>+<项>=><项>+<项>=><项>*<因子>+<项>
=><因子>*<因子>+<项>=><因子>*<因子>+<因子>=i*i+i
(5) <表达式> => <表达式>+<项>=><项>+<项>=><因子>+<项>=i+<项>
直接短语：a1, b1, b2, a2,,
句柄：a1
14(1)
SAB
AaAb |ε
BaBb |ε
(2)
S1S0
SA
A0A1 |ε
第四章
1.1. 构造下列正规式相应的DFA
(1)1(0|1)*101
NFA
(2) 1(1010*|1(010)*1)*0
NFA
(3)NFA
(4)NFA
2.解：构造DFA矩阵表示
{1,2,3,5}b={4,3,2}
因为{1,5}b={4} {23}b={2,3}
所以应将{1,2,3,5}划分为{1,5}{2,3}
G=({0}{1,5}{2,3}{4})
{1,5}a={1,5} {1,5}b={4} 所以{1,5} 不用再划分
{2,3}a={1,3} {2,3}b={3,2}
=> abBS => abbS => abbAa => abbaa
最右推导：S => ABS => ABAa => ABaa => ASBBaa
=> ASBbaa => ASbbaa => Abbaa => a1b1b2a2a3
(2)文法：SABS
SAa
Sε
Aa
Bb
(3)短语：a1, b1, b2, a2, , bb , aa , abbaa,