第四章 程序设计语言和编译程序
第一节 上下文无关文法
一, 文法
文法是描述语言的语法结构的形式规
则,必须准确,易于理解,且描述能力强
1,文法的形式定义
G=(VT,VN,S,P)
例 G0=(VT,VN,S,P),
E→E+T|T
T→T*F|F
F→(E)|i
显然 VT ={+,*,(,),i}
VN ={E,T,F}
S=E
P为上述产生式的集合
说明, ① ?→ ?的读法,
其中 ? ?V*VNV*,? ? V*
② ? → ? 1
? → ? 2
,,
,
? → ? n
缩写为 ? → ? 1| ? 2|…| ? n
2,文法的分类
① 0型文法,产生式形如 ?→ ?
② 1 型文法,│α│<=│β│ 或产生式形如
αAβ→α ?β
(上下文有关文法 )
③ 2型文法,产生式形如 A→α
(上下文无关文法 )
④ 3型文法,产生式形如 A→α 或 A→αB
(正则文法,右线性文法 )
3,简化的上下文无关文法
① 不含形如 A→A 的有害规则
② 不含多余规则
即 A?VN,必有 S ?αAβ *
二, 文法产生的语言
1,推导与归约
① 直接推导, αβ? ?α??
即由产生式右边替换产生式左边
② 推导,α1 ? αn,α1 ? αn
③ 归约,推导的逆过程
* +
举例, 已知 G(E) E→E+E│E*E│(E)│i
i+i*i的推导过程
? E ?E+E ?E+E*E ?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*i ?E+E*i ?E+i*i ?i+i*i
2,句型和句子
?设文法 G=(VT,VN,S,P),若 S ?α,α?V*,则称 α为
文法 G的一个 句型 。
?若上述 α ?VT,则称 α是一个句子，即只含终结
符的句型是一个 句子 。
*
*
3,文法产生的语言
文法 G=(VT,VN,S,P)的句子的全体,称为由文法
G产生的语言,记为 L(G),即
L(G)={α│S ? α?α ?VT*} +
G2(I),
I→L│LS
S→T│ST
T→L│D
L→a│b│,,,│z
D→ 0│1│2│,,,│9
G3(S),
S→aS│aP
P→bP│bQ
Q→cQ│c
L(G3)={aibjck│i,j,k?1}
G4(S),
S→aSPQ│abQ
QP→PQ
bP→bb
bQ→bc
cQ→cc
L(G4)={ aibici│i ?1}
S?ai-1S(PQ)i-1 (i-1次使用第一个产生式 )
?aibQ(PQ)i-1 (使用第二个产生式 )
?aib(PQ)i-1Q (i-1次使用第三个产生式 )
?aib2(QP)i-2Q2 (使用第四个产生式 )
?aib3(QP)i-3Q3 (i-2次使用第三个产生式 )
?……
?aibiQi
?aibicQi-1 (使用第五个产生式 )
?aibici (i-1次使用第三个产生式 )
*
*
*
*
*
*
*
*
*
① 文法的重要特性,用 有限 规则描述
无穷 语言
② 文法的等价,两个文法 G和 G’,如果
有 L(G)=L(G’ ),则称 G和 G’ 等价
4,短语和句柄
① 短语,设 αβ?是上下文无关文法 G的一个句
型,如果有 S ? αA?,并且 A ? β,则称 β是
句型 αβ?关于非终结符 A的一个短语,或称
β是句型 αβ?的一个短语 。
② 直接短语 （ 简单短语 ）, A ? β
③ 句柄：一个句型的最左直接短语 。
* +
例, G0(E) E→E+T|T
T→T*F|F
F→(E)|i
求 E+T*F的短语、直接短语、句柄
④ 素短语：含有终结符的短语，并且它的
真子串不具有这种特性
⑤最右推导（规范推导）
⑥最左推导
5,推导树
—— 以图的方式表示推导过程
① 推导树是一棵有序的标记树
?每个结点的标记是文法 G的非终结符或终结符；
?标记为 A的内部结点从左到右有子结点 X1，
X2,…,Xn,则 A→X 1… Xn是一个产生式 ;
?如果有结点标记为 ?,则它必是叶结点, 且它
是该父结点的唯一子结点 。
② 推导树的构造
例 （ i+i*i）
E
（ E ）
E E *
E E +
i i
i
E
（ E ）
E E +
E E i
i i
*
③ 推导树的 边缘,一棵推导树所有叶结点
的从左到右的连接 。
④ 文法的二义性：一个 句子 有两棵不同的
推导树 。
⑤ 由推导树确定短语等 (见下页 )
E
（ E ）
E E *
E E +
i i
i
E
（ E ）
E E +
E E i
i i
*
例（ i+i*i）
第二节 自动机
文法是语言的生成系统，而自动机是
语言的识别系统。自动机分为,图灵机、
线性有界自动机、下推自动机、有限自
动机
一, 有限自动机的定义
1,确定的有限自动机
DFA Md=(?,S,s0,F,?)
?,S?? →S
例, ?={0,1} s0是初态
S={s0,s1,s2,s3}
F={s0}
?(s0,0)=s2 ?(s0,1)=s1
?(s1,0)=s3 ?(s1,1)=s0
?(s2,0)=s0 ?(s2,1)=s3
?(s3,0)=s1 ?(s3,1)=s2
2,非 确定的有限自动机
NFA Mn=(?,S,s0,F,?)
?,S?? →2 S
例, ?={0,1} s0是初态
S={s0,s1,s2,s3,s4}
F={s2,s4}
?(s0,0)={s0,s3} ?(s0,1)={s0,s1}
?(s1,0)=? ?(s1,1)={s2}
?(s2,0)={s2} ?(s2,1)={s2}
?(s3,0)={s4} ?(s3,1)=?
?(s4,0)={s4} ?(s4,1)={s4}
第一节 上下文无关文法
一, 文法
文法是描述语言的语法结构的形式规
则,必须准确,易于理解,且描述能力强
1,文法的形式定义
G=(VT,VN,S,P)
例 G0=(VT,VN,S,P),
E→E+T|T
T→T*F|F
F→(E)|i
显然 VT ={+,*,(,),i}
VN ={E,T,F}
S=E
P为上述产生式的集合
说明, ① ?→ ?的读法,
其中 ? ?V*VNV*,? ? V*
② ? → ? 1
? → ? 2
,,
,
? → ? n
缩写为 ? → ? 1| ? 2|…| ? n
2,文法的分类
① 0型文法,产生式形如 ?→ ?
② 1 型文法,│α│<=│β│ 或产生式形如
αAβ→α ?β
(上下文有关文法 )
③ 2型文法,产生式形如 A→α
(上下文无关文法 )
④ 3型文法,产生式形如 A→α 或 A→αB
(正则文法,右线性文法 )
3,简化的上下文无关文法
① 不含形如 A→A 的有害规则
② 不含多余规则
即 A?VN,必有 S ?αAβ *
二, 文法产生的语言
1,推导与归约
① 直接推导, αβ? ?α??
即由产生式右边替换产生式左边
② 推导,α1 ? αn,α1 ? αn
③ 归约,推导的逆过程
* +
举例, 已知 G(E) E→E+E│E*E│(E)│i
i+i*i的推导过程
? E ?E+E ?E+E*E ?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*i ?E+E*i ?E+i*i ?i+i*i
2,句型和句子
?设文法 G=(VT,VN,S,P),若 S ?α,α?V*,则称 α为
文法 G的一个 句型 。
?若上述 α ?VT,则称 α是一个句子，即只含终结
符的句型是一个 句子 。
*
*
3,文法产生的语言
文法 G=(VT,VN,S,P)的句子的全体,称为由文法
G产生的语言,记为 L(G),即
L(G)={α│S ? α?α ?VT*} +
G2(I),
I→L│LS
S→T│ST
T→L│D
L→a│b│,,,│z
D→ 0│1│2│,,,│9
G3(S),
S→aS│aP
P→bP│bQ
Q→cQ│c
L(G3)={aibjck│i,j,k?1}
G4(S),
S→aSPQ│abQ
QP→PQ
bP→bb
bQ→bc
cQ→cc
L(G4)={ aibici│i ?1}
S?ai-1S(PQ)i-1 (i-1次使用第一个产生式 )
?aibQ(PQ)i-1 (使用第二个产生式 )
?aib(PQ)i-1Q (i-1次使用第三个产生式 )
?aib2(QP)i-2Q2 (使用第四个产生式 )
?aib3(QP)i-3Q3 (i-2次使用第三个产生式 )
?……
?aibiQi
?aibicQi-1 (使用第五个产生式 )
?aibici (i-1次使用第三个产生式 )
*
*
*
*
*
*
*
*
*
① 文法的重要特性,用 有限 规则描述
无穷 语言
② 文法的等价,两个文法 G和 G’,如果
有 L(G)=L(G’ ),则称 G和 G’ 等价
4,短语和句柄
① 短语,设 αβ?是上下文无关文法 G的一个句
型,如果有 S ? αA?,并且 A ? β,则称 β是
句型 αβ?关于非终结符 A的一个短语,或称
β是句型 αβ?的一个短语 。
② 直接短语 （ 简单短语 ）, A ? β
③ 句柄：一个句型的最左直接短语 。
* +
例, G0(E) E→E+T|T
T→T*F|F
F→(E)|i
求 E+T*F的短语、直接短语、句柄
④ 素短语：含有终结符的短语，并且它的
真子串不具有这种特性
⑤最右推导（规范推导）
⑥最左推导
5,推导树
—— 以图的方式表示推导过程
① 推导树是一棵有序的标记树
?每个结点的标记是文法 G的非终结符或终结符；
?标记为 A的内部结点从左到右有子结点 X1，
X2,…,Xn,则 A→X 1… Xn是一个产生式 ;
?如果有结点标记为 ?,则它必是叶结点, 且它
是该父结点的唯一子结点 。
② 推导树的构造
例 （ i+i*i）
E
（ E ）
E E *
E E +
i i
i
E
（ E ）
E E +
E E i
i i
*
③ 推导树的 边缘,一棵推导树所有叶结点
的从左到右的连接 。
④ 文法的二义性：一个 句子 有两棵不同的
推导树 。
⑤ 由推导树确定短语等 (见下页 )
E
（ E ）
E E *
E E +
i i
i
E
（ E ）
E E +
E E i
i i
*
例（ i+i*i）
第二节 自动机
文法是语言的生成系统，而自动机是
语言的识别系统。自动机分为,图灵机、
线性有界自动机、下推自动机、有限自
动机
一, 有限自动机的定义
1,确定的有限自动机
DFA Md=(?,S,s0,F,?)
?,S?? →S
例, ?={0,1} s0是初态
S={s0,s1,s2,s3}
F={s0}
?(s0,0)=s2 ?(s0,1)=s1
?(s1,0)=s3 ?(s1,1)=s0
?(s2,0)=s0 ?(s2,1)=s3
?(s3,0)=s1 ?(s3,1)=s2
2,非 确定的有限自动机
NFA Mn=(?,S,s0,F,?)
?,S?? →2 S
例, ?={0,1} s0是初态
S={s0,s1,s2,s3,s4}
F={s2,s4}
?(s0,0)={s0,s3} ?(s0,1)={s0,s1}
?(s1,0)=? ?(s1,1)={s2}
?(s2,0)={s2} ?(s2,1)={s2}
?(s3,0)={s4} ?(s3,1)=?
?(s4,0)={s4} ?(s4,1)={s4}
