raw.doc
若用 compi 表示第 i 次扫描程序;用 Li 表示 compi 的工作结果。
则有 comp1(Lo)=>comp2(L1)=>comp3(L2)=>…
L1 源程序 =>compn(Ln-1)=Ln-目标程序
因为:L2… ,Ln-1 是中间结果,不必保留
所以:Li+1 可覆盖 Li
第三章 文法和语言
第一节 基本概念(1)
一.基本术语:
1.字母表:一个非空有穷集合,如 A={a,b}
2.符号:也叫字符,是字母表中的元素
3.符号有穷序列,如,abb,aaab,bb.
4.空串:不含任何字符的序列,用 E 表示
5.长度:每个串中所含符号个数
6.连结:设 x,y 是符号串,则 xy 是它们的连结
7.集合的乘积:设 A.B 是符号串的集合,则 A.B 的乘积 AB={xy|x 属于 A,y 属于 B}。如
A={ab,cc}, B={a,d},则 AB={aba,abd,cca,ccd}
8.空集:不含任何元素的集合,用空表示。*对任一集合 A,ΦA=AΦ=Φ
9.方幂:X 为一个符号串,则 X 的 n 次方=X…X
10.正闭包:A 是一个集合,A+=A1U A2U……UAnU……
自反闭包:A*=A0U A+= A0U A1U A2U……UAnU
第一节 基本概念(2)
1.直接推导:设 X,Y 是符号串 X=>Y iff X→Y 是一个产生式且称 Y 为 X 的一个直接推
导。
2.推导:若 X=>a =>a1=>……=>an=>Y ,则称 Y 为 X 的记作 X==>Y
3.句型:设 Z 是文法的开始符.若有 Z==>*X,则称 X 为文法 G 的显然,开始符 Z 本身即为
句型.
4.句子:仅含终极符的句型
5.语言:所有句子的集合
6.等价:设 G1 和 G2 是给定文法,若 L(G1)=L(G2)则称 G1 和 G2 等价
7.短语:设 G 是一个文法,S 是开始符,设 XUY 是 G 的一个句型,(S==>*xuy)符号串,
若有(1)S==>x∪y;(2)U==>u,则称 U 为句型 xuy 的短语。
8.简单短语:若有(1)S==>x∪y;(2)U==>μ,则称 u 为 xuy 的简单短语.
9.句柄:一个句型的最左边的简单短语。称为句柄
第二节 文法构成及类型
一.文法的构成:
1.抽像为 G=(Vn , Vt , P , S )
Vn-----非终极符集合(大写字母) P----规则式集合
Vt-----终极集符合(小写字母) S----开始符
2.文法----是由形如 A=>X1X2…Xn 的式子构成,该式称为文法的规则(生成式或规则式)
二.文法的类型:
分四种类型 :0 型文法、1 型文法、2 型文法、3 型文法
<一>.0 型文法:每个规则式的由形如 α→β,α, β 是符号串(α, β∈V*)
(短语文法)
第 3 页 共 13 页 2021-8-6
评论3