编译原理陈火旺版2章2.ppt

2.6 有关文法的实用限制 1.不能有形如： U →U的产生式； 2.不能有多余产生式，多余产生式可以从文法中删掉，所谓多余产生式有这样的特点： (1)在推导文法的所有句子时，始终都用不到的产生式； (2)在推导过程中，一旦使用此产生式，将无法推出任何句子的的产生式； 例：有文法G[z]: Z →Be A →Ae | e B → Ce | Af C → Cf D → f Z →BeA →Ae | eB →Af 无多余产生式的条件: (1)Z ? * xUy (2)U ? + t t?VT* 2.7 扩充的巴科斯范式(EBNF)表示 1. 产生式的花括号表示法 表示符号串t可重复出现n次到m次(nm)，一般约定n=0; 例：若有产生式 S→xS│x，其中：S∈VN，x∈VT ，则可用花括号表示为： S→x{x} 2. 产生式的方括号表示法 [t] 表示符号串t为可选项，即可出现0次或1次： 例1：设有两个产生式T→T*F│F，可用方括号表示成： T→ [T*]F 例2：条件语句 → if 条件 then 语句 [else 语句] 3. 使用圆括号( )——提取候选式的公用因子 例1：若有产生式 A→xW1y│xW2y│┄│xWny 则可表示成： A→x(W1│W2│ ┄│Wn )y 例2：S→if B then S│if B then S else S 提取左公因子，可写成： S→if B then S (ε│else S) Exercise: P35 6 、 7 、8、9、11 * 引言在蒋立源的书上，之后2.1、2.2在陈的书上，2.3是两本书的结合 * 在此页介绍完后引入上下文无关文法的定义 * 巴科斯范式一种简洁的表示 * 判断文法是否递归，可以看其产生式是否递归 第二章 高级语言及其语法描述 引言：关于形式语言 2.1程序语言的定义 1、词法规则、语法规则p12-13 2、语义P14 2.2高级语言的一般特性P14-25 (关于算符的优先顺序p23、名字的左值和右值p24） 2.3 程序语言的语法描述p25 2.3 程序语言的语法描述 一、符号和符号串 字母表：字母表Σ是符号元素的非空集合。 符号：字母表中的元素。 符号串：字母表中的符号所组成的任何有穷序列。 例如，若有字母表Σ={a,b} 则a，b是字母表Σ中的元素(符号)； a，b，aa，ab，ba…都是符号串。 注意：符号串中的符号与顺序有关，ab和ba是不同的符号串 特别定义:空符号串——不含任何符号的符号串，用 ε 表示。 设有字母表Σ={a…z, A…Z,0…9,…, 各种运算符和其它特殊 符号，…}，则，由这些字母表中的元素(符号)可以组成不同 的符号串： Program example; Var sum,I: integer; Begin Sum := 0; For I:=1 to 10 do sum:=sum+I; 12345:=sum; End. Write(‘sum=’,sum); A={ …} 符号串的运算： 符号串的连接（联结、乘积）：符号串x和y的连接是指x和y的符号按先后顺序排列在一起组成一个新的符号串，用xy表示。 例，若字母表Σ={a,b}，符号串x=ab，y=ba 则xy=abba 符号串的长度：符号串中符号的个数为符号串的长度。 注意: (1)连接运算不满足交换律，即xy≠yx  (2)任何符号串x与空串ε的连接都等于x，即： εx=xε=x。 若ab是符号串，则|ab|表示符号串的长度。 |ab|=2 同理：|aabb|= 4 注意：特别规定 |ε|=0。 若有两个符号串x=ab,y=cde 那么，|xy|=? 5 符号串的前缀与后缀(头和尾)：若有符号串 z=xy(x,y是符号串),我们称x为z的前缀，y为z的后缀。 例z=abcd则：z的头有， ε , a , ab , abc , abcd z的尾有， ε ,d , cd , bcd , abcd 符号串的幂运算：设X是一个符号串，则： X0=ε，X1=X，X2=XX，…，Xn=X…X=Xn 例：若有符号串x=ab，则： x0= ε, x1= ab, x2