《程序设计语言与编译》课程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β