[编译原理第三章语法分析.ppt

第三章 语法分析 语法分析器的作用 上下文无关文法（CFG） 定义：上下文无关文法是一个四元组G=(N,T,P,S) ① N是非终结符的有限集合； ② T是终结符的有限集合，且N∩T＝Ф； ③ P是产生式的有限集合； ④ S是非终结符，是文法的开始符号。 例：定义上下文无关文法G=(N,T,P,S)如下： N={E} T={+,*,(,),-,id} S=E P: E→E+E E→E*E E→(E) E→-E E→id 形式语言分类 定义：若文法G=(N,T,P,S)的每个产生式α→β中，均有 α∈(N∪T)*N(N∪T)*,且至少含有一个非终结符， β∈(N∪T)*,则称G为0型文法（短语文法）。 ①1型文法（上下文有关文法）：G的任何产生式α→β(S→ε除外)均满足|α|≤| β| (|x|表示x中文法符号的个数)； ②2型文法（上下文无关文法）：G的任何产生式形如A→β，其中A∈N，β∈(N∪T)*； ③3型文法（正规文法、线性文法）：G的任何产生式形如A→a或者A→aB(或者A→Ba）,其中A,B∈N,a∈T*。 正规式与上下文无关文法 正规式所描述的语言结构均可以用CFG描述，反之不一定。 例：正规式r=(a|b)*abb的CFG描述如下 A→HT H→ε|aH|bH T→abb 往往采用正规式而不是CFG描述词法。 正规式适合描述线性结构； CFG适合描述具有嵌套（层次）性质的非线性结构。 CFG产生语言的基本方法——推导 定义：将产生式A→γ的右部代替文法符号序列αAβ 中的A得到αγβ的过程，称为αAβ直接推导 出αγβ，记作：αAβ?αγβ。 α1?αn为零步或多步推导； α1?αn为零步推导； 任何文法符号序列可以推导出它自身，α?α； 推导具有传递性，α?β,β?γ,则α?γ 定义：由CFG G所产生的语言 L(G)={ω|S?ω and ω∈T*}称为上下文无关语言，ω称为句子。若S?α,α∈(N∪T)*,则称α为G的一个句型。 只含终结符的句型是句子。 定义：在推导中，若每次直接推导均替换句型中最左边的非终结符，则称为最左推导，产生的句型称为左句型。 最右推导也称为规范推导。 例： 已知G(E),E→E+E|E*E|(E)|-E|id id+(id*id)的推导过程： 最左推导： E ?E+E ?id+E ?id+(E) ?id+(E*E) ?id+(id*E) ? id+(id*id) 最右推导： E ?E+E ?E+(E) ?E+(E*E) ?E+(E*id) ?E+(id*id) ?id+(id*id) 短语与语法树 定义： ①设αβ?是上下文无关文法G的一个句型, 如果有S ?αA?, 并且A?β,则称β是句型αβ?关于非终结符A的一个短语, 或称β是句型αβ?的一个短语。 ②直接短语（简单短语）：A→β ③句柄：一个句型的最左直接短语。 ④素短语:含有终结符的短语,但不存在也具有相同性质的真子串 短语：以非终结符为根的子树中所有从左到右排列的叶子； 直接短语：只有父子关系的树中所有从左到右排列的叶子（树高为2）； 句柄：最左边父子关系树中所有从左到右排列的叶子（句柄是唯一的）。 素短语:子树末端结点组成的符号串含终结符,且在该子树中不再有包含 含有终结符的更小子树 例：G(E)：E→E+T|T T→T*F|F F→(E)|i 句型：i*i+i的短语、直接短语、句柄和素短语 短语：i1*i2+i3,i1*i2,i1,i2,i3 直接短语：i1,i2,i3 句柄：i1 素短语: i1，i2，i3 分析树： ①根由开始符号标记； ②每个叶子由一个终结符、非终结符或ε标记； ③每个内部结点由一个非终结符标记； ④若A→X1X2…Xn是一个产生式，则标记为A的内部结 点从左到右有子结点X1，X2，…，Xn； ⑤若A→ε，则ε必是叶结点，且它是A的唯一子结点。 例： 语法树： ①根与内部结点由表达式中的操作符标记； ②叶子由表达式中的操作数标记； ③用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中； 例： 语法树只反映句型的结构，忽略了推导句型的过程。 二义性与二义性的消除 定义：若文法G对同一个句子产生不止一棵分析树，则称G是二义的。 例：id+id*id 原因是文法中缺少对文法符号优先级和结合性的规定 自上而下语法分析 自上而下语