正规式和有穷自动机的等价性

第三章词法分析本章要点１．词法分析器设计，２．正规表达式与有限自动机，３．词法分析器自动生成。

本章目标：１．理解对词法分析器的任务，掌握词法分析器的设计；２．掌握正规表达式与有限自动机；３．掌握词法分析器的自动产生。

本章重点：1．词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实现有关。

应重点掌握词法分析器的任务与设计，状态转换图等内容。

2．掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法。

（1）非形式描述的语言↔正规式（2）正规式→ NFA（非确定的有限自动机）（3）NFA→ DFA（确定的有限自动机）（4）DFA→最简DFA本章难点（1）非形式描述的语言↔正规式（2）正规式→ NFA（非确定的有限自动机）（3）NFA→ DFA（确定的有限自动机）（4）DFA→最简DFA作业题一、单项选择题（按照组卷方案，至少15道）1. 程序语言下面的单词符号中，一般不需要超前搜索a. 关键字b. 标识符c. 常数d. 算符和界符2. 在状态转换图的实现中，一般对应一个循环语句a. 不含回路的分叉结点b. 含回路的状态结点c. 终态结点d. 都不是3. 用了表示字母，d表示数字， ={l，d}，则定义标识符的正则表达式可以是：。

(a)ld*(b)ll*(c)l(l | d)*(d)ll* | d*4. 正规表达式(ε|a|b)2表示的集合是(a){ε，ab，ba，aa，bb} (b){ab，ba，aa，bb}(c){a，b，ab，aa，ba，bb} (d){ε，a，b，aa，bb，ab，ba}5. 有限状态自动机可用五元组（V T，Q，δ，q0，Q f）来描述，设有一有限状态自动机M的定义如下：V T={0，1}，Q={q0，q1，q2}，Q f={q2}，δ的定义为：δ（q0，0）=q1δ（q1，0）=q2δ（q2，1）=q2δ（q2，0）=q2M所对应的状态转换图为。

6. 有限状态自动机可用五元组（V T，Q，δ，q0，Q f）来描述，设有一有限状态自动机M的定义如下：V T={0，1}，Q={q0，q1，q2}，Q f={q2}，δ的定义为：δ（q0，0）=q1δ（q1，0）=q2δ（q2，1）=q2δ（q2，0）=q2M所能接受的语言可以用正则表达式表示为。

注意：本题应该理解为对图(a)进行确定化和对图(b)进行最小化。提供的答案没有对图(a)确 定化。
盛威网（）专业的计算机学习网站 14
《编译原理》课后习题答案第四章
第5题 构造一个 DFA，它接收 Σ={0,1}上所有满足如下条件的字符串：每个 1 都有 0 直接跟在 右边。并给出该语言的正规式。 答案： 按题意相应的正规表达式是(0*10)*0*， 或 0*(0 | 10)*0* 构造相应的 DFA， 首先构造 NFA 为
7
《编译原理》课后习题答案第四章
注意：这个题，也可以这样构造 NFA（用最少的ε，但注意不能出错） ：
a,b 0 a a 2 a,b 1 a b 3
盛威网（）专业的计算机学习网站
8
《编译原理》课后习题答 ε X b A ε F B a C b ε b G b H ε ε D ε E a I b Y
除 X，A 外，重新命名其他状态，令 AB 为 B、AC 为 C、ABY 为 D，因为 D 含有 Y（NFA 的终态），所以 D 为终态。 . X A B C D DFA 的状态图：: 0 . A C A C 1 A B B D B
(2)先构造 NFA： 0 ε X 1 A ε ε F B 1 C 1 0 ε 0 D 1 E 1 0 ε 用子集法将 NFA 确定化 ε X T0=X A T1= ABFL Y CG T2= Y T3= CGJ DH K T4= DH EI T5= ABFKL T6= ABEFIL EJY T7= ABEFGJLY EHY CGK T8= ABEFHLY EY CGI T9= ABCFGJKL DHY T10= ABEFLY T11= CGJI DHJ T12= DHY T13= DHJ EIK T14= ABEFIKL ABEFIKL EJY CG DHJ ？正确 DHJG EI EIK DHY EY DHJ CG K ABEFLY CGJI DHY CGK ABEFHLY ABCFGJKL EY CGI ABEFGJLY EHY CGK ABEFIL Y EJY CG CG DH ABFKL EI DH K Y CGJ ABFL Y CG X A 0 1 1 ε L ε K ε J 0 Y

第一章高级语言与编译程序概述典型例题:单项选择题1.1.1．将编译程序分成若干个“遍”是为了___。

a.提高程序的执行效率b.使程序的结构更加清晰c.利用有限的机器内存并提高机器的执行效率d.利用有限的机器内存但降低了机器的执行效率1.1.2．构造编译程序应掌握____。

（陕西省2000年自考题）a.源程序b.目标语言c.编译方法d.以上三项都是1.1.3．变量应当＿。

a.持有左值b.持有右值c.既持有左值又持有右值d.既不持有左值也不持有右值1.1.4．编译程序绝大多数时间花在____上。

（陕西省1998年自考题）a.出错处理b.词法分析c.目标代码生成d.管理表格1.1.5．____不可能是目标代码。

( 陕西省1997年自考题)a.汇编指令代码b.可重定位指令代码c.绝对指令代码d.中间代码1.1.6．数组A[1…20,1…10]的首地址偏移量为0，按列存储，每个元素占一个字节，存储器按字节编址，则A[i,ｊ］的偏移地址为____。

a.(i-1)X10+（j-1）b.(i-1)X20+(j-1)c. (i-1)＋(j-1)X10d.(i-1)+(j-1)X201.1.7.使用____可以定义一个程序的意义。

a.语义规则b.词法规则c.产生规则d.左结合规则1.1.8．表达式X:=5中，变量x____。

a.只有左值b.只有右值c.既有左值又有右值d.没有左值也没有右值1.1.9．词法分析器的输入是__。

a.单词符号b.源程序c.语法单位d.目标程序1.1.10．中间代码生成时所遵循的是＿。

a.语法规则b.词法规则c.语义规则d.等价变换规则1.1.11．编译程序是对__。

a.汇编程序的翻译b.高级语言程序的解释执行c.机器语言的执行d.高级语言的翻译1.1.12．词法分析应遵循＿。

（陕西省2000年自考题）a.语义规则b.语法规则c.构词规则d.等价变换规则多项选择题：1.2.1 编译程序各阶段的工作都涉及到___。

第3章文法和语言第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试给出下述表达式的推导及语法树。

（５）i+(i+i)（６）i+i*i答案：(5)<表达式>=><表达式>＋<项>=><表达式>＋<因子>=><表达式>＋（<表达式>）=><表达式>＋（<表达式>＋<项>）=><表达式>＋（<表达式>＋<因子>）=><表达式>＋（<表达式>＋i）=><表达式>＋（<项>＋i）=><表达式>＋（<因子>＋i）=><表达式>＋（i＋i）=><项>＋（i＋i）=><因子>＋（i＋i）=>i＋（i＋i）(6)<表达式>=><表达式>＋<项>=><表达式>＋<项>*<因子>=><表达式>＋<项>*i=><表达式>＋<因子>*i=><表达式>＋i*i=><项>＋i*i=><因子>＋i*i=>i＋i*i<表达式><表达式>+<项><因子><表达式><表达式>+<项><因子>i<项><因子>i<项><因子>i（)<表达式><表达式>+<项><项>*<因子><因子>i<项><因子>ii第7题证明下述文法G[〈表达式〉]是二义的。