编译原理第二章.pptVIP

**文法和识别系统0型文法（短语文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的1型文法（上下文有关文法）：产生式的形式为α1Aα2→α1βα2，即只有A出现在α1和α2的上下文中时，才允许β取代A。其识别系统是线性界限自动机。**带a0a1a2a3a4a5a6a7a8…an-1an有限控制器磁头图灵机**文法的类型2型文法（上下文无关文法、CFG）：产生式的形式为A→β，β取代A时与A的上下文无关。其识别系统是不确定的下推自动机。3型文法（正规文法、右线性文法）：产生的语言是有穷自动机（FA）所接受的集合**2.5上下文无关文法及其语法树上下文无关文法有足够的能力描述现今程序设计语言的语法结构算术表达式语句赋值语句条件语句读语句……**例：算术表达式上下文无关文法表示文法G=({E},{+,*,I,(,)},P,E} P: E→i E→E+E E→E*E E→(E)**例：条件语句上下文无关文法表示条件语句→if条件then语句

|if条件then语句else语句**2.5.1上下文无关文法的语法树用于描述上下文无关文法的句型推导的直观方法例:G[S]: S→aAS A→SbA A→SS S→a A→baSaASSbAaaba句型aabbaa的语法树（推导树）叶子结点：树中没有子孙的结点。

从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。**上下文无关文法的语法树给定文法G，对于G的任何句型都能构造与之关联的语法树（推导树）。这棵树满足下列4个条件：1、每个结点都有一个V中的符号作标记2、根的标记是开始符号S3、若一结点n至少有一个它自己除外的子孙，并且n有标记A，则A∈VN4、如果结点n的直接子孙，从左到右的次序是结点n1,n2,…,nk，其标记分别为A1,A2,…,Ak，那么A→A1A2,…,Ak一定是P中的一个产生式**上下文无关文法的语法树推导过程中施用产生式的顺序例:G[S]: S→aAS A→SbA A→SS S→a A→baSaASSbAaabaS?aAS?aAa?aSbAa?aSbbaa?aabbaaS?aAS?aSbAS?aabAS?aabbaS?aabbaaS?aAS?aSbAS?aSbAa?aabAa?aabbaa**最左（最右）推导：在推导的任何一步α?β，其中α、β是句型，都是对α中的最左（右）非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型**2.5.2二义性问题：一个句型是否对应唯一的一棵语法树？例：G[E]:

E→i E→E+E E→E*E E→(E)EE+EE*EiiiEE*EiE+Eii句型i*i+i的两个不同的最左推导：推导1：E?E+E?E*E+E?i*E+E?i*i+E?i*i+i推导2：E?E*E?i*E?i*E+E?i*i+E?i*i+i**第二章

文法和语言**本章内容2.1符号、符号串及其集合的运算2.2文法的直观概念2.3文法和语言的形式定义2.4文法的类型2.5上下文无关文法及其语法树2.6句型的分析2.7文法实用中的一些说明**2.1符号、符号串及其集合的运算任何一种语言都是由该语言的基本符号组组成的符号串的集合。基本符号集任何语言的单词符号就是定义在它的字符集上的字符串该语言的任何语句就是定义在其单词符号集上的单词串(符号串)2.1.1字母表和符号串2.1