形式语言学ch6.pdf

文法的乔姆斯基体系 文法G=(V，T，P ，S) (变量, 终极符,产生式,开始符号) G叫做0型文法(type 0 grammar)，也叫做短语结构文法 (phrase structure grammar, PSG)。 L(G) 叫做0型语言。也可以叫做短语结构语言(PSL)、递 归可枚举集(recursively enumerable ，r.e. )。 文法的乔姆斯基体系 G是0型文法。 如果对于∀α→β∈P ，均有| β|≥| α|成立，则称G为 1型文法(type 1 grammar)，或上下文有关文法 (context sensitive grammar,CSG)。 L(G) 叫做1型语言(type 1 language)或者上下文有关 语言(context sensitive language ,CSL)。 1 文法的乔姆斯基体系 G是1型文法 如果对于∀α→β∈P ，均有| β|≥| α|，并且α∈V成立， 则称G为2型文法(type 2 grammar)，或上下文无关文法 (context free grammar,CFG)。 L(G) 叫做2型语言(type 2 language)或者上下文无关语言 (context free language ,CFL)。 文法的乔姆斯基体系 G是2型文法 如果对于∀α→β∈P ，α→β均具有形式 A→w A→wB + 其中A ，B ∈V ，w ∈T 。则称G 为3型文法(type 3 grammar)， 也 可 称 为 正则文法 ( regular grammar ,RG)或者正规文法。L(G) 叫做3型语言 (type 3 language)，也可称为正则语言或者正规 语言(regular language ,RL)。 2 文法的乔姆斯基体系 ⑴ 如果一个文法G是RG ，则它也是CFG、CSG和短语结 构文法。反之不一定成立。 ⑵ 如果一个文法G是CFG，则它也是CSG和短语结构文法。 反之不一定成立。 ⑶ 如果一个文法G是CSG，则它也是短语结构文法。反 之不一定成立。 相应地： ⑷ RL也是CFL、CSL和短语结构语言。反之不一定成立。 文法的乔姆斯基体系 ⑸ CFL也是CSL和短语结构语言。反之不一定成立。 ⑹ CSL也是短语结构语言。反之不一定成立 ⑺ 当文法G是CFG时，L(G)却可以是RL。 ⑻ 当文法G是CSG时，L(G)可以是RL、CSL。 ⑼ 当文法G是短语结构文法时，L(G)可以是RL、CSL和CSL。 3 第6章上下文无关文法和上下文无关语言 Gbra ：S→S(S)| ε L(Gbra)不是RL,是CFL (n1` )n1 (n2 )n2 (nh )nh n1` n1 n2 n2 nh nh 0 1 0 1 0 1 •高级程序设计语言的绝大多数语法结构都可以用上下 文无关文法(CFG)描述。。 •BNF(巴科斯范式：Backus normal form，又叫 Backus-naur form)。 正则文法只能对语言中组成单词的规则 进行描述，通常称其为“词法”。 正则文法对表达式和语句等复杂结构而 言失去了描述能力。 语法 上下文无关文法 。 第6章上下文无关语言 主要内容 关于CFL 的分析 • 派生和归约、派生树 CFG的化简 • 无用符、单一产生式、空产生式 重点 CFG的化简。