复习：程序语言的语法描述 ■几个概念： 口考虑一个有穷字母表Σ字符集 口其中每一个元素称为一个字符 口Σ上的字（也叫字符串）是指由∑中的字符所构 成的一个有穷序列 口不包含任何字符的序列称为空字，记为ε 口用∑*表示∑上的所有字的全体，包含空字ε 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 复习：程序语言的语法描述 ◼ 几个概念: 考虑一个有穷 字母表∑ 字符集 其中每一个元素称为一个字符 ∑上的字(也叫字符串) 是指由∑中的字符所构 成的一个有穷序列 不包含任何字符的序列称为空字，记为ε 用∑*表示∑上的所有字的全体,包含空字ε
复习：程序语言的语法描述 ■∑*的子集U和V的连接（积）定义为 UV={aB1ax∈U&B∈V} ■V自身的n次积记为 Vn=VV...V 规定V={ε，令 VVOUVUV2UV3U... 称V是V的闭包； ■记V+=VV,称V+是V的正规闭包。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 复习：程序语言的语法描述 ◼ ∑*的子集U和V的连接（积）定义为 UV＝{ | U & V } ◼ V自身的 n次积记为 Vn=VV…V ◼ 规定V0={}，令 V*=V0∪V1∪V2∪V3∪… 称V*是V的闭包; ◼ 记 V＋＝VV* ，称V+是V的正规闭包
复习：程序语言的语法描述 ■上下文无关文法的定义： 一个上下文无关文法G是一个四元式 G=(V,VN,S,P),其中 ▣V:终结符集合（非空） 口VN:非终结符集合（非空），且VOVN=② 口S:文法的开始符号，S∈VN 口P:产生式集合（有限），每个产生式形式为 P-→o,P∈VN,a∈(VTUVN)* 口开始符$至少必须在某个产生式的左部出现一次。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 复习：程序语言的语法描述 ◼ 上下文无关文法的定义： 一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中 VT：终结符集合(非空) VN：非终结符集合(非空)，且VT VN= S：文法的开始符号，SVN P：产生式集合(有限)，每个产生式形式为 P→， PVN， (VT VN) * 开始符S至少必须在某个产生式的左部出现一次
复习：程序语言的语法描述 ■定义：称oAB直接推出oyB,即 AB→oyB 仅当A→Y是一个产生式， 且a,B∈(VTUVN)。 如果1→c2→.→n,则我们称这个序 列是从1到o的一个推导。若存在一个从 o1到an的推导，则称o可以推导出on。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 复习：程序语言的语法描述 ◼ 定义：称A直接推出，即 A 仅当A → 是一个产生式， 且， (VT VN) * 。 ◼ 如果1 2 n，则我们称这个序 列是从1到n的一个推导。若存在一个从 1到n的推导，则称1可以推导出n
通常，用心，→n表示：从出发，经过 一步或若干步，可以推出o。 用1→0n表示：从1出发，经过0步或 若干步，可以推出o 所以：→B即a=B或→B 口定义：假定G是一个文法，S是它的开始符号。 如果<」 米 ,.则α称是一个句型。仅含终结符 号的付型是之朵句子。文法G所产生的句子的全 体是一个语言，将它记为L(G)。 L(G)={a&LS→ox,Cx∈VT} 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 ◼ 通常，用 表示：从1出发，经过 一步或若干步，可以推出n。 n + 1 n * 用 1 表示：从1出发，经过0步或 若干步，可以推出n。 = + * 所以 ： 即 或 * S ( ) { | , } * VT L G = S + ❑定义：假定G是一个文法，S 是它的开始符号。 如果 ，则称是一个句型。仅含终结符 号的句型是一个句子。文法G所产生的句子的全 体是一个语言，将它记为 L(G)
复习：程序语言的语法描述 最左推导：任何一步o→B都是对α中的最 左非终结符进行替换。 最右推导：任何一步α→B都是对o中的最 右非终结符进行替换。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 复习：程序语言的语法描述 ◼ 最左推导：任何一步 都是对中的最 左非终结符进行替换。 最右推导：任何一步 都是对中的最 右非终结符进行替换
复习：程序语言的语法描述 ■用一张图表示一个句型的推导，称为语法树。 E E→(E) E→(E) →(E+E) →(E+E) E →(E*E+E) →(E+i) →(i*E+E) →(E*E+i) →(i*i+E) →(E*i+i) 1 1 →(i*i+iD) →(i*i+i) 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 复习：程序语言的语法描述 ◼ 用一张图表示一个句型的推导,称为语法树。 E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i) E (E) (E+E) (E+i) (E*E+i) (E*i+i) (i*i+i)
复习：程序语言的语法描述 ■定义：如果一个文法存在某个句子对应两 颗不同的语法树，则说这个文法是二义的。 ■ 语言的二义性：一个语言是二义性的，如 果对它不存在无二义性的文法。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 复习：程序语言的语法描述 ◼ 定义：如果一个文法存在某个句子对应两 颗不同的语法树，则说这个文法是二义的。 ◼ 语言的二义性：一个语言是二义性的，如 果对它不存在无二义性的文法
复习：程序语言的语法描述 ■形式语言鸟瞰 ◆0型（短语文法，图灵机）： 产生式形如：Q→B 其中：∈(VUVW且至少含有一个非终结符；B∈ VOVN) ◆1型（上下文有关文法，线性界限自动机）： 产生式形如：→阝 其中：I侧≤βl,仅S→ε例外。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 复习：程序语言的语法描述 ◼ 形式语言鸟瞰 0型(短语文法，图灵机)： 产生式形如： → 其中： (VT VN) *且至少含有一个非终结符； (VT VN) * 1型(上下文有关文法，线性界限自动机)： 产生式形如： → 其中：|| ||，仅 S→ 例外
复习：程序语言的语法描述 ■形式语言鸟瞰 ◆2型（上下文无关文法，非确定下推自动机）： 产生式形如：A→阝 其中：A∈VN;B∈VTUVN). ◆3型（正规文法，有限自动机）： 产生式形如：A→B或A→o 其中：∈Vr;A,B∈VN 产生式形如：A→B0或Ao 其中：o∈VT；A,B∈VN 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 复习：程序语言的语法描述 ◼ 形式语言鸟瞰 2型(上下文无关文法，非确定下推自动机)： 产生式形如： A → 其中：A VN； (VT VN) * 。 3型(正规文法，有限自动机)： 产生式形如：A → B 或 A → 其中： VT * ；A，BVN 产生式形如：A → B 或 A → 其中： VT * ；A，BVN