推导(续) 推导序列∞1→x2→…→an,称为α推导到αn。记作1 α÷指经过零步或多步推导。 ●对于任意串a,aa 如果a=B且B→y,那么a÷y 今表示经过一步或多步推导出 ●句型:如果从文法的开始符号S开始,S亠α则称α是G的 个句型。 句子,不包括非终结符号的句型。 ●语言:句子的集合{wS=w,由文法G生成的语言被称为 上下文无关语言L(G)。 ●文法的等价性:两个文法生成相同语言,则两文法等价
推导（续） 推导序列α1 α2 … αn， 称为α1推导到αn。记作 α1 αn， 指经过零步或多步推导。 对于任意串 如果 表示经过一步或多步推导出 句型：如果从文法的开始符号S开始， ，则称α是G的 一个句型。 句子，不包括非终结符号的句型。 语言：句子的集合{w|S w}，由文法G生成的语言被称为 上下文无关语言L(G)。 文法的等价性：两个文法生成相同语言，则两文法等价 11
推导例子 E→-E→-(E)→-(E+E)→-(id+E)→-(id+id)
推导例子 12
推导中的问题 从推导的角度看,语法分析的任务是:接受一个终结 符号串作为输入,找出从文法的开始符号推导出这个 串的方法。 ●推导中可能遇到的两个问题 每一步替换哪个非终结符号 若以这个非终结符号为头的产生式有多个,用哪个产生 式的右部替换
推导中的问题 从推导的角度看，语法分析的任务是：接受一个终结 符号串作为输入，找出从文法的开始符号推导出这个 串的方法。 推导中可能遇到的两个问题 每一步替换哪个非终结符号 若以这个非终结符号为头的产生式有多个，用哪个产生 式的右部替换 13
非终结符号的替换顺序 ●通常使用两种方式进行推导 最左推导:总是选择每个句型的最左非终结符号。记作→ 最右推导:总是选择最右边的非终结符号。记作→ 每个最左推导步骤可以写成m4y= A→δ 是 应用的产生式 ●如果α经过最左推导得到,β作a≥B 最左句型α:S是文法G的识别符号,如果S≥α 是G的左句型
非终结符号的替换顺序 通常使用两种方式进行推导 最左推导：总是选择每个句型的最左非终结符号。记作 最右推导：总是选择最右边的非终结符号。记作 每个最左推导步骤可以写成 ， , 是 应用的产生式 如果 经过最左推导得到 ，记作 最左句型 ：S是文法G的识别符号，如果 ，则 是G的最左句型 14
语法分析树 是推导的图形表示形式,树上 看不出来推导的顺序 E 能够反映串的语法层次结构 语法分析树 内部节点:对应于一个非终结符 E|E| E 子节点:,对应于其父节点为头的 生式体 叶子节点:可以是终结符号或非 终结符号,从左到右排列可以得 到一个句型,称为这棵树的结笑。图43-(id+id)的 语法分析树
语法分析树 是推导的图形表示形式，树上 看不出来推导的顺序 能够反映串的语法层次结构 语法分析树 内部节点：对应于一个非终结符 号 子节点：对应于其父节点为头的 产生式体 叶子节点：可以是终结符号或非 终结符号，从左到右排列可以得 到一个句型，称为这棵树的结果。 15