编译原理语法1文法和语言.ppt

编译原理语法1文法和语言.ppt第4讲编译原理西北农林科技大学本科教程主讲教师:《语法分析》(4类)正规表达式与上下文无关文法重点掌握文法的表示本讲目标定位语法分析是编译过程的第二个阶段,也是核心部分任务根据语言的语法规则对单词序列进行语法分析,识别合法的语法单位(如表达式、语句、程序段等),若不存在语法错误则给出正确的语法结构(语法树)理论依据:上下文无关文法方法自顶向下分析(推导:开始符号句子)自底向上分析(规约:句子开始符号)语法分析:(Grammar)是程序语言的生成系统,用文法可以精确定义一个语言,并依据该文法构造出识别这个语言的自动机文法对程序语言和编译程序的构造具有重要意义,如程序语言的词法可用正规文法描述,语法可用上下文无关文法描述,、语言通常我们用Σ表示字母表,字母表中的每个元素称为字符或符号。不同语言的字母表可能是不同的,程序语言的字母表通常是ASCII字符集。由字母表Σ中的字符所组成的有穷系列称为Σ上的字符串或字,字母表Σ上的所有字符串(包括空串)组成的集合用Σ*表示。那么,对字母表Σ来说,Σ*上的任意一个子集都称为Σ上的一个语言,记为L(),该语言的每一个字符串称为语言L的一个语句或句子。、语言例如,设Σ = {a,b,c},则:L = {ε,a,aa,ab,aaa,aab,aba,abb,…}为Σ上的一个语言。如果a表示字母,b表示数字,c看做其它符号,则L即是程序语言中的标识符集,其中的每个标识符就是标识符集中的一个句子。、文法(定义)文法通常表示成四元组G[S] = (VT,VN,S,ξ):(1) VT为终结符号集,这是一个非空有限集,它的每个元素称为终结符号。(2) VN为非终结符号集,它也是一个非空有限集,其每个元素称为非终结符号,且有VT∩VN = Φ;(3) S为文法开始符,是一个特殊的非终结符号,即S∈VN;、文法(定义)文法通常表示成四元组G[S] = (VT,VN,S,ξ):(4) ξ是产生式的非空有限集,其中每个产生式(或称规则)是一序偶(α,β),通常写作α → β或α ::= β读作“α产生β”、“α是β”或“α定义为β”。在此,α为产生式的左部,而β为产生式的右部,α、β是由终结符和非终结符组成的符号串,α∈(VT∪VN)+ 且至少有一个非终结符,而β∈(VT∪VN)*。