程序语言的语法描述与分析 目的： ●语言的语法结构的形式描述 ●从形式描述中，研究语法分析器的构造 (算待优先分析法和递归子程序分析法)
程序语言的语法描述与分析 目的： ⚫语言的语法结构的形式描述 ⚫从形式描述中，研究语法分析器的构造 （算符优先分析法和递归子程序分析法）
第三章 文法和语言 本章内容 ●引言 语言和文法的直观概念 ~符号和符号串的相关概念 ●文法与语言 文法和语言的形式定义 文法的分类 上下文无关文法 ●语法树与二义性 ●句型的分析 。文法的改造
本章内容 ⚫引言 -语言和文法的直观概念 -符号和符号串的相关概念 ⚫文法与语言 -文法和语言的形式定义 -文法的分类 -上下文无关文法 ⚫语法树与二义性 ⚫句型的分析 ⚫文法的改造 第三章 文法和语言
一、引言 定义或表示语言的方法： ·当一个语言有有限个句子时，可采用枚举法 如：L语言只有两个句子，则可表示为： L={I am a teacher,You are student) ÷大多数语言都是无穷的，可用下列方法描述 1.制定有限条规则，用来产生所需要描述的语 言中的所有句子 2.建立一种装置（自动机）
定义或表示语言的方法： ❖ 当一个语言有有限个句子时，可采用枚举法 如：L语言只有两个句子，则可表示为： L={ I am a teacher，You are student} ❖ 大多数语言都是无穷的，可用下列方法描述 ⒈制定有限条规则，用来产生所需要描述的语 言中的所有句子 ⒉建立一种装置（自动机） 一、引言
=> 例： =>… ：= ：=the ：= ：= ：=monkey|banana ：=atehas ：=thela
例： ::= ::=the ::= ::= ::=monkey|banana ::=ate|has ::=the|a => =>…
一、引言 ●文法(grammar) 问题： 如何描述语言 定义： 文法是描述语言的语法结构的形式规则（即语法规 则) 目的： 解决语言的有穷说明问题，包含对语法的描述，但 却不表达任何语义
⚫文法（grammar) 问题： 如何描述语言 定义： 文法是描述语言的语法结构的形式规则（即语法规 则 ) 目的： 解决语言的有穷说明问题，包含对语法的描述，但 却不表达任何语义 一、引言
几个概念： 1.字母表 2.特号串 9符号串集合 3.符号串的长度 4.空符号串 10.符号串集合的和、积 5.待号串的前缀（头） 11.特号串集合的方累 符号串的后缀（尾） 符号串的真前缀（真后缀) 12.符号串集合的闭包 6.符号串的子串 7.符号串的连接 8.符号串的方暴
几个概念： 1. 字母表 2. 符号串 3. 符号串的长度 4. 空符号串 5. 符号串的前缀（头） 符号串的后缀（尾） 符号串的真前缀（真后缀） 6. 符号串的子串 7. 符号串的连接 8. 符号串的方幂 9.符号串集合 10.符号串集合的和、积 11.符号串集合的方幂 12.符号串集合的闭包
规则一重写规则、产生式或生成式。 是形如a一β或a:=β的（a,阝)有序对， 其中α是某字母表V的的正闭包V+的一个符号，阝是 V*的一个符号。 a称为规则的左部，B称为规则的右部。 →和：=含义相同，读作“生成
❖ 规则——重写规则、产生式或生成式。 是形如α→β或α ∷= β的（ α ， β ）有序对， 其中α是某字母表V的的正闭包V+的一个符号， β是 V*的一个符号。 α称为规则的左部， β称为规则的右部。 →和∷=含义相同，读作“生成
二、文法与语言 1、一个上下文无关文法G是一个四元式(V,VN,S,P), 其中： V:是非空有限集，它的每个元素是终结符号； VT:是非空有限集，它的每个元素是非终结符号； VnVN=Φ； VTUVN=V; S:SEVN,称为开始特号； P:产生式集合（有限），每个产生式形式是 {P>a|P∈VN,a∈VUV)*,S至少一次为P;
二、文法与语言 1、 一个上下文无关文法G是一个四元式（VT ,VN,S, P ）， 其中: VT：是非空有限集，它的每个元素是终结符号； VT：是非空有限集，它的每个元素是非终结符号； VT∩VN=Φ; VT∪VN=V; P ：产生式集合（有限），每个产生式形式是 { P->α| P∈VN，α∈(VT∪VN)*，S至少一次为P }； S：S∈VN，称为开始符号；
例1、考虑下面的算术表达式的文法及语言 VT: id+-*/↑() VN: 表达式、运算待 S: 表达式 P: 表达式->表达式运算符表达式 表达式->（表达式） 得到文法 E秦E川-E]d >id G1(E: 芝茅特A世
例1、考虑下面的算术表达式的文法及语言 VT： id + － * / ↑ ( ) VN： 表达式、运算符 S： 表达式 P： 表达式 ->表达式运算符 表达式 表达式 ->（表达式） 表达式 -> －表达式 表达式 -> id 运算符 -> +| －| * |/|↑ 得到 文法 G1(E): E ->EAE|( E )| －E |id A -> + |－|*|/|↑
由此可见，文法G1(E)所定义的语言是上述算术表达式， 如：id+id,id*(id+id等 它表达了简单算术表达式由id用A连接起来 该文法的： VN是出现P的左部所有符号集合 V是P的所有特号 ..V=VIVN S是该文法所定义的句子名字 写出了P,就能找出其它三元素
该文法的： VN是出现P的左部所有符号集合 V是P的所有符号 ∴VT = V \ VN S是该文法所定义的句子名字 ∴写出了P ，就能找出其它三元素 由此可见，文法G1(E)所定义的语言是上述算术表达式， 如：id+id，id*(id+id) 等 它表达了简单算术表达式由id用A连接起来