国防科技大学：《编译原理》课程电子教案（PPT教学课件）第3章 词法分析

复习：程序语言的语法描述 ■几个概念： 口考虑一个有穷字母表Σ字符集 口其中每一个元素称为一个字符 口Σ上的字（也叫字符串）是指由∑中的字符所构 成的一个有穷序列 口不包含任何字符的序列称为空字，记为ε 口用∑*表示∑上的所有字的全体，包含空字ε 国防科技大学计算机系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：文法的开始符号，SVN  P：产生式集合(有限)，每个产生式形式为 P→， PVN，   (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)