定义:称aAB直接推出ayB,即 aA→ay 仅当A→y是一个产生式, 且a,B∈(VV 如果a1→a2→…an,则我们称这个序 列是从a到an的一个推导。若存在一个从 a到an的推导,则称a1可以推导出an 例:对文法(1) e→(e)→(e+e)→i+e)→i+i) 编译原理
编译原理 ◼ 定义：称A直接推出，即 A 仅当A → 是一个产生式， 且， (VT VN) * 。 ◼ 如果1 2 n，则我们称这个序 列是从1到n的一个推导。若存在一个从 1到n的推导，则称1可以推导出n 。 ◼ 例：对文法(1) E (E) (E+E) (i+E) (i+i)
通常,用a1→an表示:从a1出发,经过 一步或若干步,可以推出an 用a1→an表示:从a1出发,经过0步或 若步,可以推出an 所以:a→β即a=或a→β 口定义:假定G是一个文法,S是它的开始符号。 如果 S 则a称是一个句型。仅含终结符 号的句型是一个句子。文法G所产生的句子的全 体是一个语言,将它记为L(G)。 (G)={a|s→a,a∈r}
编译原理 ◼ 通常，用 表示：从1出发，经过 一步或若干步，可以推出n。 n + 1 n * 用 1 表示：从1出发，经过0步或 若干步，可以推出n。 = + * 所以 ： 即 或 ( ) { | , } * VT L G = S + ❑定义：假定G是一个文法，S 是它的开始符号。 如果 ，则称是一个句型。仅含终结符 号的句型是一个句子。文法G所产生的句子的全 体是一个语言，将它记为 L(G)。 * S
4.1语法分析器的功能 语法分析的任务是分析一个文法的句子 结构。 语法分析器的功能:按照文法的产生式 (语言的语法规则),识别输入符号串是 否为一个句子(合式程序)。 编译原理
编译原理 4.1 语法分析器的功能 ◼ 语法分析的任务是分析一个文法的句子 结构。 ◼ 语法分析器的功能：按照文法的产生式 (语言的语法规则)，识别输入符号串是 否为一个句子(合式程序)
单词符号 语法分 源程序词法分 语法分析树编译程序 析器 析器 后续部分 取下一单词 个 符号表 编译原理
编译原理 源程序 单词符号 取下一单词 ... 语法分 词法分 析树 析器 语法分 析器 符号表 编译程序 后续部分
语法分析的方法: 口自下而上分析法(Bottom--up) 基本思想:从输入串开始,逐步进行“归 约”,直到文法的开始符号。即从树末端开 始,构造语法树。所谓归约,是指根据文法的 产生式规则,把产生式的右部替换成左部符号。 算符优先分析法:按照算符的优先关系和结合 性质进行语法分析。适合分析表达式。 LR分析法:规范归约 编译原理
编译原理 ◼语法分析的方法： 自下而上分析法(Bottom-up) ◼基本思想：从输入串开始，逐步进行“归 约”，直到文法的开始符号。即从树末端开 始，构造语法树。所谓归约，是指根据文法的 产生式规则，把产生式的右部替换成左部符号。 ◼算符优先分析法：按照算符的优先关系和结合 性质进行语法分析。适合分析表达式。 ◼ LR分析法：规范归约