编译原理 1~2章精品.pptVIP

短语与句柄 定义6.1: 设S是文法G的开始符号， 若 , , U∈VN*, x,y∈（VN∪VT）*, 称α是句型xUy相对于U的短语。 又若 ， ， U∈VN*， x,y∈（VN∪VT）*， 称α是句型xUy相对于U的直接短语或简单短语。 一个句型的最左直接短语称该句型的句柄。 构造下列语言的文法 { a3n|n≥1}; 解：G(S): S →aaaS|aaa 偶数集合 解：G(N): N →AB A →DA|ε D →0|1|2|3|4|5|6|7|8|9 B →0|2|4|6|8 {anbmck|n,m,k≥0} 语法树 设文法 G=(VT，VN，P，S)，对于文法G的任意一个句型都存在一个相应的语法树： ① 树中每个结点都有一个标记，该标记是VN∪VT中的一个符号； ② 树的根结点标记是文法的识别符号S； ③ 若树的一个结点至少有一个叶子结点，则该结点的标记一定是一个非终结符； ④ 若树的一个结点有多个叶子结点，该结点的标记为A，这些叶子结点的标记从左到右分别是B1，B2，…，BN，则(A，B1，B2…BN) ∈P。 语法树举例 文法 G[E] E→ E+T|T； T→ T*F|F； F→ i|(E)； E+i*(E+T) 产生式树 文法的句型可依据文法的产生式树来生成相应的语法树。 产生式树举例 文法 G[E] E→ E+T|T； T→ T*F|F； F→ i|(E)； 无用VN、不可达VN 文法中规则的个数应该是恰当的。再少，不足以完全描述一个语言，再多，又无必要。 程序设计语言中存在有多余规则时，往往存在有错误 多余规则使句子的分析复杂和增加困难度。 明显的多余规则有两种。 一是形如U→U的单规则，引起文法上的二义性。应该首先把它们删除去。 另—是规则U→u，其左都非终结符号U不出现在其它任何规则的右部，也应删除。 (U例外)。 无用VN、不可达VN举例 例如，对于文法G [Z]： Z→Be A→Ae | A | e B→Ce|Af C→Cf D→f 首先删除规则A→A; 又由于D不出现在任何规则右部，应删去规则D。 规则不多余的条件：U 条件1 x,y∈（VN∪VT）* 条件2 α∈VT*。 条件1要求u在句型中出现，条件2则进一步要求能从u推导出终结符号串。 显然，如果存在某个非终结符号U，它不满足上述两条件，则以U为左部的那些规则必是多余的。 分析方法简介 自上而下分析方法 确定性的自上而下分析方法 自下而上分析方法 第2章 习题 (学号后2位+6 ) %9+1 编译原理 1~2章 陈炬桦 isscjh@mail.sysu.edu.cn 第一章 语言的基本概念 程序设计语言 程序：告诉计算机“做什么”和“怎么做” 程序设计：编写程序的过程 程序设计语言：编写程序使用的语言 语句：定义在一个字符集合上的按一定的语法规则连接的有意义的字符串 语言：由语句组成的全体 作用：交换信息的工具 自然语言与形式语言 自然语言：人与人交换信息的工具。不精确，有二义性（手提包） 汉语、英语 形式语言：数学语言，精确语言，无二义性。计算机语言为人与计算机交换信息的工具 计算机语言 计算机语言有如下几类 机器语言：程序由一组能直接执行的指令组成，一条指令包括两部分 二进制：操作码和操作数均用二进制表示 与机器有关：不同的计算机有不同的指令系统和地址 汇编语言：用符号代替机器语言中的二进制码和操作数地址等，与机器有关 高级语言：接近于数学公式和英语，与机器无关 高级语言和汇编语言不能直接在计算机上执行，需要翻译程序翻译成机器语言后执行 翻译程序 高级语言和汇编语言不能直接在计算机上执行，需要翻译程序翻译成机器语言后执行 高级语言源程序 机器语言目标程序 结果 汇编语言源程序 机器语言目标程序 结果