编译原理 第2章 文法和语言.ppt

编译原理_第2章_文法和语言基本概念字母表、符号、符号串、闭包等文法的定义文法的分类Chromsky对文法的分类文法和语言推导、归约、句型、句子、:inti=0;包含字母i,n,t,=,0,;,所有字母形成字母表;符号串,:字母表∑是符号元素的非空有限集合。(字符):字母表中的元素。(字符串):字母表中的符号所组成的任何有穷序列。如字母表∑={a,b},则a,b是字母表∑中的元素,a,b,aa,ab,…都是符号串。空符号串:不含任何符号的符号串,用ε表示。字母表,符号,:指x和y的符号按先后顺序排列在一起组成的新的符号串,用xy表示。例:若∑={a,b},x=ab,y=ba,则xy=abba,yx=baab。注意:(1)xy≠yx;(2)εx=xε=x。:指符号串中符号的个数。例:|ab|=2,|aabb|=4,|ε|=0。字符串连接、:分别指符号串的左部和右部任意字符串。例:ab的前缀有ε、a、ab;后缀有ε、b、ab。:设A、B是字母表∑上的符号串集合,则定义A与B的乘积:AB={xy|x∈A,y∈B}。例:设∑={a,b,c,d},令A={aa,bb},B={cc,dd},则 AB={,aadd,,bbdd}, BA={bb,ddaa,ddbb}。显然AB≠BA定义空集合:Φ={ε},有{ε}A=A{ε}=A。前缀、后缀、:设x是符号串,则:x0=ε,x1=x,x2=xx,…,xn=x…x(n个):A0={ε},A1=A,A2=AA,…,An=A…A(n个A)A的正闭包:A+=A1∪A2∪…A的闭包:A*=A0∪A1∪A2∪…显然:A*=A0∪A+,A+=AA*问题:A={0,1},则A+表示的集合意义?方幂、正闭包、,是规则的非空有穷集合规则又称为重写规则,产生式或生成式,每个产生式为αβ或α::=β,α是某字母表A的正闭包A+的一个符号称为规则的左部;β是A*中的一个符号,称为规则的右部。α与β的区别?,是规则的非空又穷集合规则又称为重写规则,产生式或生成式,每个产生式为αβ或α::=β,α是某字母表A的正闭包A+的一个符号称为规则的左部;β是A*中的一个符号,称为规则的右部。α与β的区别?例句::<句子><主语><谓语><间接宾语><直接宾语><主语><代词>|<名词><谓语><动词><间接宾语><代词><直接宾语><冠词><名词><代词>He|me<名词>book<动词>gave<冠词>a|an|the例句:,可推出该例句。<句子>=><主语><谓语><间接宾语><直接宾语>=><代词><谓语><间接宾语><直接宾语>=>He<谓语><间接宾语><直接宾语>=>He<动词><间接宾语><直接宾语>=>Hegave<间接宾语><直接宾语>=>Hegave<代词><直接宾语>=>Hegaveme<直接宾语>=>Hegaveme<冠词><名词>=>Hegavemea<名词>=>=0;i=i+1;<程序>{<句子>}+<句子><声明语句>|<