编译原理习题与解析（第2版）一二 解答：采用多遍扫描的方式，往往可以节省内存空间、提高目标程序的质量、缩短产 生编译程序的周期等，但也将使各遍扫描之间做一些重复性的工作，如各端都有读符号、 送符号等工作，这就延长了编译时间，降低了编译效率。 所以，不能说多遍扫描的编译程序就绝对好。 至于采用何种编译程序结构，是分遍还是不分遍，应根据具体情况决定，如语言的大 小与结构（若有先使用后说明现象则需要多遍扫描）、机器规模（多遍扫描可重复使用内 存)、设计日的（是否考虑编译的速度和日标程序的运行速度）以及设计人员的素质及数 量等。 14 Page
第3章」 文法和语言的形式定义 3.1基本内容 3.1.1符号串和符号串集合 1.字母表与符号 ·字母表 字母表是元素有穷非空的集合。 一个程序设计语言只使用一个有限字符集作为字母表。例如，PASCAL语言的字母 表包含有：26个英文字母a,b,c,…,X,y,z:10个阿拉伯数字0,1，…，8,9： 以及20个其他字符—空格，+，-，*，1，兰，<，>，(，)，【小， {},“，，，,；，:，↑。 ·符号 字母表中的元素称为符号，字母表 (begin,end,if,then,else) 中有5个符号：begin,cnd,if,then和clsc。 ·符号串 字母表中符号所组成的任何有穷序列称为符号串，通常用小写字母表示。 不包含任何符号的符号串为空串，记为6。 某程序设计语言的一个源程序，就是该语言字母表上的满足相应语法规则的一个符 号串。 符号串的头和尾 对于符号串z=xy,x是z的头（前缀），y是z的尾（后缀）。 2.符号串和符号串集合的运算 ·符号串的连接 设x、y是两个符号串，则xy被称为符号串x与y的连接。对任意的符号串x,有 X6-EX=X ·符号串x的方幂 x°-ex'-x x2-xx x-xrx-xx1-这3 ·符号串集合A与B的乘积 n 设A和B为符号串集合，则A和B的乘积定义 AB={xyIx∈A)AyeB)}
编译原理习题与解析（第2版）一二了 ·符号串集合的方幂 设A为符号串集合，则A的n次方幂A定义为 A=AAA=AA=AA 个 ·符号串集合的正闭包A A=A'UA2UUAU… ·符号串集合的闭包A A'-AUA-)UA* 3.1.2文法和文法的分类 1.文法的形式定义 终结符号集VT 终结符号是组成语言的基本符号，一个具体的保留字、运算符、界限符等都是终结 符号，如“f”, “+” “,”等。终结符号是语言的不可再分的基本符片。终 结符号形成的集合记为V, ·非终结符号集VN 非终结符号用来表示语言的语法成分（或语法范畴、语法单位），例如“赋值语句”、 “表达式”等。非终结符号所形成的集合记为VN。 VmnVN-0 ·产生式（规则） 产生式是一个有序对(u,V),通常写作 u=v(或u+v) 其中，u∈(VUV,v∈(VUV).u称为产生式（规则）的左部，v称为产生式（规 则)的右部。 ·文法GZ 文法G[Z是产生式（规则）有穷非空的集合。其中Z称为识别符号（或开始符号）， 它至少要在一条产生式（规则）中作为左部出现。文法形式化地定义为-个四元组： GIZ(VN,VT,P,Z) P为有穷非空的产生式（规则）集。 2.文法的分类 乔姆斯基(Chomsky)将文法和语言分为4类，如表3.1所示，划分的依据是对文法产生 式（规则）的形式施加不同的限制。 公 Page
、第3章文法和语言的形式定义·· 表3.1文法的分类 文法类别 规则形式 产生的语言 说明 0型文法· U-v 0型语言 对规则无限制 (短语结构文法) uEV',veV' 1型文法 1型语言 替换时，必须考虑被替 (上下文有关文法) uEV',veV' (上下文有关语言) 换符号的上下文 且1susw 2型文法 U-u 2型语言 无需考忠U在上下文 (.上下文无关文法) (上下文无关语言) 中的出现情况 3型文法 l.U+a或U→wa 3型语离 一个文法中的规则全 (正规文法) 或者 (正规语言) 部满足1或全部满足2 2.U+a或U→aw 的形式要求 其中U,WeVN,aeV 其中V-VTUVN- 3.1.3语言的形式定义 已知文法GZ=(VN,V,P,Z)。设V=VTUVN。 ·直接推导直接归约、推导/归约 如果U→u是G中的一条规则，而x,y是V中任一符号串，则将U→u作用于符号串 V=xUy上得到符号串w=Xuy,记为 xUy=xuy (v-w) 这时，称符号串w=xuy是符号串v=xUy的直接推导，或叫符号串v直接产生了符号串 w(也称w直接归的到V). 设o,u,…,n(>0)均为V中的符号串，且有 则称以上序列是长度为n的推导，也称v产生w(或称w归的到v),记为 V w 如果v古w或者v=w(表示0步推导)，则记为 Vw ·句型、句子与语言 设有文法G[Z),如果有Z些x,则称符号串x为文法G的句型（即符号串x是由识 别符号Z推导出来的)。仅由终结符号组成的句型称为句子。 由文法G[Z]产生的所有句子组成的集合叫做文法G[Z)所描述的语言，记为L(G[Z)。 L(G[Z))x,xEVT') 等价文法 如果两个不同形式的文法能产生相同的语言，则称这两个文法是等价的
编译原理习题与解析（第2版）一二 相同的语言指的是：两个语言包含同样的句子：分属于两个语言的两个句子，在包含 的符号及符号的排列顺序上是一样的，但这两个句子在含义上不一定等价。 3.1.4与语法分析有关的概念 ·短语、直接短语（简单短语）与句柄 设有文法GZ☑，w一xuy是它的一个句型，如果有 Z基xUy且U±u 则称句型xuy中的子串u为句型xy(相对于非终结符号U)的短谣。 特别地，如果前述条件中U吉u为 Uu 则称u为句型xuy(相对于非终结符号U)的直接短语（简单短语） 句型的最左直接短语（简单短语）称为句柄。 ·最左推导和最右推导、规范推导和规范归约、规范句型 如果在得到推导v去w的每一步直接推导中，都是对当前符号申中最左（右）的非 终结符号进行替换，则称v本w为最左（右）推导。最右推导又叫做规范推导。山 规范推导得到的句型称为规范句型。 规则递归与文法递归 规则呈U→U…(或U→U、U4U…)形式，则称其为规则左（或右、自嵌入） 递归，也称直楼递归。如果有推导序列U古U…(或U古…U、U古…U…),则 称其为文法左（或右、自嵌入）递归，也称间楼递归。 3.1.5语法树和二义性 1.语法树的定义 设有文法G-(VN,V,P,Z),则满足以下条件的树称为棵语法树： (1)树中的每个结点都有标记，该标记是V=VNUV中某个符号： (2)树根的标记是识别符号Z: (3)若一个结点至少有一个后继结点，则该结点上的标记必为非终结符号： (4)若一个标记为U的结点，它有标记依次为x,x2,…,X的直接后继结点，则U→x1x2 x必定是文法G的一条产生式。 2.语法树与推导 语法树的画法：从识别符号出发，向下画一个分枝，表示第一个直接推导：然后再从 非终结符号往下画分枝，表示即将进行的直接推导…直到全部推导都在树上表示出来。 也可以通过对语法树剪枝，得到一棵语法树所描述句型的推导或归约过程。 语法树和推导之间的对应关系为：每一棵语法树至少存在一个推导与之对应，每一个 推导都存在一棵语法树。 Page