编译原理第二章课件(续)——张淑艳

言？
2020/6/27
L(G6)={aa,ab,ba,bb}
S →aB | bB
B →a | b
中国科大
2.3.1 上下文无关文法
E E + E | E * E | (E ) | E | id
E E (E) (E + E)
？
？
最左推导:任何一步α β都是对α的最左非终结符进
行替换的。
E lm E lm (E) lm (E + E)
…
L(G2)={ambn|m,n≥1}
G2：S→AB A→aA | a B→bB | b
G2’ S→ACB A→aA | a C →aCb|ε B→bB | b
(1)给定一个文法G，就可以从结构上唯一地确定其 语言 GL(G) (2)给定一种语言L，能确定其文法，但这种文法可 能202不0/6/2是7 唯一的：LG1或中G国2科大
符号串集合的连接
Σ*的子集U和V的连接（积）定义为
UV = {αβ|α∈U & β∈V }
指数：Vn= VV…V，V0 = {ε}
闭包：V* = V0 ∪ V1 ∪ V2 ∪ V3 ∪ …
正闭包：V+ = VV* = V1 ∪ V2 ∪ V3 ∪ …
练习
U: { A, B, …, Z, a, b, …, z }, V: { 0, 1, …, 9 }
则称αn是α1的推导。
记作：α1 + αn
特别约定：若在推导关系α1 αn中允许α1=αn，
则20称20/α6/n2是7 α1 的广义推导
中国科记大作：α1 * αn
温故知新
定义3：句型、句子和语言，已给文法G=(VN,VT, S, P ）
若 S * α,α∈ (VN∪VT)* ，则称α为文法G的句型 若 S * α,α∈VT*，则称α为文法G的句子 文法G所对应的语言是句子的集合，记作 L(G)={α|α∈VT*，且S +α}
程序设计语言
编译原理
2020/6/27
中国科大
温故知新
字母表
集合
符号
组合
符号串
集合 语言
区别ε, ɸ 和{ε}
符号串的长度
符号串的连接：符号串x和y的连接表示为xy
符号串的幂运算：设x是一个符号串，则：
x0=ε，x1 = x，x2 = xx，…，xn = x…x
2020/6/27
中国科大
温故知新
EE+E Ei E(E) EE + E E i
E i
2020/6/27
中E国科大 i
E E * E
E+E * E i + E * E i + (E) * E i + (E + E) * E i + ( i + E) * E i + ( i + i) * E i + ( i + i) * i
温故知新
例：构造一个文法G3使L(G3)={anbn|n≥1} G3: S→aSb | ab
例：有文法G4:
例：已知语言为
S→aSb
L(G)={abna | n≥1}
S→ab
试给出其文法。
它确定的语言是什么？
G5:
G5’:
L(G4)={anbn | n≥1}
S→aBa S→aBa
例：有文法G6 确定什么语 B→bB|b B→Bb|b
i + i 和 i +(i + i) * i 都是
E i | E + E| E * E|(E)
的句子 2020/6/27
中国科大
例：考虑文法G1定义的语言。 G1: S→bA A→aA | a
S bA ba S bA baA baa
S bA baA baA… baa..a
L(G1)={ban|n≥1}
( )
简化表示
Ei
中国科大
| E + E| E * E|(E)
温故知新
上下文无关文法如何定义语言？推导 把产生式看成重写规则，把当前符号串中的非终 结符用其产生式右部的串来代替。
E i | E + E| E * E|(E)
E E *E
E (E)
EE+E Ei
Ei
E (E) (E + E) (i + E) (i + i)
…
2020/6/27
中国科大
例：考虑文法G2定义的语言。 G2：S→AB A→aA | a B→bB | b
S ABaB ab S AB aAB… a…aB a…ab
S AB … a…aB a…abB … a…abb…B a…ab…b
2020/L6/2(7 G2)={ambn|m,n≥中1国科}大
最右推导：
E E+E E+i E*E+i E*i+i i*i+i
最左推导：
E E*E i*E i*E+E i*i+E i*i+i
E E+E E*E+E i*E+E i*i+E i*i+i
2020/6/27
中国科大
2.3.2 语法分析树与二义性
UV, V6, V*, U(V )*, U+
2020/6/27
源自文库
中国科大
温故知新
字母表 词法分析器（正规式）
集合 组合
符号
符号串
单词符号
集合 语言
表达式
语句
2020/6/27
程序块 中国科大 程序
（
语
上 下
法文
分无
析 器
关 文 法
）
语法分析树
温故知新
定义1：上下文无关文法是四元组G =（VT , VN , S, P ） VT : 终结符集合 VN : 非终结符集合, VT ∩VN =ɸ S : 开始符号, S∈VN
定义2：符号串的推导与归约：已给文法G=(VN,VT, S, P ） 令α,β∈(VN∪VT)*，且Aγ ∈ P ，此时，由符号串αAβ能 够直接推出符号串αγβ ，我们称：
符号串αγβ是符号串αAβ的直接推导； 符号串αAβ是符号串αγβ的直接归约
记作: αAβ αγβ
若有α1,α2,…,αn∈ (VN∪VT) * 且α1 α2 … αn-1 αn
P : 产生式集合， 产生式形式 : P , P ∈ VN , ∈(VN∪
VT)* 例 :变量i是一个算术表达式；
若E1和E2是算术表达式，则E1+E2、E1*E2和(E1)也是
算术表达式 ( {i, +, *, (, )}, {E}, E, P )
Ei E E +E E E *E E E 2020/6/27
lm (id + E) lm (id + id)
最右推导（规范推导）
E rm E rm (E) rm (E + E) 2020/6/27 rm (E + id) rm中国科(大id + id)
2.3.1 上下文无关文法
例：文法G: E i| E+E | E*E | (E) 给出句子 i*i+ i 的最右及最左推导 。