编译原理文法和语言.ppt

《编译原理文法和语言.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理§3.1符号和符号串§3.2文法和语言的形式定义§3.3文法的分类§3.4语法树和二义性§3.5有关文法的实用限制第三章文法和语言语言的组成语言：句子的集合句子：多个单词按一定规则组成单词：多个字符按一定规则组成程序设计语言编程语言程序的语句集合语句：多个单词按语法规则组成单词：多个字符按词法规则组成程序设计语言和自然语言的组成结构语言定义的方法枚举方法一个语言中的句子有限（非形式化描述）形式化描述方法（文法）一组数学符号（形式化描述）产生语言中全部句子的有限个规则自动机方法识别某字母表上所有符号串是否是该语言句子的一种装置（算法或过程）产生的观点识别

2、的观点§3.1符号和符号串一、字母表与符号1.字母表：元素的非空有限集合例：={a，b，c}={begin,end,if,then,else}2.符号：字母表中的元素例：a，b，cbegin,end,if,then,else§3.1符号和符号串字母表辨析：例：1={aa，bb，cc}2={a,a’,b,b’}3={a，b，a}4={}解析：1和2是字母表，体现了字母表的整体性和可辨认性；3中有相同的符号；4也不是字母表，因为要求字母表非空。§3.1符号和符号串一、字母表与符号3.符号串：由字母表中的符号组成的任何有穷序列例：Σ={a,b}ε,a,

3、b,aa,ab,aabba…都是上的符号串符号串的长度：符号串x中符号的数目,

4、x

5、=m空符号串：无任何符号的符号串,记为ε,

6、ε

7、=0§3.1符号和符号串一、字母表与符号4.符号串的头和尾：对于符号串z=xy，x是z的头，y是z的尾。如果x非空，那么y是固有尾；如果y非空，那么x是固有头。例：设z=abc,z的头是ε，a，ab，abc，固有头是ε，a，ab；z的尾是ε，c，bc，abc，固有尾是ε，c，bc。§3.1符号和符号串二、字符串和字符串集合的运算1.字符串的连接：设x和y是两个字符串，则xy被称为符号串x与y连接。εx=xε=x(xy)z=x(y

8、z)

9、xy

10、=

11、x

12、+

13、y

14、例：x=ST，y=abu，则xy=STabu，可看出

15、x

16、=2，

17、y

18、=3，

19、xy

20、=5§3.1符号和符号串2.字符串x的方幂：即把x重复写n次，记为z=xn。例：若x=AB则:x0=εx1=ABx2=ABABx3=ABABABxn=xxn-1=xn-1x(n>0)二、字符串和字符串集合的运算对于m,n≥0xmxn=xm+n(xm)n=xmn§3.1符号和符号串3.字符串A与B的乘积：设A和B为符号串集合，则A与B的乘积定义为AB=xy

21、xA且yB例：若集合A=ab,cde集合B=0,1则AB=ab0,ab1,cd

22、e0,cde1二、字符串和字符串集合的运算§3.1符号和符号串4.字符串集合的正闭包：设∑为字母表，则∑+=∑1∪∑2∪…∪∑n，n>1例：若∑=0,1则∑+=0,1,00,01,10,11,000,001,…二、字符串和字符串集合的运算注：指定字母表∑后，可用∑n表示∑上所有长度为n的串的集合。§3.1符号和符号串5.字符串集合的闭包(星闭包)：设∑为字母表，则∑*=∑0∪∑1∪∑2∪…∪∑n,n≥0∑*可表示∑上所有有穷长的串的集合；∑*=∑0∪∑+∑+=∑∑*=∑*∑∑*=∑+∪{ε}，∑+=∑*-{ε}例：若∑=0,1,则∑*=ε,0,

23、1,00,01,10,11,…二、字符串和字符串集合的运算若A为某语言的基本字符集A＝{a,b,……z,0,1,……,9,+,－,×,_/,(,),=……}B为单词集B={begin,end,if,then,…,<标识符>,<常量>,……}则BA*。语言的句子是定义在B上的符号串。若令C为句子集合，则CB*,程序C为什么对符号、符号串、符号串集合以及它们的运算感兴趣？§3.2文法和语言的形式定义一、文法的直观理解1.什么是文法文法是对语言结构的定义与描述，即从形式上描述和规定语言结构，也称为语法。例：句子：“我是大学生”。该句子的结构（称为语法结构）是

24、由它的语法决定的。如何定义该句子的语法结构呢？——语法规则一、文法的直观理解2.语法规则通过建立一组规则（产生式），来描述句子的语法结构。规定用“::=”表示“由…组成”或“定义为…”。<句子>::=<主语><谓语><主语>::=<代词>

25、<名词><代词>::=你

26、我

27、他<名词>::=王民

28、大学生

29、工人

30、英语<谓语>::=<动词><直接宾语><动词>::=是

31、学习<直接宾语>::=<代词>

32、<名词>§3.2文法和语言的形式定义一、文法的直观理解3.由产生式推导句子推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去

33、进行推导。§3.2文法和语言的形式定义