编译器前端结构 字符流 单词流 中间代码 词法分析器 法导向的翻译器
编译器前端结构 字符流 词法分析器 单词流 语法导向的翻译器 中间代码
文法 Grammar 我们采用文法来描述语言的句子结构 ■在得到某语言的文法基础上,我们可判定 个句子是否属于该语 判定一个句子是否满足某语言的文法成为 法分析的核心问题 下面的内容围绕如何设计上下文无关的文 法以解决这个判定问题
文法Grammar ◼ 我们采用文法来描述语言的句子结构 ◼ 在得到某语言的文法基础上，我们可判定 一个句子是否属于该语言 ◼ 判定一个句子是否满足某语言的文法成为 语法分析的核心问题 ◼ 下面的内容围绕如何设计上下文无关的文 法以解决这个判定问题
上下文无关的文法 a stmt-> it expr stmt else stmt ■上下文无关的文法,有以下几个组成: 终止符(集合),或称为 token 非终止符(集合) tm,e、r 产生式(集合) stmt-> it expr stmt else stmt ■左侧有且仅有一个非终止符 有且仅有一个非终止符作为起始符,如非终止 符为文法G的起始符,表示为G
上下文无关的文法 ◼ stmt -> if (expr) stmt else stmt ◼ 上下文无关的文法，有以下几个组成： ◼ 终止符（集合），或称为token ◼ if, (, ), else ◼ 非终止符（集合） ◼ stmt, expr ◼ 产生式（集合） ◼ stmt -> if (expr) stmt else stmt ◼ 左侧有且仅有一个非终止符 ◼ 有且仅有一个非终止符作为起始符，如非终止 符S为文法G的起始符，表示为G[S]
描述加减的文法G[is,有以下4个 产生式组成 list-> list digit list-> list digit list -> digit dgy->|21|4||9 口左部相同的产生式,可以合并为: list-> list digit list digit digit 口终止符集合Ⅴ1为:{,,,…,}
描述加减的文法G[list]，有以下4个 产生式组成 list -> list + digit list -> list – digit list -> digit digit -> 0|1|2|3|4|5|6|7|8|9 ------------------------------------------ 左部相同的产生式，可以合并为： list -> list + digit | list – digit | digit 终止符集合VT为：{+,-,0,1,…,9}， 非终止符集合V 为：{list, digit}
文法导出串(句型) 从起始符开始,重复替换非终止符为其所 在产生式的右侧,所得到的符号串即称为 文法导出串,也称为句型。 如文法G的句型有: list => list di (一个句型) =>it-wi+lwt(一个句型) digit digit+lit(一个句型) >95+2(一个句型且是句子) 口只包括终止符的文法导出串,称为该文法 的句子,句子的集合,称为该文法定义的
文法导出串（句型） ◼ 从起始符开始，重复替换非终止符为其所 在产生式的右侧，所得到的符号串即称为 文法导出串，也称为句型。 如文法G[list]的句型有： list => list + digit （一个句型） => list – digit + digit （一个句型） => digit – digit + digit （一个句型） => 9 - 5 + 2 （一个句型且是句子） 只包括终止符的文法导出串，称为该文法 的句子，句子的集合，称为该文法定义的 语言。 *