《程序设计语言与编译》课程PPT教学课件（高职）第十讲 程序设计语言和编译程序

第四章程序设计语音和编译程序 第一节上下文无关文法 文法 文法是描述语言的语法结构的形式规则, 必须准确易于理解,囯描述能力强

第四章 程序设计语言和编译程序 第一节 上下文无关文法 一. 文法 文法是描述语言的语法结构的形式规则, 必须准确,易于理解,且描述能力强

1.文法的形式定义 G=(VTVN,S, P) 例Go=(VnVN,P) E→E+TT T→T*FF F→(E)i 显然Vr={+*()i VNETFI S=E P为上述产生式的集合

1. 文法的形式定义 G=(VT,VN,S,P) 例 G0=(VT,VN,S,P): E→E+T|T T→T*F|F F→(E)|i 显然 VT ={+,*,(,),i} VN ={E,T,F} S=E P为上述产生式的集合

说明:①α→β的读法, 其中a∈V*VNV*,阝∈V* ②a→阝 →→β2 缩写为α→β1|βB2.Bn C→→βn

说明: ①→的读法, 其中 V*VNV*,   V* ②  →  1  →  2 . . .  →  n 缩写为 →  1|  2|…| n

2.文法的分类 ①0型文法产生式形如a→β ②1型文法:||<|β或产生式形如 Aβ→0oB 上下文有关文法) ③2型文法产生式形如A→α (上下文无关文法) ④3型文法产生式形如A→或A→0B (正则文法右线性文法)

2. 文法的分类 ①0型文法:产生式形如→ ② 1 型 文 法 :│α│<=│β│ 或 产 生 式 形 如 αAβ→αβ (上下文有关文法) ③2型文法:产生式形如A→α (上下文无关文法) ④3型文法:产生式形如A→α或A→αB (正则文法,右线性文法)

3.简化的上下文无关文法 ①不含形如A→A的有害规则 ②不含多余规则 即A∈VN,必有S当aAβ

3. 简化的上下文无关文法 ①不含形如A→A的有害规则 ②不含多余规则 即AVN, 必有S * αAβ

二.文法产生的语言 1推导与归约 ①直接推导:aβ→06v 即由产生式右边替换产生式左边 ②推导a1当an、a1→d ③归约推导的逆过程

二. 文法产生的语言 1. 推导与归约 ①直接推导: αβ α 即由产生式右边替换产生式左边 ②推导:α1  αn、α1  αn ③归约:推导的逆过程 * +

举例已知GF)E→E+EEE|(E 计许的推导过程 E→E+E→E+E*→E+E*→E+i*→计ⅸ E→E+E→计+E→计+E*E→计E→计+i*i E→E*→E*i→E+E*i→→E+i1→计+i*1

举例: 已知G(E) E→E+E│E*E│(E)│i i+i*i的推导过程 E E+E E+E*E E+E*i E+i*i i+i*i E E+E  i+E i+E*E i+i*E i+i*i E E*E E*i E+E*i E+i*i i+i*i

2.句型和句子 设文法G=(VnVS,P),若S,α∈V*,则称α为 文法G的一个句型 若上述a∈V,则称是一个句子,即只含终结 符的句型是一个句子

2. 句型和句子 设文法G=(VT,VN,S,P), 若S α, αV*, 则称α为 文法G的一个句型。 若上述α VT，则称α是一个句子，即只含终结 符的句型是一个句子。 * *

3.文法产生的语言 文法G=(VnVN,S,P)的句子的全体,称为由文法 G产生的语言,记为L(G)即 L(G)={a|S→b入a∈V*}

3. 文法产生的语言 文法G=(VT,VN,S,P)的句子的全体, 称为由文法 G产生的语言, 记为L(G), 即 L(G)={α│S +αα VT*}

G2(1) I→L|LS S→TST T→LD L→ab|.|z 0121.|9

G2(I): I→L│LS S→T│ST T→L│D L→a│b│. . .│z D→0│1│2│ . . .│9