02第2章 文法和语言

02第2章 文法和语言

ID:20528857

大小:1.98 MB

页数:82页

时间:2018-10-12

02第2章 文法和语言_第1页
02第2章 文法和语言_第2页
02第2章 文法和语言_第3页
02第2章 文法和语言_第4页
02第2章 文法和语言_第5页
资源描述:

《02第2章 文法和语言》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第二章文法和语言2021/7/51内容提要字母表与符号串文法(定义,推导,句型与句子)语言递归规则与递归文法语法树(短语、简单短语和句柄)语法树与文法的二义性2021/7/522.1字母表与符号串字母表符号串符号串及集合的运算2021/7/532.1.1字母表字母表是符号的非空有穷集合。例如:1.机器语言字母表:由符号“0”和“1”组成的字母表,∑={0,1}2.ASCII字符集3.Pascal字母表为:∑={AZ,az,09,+,-,*,/,<,=,>,:,',',;,.,,(,),{,},[,]}……2021/

2、7/542.1.2符号串定义:(1)ε是∑上的一个符号串。(2)若x是∑上的符号串,而a是∑的元素,则xa是∑上的符号串。(3)y是∑上的符号串,当且仅当它由(1)和(2)导出。即:符号串由字母表中的符号所组成的任何有穷序列。2021/7/552.1.3符号串及其集合的运算1.符号串的长度:指符号串x中所含符号的个数,记为

3、x

4、。如

5、xyz

6、=3,

7、123+321

8、=7,而

9、ε

10、=02.符号串相等:若x、y是字母表∑上的两个符号串,当且仅当组成x的各符号与组成y的各符号依次相等时,则符号串x与符号串y相等,记作x=y。如:

11、当x=abbc,y=abbc时,则x=y;而当x=ab,y=ba时,则x≠y3.符号串的前缀:指从符号串x的末尾删除0或多个符号后得到的符号串,如u、uni、university都是university的前缀。4.符号串的后缀:指从符号串x的开头删除0或多个符号后得到的符号串,如ty、sity、university都是university的后缀。2021/7/565.符号串的子串:指从符号串x的开头和末尾删除0或多个符号后得到的符号串,如ver是university的子串,符号串的前缀、后缀都是它的子串。6.符号串的连接:

12、若x、y是两个符号串,则xy表示连接,是将符号串y连接在符号串x的后面。若x、y是字母表∑上的两个符号串,则xy也是字母表∑上的符号串。例如:x=ab,y=ba,则xy=abba注意:连接没有交换律,即xy≠yx而对于空串ε有εx=xε=x2021/7/577.集合的乘积运算:令A、B为两个符号串集合,A和B的乘积AB定义为:AB={xy

13、x∈A,y∈B}例如:A={a,b}B={c,d},则AB={ac,ad,bc,bd}对于空集合有{ε}有:{ε}A=A{ε}=A8.符号串的幂运算:若x是符号串,则x的幂运算定义为:x

14、0=ε,x1=x,x2=xx,…,xn=xx…x=xxn-1=xn-1x,其中n>0例如:x=abc,x0=ε,x1=abc,x2=abcabc,…2021/7/589.集合的幂运算:设A为符号串集合,则A的幂运算定义为:A0={ε}A1=AA2=AA……An=AA…A=AAn-1=An-1A,其中n>0例如:A={a,b},则A0={ε}A1={a,b}A2={aa,ab,ba,bb}2021/7/5910.集合的正闭包和集合的闭包:设A为一个集合,则集合A的正闭包用A+表示,定义为:A+=A1∪A2∪…∪An∪…集合A

15、的闭包用A*表示,定义为:A*=A0∪A+例如:A=={a,b},则A+={a,b,aa,ab,ba,bb,aaa,aab,…}A*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}2021/7/5102.2文法文法是描述语言语法结构的形式规则。文法需要说明语言的语法成分,句子中的符号以及语法结构。例:能够描述句子“themonkeyatethebanana”的文法:<句子>→<主语><谓语><主语>→<冠词><名词><冠词>→<谓语>→<动词><直接宾语><动词>→<直接宾语>→<冠词><名

16、词><名词>→<名词>→该例中语法成分,句子中的符号,语法结构是什么?2021/7/5112.2.1文法形式定义文法的形式定义:文法可表示为一个四元组G=(Vn,Vt,P,Z)Vn:非空有穷集合,其元素为非终结符号。Vt:非空有穷集合,其元素为终结符号且Vt∩Vn=Ф,V=Vt∪Vn是该文法的字母表。P:非空有穷集合,其元素为产生式或规则。产生式的形式为:α→β或α::=β;α是产生式左部且不能为空,β是产生式右部,并且α、β∈(Vt∪Vn)*,“→”或“::=”含义相同,表示“定义为”或“

17、由……组成”。Z:Vn中一个特殊的非终结符号,称为文法的识别符号或开始符号。必须至少在某个产生式的左部出现一次。2021/7/5122.2.1文法形式定义按文法形式定义表示“themonkeyatethebanana”文法。解:根据文法的形式定义,文法G1=(Vn,Vt,P,Z)非终结符号集合:Vn={

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。