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

?基本概念字母表、符号、符号串、闭包等?文法的定义?文法的分类Chromsky 对文法的分类?文法和语言推导、归约、句型、句子、语言? 文法和语言的定义例句:int i = 0;包含字母i, n, t, =, 0, ; ,所有字母形成字母表;符号串, 字母表:字母表∑是符号元素的非空有限集合。 符号(字符):字母表中的元素。 符号串(字符串):字母表中的符号所组成的任何有穷序列。如字母表∑={a,b},则a,b是字母表∑中的元素,a,b,aa,ab,…都是符号串。空符号串:不含任何符号的符号串,用ε表示。字母表,符号, 文法和语言的定义? 符号串x和y的连接:指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个)? 符号串集合A的方幂: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 gave me a :<句子> ?<主语> <谓语> <间接宾语> <直接宾语><主语> ?<代词>|<名词><谓语> ?<动词><间接宾语> ?<代词><直接宾语> ?<冠词> <名词><代词> ? He|me<名词> ? book<动词> ? gave<冠词> ? a|an|the例句:He gave me a book. 根据上述语法规则对例句进行分析,可推出该例句。<句子> => <主语> <谓语> <间接宾语> <直接宾语>=> <代词> <谓语> <间接宾语> <直接宾语> => He <谓语> <间接宾语> <直接宾语> => He <动词> <间接宾语> <直接宾语> => He gave <间接宾语> <直接宾语> => He gave <代词> <直接宾语> => He gave me <直接宾语> => He gave me <冠词> <名词> => He gave me a <名词> => He gave me a 文法和语言的定义int i = 0;i = i + 1;<程序>?{<句子>}+<句子>?<声明语句>|<赋值语句>|……<声明语句>?<数据类型> {<变量>[=<常量>]}+<赋值语句>?<变量>=<表达式><变量>?(a|…|z|A|…|Z|_)(a|…|z|A|…|Z|_|0|…|9)<数据类型>?int|char|………文法包含的要素:终极字符集:如int i非终极字符集:如<程序>、<句子>产生