当前位置: 首页 > >

【编译原理】第2章 文法和语言

发布时间:


2 文法和语言




目录
一、基本概念二、文法和语言的形式定义三、文法的类型四、上下文无关文法及其语法树五、上下文无关文法的句型分析六、有关文法使用中的一些说明章节小练


一、基本概念

语言由句子组成的集合,是由一组记号所构成的集合。

语言研究三方面:语法、 语义、 语用
语法:表示构成语言句子的各个记号之间的组合规律 一套规则
语义:表示按照各种表示方法所表示的各个记号的特定含义(各个记号和记号所表示的对象之间的关系) 语法、语义有区别
语用:表示在各个记号所出现的行为中,它们的来源、使用和影响
eg: 客人来了和来了客人,语义同,1定指,2非定指,即语用不同


有关定义和记号




语言的描述
描述一种语言:
?语言有穷(只含有有穷多个句子):可以将句子逐一列出来表示
?语言无穷:找出语言的有穷表示。


①生成方式 (文法):语言中的每个句子可以用严格定义的规则来构造。

②识别方式(自动机):用一个过程,当输入的一任意串属于语言时,该过程经有限次计算后就会停止并回答“是”,若不属于,要么能停止并回答“不是”,(要么永远继续下去)


二、文法和语言的形式定义

文法



推导

句型、句子、语言


文法的等价
若L(G1)=L(G2),则称文法G1和G2是等价的。
如:文法G1[A]:A→0R 与G2[S]:S→0S1 等价
? ? ? ? ? ? ? ? ? ? ? ? A→01 ? ? ? ? ? ? ? ? S→01
? ? ? ? ? ? ? ? ? ? ? ? R→A1


三、文法的类型

0型、1型、2型、3型共4种


0型文法产生的语言称为0型语言
0型文法短语文法)的能力相当于图灵机,可以表征任何递归可枚举集,而且任何0型语言都是递归可枚举的
1型文法或上下文有关文法( CSG )产生的语言称为1型语言或上下文有关语言(CSL)
1型文法(上下文有关文法):产生式的形式为α1Aα2→α1βα2,即只有A出现在α1和α2的上下文中时,才允许β取代A。其识别系统是线性界限自动机。
2型文法或上下文无关文法( CFL )产生的语言称为2型语言或上下文无关语言( CF L )
2型文法上下文无关文法、CFG):产生式的形式为A→β,β取代A时与A的上下文无关。其识别系统是不确定的下推自动机。
3型文法或正则(正规)文法( RG )产生的语言称为3型语言正则(正规)语言( RL )
3型文法正规文法、右线性文法):产生的语言是有穷自动机(FA)所接受的集合

四、上下文无关文法及其语法树

上下文无关文法的语法树用于描述上下文无关文法的句型推导的直观方法

给定文法G,对于G的任何句型都能构造与之关联的语法树(推导树)
这棵树满足下列4个条件:
①每个结点都有一个V中的符号作标记
②根的标记是开始符号S
③若一结点n至少有一个它自己除外的子孙,并且n有标记A,则A∈VN
④如果结点n的直接子孙,从左到右的次序是结点n1,n2,…,nk,其标记分别为A1,A2,…,Ak,那么A→A1A2,…,Ak一定是P中的一个产生式


二义文法
若一个文法存在某个句子对应两棵不同的语法树,则称这个文法是二义的。
或者,若一个文法存在某个句子有两个不同的最左(右)推导,则称这个文法是二义的。
产生某上下文无关语言的每一个文法都是二义的,则称此语言是先天二义的。
判定任给的一个上下文无关文法是否二义,或它是否产生一个先天二义的上下文无关语言,这两个问题是递归不可解的。但可以为无二义性寻找一组充分条件。


五、上下文无关文法的句型分析
句型分析就是识别一个符号串是否为某文法的句型,是某个推导的构造过程。
在语言的编译实现中,把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。
从左到右的分析算法,即总是从左到右地识别输入符号串,首先识别符号串中的最左符号,进而依次识别右边的一个符号。



句型分析


六、有关文法使用中的一些说明

有关文法的实用限制

文法中不得含有有害规则和多余规则
有害规则:形如U→U的产生式。会引起文法的二义性
多余规则:指文法中任何句子的推导都不会用到的规则
1)文法中某些非终结符不在任何规则的右部出现,该非终结符称为不可到达
2)文法中某些非终结符,由它不能推出终结符号串来,称为不可终止的


章节小练




bingo~ ? ? 人生没有白走的路,每一步都算数




友情链接: