编译原理第三章

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

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

本章重点：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所能接受的语言可以用正则表达式表示为。

《编译原理》课后习题答案第三章第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])的全部元素。

盛威网（）专业的计算机学习网站 1《编译原理》课后习题答案第三章答案：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盛威网（）专业的计算机学习网站 2 《编译原理》课后习题答案第三章答案：<表达式><表达式> + <项><因子><表达式><表达式> + <项><因子>i<项><因子>i<项><因子>i（ )(5) <表达式>=><表达式>＋<项>=><表达式>＋<因子>=><表达式>＋（<表达式>）=><表达式>＋（<表达式>＋<项>）=><表达式>＋（<表达式>＋<因子>）=><表达式>＋（<表达式>＋i）=><表达式>＋（<项>＋i）=><表达式>＋（<因子>＋i）=><表达式>＋（i＋i）=><项>＋（i＋i）=><因子>＋（i＋i）=>i＋（i＋i）<表达式><表达式> + <项><项> * <因子><因子> i<项><因子>ii(6) <表达式>=><表达式>＋<项>=><表达式>＋<项>*<因子>=><表达式>＋<项>*i=><表达式>＋<因子>*i=><表达式>＋i*i=><项>＋i*i=><因子>＋i*i=>i＋i*i盛威网（）专业的计算机学习网站 3《编译原理》课后习题答案第三章第7 题证明下述文法G[〈表达式〉]是二义的。

编译原理_第3章课件第三章词法分析本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的⾃动构造原理。

教学要求１.掌握：正规式，DFA的概念，NFA的概念２.理解：将NFA转换为DFA ,正规式、正规⽂法与有穷⾃动机间的转换⽬录3.1 词法分析程序的设计3.2 单词的描述⼯具3.3 有穷⾃动机3.4 正规式与有穷⾃动机的等价性3.5 正规⽂法和有穷⾃动机的等价性3.6 词法分析程序的⾃动构造⼯具⼩结3.1.词法分析（lexical analysis）程序的设计回顾：1、词法分析的任务：逐个读⼊源程序字符并按照构词规则切分成⼀系列单词。

2、词法分析程序：实现词法分析的程序。

⼀.词法与语法分析程序的接⼝⽅式1、作为独⽴的⼀遍词法分析是编译过程中的⼀个阶段，在语法分析前进⾏，把字符流的源程序变为单词序列，输出在⼀个中间⽂件上。

2、与语法分析结合在⼀起作为⼀遍⼀般、把词法分析程序设计成⼀个⼦程序，由语法分析程序调⽤词法分析程序来获得当前单词，供语法分析使⽤。

….词法分析程序的主要任务：读源程序，产⽣单词符号词法分析程序的其他任务：滤掉空格，跳过注释、换⾏符追踪换⾏标志，复制出错源程序，宏展开，……⼆、词法分析程序的输出输出是单词符号。

单词是语⾔中具有独⽴意义的最⼩单位。

单词包括：保留字标识符常量运算符界符（标点符号）词法分析程序所输出的单词符号常常采⽤以下⼆元式表⽰：(单词种别，单词⾃⾝的值)。

单词的种别是语法分析需要的信息，⽽单词⾃⾝的值则是编译其它阶段需要的信息。

(标识符，指向该标识符所在符号表中位置的指针) 单词的种别可以⽤整数编码表⽰，假如标识符编码为1，常数为2，保留字为3，运算符为4，界符为5例如：程序段if i=5 then x∶=y；在经词法分析器扫描后输出的单词符号和它们的表⽰如下：- 保留字if(3，'if')- 标识符i(1，指向i的符号表⼊⼝)- 等号=(4，'=')- 常数5(2，'5')- 保留字then(3，'then')- 标识符x(1，指向x的符号表⼊⼝)- 赋值号∶=(4，'∶=')- 标识符y(1，指向y的符号表⼊⼝)- 分号；(5，'；')三、词法分析⼯作从语法分析⼯作独⽴出来的原因：简化设计改进编译效率增加编译系统的可移植性3.2 单词的描述⼯具程序设计语⾔中的单词是基本语法成分.单词符号的语法可以⽤有效的⼯具加以描述，并且基于这类描述⼯具，实现词法分析程序的⾃动构造.描述⼯具：正规⽂法和正规式识别⼯具：有穷⾃动机⼀．正规⽂法多数程序设计语⾔的单词的语法能⽤正规⽂法来描述。

第三章语法分析3.1 完成下列选择题：(1) 文法G：S→xSx|y所识别的语言是。

a. xyxb. (xyx)*c. xnyxn(n≥0)d. x*yx*(2) 如果文法G是无二义的，则它的任何句子α。

　a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同(3) 采用自上而下分析，必须。

a. 消除左递 a. 必有ac归b. 消除右递归c. 消除回溯d. 提取公共左因子(4) 设a、b、c是文法的终结符，且满足优先关系ab和bc，则。

b. 必有cac. 必有bad. a～c都不一定成立(5) 在规范归约中，用来刻画可归约串。

a. 直接短语b. 句柄c. 最左素短语d. 素短语(6) 若a为终结符，则A→α·aβ为项目。

a. 归约b. 移进c. 接受d. 待约(7) 若项目集Ik含有A→α· ，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α· ”动作的一定是。

a. LALR文法b. LR(0)文法c. LR(1)文法d. SLR(1)文法(8) 同心集合并有可能产生新的冲突。

a. 归约b. “移进”/“移进”c.“移进”/“归约”d. “归约”/“归约”【解答】(1) c (2) a (3) c (4) d (5) b (6) b (7) d (8) d3.2 令文法G[N]为G[N]: N→D|NDD→0|1|2|3|4|5|6|7|8|9(1) G[N]的语言L(G[N])是什么?(2) 给出句子0127、34和568的最左推导和最右推导。

【解答】(1) G[N]的语言L(G[N])是非负整数。

(2) 最左推导：NNDNDDNDDDDDDD0DDD01DD012D0127NNDDD3D34NNDNDDDDD5DD56D568最右推导：NNDN7ND7N27ND27N127D1270127NNDN4D434NNDN8ND8N68D685683.3 已知文法G[S]为S→aSb|Sb|b，试证明文法G[S]为二义文法。

第三章作业第三章作业答案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是它的一个句型，指出这个句型的所有短语、直接短语和句柄。