编译原理文法及语言.pptVIP

编 译 原 理;§3.1 符号和符号串 §3.2 文法和语言的形式定义 §3.3 文法的分类 §3.4 语法树和二义性 §3.5 有关文法的实用限制;语言的组成;语言定义的方法;§3.1 符号和符号串;§3.1 符号和符号串;§3.1 符号和符号串;§3.1 符号和符号串;§3.1 符号和符号串;§3.1 符号和符号串;§3.1 符号和符号串;§3.1 符号和符号串;§3.1 符号和符号串; 若A为某语言的基本字符集 A＝{a,b,……z,0,1,……,9, +,－,×,_/, ( , ), =……} B为单词集 B ={begin, end, if, then, …,标识符,常量,……} 则B ? A* 。 语言的句子是定义在B上的符号串。 若令C为句子集合，则C ? B * , 程序? C;§3.2 文法和语言的形式定义;一、文法的直观理解;一、文法的直观理解;句子 ? 主语谓语;一、文法的直观理解;二、文法的形式定义;二、文法的形式定义;P = {无符号整数 → 数字串 ； 数字串 → 数字串 数字 ； 数字串 → 数字 ； 数字 →0； 数字 →1； ………… 数字 →9； } S = 无符号整数；;也可以写做： G[{无符号整数]: 无符号整数 → 数字串 ； 数字串 → 数字串 数字 ； 数字串 → 数字 ； 数字 →0|1|2|…|9； ;三、推导和归约;三、推导和归约;三、推导和归约;三、推导和归约;三、推导和归约;三、推导和归约;三、推导和归约;§3.2 文法和语言的形式定义;四 、句型、句子和语言;四 、句型、句子和语言;四 、句型、句子和语言; 给定文法G[A]： A→bA|cc，下面的符号串中，为该文法句子的是： ①cc ②bcbc ③bcbcc ④bccbcc ⑤bbbcc; 已知句子L(G)={abna|n≥1}，构造文法。;§3.3 文法的分类;§3.3 文法的分类;§3.3 文法的分类;§3.3 文法的分类;§3.3 文法的分类;§3.3 文法的分类; 标识符→l|l字母数字　 字母数字→l|d|l字母数字|d字母数字　　无符号整数→d|d无符号整数　　运算符→+|-|*|/|=|等号|等号……　　等号→=　　界符→，|；|(|)|……　　其中l表示a～z中的任何一英文字母，d表示0～9中的任一数字。;§3.3 文法的分类;1：已知文法G[P]： P?aPQR|abR RQ?QR bQ?bb bR?bc cR?cc 它是Chomsky哪一型文法？;2：已知文法G[Z]： Z?U0|V1 U?Z1|1 V?Z0|0 它是Chomsky哪一型文法？并写出全部由此文法描述的只含有四个符号的句子。; Z?U0|V1 U?Z1|1 V?Z0|0;§3.4 语法树和二义性;§3.4 语法树和二义性;§3.4 语法树和二义性;§3.4 语法树和二义性;§3.4 语法树和二义性;§3.4 语法树和二义性;§3.4 语法树和二义性;§3.4 语法树和二义性;§3.4 语法树和二义性;E;§3.4 语法树和二义性;例：G[S]：S→a|ε|(T) T→T,S|S 给出句子(a,(a,a))的最左、最右推导。 ;答：最右推导： S?(T) ?(T,S) ?(T,(T)) ?(T,(T,S)) ?(T,(T,a)) ?(T,(S,a)) ?(T,(a,a)) ?(S,(a,a)) ?(a,(a,a));§3.4 语法树和二义性;例：G[E]: E → i|E+E|E*E|(E)，写出句型 i*i+i的最左推导。;§3.4 语法树和二义性;§3.4 语法树和二义性;;§3.4 语法树和二义性; E E * E i E + E i i;文法G[P]： P→PaP|PbP|cP|Pe|f 证明文法G是二义性文法。;§3.5 有关文法的实用限制;§3.5 有关文法的实用限