第二章 词法分析 2.1 完成下列选择题： (1) 词法分析器的输出结果是 。 a. 单词的种别编码 b. 单词在符号表中的位置 c. 单词的种别编码和自身值 d. 单词自身值 (2) 正规式M1和M2等价是指 。 a. M1和M2的状态数相等 b. M1和M2的有向边条数相等 c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向边条数相等 (3) DFA M(见图2-1)接受的字集为 。 a. 以0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合 c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合 【解答】 (1) c (2) c (3) d 图2-1 习题2.1的DFA M 2.2 什么是扫描器？扫描器的功能是什么？ 【解答】 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。 2.3 设M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机，其中f 定义如下： f(x,a)={x,y} f {x,b}={y} f(y,a)=Φ f{y,b}={x,y} 试构造相应的确定有限自动机M ′。 【解答】 对照自动机的定义M=(S,Σ,f,So,Z)，由f 的定义可知f(x,a)、f(y,b)均为多值函数，因此M 是一非确定有限自动机。 先画出NFA M 相应的状态图，如图2-2所示。 图2-2 习题2.3的NFA M 用子集法构造状态转换矩阵，如表 表2-1 状态转换矩阵 1b a
第二章 3.何谓“标志符”，何谓“名字”，两者的区别是什么 答：标志符是一个没有意义的字符序列，而名字却有明确的意义和属性。 4.令+、*和↑代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值。 （1）优先顺序（从高到低）为+、*和↑，同级优先采用左结合。 （2）优先顺序为↑、+、*，同级优先采用右结合。 答：（1）1+1*2↑2*1↑2=2*2↑2*1↑2=4↑2*1↑2=4↑2↑2=16↑2=256 （2）1+1*2↑2*1↑2=1+1*2↑2*1=1+1*4*1=2*4*1=2*4=8 6.令文法G6为 N-〉D|ND D-〉0|1|2|3|4|5|6|7|8|9 （1）G6的语言L（G6）是什么 （2）给出句子0127、34、568的最左推导和最右推导。 （1）由0到9的数字所组成的长度至少为1的字符串。即：L（G6）={d n|n≧1,d∈{0,1,…,9}}答： （2）0127的最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127 0127的最右推导：N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127（其他略） 7.写一个文法，使其语言是奇数集，且每个奇数不以0开头。 答：G（S）：S->+N|-N N->ABC|C C->1|3|5|7|9 A->C|2|4|6|8 B->BB|0|A|ε ［注］：可以有其他答案。 ［常见的错误］：N->2N+1 原因在于没有理解形式语言的表示法，而使用了数学表达式。
8.令文法为 E->T|E+T|E-T T->F|T*F|T/F F->(E)|i (1)给出i+i*i 、i*(i+i)的最左推导和最右推导。 (2)给出i+i+i 、i+i*i 和i-i-i 的语法树，并给出短语，简单短语和句柄。 答：(1) i*(i+i)的最左推导： E=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=>i*(i+F)=> i*(i+i) i*(i+i)的最右推导： E=>T=>T*F=>T*(E) =>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*(T+i)=>T*(F+i)=> T*(i+i)=> F*(i+i) => i*(i+i) （其他略） ［注］：要牢记每一步都是对最左（右）的一个非终结符号进行一步推导。 (2) i+i+i 的语法树： （其他略） ９.证明下面的文法是二义的：S->iSeS|iS|i 证明：反例法： 对于该文法的句子iiiei 有两个最右推导如下，所以该文法是二义的： E E + T E + T T F i １ F i F i 短语：i １, i 2, i 3, i １+ i 2, i １+i 2+ i 3 简单短语：i １, i 2, i 3
2．1回答下面的问题： （周期律 02282067） （1）在文法中，终极符号和非终极符号各起什么作用？ ? 终结符号是一个文法所产生的语言中句子的中出现的字符，他决定了一个文法的产生语 言中字符的范围。 ? 非终结符号又叫做一个语法变量，它表示一个语法范畴，文法中每一个产生式的左部至 少要还有一个非终结符号，（二，三型文法要求更严，只允许左部为一个非终结符号）他是推导或归约的核心。 （2）文法的语法范畴有什么意义？开始符号所对应的语法范畴有什么特殊意义？ ? 文法的非终结符号A 所对应的语法范畴代表着一个集合L （A ），此集合由文法产生式 中关于A 的产生式推导实现的 ? 开始符号所对应的语法范畴则为文法G = {V ，T ，P ，S}所产生的语言L （G ） ={w S T w w **|?∈且} （3）在文法中，除了的变量可以对应一个终极符号行的集合外，按照类似的对应方法，一个字符串也可以对应一个终极符号行集合，这个集合表达什么意义？ ? 字符串对应的终极符号行集合表示这个字符串所能推导到的终极字符串集合，为某个句 型的语言。 （4）文法中的归约和推导有什么不同？ ? 推导：文法G = {V ，T ，P ，S}，如果,)(,,* T V P ∈∈→δγβα则称γαδ在G 中推导出了γβδ。 ? 归约：文法G = {V ，T ，P ，S}，如果,)(,,* T V P ∈∈→δγβα则称γβδ在G 中归约到γαδ。 ? 这他们的定义，我个人理解两个概念从不同角度看待文法中的产生式，推导是自上而下 （从产生式的左边到右边），而归约是自下而上（从产生式的右边到左边），体现到具体实际中，如编译中语法分析时语法树的建立，递归下降，LL （1）等分析法采用自开始符号向下推导识别输入代码生成语法树，对应的LR （1），LALR 等分析法则是采用自输入代码（相当于文法中语言的句子）自底向上归约到开始符号建立语法树，各有优劣。 （5）为什么要求定义语言的字母表上的语言为一个非空有穷集合？ ? 非空：根据字母表幂的定义：εε,}{0∑=为字母表中０个字符组成的。这样，当字母 表中没有字符的情况，字母表也有一个元素，字母表为空就没有意义，而且，如果字母表为空，将无法定义其上的语言，使得理论体系不严密。 ? 有穷：我们将语言抽象成形式语言的目的就是为了有穷的表示无限的语言，在此基础上 我们才定义了字母表和语言，如果字母表为无穷的，他就违背了我们研究问题的初衷，这也使得研究失去意义
第二章文法和形式语言 《编译原理》课程组 计算机工程学院 第二章文法和形式语言 2.1 文法的直观概念 2.2 符号和符号串 2.3 文法和语言的形式定义 2.4 文法的类型 2.5 上下文无关文法机器语法树 2.6 句型分析 2.7 文法的实用限制 第2章文法和语言 【学习目标】 本章目的是为语言的语法描述寻求工具 ◇掌握对源程序给出精确无二义（严谨、简洁、易读）的语法描述手段之一——文法。 ◇对形式语言的理论有一个初步基础 ◇根据语言文法的特点指导语法分析的过程 本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。 第2章文法和语言 【教学重点】 概念：文法，推导，直接推导，最左(右)推导，产生式，句型，短语，直接短语，句柄，语法树，规范推导，二义文法等 4种文法的定义、文法的构造和文法的推导 语法树的构造和最左（右）推导； 二义文法、二义性的证明； 句型分析； 2.1 文法的直观概念 一、语言概述 语言是由符合语法的句子组成的集合。 –汉语-- 所有符合汉语语法的句子的全体 –英语-- 所有符合英语语法的句子的全体 –程序设计语言-- 所有该语言的程序的全体
每个句子构成的规律 研究语言每个句子的含义 每个句子和使用者的关系 一、语言概述（续1） 研究程序设计语言 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系 语言研究的三个方面 语法Syntax 语义Semantics 语用Pragmatics 一、语言概述（续2） 语法：指语言的一组规则，用它可以形成和产生一个合适的程序。 –如何由基本字符构成一个个单词； –如何由一系列单词构成程序 语法只定义什么样的符号序列是合法的，而不表达这些符号及符号序列的含义 语义：明确程序各部分的含义 –静态语义：由一系列限定规则组成，并确定哪些合乎语法的程序是合适的； –动态语义：表明程序要做些什么，要计算什么 一、语言概述（续3） 形式语言：只考虑语法而不考虑语义的符号语言。 每种语言具有两个可识别的特性， –语言的形式 –该形式相关联的意义 “形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。 形式语言理论是对符号串集合的表示法、结构及其特性的研究，是程序设计语言语法分析研究的基础。 语言可以看成在一个基本符号集上定义的，按一定规则构成的基本符号串组成的所有集合。 二、文法的直观概念 表达语言时，一般无法穷尽语言的所有句子，常用规则加以描述 例：汉语句子的构成规则： 〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉|〈名词〉 〈代词〉∷= 我| 你| 他 〈名词〉∷= 王明| 大学生| 工人| 英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷= 是| 学习 〈直接宾语〉∷=〈代词〉|〈名词〉
3.何谓“标志符”，何谓“名字”，两者的区别是什么？ 答：标志符是一个没有意义的字符序列，而名字却有明确的意义和属性。 4.令+、*和↑代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值。 （1）优先顺序（从高到低）为+、*和↑，同级优先采用左结合。 （2）优先顺序为↑、+、*，同级优先采用右结合。 答：（1）1+1*2↑2*1↑2=2*2↑2*1↑2=4↑2*1↑2=4↑2↑2=16↑2=256 （2）1+1*2↑2*1↑2=1+1*2↑2*1=1+1*4*1=2*4*1=2*4=8 6.令文法G6为 N-〉D|ND D-〉0|1|2|3|4|5|6|7|8|9 （1）G6的语言L（G6）是什么？ （2）给出句子0127、34、568的最左推导和最右推导。 （1）由0到9的数字所组成的长度至少为1的字符串。即：L（G6）={d n|n≧1,d∈{0,1,…,9}}答： （2）0127的最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127 0127的最右推导：N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127 （其他略） 7.写一个文法，使其语言是奇数集，且每个奇数不以0开头。 答：G（S）：S->+N|-N N->ABC|C C->1|3|5|7|9 A->C|2|4|6|8 B->BB|0|A|ε ［注］：可以有其他答案。 ［常见的错误］：N->2N+1 原因在于没有理解形式语言的表示法，而使用了数学表达式。 8.令文法为 E->T|E+T|E-T T->F|T*F|T/F F->(E)|i (1)给出i+i*i、i*(i+i)的最左推导和最右推导。 (2)给出i+i+i、i+i*i和i-i-i的语法树，并给出短语，简单短语和句柄。 答：(1) i*(i+i)的最左推导： E=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=>i*(i+F)=> i*(i+i) i*(i+i)的最右推导： E=>T=>T*F=>T*(E) =>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*(T+i)=>T*(F+i)=> T*(i+i)=> F*(i+i) => i*(i+i) （其他略） ［注］：要牢记每一步都是对最左（右）的一个非终结符号进行一步推导。 (2) i+i+i的语法树：
