编译程序的组织 (6).ppt
1Chomsky将文法分为四种类型：将文法分为四种类型：0型文法型文法：对任一产生式：对任一产生式，都有，都有（VNVT）+，（VNVT）*1型文法型文法：对任一产生式：对任一产生式，都有，都有|，仅仅，仅仅 S除外除外 2型文法型文法：对任一产生式：对任一产生式，都有，都有 VN，（VNVT）*3型文法型文法：任一产生式：任一产生式的形式都为的形式都为AaB或或Aa，其中其中AVN，BVN，aVT2.3 2.3 文法的类型文法的类型V=（VNVT）0 0型文法型文法:若若P P中任一产生式都有一般形式中任一产生式都有一般形式 V+V+V*V*且对且对，不加任不加任何限制，则称何限制，则称GG为为0 0型文法型文法（短语结构文法，记为短语结构文法，记为PSG:Phrase PSG:Phrase Structure GrammarStructure Grammar)。由。由0 0型文法生成（或者说：定义）的语言称为型文法生成（或者说：定义）的语言称为0 0型型（递归可枚举递归可枚举）语言语言。它可由。它可由图灵图灵（TuringTuring）机机识别。识别。例如：例如：S SACaB ACaB Ca CaaaC aaC CB CBDB DB CB CBE E aD aDDa Da AD ADAC AC aE aEEa Ea AE AE 对于程序设计语言来，对于程序设计语言来，0 0型文法有很大的随意性，还须加以限制型文法有很大的随意性，还须加以限制0 0型文法型文法，它所产生的语言为它所产生的语言为1 1型文法型文法:若若0型文法中所有产生式具有形式型文法中所有产生式具有形式 1A 2 1 2 其中，其中，1,2 V*V+A VN,则称则称G 为为1型型(前后文有关前后文有关)文法文法，记为，记为CSG(Context Sensitive Grammar)。1型文法型文法产生的语言称为产生的语言称为前后文有关语言前后文有关语言CSL，它可由，它可由线性限界自动机线性限界自动机识别。识别。命名的由来命名的由来：只有当非终结符：只有当非终结符A的前后分别为的前后分别为 1,2 时，才能将时，才能将A替换为替换为。1 型文法还有另一种定义形式：型文法还有另一种定义形式：G的每个产生式形为的每个产生式形为且满足且满足：|,V+则则G是是1型文法。型文法。注注：根据定义，含有根据定义，含有 产生式的文法不是产生式的文法不是1型文法。由于实际需要，我们将型文法。由于实际需要，我们将-产产生式作为生式作为1型文法的特例而接受之。型文法的特例而接受之。例例 文法文法 G：S|A AaABC|abC CBBC bBbb bCbc cCcc 它不是一个严格意义下的它不是一个严格意义下的1型文法。它所产生的语言为型文法。它所产生的语言为2型文法若一若一1型文法型文法G中所有产生式具有形式中所有产生式具有形式:A V+A VN 则称则称G为为2型型(前后文无关前后文无关)文法文法，记为，记为CFG(Context Free Grammar)。2型文法产生的语言称为型文法产生的语言称为前后文无关语言前后文无关语言CFL，它可由，它可由下推自动机下推自动机识别。识别。若允许若允许-产生式存在，则产生式存在，则CFG产生式形式为产生式形式为 A V*A VN 例例：GS=(S,a,b,SaSb Sab,S)产生的语言为产生的语言为3 3型文法型文法若若2型文法型文法G中仅含有形如：中仅含有形如：AaB Aa 的产生式，的产生式，其中其中 A,B VN,a VT 则称则称G为为右线性文法右线性文法。若若G中仅含有形如中仅含有形如 ABa Aa的产生式，则称的产生式，则称G为为左线性左线性文法文法。把把左线性文法左线性文法和和右线性文法右线性文法都称为都称为3型文法型文法（正规文法正规文法）3型文法型文法产生的语言称为产生的语言称为3型（型（正规正规）语言）语言，它可由，它可由有限自有限自动机动机识别。识别。正规语言正规语言可用可用正规表达式正规表达式表示。表示。注意：注意：若一文法即含若一文法即含左线性左线性又含又含右线性产生式右线性产生式，则它，则它不一不一定是定是3型文法型文法！3型文法型文法还可拓广定义为还可拓广定义为 AB A （VT+）6例：例：1 1型（上下文有关）文法型（上下文有关）文法文法文法GS:SCDGS:SCD AbbAAbbACaCACaCABaaBBaaBCbCBCbCBBbbBBbbBADaDADaDCCBDbDBDbDDDAabDAabDL L（G G）=ww|www|wa a，b b*7例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS:S0A|1B|0GS:S0A|1B|0A0A|1B|0SA0A|1B|0SB1B|1|0B1B|1|0文法文法GS:SaB|bAGS:SaB|bAAa|aS|bAAAa|aS|bAABb|bS|aBBBb|bS|aBB8例：定义标识符的例：定义标识符的3型（正规）文法型（正规）文法文法文法GI:I lT I l T lT T dT T l T d l：az d：092023/5/249四种文法之间的关系是将产生式作进一步限制而定义的，他们四种文法之间的关系是将产生式作进一步限制而定义的，他们呈逐级呈逐级“包含包含”关系关系0型文法型文法1型文法型文法 2型文法型文法3型文法型文法 .
