33语言与文法简介 矿上下文有关语言 Context Sensitive Language, CsL 程序设计语言中除了CFG可以描述的结构之外,还有一些是 CFG无法描述的所谓上下文有关的结构 典型的这类语言结构包括:变量的声明与引用、过程调用时形 参与实参的一致性检查等。 描述它们的文法被称为上下文有关文法( Context sensitive Grammar,CSG)
12 3.3 语言与文法简介 上下文有关语言 Context Sensitive Language, CSL 程序设计语言中除了CFG可以描述的结构之外，还有一些是 CFG无法描述的所谓上下文有关的结构。 典型的这类语言结构包括：变量的声明与引用、过程调用时形 参与实参的一致性检查等。 描述它们的文法被称为上下文有关文法（Context Sensitive Grammar, CSG）
33语言与文法简介 [例3.12]不能用CFG描述的语言: Ll={0c0)0∈(ab)*} (标识符声明与引用一致性的抽象) L2={a"b"c"dn1和m1}(形参与实参一致性的抽象) 3={a"b"cn1 (计数问题的抽象) 相近的CFL: Ll={ carlo∈(ab)*} S→ asabsblc L2={a"bpec"d四n1,m1}S→ asaad A→ bAcbc L2"={a"b"cdn>l,m1}s→ABA→ lablab B→ cEded L3={a"b"c"m,n1} A→ACA→ lablab C→cC|c
13 3.3 语言与文法简介 [例3.12] 不能用CFG描述的语言： L1={ωcω|ω∈(a|b)*} (标识符声明与引用一致性的抽象) L2={anb mc nd m|n≥1和m≥1} (形参与实参一致性的抽象) L3={anb nc n |n≥1} (计数问题的抽象) 相近的CFL： L1'={ωcωr|ω∈(a|b)*} L2'={anb mc md n |n≥1, m≥1} L2''={anb nc md m|n≥1, m≥1} L3'={amb mc n |m, n≥1} S→aSa|bSb|c S→aSd|aAd A→bAc|bc S→AB A→aAb|ab B→cBd|cd A→AC A→aAb|ab C→cC|c
33语言与文法简介 计数问题 L3-anbncnne1) CSL L3=ambmcn m, n21g CFLA→ACA→ lAblab C→cCk L3"={abck,m,n>1}正规集abtc 命题:L3不是正规集,因为构造不出可以识别L3的DFA。 证明:(反证) 假设L3是正规集,则可构造n个状态的DFAD,它接受L3; 考察D读完,a,a,…,an,分别到达S0,S1,…,Sn, 共有n+1个状态。根据鸽巢原理,序列中至少有两个状态相 同,设Si=Sj(j>i),因为abck∈L3,所以存在路径ab 但是D中也有路径ab￠,矛盾。故L3不是正规集。 a-I S Si (kck
14 3.3 语言与文法简介 计数问题 L3={anb nc n |n≥1} CSL L3'={amb mc n |m,n≥1} CFL L3''={akb mc n |k，m，n≥1} 正规集 命题：L3'不是正规集，因为构造不出可以识别L3'的DFA。 证明：（反证） 假设L3'是正规集，则可构造n个状态的DFA D，它接受L3'； 考察D读完ε，a，aa，...，an，分别到达S0，S1，...，Sn， 共有n+1个状态。根据鸽巢原理，序列中至少有两个状态相 同，设Si=Sj（j>i），因为a ib ic k∈L3'，所以存在路径a ib ic k 。 但是D中也有路径a jb ic k，矛盾。故L3'不是正规集。 A→AC A→aAb|ab C→cC|c ? a +b +c + S0 Si Sk f ai bi ck aj-i
33语言与文法简介 形式语言与自动机简介 定义38若文法G=(N,T,P,S)的每个产生式α→β中,均有 a∈(N∪T)*,且至少含有一个非终结符,β∈(N∪T)*,则 称G为0型文法。 对0型文法施加以下第i条限制,即得到型文法。 1.G的任何产生式→β(S→8除外)满足kβ|; 2.G的任何产生式形如A→β,其中A∈N,β∈(N∪T)*; 3.G的任何产生式形如A→a或者A→aB(或者A→>Ba),其 中A和B∈N,a∈T 文法语官 自动机 短语文法0型)「短语结构语言图灵机 CSG(1型) CSL 线性界线自动机 CFG(2型) CFL 下推自动机 正规文法(3型) 正规集 有限自动机
15 3.3 语言与文法简介 形式语言与自动机简介 定义3.8 若文法G=(N，T，P，S)的每个产生式α→β中，均有 α∈(N∪T)*，且至少含有一个非终结符，β∈(N∪T)*，则 称G为0型文法。 对0型文法施加以下第i条限制，即得到i型文法。 1. G的任何产生式α→β（S→ε除外）满足|α|≤|β|； 2. G的任何产生式形如A→β，其中A∈N，β∈(N∪T)*； 3. G的任何产生式形如A→a或者A→aB(或者A→Ba)，其 中A和B∈N，a∈T。 文 法 语 言 自 动 机 短语文法(0型) 短语结构语言 图灵机 CSG (1型) CSL 线性界线自动机 CFG (2型) CFL 下推自动机 正规文法(3型) 正规集 有限自动机
33语言与文法简介 再考察L3 句子a4bc的推导: L3-anbcnne1) S=>.=> ak-IS(BC)k-l(by 1) [例3.15]L3可用下述CSG描述 = a(BC)(by 2) S→aSBC(1)S→aBC(2) aBaCk(by 3 k-Ick CB→→BC(3 B→ab (4) -akbBA (by 4 =>…→>a4bCk(by5) bB→bb(5)bC→bc (6) akbkcck-l(by 6) cC→cc akbek(by 7) CSG、CFG、正规式能力递减,但是能力越强的文法,其文法 设计和自动机的构造越困难,因此语法分析仅用到CFG(除 特别指出,文法即指CFG) 16
16 3.3 语言与文法简介 再考察L3： L3={anb nc n |n≥1} [例3.15] L3可用下述CSG描述： S→aSBC (1) S→aBC (2) CB→BC (3) aB→ab (4) bB→bb (5) bC→bc (6) cC→cc (7) CSG、CFG、正规式能力递减，但是能力越强的文法，其文法 设计和自动机的构造越困难，因此语法分析仅用到CFG（除 特别指出，文法即指CFG ） 句子a kb kc k 的推导： S =>...=> ak-1S(BC)k-1 (by 1) => ak (BC)k (by 2) =>...=> akBkCk (by 3) => akbBk-1Ck (by 4) =>...=> akb kCk (by 5) => akb kcCk-1 (by 6) =>...=> akb kc k (by 7)