清华大学：《编译原理》课程教学资源_第四章 文法和语言

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

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

本章内容 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 上下文无关文法的句型分析 有关文法实用中的一些说明

2 本章内容 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 上下文无关文法的句型分析 有关文法实用中的一些说明

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

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

文法即是生成方式描述语言的:语言中的 每个句子可以用严格定义的规则来构造 文法的定义 推导的概念 句型、句子和语言的定义

4 文法即是生成方式描述语言的：语言中的 每个句子可以用严格定义的规则来构造 文法的定义 推导的概念 句型、句子和语言的定义

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

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

文法的定义 例文法G=(VN,Vr,P,S) vN={S}V={01 P={s→0s1,S→01} s为开始符号

6 文法的定义 例 文法G=（VN，VT，P，S） VN = { S }, VT ={ 0, 1 } P={ S→0S1, S→01 } S为开始符号

例文法G=(VA,Vr,P,S) VN={标识符,字母,数字 v={abcr…xyz,01…9} P={→ →≤标识符> →≤标识符> →a →z →0 →9 S=

例 文法G=（VN，VT，P，S） VN ={标识符，字母，数字} VT ={a,b,c,…x,y,z,0,1,…,9} P={→ → → →a … →z →0 … →9 } S=

文法的写法元符号:→∷=|< 习惯大写字母表示非终结符小写字母表示终结符 (1)G:S→aAb (2)G[S]:A→ab A→ab A→aAb A→aAb A A→ε S→aSb (3)G[S]:A→ab|aAb S→aSb

8 文法的写法 元符号: → ∷= | 习惯 大写字母表示非终结符 小写字母表示终结符 (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→aSb

推导的定义 直接推导“→” a→β是文法G的产生式,若有v,w满足: v=γa8,w=yβδ,其中γ∈V,δ∈V 则称v直接推导到w,记作ⅴ→W 也称w直接归约到v 例:G:S→0S1,S→01 0s1→00S1l 00s11→000S11l 000S11l→000011ll S→0S1

9 推导的定义 直接推导“” α→β是文法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 0S1

推导 → (→) → (→) VAR BEGIN READI()END.→ VARA; BEGIN READ()END (标识符>→A) VARA; BEGIN READ()END VAR A; BEGIN READ(A) END. (→A)

10 推导 . (  . ) .  . (  ) VAR;BEGIN READ()END.  VAR A;BEGIN READ( ) END. ( A) VAR A;BEGIN READ( ) END.  VAR A;BEGIN READ( A) END. ( A)