最右推导 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)
编译原理
8. 令文法为
E → T|E+T|E-T T → F|T*F|T/F
F → (E)|i
(2) 给出 i+i+i、i+i*i和i-i-i的语法树。 注意：树枝和符号均不可随意增减！
编译原理
5
回顾
文法产生语言
假定G是一个文法，S是它的开始符号。 如果S * ，则称是一个句型。仅含终 结符号的句型是一个句子。
文法G所产生的句子的全体是一个语言， 将它记为L(G) L(G) =｛ | S + & ∈VT*｝
编译原理
6
回顾
文法和语言的二义性
定义：如果一个文法存在某个句子对应两 颗不同的语法树，则说这个文法是二义的。
描述工具：正规式和有限自动机理论
语法规则：语法单位的形成规则。
语法单位通常包括：表达式、语句、子程序、 过程、函数、程序等;
描述工具：上下文无关文法
编译原理
3
回顾
标识符与名字
标识符：以字母开头的，由字母数字组成 的字符串。
标识符与名字两者有本质区别：
标识符是语法概念 名字有确切的意义和属性
语言的二义性：一个语言是二义性的，如 果对它不存在无二义性的文法。
可能存在G和G’，一个为二义的，一个为无二 义的。但L(G)=L(G’)
编译原理
7
例题2.1：有一个文法
G=({S,A,B},{a,b},P,S),其中Pa: S aB|bA A a|aS|bAA B b|bS|aBB 采用最左推导产生句子aabbab 并画出相应的语法树。
i-i-i 的语法树 E
E -T
E-T F
T
Fi
F
i
i
i+i+i 的语法树 E
E+T
E +T FTFra bibliotekFiF
i
i
编译原理
i+i*i 的语法树
E E +T T T* F FF i ii
9、证明文法: S → iSeS | iS | i 是二义的。
二义性的含义: 如果文法存在某个句子对应两棵以上
不同的语法树，或者两种以上不同的最 左/右推导，则称这个文法是二义的。
L(G6)={x|x∈{0,1,2,3,4,5,6,7,8,9}+} （2）给出句子0127、34和568的最左和最右推导。
编译原理
11
注意：1)步骤，和 + 的区别；2) 不能写 为→
解：0127的最左推导： NNDNDDNDDDDDDD
0DDD01DD012D0127 0127的最右推导：
1) 引进新的初态结点X和终态结点Y，X,YS， 从X到S0中任意状态结点连一条箭弧， 从F 中任意状态结点连一条箭弧到Y。
2) 对M的状态转换图进一步施行替换，其中k是 新引入的状态。
编译原理
23
按下面的三条规则对V进行分裂:
i AB j 代之为 i A k
例题与习题解答
第二章
-
1
回顾
程序语言的定义
一个程序语言是一个记号系统,它主要由以下方 面定义：
语法 语义
每个句子构成的规律 研究语言
每个句子的含义
语法 语义
编译原理
2
回顾
语法={词法规则+语法规则}
词法规则：单词符号的形成规则。
单词符号是语言中具有独立意义的最基本结构 。一般包括：常数、标识符、基本字、算符、 界符等。
编译原理
4
回顾
上下文无关文法的定义：一个上下文无关文法 G是一个四元式G=(VT，VN，S，P)，其中
VT：终结符集合(非空)
VN：非终结符集合(非空)，且VT VN=
S：文法的开始符号，SVN
P：产生式集合(有限)，每个产生式形式为
P， PVN， (VT VN)*
开始符S至少必须在某个产生式的左部出现一次。
A aAb|ab B cB|
编译原理
9
例题2.3 请证实文法G(E): E EiT | T T T+F | iF | F F E* | (
是一个二义文法。
编译原理
10
P36-6.
文法G6为:
N →D|ND
D →0|1|2|3|4|5|6|7|8|9
（1） G6的语言L(G6)是什么?
G6的语言是： 0~9的数字组成的任意非空数字串
S aBaaBB aabSB aabbABaabbaB aabbab
S
B aBB
bS
b
bA
a
编译原理
8
例题2.2 试构造生成语言 L={anbnci|n1, i 0}的文法
分析：要求a和b的个数一样多，并至少为一个， 而c的个数为0个以上即可，所以可以用一个终结 符去生成anbn串，用另一个非终结符去生成ci 。 G(Z): ZAB
首先：找到此文法对应的一个句子 iiiei 其次：构造与之对应的两棵语法树
S
S
i SeS
iS
iS
i
i S eS
i
ii
结论：因为该文法存在句子iiiei对应两棵
不同的语法树，因而该文法是二义的。
编译原理
18
10. 把下面文法改写成无二义性的文法 S->SS | (S) | ( )
解答： S-> TS | T T->(S) | ( )
编译原理
19
11、给出下面语言的相应文法
L2={aibncn| n≥1,i≥0}
G2(S): S→AB A→aA|ε B→bBc|bc
L3={anbnambm| m,n≥0}
G3(S): S→AB A→aAb|ε B→aBb|ε
编译原理
20
L4={1n 0m 1m 0n| n,m≥0} 可以看成是两部分：
NNDN7ND7N27ND27 N127D1270127
编译原理
8. 令文法为 E → T|E+T|E-T T → F|T*F|T/F F → (E)|i
(1) 给出 i+i*i、i*(i+i)的最左推导 和最右推导。
解：此处仅以 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)
中间部分是 0m 1m ： A→ 0A1 | ε 剩下两边的部分就是： S→ 1S0 | A
所以G4[S]可以写为： S→ 1S0 | A A→ 0A1 |ε
编译原理
21
例题与习题解答
第三章
-
22
非确定有限自动机状态图的改造
1. 假定NFA M=<S, , , S0, F>，我们对M的 状态转换图进行以下改造：