当前位置：文档之家 › 第二章-文法和语言的基本知识002

第二章-文法和语言的基本知识002

  • 格式：pptx
  • 大小：74.02 KB
  • 文档页数：11

下载文档原格式

  / 11

合集下载

z第二章 文法和语言

z第二章 文法和语言

例子：考虑一个文法
G＝({a, b}, {S}, S，P） 其中 P：SaSb ab。试推导其语言。 SaSb aaSbb a3Sb3 …… an-1Sbn-1 anbn 其语言为：L(G)={anbn |n>=1}
说明：
★ 只用一个产生式并不足以定义一个语法范 畴,在绝大部分情况下都需要用好几个产生式, 特别是需要含有递归的产生式(产生式左部的 符号直接在右部出现). ★ VN∩VT=Φ:即文法中的任意一个符号要么 为非终结符号,要么为终结符号.
A A1 A 2 A 3 ......

定理2.1 若A是符号串集合，则A*=(A*)* 。
证明 显然 A* (A*)* , 现证 (A*)* A* 任给符号串 x∈(A*)*，则存在n，使得 x∈(A*)n， x 必存在n个子串x1 ,…,xn ， 使得x= x1…xn ，且 xi∈A* (i=1,…,n)。 由xi∈A* ，必存在整数pi ,使得xi∈Api ， 令 n
句型、句子和语言
* ，其中 S 是开始符号， ∈ V* ，则称 若S 为文法G的句型。 * 特别地，若 S ，且 ∈ VT* ，则称 为 G 的 句子。 文法G所定义的语言，记作：
L(G)={|∈VT*，且S}
*
同一句型有不同的推导序列
设有文法G[N1]: N1→N N →ND|D D→0|1|2 则句子12可由三种不同的推导序列推导出来： (1) N1 N ND N2 D2 12 (2) N1 N ND DD 1D 12 可见，同一句型（句子）可以通过不同的推导 序列推导出来。

|x|= 2 |y|= 3 |z|= 5
|xy|=|x|+|y|

编译原理 第02章_文法和语言的基本知识

编译原理 第02章_文法和语言的基本知识

2.3.2 语言的形式定义
S→01 | 0S1
S 0S100S11…0n-1S1n-10n1n * 即S0n1n
可见，此文法定义的语言为 L(G[S])={ 0n1n | n≥1}
2.3.2 语言的形式定义
例4 设有文法G[S]：S→0S | 1S |ε 该文法所定义的语言是什么？
由该文法所确定的语言为 L(G[S])={ε, 0, 1, 00, 01, 10, 11, …} ={ x | x∈{0,1}* }
2.3.1 文法的形式定义
2. 文法
规则的非空有穷集合，通常表示 成四元组 G={VN,VT, P, S } VN是规则中非终结符号的集合。 VT是规则中终结符号的集合。
P 是文法规则的集合。
2.3.1 文法的形式定义
S 是一个非终结符号，称为文法 的开始符号或文法的识别符号，它至 少要在一条规则中作为左部出现。由 它开始，识别出我们所定义的语言。 由文法定义可知，文法是对语言 结构的定义和描述，文法四大要素中 关键是规则的集合。
2.3.2 语言的形式定义
广义推导
* 0n表示从0出发，经0步或若干步， 可推导出n。 * 意味着 + 或者 = 。 也就是说0 n 0 n 0 n
对上例 E→E+T | T T→T*F | F F→(E) | i *E * i+i*i 我们有： E E
2.3.2 语言的形式定义
4. 句型和句子
设有文法G[S]（S是文法G的开始符号） * 如果S x, x ∈(V ∪V )* 则称符号串x
N T
为文法G[S]的句型。 * x, x ∈V * 则称符号串x为文法 如果S T G[S]的句子。
2.3.2 语言的形式定义

02第2章-文法和语言--

02第2章-文法和语言--
其中“=>”表示一步推导, 上述推 导过程表示经过两步推导，从<句 子>可推导出<冠词><名词><谓语>。
2014-1-4
18
2.3 推导
直接推导的定义 (1) →是文法G=(VN ,VT ,P,S)的规
V=，W＝
则，和是(VN ∪ VT )*中的任意符号,若 有符号串V,W满足：
2014-1-4 6
2.1.3 符号串及其集合的运算2
5.符号串的子串：指从符号串x的开头和末尾删除0或多个符号 后得到的符号串，如ver是university的子串, 符号串的前缀、 后缀都是它的子串。 6.符号串的连接：若x、y是两个符号串，则xy表示连接，是将 符号串y连接在符号串x的后面。若x、y是字母表∑上的两个符 号串，则xy也是字母表∑上的符号串。 例如： x = ab，y = ba，则 xy = abba 注意：连接没有交换率，即 xy ≠ yx
1.符号串的长度：指符号串x中所含符号的个数，记为|x|。 如|xyz|=3，|123+321|=7，而|ε|=0 2.符号串相等：若x、y是字母表∑上的两个符号串，当且仅当 组成x的各符号与组成y的各符号依次相等时，则符号串x与符 号串y相等，记作x=y。
如： 当x=abbc，y=abbc时，则x=y；
α E E+T T+T F+T a+T a+F
β E+T T+T F+T a+T a+F a+a
产生式 EE+T ET TF Fa TF Fa
a+ a+
+T +T +T

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

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

2.1 文法和语言的定义
字符串连接、字符串长度
定义2.4 符号串x和y的连接：指x和y的符号按先后顺序排列 在一起组成的新的符号串，用xy表示。 例：若∑={a,b}, x=ab, y=ba, 则xy=abba, yx=baab。 注意：（1）xy≠yx； （2）εx=xε=x。
定义2.5 符号串的长度：指符号串中符号的个数。
2.1 文法和语言的定义
文法
什么是文法
文法是定义或描述语法结构的一组形式规则，是规则的非空有穷集合 规则又称为重写规则，产生式或生成式，每个产生式为αβ或 α::=β， α是某字母表A的正闭包A+的一个符号称为规则的左部； β是A*中的一 个符号，称为规则的右部。
α与β的区别？
2.1 文法和语言的定义
文法 定义2.11 符号串的推导与归约：已给文法G={VN, VT, P, S}， V=VN∪VT，令x,y,α,β ∈V*，且αβ∈P，则xαy能直接推导出xβy ，或者xβy 直接规约到xαy ，记作xαyxβy。 “”读作直接推导
例2.1 G=({ N }, { 0,1 },{ N0N, N1N, N0, N1 }, N)中，存
2.1 文法和语言的定义
当语言包含的句子无限时，如何构造文法？
2.1 文法和语言的定义
根据语言构造文法 例2.3 构造文法G，使其描述的语言为正奇数集合。 分析：正奇数要求，要么是一位奇数数字，要么是以奇数数字结尾的十进 制数字。 令G={VN,VT,P,<正奇数>} VT={0,1,2,3,4,5,6,7,8,9} P: <一位奇数>1|3|5|7|9 <正奇数><一位奇数>|<数字串><一位奇数> <数字串><数字串><数字>|<数字> <数字> <一位奇数>|0|2|4|6|8 VN={<正奇数>,<一位奇数>,<数字串>,<数字>}

编译原理第二章文法和语言

编译原理第二章文法和语言

语言的语法结构
总结词
语言的语法结构是语言形成和发展的核心要素，决定 了语言的表达方式和意义。
详细描述
语言的语法结构是指语言的组织规律和规则，包括词 法、句法、语义等方面的规则。词法规定了词汇的构 成和变化规则，如名词、动词、形容词等词类的划分 ；句法规定了句子结构的规则，如主语、谓语、宾语 等句子的成分及其排列顺序；语义则涉及到词汇和句 子的意义和解释。语言的语法结构是语言理解和生成 的基础，也是语言演变和发展的关键因素。
文法和语言的应用前景
1 2
人工智能领域
文法和语言是人工智能领域的重要基础，可用于 自然语言处理、机器翻译、语音识别等技术的研 究和应用。
计算机科学教育
文法和语言是计算机科学专业的重要课程之一， 对于培养计算机科学人才具有重要意义。
3
软件工程领域
文法和语言可用于软件工程领域中的编译器设计 和开发，提高软件开发的效率和可靠性。
05
文法和语言的未来发展
文法和语言的研究方向
形式语言理论
深入研究形式语言的基本理论， 包括语法、语义和语用等方面， 为自然语言处理和人工智能等领 域提供理论基础。
自然语言处理
结合自然语言处理技术，研究自 然语言的语法、语义和语用规律， 提高自然语言处理的准确性和效 率。
计算语言学
将计算语言学与形式语言理论相 结合，研究语言处理算法和模型， 为机器翻译、语音识别等领域提 供技术支持。
文法和语言的发展趋势
深度学习与文法和语言的结合
01
随着深度学习技术的发展，文法和语言的研究将更加注重与深
度学习的结合，以提高语言处理的性能和效率。
跨媒体语言处理
02
随着多媒体数据的普及，文法和语言的研究将逐渐扩展到跨媒

编译原理第二章 文法和语言资料

编译原理第二章 文法和语言资料

第二章文法和语言本章讲述目前广泛使用的上下文无关文法。

即用上下文无关文法作为程序设计语言语法的描述工具。

阐明语法的一个工具是文法。

本章将介绍文法和语言的概念。

本章重点：上下文无关文法及其句型分析中的有关问题。

第一节文法的直观概念当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。

以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明（或者定义）句子的组成结构，比如：“我是大学生”。

是汉语的一个句子。

汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用EBNF来表示这种句子的构成规则：〈句子〉∷＝〈主语〉〈谓语〉〈主语〉∷＝〈代词〉|〈名词〉〈代词〉∷＝我|你|他〈名词〉∷＝王明|大学生|工人|英语〈谓语〉∷＝〈动词〉〈直接宾语〉〈动词〉∷＝是|学习〈直接宾语〉∷＝〈代词〉|〈名词〉“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。

这些规则成为我们判别句子结构合法与否的依据。

一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子。

我们开始去找∷＝左端的带有〈句子〉的规则并把它表示成∷＝右端的符号串，这个动作表示成：〈句子〉⇒〈主语〉〈谓语〉，然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应的规则∷＝右端代替之。

比如，选取了〈主语〉,并采用规则〈主语〉∷＝〈代词〉，那么得到：〈主语〉〈谓语〉⇒〈代词〉〈谓语〉，重复做下去，我们得到句子：“我是大学生”的全部动作过程是：〈句子〉⇒〈主语〉〈谓语〉⇒〈代词〉〈谓语〉⇒我〈谓语〉⇒我〈动词〉〈直接宾语〉⇒我是〈直接宾语〉⇒我是〈名词〉⇒我是大学生符号⇒的含义是，使用一条规则，代替⇒左边的某个符号，产生⇒右端的符号串。

显然，按照上述办法，不仅生成“我是大学生”这样的句子，还可以生成“王明是大学生”，“王明学习英语”，“我学习英语”，“他学习英语”，“你是工人”，“你学习王明”等几十个句子。

第二章 文法和语言基本知识

{AZ, az, 09, +, -, *, /, <, =, >,:, ‘,’, ; ，.，!, ~,%,&, ¦,^, (, ), {, },[, ] }
2.2 字母表和符号串的基本概念
2.2.1 字母表和符号串
1、字母表：元素的非空有穷集合。 2、符号：字母表∑中的元素。 3、符号串（字） • 符号串：字母表∑中的符号所构成的一个有穷序列。 • 空字ε ：不包含任何符号的序列。 • φ ：不含任何元素的空集{}
2.2 字母表和符号串的基本概念
2.2.2 符号串的运算
1. 符号串的连接
εy=yε=y
2. 集合的乘积
{ε}A=A{ε}=A
3. 符号串的幂运算 y0=ε y1=y y2=yy
4. 集合的幂运算 A0={ε} A1=A A2=AA
5. 集合A的闭包A*与正闭包A+
• ∑的闭包∑*： ∑上所有符号串的全体
→表示生成或定义为
• 语言的语法结构用一组规则来表示。 • 终结符号、非终结符号
例 赋值语句→变量=表达式
2. 文法
文法是规则的非空有穷集合，通常表示成四元式
G= （VT，VN , S, P ），其中： VT是一个非空有穷终结符号集合； VN是一个非空有穷的非终结符号集合，
且VT∩VN＝Φ； P是一个产生式的非空有穷集合，每个产生式的形式是 A (或A ::＝ )，其中 A∈VN， ∈（VT∪VN）*。 S VN ，称为开始符号，S必须至少在某个产生式的左部 出现一次 。
仅含终结符号的句型是一个句子。
5、语言 由文法G产生的所有句子所组成的集合就是语言L(G)。
L(G)＝{ |S + 且 ∈VT*}
注： L(G)是VT*的子集

编译原理：文法与语言的基本知识

2
符号与符号串
– 例1： 1＝{0,1} 1是二进制数的字母表 2＝{a,b…….z} 2是英文小写字母 3＝{A….Z,0….9,+,-,*,/,.,(,),=,$,’,:} 3是FORTRAN4语言的字母表
注意：符号可能是字符的组合
– 如： 5＝ {ASCII码} 则<=为一个符号 再如： pascal语言的:＝ C语言的&&等等
若<U> +………<U>
称为右递归
3. 对文法G1、G2，如L(G1)=L(G2)
称文法 G1、G2等价
19
短语与句柄
• 2.3.3 短语与句柄
–定义7：设G[<S>]是一个文法，并设w=xuy 是该 文法的一个句型。若<S>*x<U>y且<U>+u， 则称u为句型w=xuy对非终结符<U>的一个短语。 若<S>*x<U>y且<U>u，则称u为句型w=xuy 相对于非终结符<U>的一个简单(直接）短语。 任何一个句型的最左简单短语称为柄短语（句 柄）。
– A0＝{}
An=AAn-1 (n>0)
– A*= A0∪ A1∪A2∪…∪An ∪……
称为A的闭包
– A＋= A1∪A2∪…∪An ∪……
称为A的正闭包
7
• 由定义可知：A+=AA*=A*A • 例3：令A= 1＝{0,1}
– A*={，0，1，00，10，01，11…….} – A+= {0，1，00，10，01，11…….} – 令A= 3 则任一FORTRAN4语言所编
14
直接推导与推导

编译原理第二章_文法与语言

表示A上所有有穷长串的集合 例如：A={ab，c}，AA={…… }， AAA={…… } A+ = A* A = AA*
（8）符号串集合的自反闭包
设符号串集合为A，则A的自反闭包记为A* ，定义为： A* = A0 ∪ A1 ∪ A2∪… ∪ An
即A* = A0 ∪ A+ = {ε} ∪ A+ 例如： A= {a,b}，则 A*={ε, a, b, aa, ab, ba, bb, aaa, …… }
AB={xy|x∈A,y∈B} 如：若A={ab,c}, B={d,efg},则AB={abd,abefg,cd,cefg} 特别地，有：{ε}A=A{ε}=A
• 空集φ 表示不含任何元素的空集{ }。 有： φA=A φ= φ
<注>请区别： ε，{}，{ε}三种表示方法的含义
12
（5） 符号串的方幂
a1 an 表示：从a1出发经过一步或若干步，可推导出an 。
定义2.5 长度为n（n≥0）的推导 a1 an 表示：从a1出发经过0步（ a1 ＝an ）或若干步，可推导
出an 。
22
2.2.3 句型、句子、语言
1.句型：设G[S]是一个文法，S是它的开始符号，若S α , 则称α是文法G[S]的句型。
5
（1） <句子>::= <主语> <谓语>
推导过程(3/5)
（2） <主语>::= <代词> | <名词> （3） <代词>::= 我 | 你 | 他 （4） <名词>::=王明| 大学生|工人|英语
（5） <谓语>::=<动词> <直接宾语>

第2章 文法和语言


（2）符号串的连接
符号串x和符号串y的连接，是把y的所有符号相继写在x的符号之后得
到的符号串，记为xy。 例如： x=ab，y=cd 则 xy=abcd ，yx=cdab。aɛ= ɛa=a。
（3）符号串的方幂
符号串a自身连接n次得到的符号串称为a的n次方幂。记为an 。 例如： a1=a， a2=aa，a0=ɛ。
2.3 Chomsky文法分类
四种文法之间的逐渐包含关系 0型文法 1型文法
2型文法
3型文法 各文法与自动机的对应关系
2.4 文法和语言的二义性
（1）文法的二义性
若文法G的一个句子能找到两种不同的最左推导(或最右推导)，或者
存在两棵不同的语法分析树，则称这个句子是二义性的。一个文法如果
包含二义性的句子，则这个文法是二义文法，否则是无二义文法。
对于句子，i+i*i存在着两种最左推导：
E E E i E i E *E i i*E i i*i E E *E E E *E i E *E i i*E i i*i
并且它存在两棵不同的语法分析树，因此该文法是二义的。
2.4 文法和语言的二义性
【例2.14】 文法G[S]为：
S→if B S
S→if B S else S
S→A 其中，VN = {B,S,A}，VT = {if , else}，则句型if B if B S else S所对应的两 棵不同语法树，因此该文法也是二义的。
2.4 文法和语言的二义性
（4）为什么要避免文法产生二义性？
A →X1X2 …Xk∈P

2、推导和语法分析树
【例2.4】 文法G： S→aAcB|Bd A→AaB|c B→bScA|b
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2015年2月15日
编译原理
形式语言的表示方法
• 有穷语言可以用穷举法枚举全部句子。例如设有字母表： A={a,b,c}，则 • L1={a，b，c} • L2={a，aa，ab，ac} • L3={c，cc} • 均表示字母表上一个形式语言。由于这三个语言均是有限符号串 的集合，因此可用枚举法来表示。
A1 A A A2 A A3 A
, xxx,xxy,xyx,xyy, ……} A*＝ ？ {ε,0x,y,1 xx,xy,yx,yy 2 3
2015年2月15日
编译原理
Σ的闭包* 表示上的一切符号串（包括ε）组成的集合 Σ的正闭包+ 表示上的除ε外的所有符号串组成的集合
{ } ...... * * 2 3 { } ......
2015年2月15日
编译原理
语言是由句子组成的集合，是由一组符号所构成的集合
字母表上的一个语言是上的一些符号串的集合 字母表上的每个语言是*的一个子集 例如：字母表Σ ={a,b} ,Σ *={ε ,a,b,aa,ab,ba,bb,aaa,aab,…}
集合{ab,aabb,aaabbb,…,anbn,…} 或表示为{w|w∈Σ*且w=anbn,n≥1}为字母表上的一个语言 集合{a,aa,aaa,…} 或表示为{w|w∈Σ*且w=an,n≥1} 为字母表 上的一个语言
2015年2月15日
编译原理
符号串集合的幂运算 有符号串集合A，定义A0 ={ε}, A1=A, A2=AA, A3=AAA,…… An＝An-1A=AAn-1 ，n>0
例如，A＝{0,1}，则 A0= {ε} A1= {0,1} A2= {00,01,10,11} A3= {000,001,010,011,100,101,110,111}
2015年2月15日 编译原理
2.3文法和语言的形式定义
2.3.1形式语言的概念 字母表上的符号按照某种规则构成的所有符号串的集 合可定义为一个形式语言 • 对每一个具体语言，都有语法和语义两个方面，形式语 言是指不考虑语言的具体意义。例如：C语言是其基本符 号字母表上的符号串的集合，而每个C语言程序是基本符 号的符号串集合的子集。 • 如果一个语言中含有无穷个句子，则称该语言是无穷的， 否则就是有穷的。
2015年2月15日
编译原理
形式语言的表示方法
• 对无穷语言来说，需要解决该语言的有穷表示问题。并 不是所有语言都是有穷集，例如：设字母表∑={0，1}， 则Σ+=Σ1∪Σ2∪Σ3∪…={0，1，00，01，10，11，000， 001，…}
• 它是0和1构成的所有可能的符号串的集合，无法用枚举 法来描述。我们需要设计规则来描述无穷集合的语言。 • A →0 • A →1 • A →A0 • A →A1 • 这就是用文法来描述语言，它描述了无穷集合的语言。
2015年2月15日 编译原理
文法和语言的形式定义
文法是对语言结构的定义与描述。（或称为“语法”）。
<赋值语句>::=<标识符>“=”<表达式> <表达式>::=<表达式>“+”<表达式> | <表达式>“*”<表达式> <表达式>::=“(”<表达式>“)” | <标识符> | <整数> | <实数>
* 2
例：Σ ={a,b}…} Σ +={a,b,aa,ab,ba,bb,aaa,aab,…}
2015年2月15日 编译原理
为什么对符号、符号串、符号串集合以及它们的运算感兴趣？ 若A为某语言的字母表 A＝{a,b,…,0,1,…,9, +,－,×,_/, ( , ), =… if, else,for...} B为单词集 B ={if, else,for,……,<标识符>,<常量>,……} 则B A* 。 语言的句子是定义在B上的符号串。 若令C为句子集合，则C B * , 程序 C
2015年2月15日
编译原理
第二章 文法和语言的基本知识
本章主要介绍形式语言理论中的一些最 基本的概念和基础知识，它是学习以后各章 节的基础。
2015年2月15日
编译原理
符号串集合的乘积 设A、B为符号串集合，则A和B的乘积定义为：AB＝{ xy |x∈A,y∈B}
例如，A＝{a,b}，B={c,d}
则AB=
{ac,ad,bc,bd}
2015年2月15日
编译原理
符号串集合的闭包运算
设A是符号串集合，定义 A＋＝ A1 ∪ A2 ∪ A3 ∪……∪ An ∪…… 称为集合A的正闭包。 A*＝ A0 ∪A＋ 称为集合A的闭包。 例：A={x,y} A＋＝？ {x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, ……}