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

基本概念
字母表、符号、符号串、闭包等
文法的定义
文法的分类
Chromsky 对文法的分类
文法和语言
推导、归约、句型、句子、语言
语法分析树和二义性
第二章文法和语言
文法和语言的定义
例句:int i = 0;
包含字母i, n, t, =, 0, ; ,
所有字母形成字母表;
符号串,如int
字母表:字母表∑是符号元素的非空有限集合。
符号(字符):字母表中的元素。
符号串(字符串):字母表中的符号所组成的任何有穷序列。
如字母表∑={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 book.
英语中的基本语法规则:
<句子> <主语> <谓语> <间接宾语> <直接宾语>
<主语> <代词>|<名词>
<谓语> <动词>
<间接宾语> <代词>
<直接宾语> <冠词> <名词>
<代词>  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 book
文法
文法和语言的定义
int i = 0;
i = i + 1;
<程序>{<句子>}+
<句子><声明语句>|<赋值语句>|……
<声明语句><数据类型> {<变量>[=<常量>]}+
<赋值语句><变量>=<表达式>
<变量>(a|…|z|A|…|Z|_)(a|…|z|A|…|Z|_|0|…|9)
<数据类型>int|char|…
……
文法包含的要素:
终极字符集:如int i
非终极字符集:如<程序>、<句子>