编译原理 第2讲(第三章).

编译原理

第三章 文法和语言为语言的语法描述寻求工具

工具要对程序设计语言给出精确无二义 的语法描述。(严谨、简洁、易读) 形式工具--“形式”是指这样的事实：语言 的所有规则只以什麽符号串能出现的方式 来陈述1

编译原理

本章内容1. 符号和符号串 2. 文法和语言的形式定义 3. 文法的类型 4. 上下文无关文法及其语法树 5. 上下文无关文法的句型分析 6. 有关文法实用中的一些说明

编译原理

语言漫谈自然语言：英语，汉语，法语。。。 形式语言：C,Pascal,Fortran等(简单说，文法严格的语言) 自然语言比形式语言复杂。为什么？想想翻译软件的质 量。 俄文的“心灵乐意，但肉身衰弱”(对应中文：心有余而 力不足；对应英文：The spirit is willing,but the flesh is weak),以机器翻译为英文时就变为“伏特加酒很不 错，但肉已腐败”(The vodka is good,but the meat is rotten)。3

编译原理

语言漫谈程序设计语言(形式语言):是一个记号系统，完整的 定义应包括的语法和语义2个方面。 语法：是指一组规则，用它可以形成和产生一个合适的 程序。(定义什么样的符号序列是合法的) 语义：自然语言中词语的意义，逻辑形式系统中符号的 解释。(定义什么样的符号序列是有含义的) 文法：是阐明语法的一个工具。这是形式语言理论的基 本概念之一。 ??:是阐明语义的工具。这是很困难的。

编译原理

符号和符号串先了解一些基本概念

编译原理

基本概念 符号：可以相互区别的记号(元素)。 字母表：符号(元素)的非空有穷集合。 符号串：由字母表中的符号组成的任何有穷序列称为 该字母表上的符号串。

例： (1)符号“a”组成的字母表记作{a} (2)符号“a”和“b”组成的字母表记作{a,b} a, b, aa, bb, ab, abb, aab,…都是字母表{a,b}上的符 号串。

编译原理

基本概念 符号串的长度：符号串中符号的个数。 如果符号串x中有m个符号，则长度表示 |x| = m 空串 :长度为0的符号串，它不同于Ф (表示空集)。

连接：连接符号串x、y,是把y的符号串写在x的符号 串之后得到的符号串；即x、y的连接为xy。方幂：符号串自身连接n次得到的符号串； 如：x的n次连接为x x … x (n个x),也记作xn

编译原理

基本概念 头、尾、固有头、固有尾； 例：符号串x=abc的 头： , a, b, abc; 尾： , c, bc, abc; 固有头： , a, b; 固有尾： , c, bc; 符号串集合：若集合中所有元素都是某字母表上的符 号串，则称之为该字母表上的符号串集合。

符号串集合乘积 例：符号串集合A={ab, aa},B= {ba, bb} 乘积AB={abba, abbb, aaba, aabb} AB={xy|x∈A, y∈B}8

编译原理

基本概念 语言(language) 某字母表Σ上的串的集

合，是Σ*的一个子集。

例如： Σ={a, b}

{a, aa, aaa, …} 或记作：{w|w∈Σ*且w=an, n≥1}{ab, aabb, aaabbb, …, anbn, …} 或记作：{w|w∈Σ*且w=anbn, n≥1} 都可称为一种语言9

编译原理

基本概念 闭包： Σ*称为Σ的闭包，若Σ* 表示为Σ上的所有有穷 长的串的集合，可表示为： Σ*= { }Σ1∪Σ2∪Σ3∪… 正闭包： Σ+称为Σ的闭包，可表示为： Σ+ = Σ*-{ }= ΣΣ* =Σ1∪Σ2∪Σ3∪… (其中用∪代表逻辑“或”运算)

例： Σ= {a, b} Σ*= { , a, b, aa, ab, ba, bb, aaa, aab, …} Σ+ = {a, b, aa, ab, ba, bb, aaa, aab, …}

编译原理

基本概念Σ={字母，数字，空格，标点符号[‘ @ , . 等]} Σ* 就是所有可能的符号串的集合。 比如： r5*e3!dfd

this is a dog. 英语：所谓英语就是那些符合词法(字典，构词法)和 语法，语义规则的在字母表Σ上的符号串集合。

编译原理

文法和语言的形式定义如何来描述一种语言？ 如果语言是有穷的(只含有有穷多个句子),可以 将句子逐一列出来表示 如果语言是无穷的，找出语言的有穷表示。语言的 有穷表示有两个途经： 生成方式 (文法):语言中的每个句子可以用 严格 定义的规则来构造。 识别方式(自动机):用一个过程，当输入的 一任意串属于语言时，该过程经有限次计算后就会停 止并回答“是”,若不属于，要么能停止并回答“不 是”,要么永远继续下去。

编译原理

文法与语言的关系

文法即是生成方式描述语言的

语言中的每个句子可以用严格定义的规 则来构造

编译原理

文法的定义

用大写字母表示A

用小写字母表示a

文法G定义为四元组(VN,VT,P,S ),其中 VN:非终结符号(或语法实体，或变量)集； VT:终结符号集； N:Nonterminal ; P: 规则的集合； T:terminal VN,VT和P是 非空有穷集。 S:称作识别符号或开始符号的一个非终结符，它至少 要在一条产生式中作为左部出现。 VN和VT不含公共的元素，即VN ∩ VT = φ 用V表示VN ∪ VT ,称为文法G的字母表或字汇表。 规则，也称重写规则、产生式或生成式，是形如 → 或 ∷= 的( , )有序对，其中 是字母表V的正闭包V+ 中的一个符号， 是V*中的一个符号。 称为规则的左 部， 称作规则的右部。 14

编译原理

文法的例子(1)例3.1 文法G=(VN,VT,P,S) VN = { S }, VT ={ 0, 1 } P={ S→0S1, S→01 } S为开始符号

编译原理

文法的例子(2)例3.2 文法G=(VN,VT,P,S) VN ={标识符，字母，数字} VT ={a,b,c,…x,y,z,0,1,…,9} P={<标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→a … <字母>→z <数字>→0 … <数字>→9 } S=<标识符>16

编译原理

文法的写法元符号: → ∷= | < > 习惯 大写字母表示非终结符 小写字母表示终结符

(1) G: S→aAb A→ab A→aAb A→ε

(2) G[S]: A→ab A→aAb A→ε S→aSb(3) G[S]: A→ab |aAb |ε S→aSb17

编译原理

推导的定义(1)直接推导“ ” α→β是文法G的产生式，若有v,w满足： v=γαδ,w= γβδ, 其中γ∈V*,δ∈V* 则称v直接推导到w,记作 v w. 也称w直接归约到v 例：G: S→0S1, S→01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S118

编译原理

推导例子<程序> <分程序>. (<程序> <分程序>. ) <分程序>. <变量说明部分> <语句>. (<分程序> <变量说明部分> <语句>) VAR<标识符>;BEGIN READ(<标识符>)END. VAR A;BEGIN READ(<标识符> ) END. (<标识符> A) VAR A;BEGIN READ(<标识符> ) END. VAR A;BEGIN READ( A) END. (<标识符> A)

编译原理

推导的定义(2)若存在v =w0 w1 ... wn=w,(n>0) 则记为v =>+ w,称作v推导出w,或w归约到v 若有v =>+ w 或 v=w, 则记为v =>* w

编译原理

推导例子例：G: S→0S1, S→01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S =>+ 00001111 S =>* S 00S11 =>* 00S11

本文来源：https://www.bwwdw.com/article/k7g1.html