下载文档原格式
编译原理_第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 单词的描述⼯具程序设计语⾔中的单词是基本语法成分.单词符号的语法可以⽤有效的⼯具加以描述，并且基于这类描述⼯具，实现词法分析程序的⾃动构造.描述⼯具：正规⽂法和正规式识别⼯具：有穷⾃动机⼀．正规⽂法多数程序设计语⾔的单词的语法能⽤正规⽂法来描述。
编译原理第三章练习题答案编译原理第三章练习题答案编译原理是计算机科学中的重要学科，它研究的是如何将高级语言代码转化为机器语言的过程。
在编译原理的学习过程中，练习题是不可或缺的一部分，通过完成练习题可以更好地理解和掌握编译原理的知识。
本文将为大家提供编译原理第三章练习题的答案，希望对大家的学习有所帮助。
1. 什么是语法分析？语法分析是编译器中的一个重要模块，它的主要任务是根据给定的语法规则，对输入的源代码进行分析和解释。
语法分析器会根据语法规则构建一个语法树，用于表示源代码的结构和含义。
常用的语法分析方法有递归下降法、LL(1)分析法和LR分析法等。
2. 什么是LL(1)文法？LL(1)文法是一种特殊的上下文无关文法，它具有以下两个特点：(1) 对于任何一个句子，最左推导和最右推导是唯一的。
(2) 在预测分析过程中，只需要向前看一个输入符号就可以确定所采用的产生式。
LL(1)文法是一种常用的文法形式，它适用于递归下降法和LL(1)分析法。
3. 什么是FIRST集合和FOLLOW集合？FIRST集合是指对于一个文法符号，它能够推导出的终结符号的集合。
FOLLOW 集合是指在一个句型中，某个非终结符号的后继终结符号的集合。
计算FIRST集合和FOLLOW集合可以帮助我们进行语法分析，特别是LL(1)分析。
4. 什么是递归下降语法分析法？递归下降语法分析法是一种基于产生式的自顶向下的语法分析方法。
它的基本思想是从文法的开始符号开始，递归地根据产生式进行分析，直到推导出输入符号串或发现错误。
递归下降语法分析法的实现比较简单，但对于某些文法可能会出现回溯现象，影响分析效率。
5. 什么是LR分析法？LR分析法是一种自底向上的语法分析方法，它的基本思想是从输入符号串开始，逐步构建语法树，直到推导出文法的开始符号。
LR分析法具有较好的分析效率和广泛的适用性，常用的LR分析方法有LR(0)、SLR(1)、LR(1)和LALR(1)等。
编译原理(第二版)第3章文法和语法编译原理(第二版)第3章文法和语法课件第3章文法和语言教学要求：本章是编译原理课程的理论基础，要求理解文法、语言、规范推导、规范归约和短语、简单短语、句柄的基本概念；掌握语言的求解方法、文法的二义性的判断方法及句型的分析方法。
教学重点：上下文无关文法，语言定义编译原理(第二版)第3章文法和语法课件一、语言语言是由句子组成的集合，是由一组记号所构成的集合。
汉语--所有符合汉语语法的句子的全体英语--所有符合英语语法的句子的全体程序设计语言--所有该语言的程序的全体编译原理(第二版)第3章文法和语法课件二、文法一种语言描述工具，用来定义句子的结构，用有限的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。
〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉|〈名词〉〈代词〉::= 你| 我| 他〈名词〉::= 王明| 大学生| 工人| 英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::= 是| 学习〈直接宾语〉::=〈代词〉|〈名词〉“我是大学生”是否是该语言的句子？编译原理(第二版)第3章文法和语法课件〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉|〈名词〉〈代词〉::= 你| 我| 他〈名词〉::= 王明| 大学生| 工人| 英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::= 是| 学习〈直接宾语〉::=〈代词〉|〈名词〉〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生编译原理(第二版)第3章文法和语法课件三、符号和符号串任何一种语言可看成是某个符号集上定义的，按一定规则构成的一切基本符号串组成的集合。
字母表:元素的非空有穷集合。
(符号集) 符号：字母表中的元素。
例如：汉语的字母表中包括汉字、数字及标点符号等。
C语言的字母表是由字母、数字、若干专用符号及IF、FOR之类的保留字组成。
第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[〈表达式〉]是二义的。
第3章词法分析习题答案1．判断下面的陈述是否正确。
（1）有穷自动机接受的语言是正规语言。
(√)（2）若r1和r2是Σ上的正规式，则r1|r2也是Σ上的正规式。
(√)（3）设M是一个NFA，并且L(M)={x,y,z}，则M的状态数至少为4个。
(× )（4）设Σ={a,b}，则Σ上所有以b为首的符号串构成的正规集的正规式为b*(a|b)*。
(× )（5）对任何一个NFA M，都存在一个DFA M'，使得L(M')=L(M)。
(√)（6）对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')，反之亦然。
(√) （7）一个DFA，可以通过多条路识别一个符号串。
(× )（8）一个NFA，可以通过多条路识别一个符号串。
(√)（9）如果一个有穷自动机可以接受空符号串，则它的状态图一定含有 边。
(× )（10）DFA具有翻译单词的能力。
(× )2.指与出正规式匹配的串.（1)(ab|b)*c 与后面的那些串匹配？ababbc abab c babc aaabc（2）ab*c*(a|b)c 与后面的那些串匹配？ acac acbbc abbcac abc acc（3）(a|b)a*(ba)* 与后面的那些串匹配? ba bba aa baa ababa答案（1) ababbc c babc（2) acac abbcac abc（3) ba bba aa baa ababa3. 为下边所描述的串写正规式，字母表是{0, 1}.（1)以01 结尾的所有串（2)只包含一个0的所有串（3) 包含偶数个1但不含0的所有串（4)包含偶数个1且含任意数目0的所有串（5)包含01子串的所有串（6)不包含01子串的所有串答案注意 正规式不唯一（1)(0|1)*01（2)1*01*（3)(11)*（4)(0*10*10*)*（5)(0|1)*01(0|1)*（6)1*0*4.请描述下面正规式定义的串. 字母表{x, y}.（1) x(x|y)*x（2)x*(yx)*x*（3) (x|y)*(xx|yy) (x|y)*答案（1)必须以 x 开头和x结尾的串（2)每个 y 至少有一个 x 跟在后边的串 （3)所有含两个相继的x或两个相继的y的串5．处于/* 和 */之间的串构成注解，注解中间没有*/。
