4第二章高级语言及其文法3.pptVIP

第2章 高级语言及其文法（3） 本章主要内容 2.1 语言概述 2.2 基本定义(语言、句子、形式化方法、串、字母表、串的连接与幂、产生式) 2.3 文法(Grammar)的定义 2.4 CFG的语法(分析)树(Parse Tree) 2.5 文法的分类 2.6 文法的构造 2.４ 文法的分类(Chomsky体系) 语言结构的复杂程度（形式语言） 涉及文法的复杂程度、分析方法的选择 如果G满足文法定义的要求，则Ｇ是０型文法（短语结构文法PSG: Phrase Structure Grammar ）。 L(G)为PSL。 例2-3 标识符的文法2 S →L|LT T → L|N|TL|TN L → a|b|c|d N → 0|1|2|3|4|5 S → a|b|c|d S → aT|bT|cT|dT T → a|b|c|d|0|1|2|3|4|5 T → aT|bT|cT|dT|0T T →1T|2T|3T|4T|5T 例2-4 标识符的文法3 S → a|b|c|d S → aT|bT|cT|dT T → a|b|c|d T → 0|1|2|3|4|5 T → aT|bT|cT|dT|0T T → 1T|2T|3T|4T|5T S → a|b|c|d S → Ha|Hb|Hc|Hd|H0 S → H1|H2|H3|H4|H5 H → Ha|Hb|Hc|Hd|H0 H → H1|H2|H3|H4|H5 H → a|b|c|d A→aB或A→a A→Ba或A→a 正规文法(RG) 设A、B∈VN，a∈VT∪{ ? } 右线性(Right Linear)文法：A→aB或A→a 左线性(Left Linear)文法：A→Ba或A→a 都是３型文法(正规文法 Regular Grammar -RG) L(G)为3型/正规集/正则集/正则语言（RL） 例：程序设计语言的多数词法特性 左、右线性文法不可混用 例 非CFL的文法 L={anbncn|n0}的文法 S?aBC|aSBC CB?BC aB?ab bB?bb bC?bc cC? cc “可以证明”不存在CFG G ,使L(G)=L ?在我们使用的程序语言中,有些语言结构并不是总能用上下文无关文法描述的。 例 L1={wcw|w∈{a,b}+}。例,aabcaab就是L1的一个句子。这个语言是检查程序中标识符的声明应先于引用的抽象。 ?例 L2={anbmcndm|n,m≥0}，它是检查过程声明的形参个数和过程引用的参数个数是否一致问题的抽象。 高级语言中的非CFL结构 Chomsky体系——总结 1型文法 (CSG) S?aBC S?aSBC CB?BC aB?ab bB?bb bC?bc cC? cc 0型文法 (PSG) S?aBC S?aSBC CB?BC aB?ab bB?bb bC?b cC? cc 2型文法 (CFG) E→E+E E→E*E E→(E) E→id E→E-E E→E/E 3型文法 S→a|b S→aT|bT T→a|b T→1|2 T→aT|bT T→1T|2T 3型文法 S→a|b S→Ha|Hb S→H1|H2 H→Ha|Hb H→H1|H2 H→a|b Chomsky体系——总结 Ｇ = (ＶT，ＶN，Ｐ，Ｓ)是一个文法,α→β ∈ P * G是0型文法，L(G)是0型语言； ---其能力相当于图灵机(TM) * |α|≤|β|:G是1型文法，L(G)是1型语言(除Ｓ→ε); ---其识别系统是线性界限自动机(LBA) * α∈ＶN : G是2型文法，L(G)是2型语言; ---其识别系统是不确定的下推自动机(PDA) * A→aB或A→a: G是右线性文法，L(G)是3型语言 A→Ba或A→ａ: G是左线性文法，L(G)是3型语言 ---其识别系统是有穷自动机(FA) 四种文法之间的关系是将产生式作进一步限制而定义的 四种文法之间的逐级“包含”关系如下： 2型文法 1型文法 0型文法 3型文法 Chomsky体系——总结 ＢＮＦ范式——Backus-Naur Form Backus-Normal Form α→β表示为α∷＝β 非终结符用“”和“”括起来 终结符：基本符号集 其他 β(α1|α2…|αn)≡βα1|βα2…|βαn {α1|α2…|αn} ul {α1|α2…|αn}m l=0,u=m [α] ≡ α| ε …… ＢＮＦ范式——Backus Normal Form 例 简单算术表达式(只写产生式) 简单表达式∷＝简单表达式+简单表达式 简单表达式∷＝简单表达式*简单表达式 简单表达式∷＝(简单表达式) 简单表达式∷