定义：称oAB直接推出oy,即 AB→0yB 仅当A→Y是一个产生式， 且o,B∈(VUVN)。 ■如果01→02→..→0n’ 则我们称这个序 列是从到a的一个推导。若存在一个从 o1到on的推导，则称可以推导出on。 ■例：对文法(1) E→(E)→(E+E)=→(+E)=→(+i) 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 ◼ 定义：称A直接推出，即 A 仅当A → 是一个产生式， 且， (VT VN) * 。 ◼ 如果1 2 n，则我们称这个序 列是从1到n的一个推导。若存在一个从 1到n的推导，则称1可以推导出n 。 ◼ 例：对文法(1) E (E) (E+E) (i+E) (i+i)
通常，用a,→n 表示：从出发，经过 一步或若干步，可以推出o 用必1→Cn表示：从o1出发，经过0步或 若干步，可以推出on。 所以：C→B即=B或→B 口定义：假定G是一个文法，S是它的开始符号。 如果 则称是一个句型。仅含终结符 坐是句子。文法所产生的句子的全 体是一个语言，将它记为L(G)。 L(G)={Ox|S→,Ox∈V}
国防科技大学计算机系602教研室 ◼ 通常，用 表示：从1出发，经过 一步或若干步，可以推出n。 n + 1 n * 用 1 表示：从1出发，经过0步或 若干步，可以推出n。 = + * 所以 ： 即 或 ( ) { | , } * VT L G = S + ❑定义：假定G是一个文法，S 是它的开始符号。 如果 ，则称是一个句型。仅含终结符 号的句型是一个句子。文法G所产生的句子的全 体是一个语言，将它记为 L(G)。 * S
4.1语法分析器的功能 语法分析的任务是分析一个文法的句子 结构。 g】 语法分析器的功能：按照文法的产生式 (语言的语法规则)，识别输入符号串是 否为一个句子（合式程序）。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 4.1 语法分析器的功能 ◼ 语法分析的任务是分析一个文法的句子 结构。 ◼ 语法分析器的功能：按照文法的产生式 (语言的语法规则)，识别输入符号串是 否为一个句子(合式程序)
单词符号 语法分 源程序词法分 语法分 析树 编译程序 析器 取下一单词 析器 后续部分 符号表 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 源程序 单词符号 取下一单词 ... 语法分 词法分 析树 析器 语法分 析器 符号表 编译程序 后续部分
语法分析的方法： 口自下而上分析法(Bottom-up) ■基本思想：从输入串开始，逐步进行“担 约”，直到文法的开始符号。即从树末端开 始，构造语法树。所谓归约，是指根据文法的 产生式规则，把产生式的右部替换成左部符号。 ■算符优先分析法：按照算符的优先关系和结合 性质进行语法分析。适合分析表达式。 ■LR分析法：规范归约 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 ◼语法分析的方法： 自下而上分析法(Bottom-up) ◼基本思想：从输入串开始，逐步进行“归 约”，直到文法的开始符号。即从树末端开 始，构造语法树。所谓归约，是指根据文法的 产生式规则，把产生式的右部替换成左部符号。 ◼算符优先分析法：按照算符的优先关系和结合 性质进行语法分析。适合分析表达式。 ◼ LR分析法：规范归约