编译原理(龙书) 二

2016/01/01 阅读笔记

开始阅读第二章,这一章重点是编译器的前端部分简介。

上下文无关文法

文法包含四个部分

  1. 一个记号集合,成为终结符号
  2. 一个非终结符结婚
  3. 一个产生式集合。左部(非终结符) -> 记号和非终结符序列
  4. 一个开始符号(指定的非终结符)

c 语言的 if-else 语句

if (表达式) 语句 else 语句

使用 expr 标识表达式,stmt 标识一条语句,则其构造规则(产生式)可为:

stmt -> IF (expr) stmt ELSE stmt

用加好和减号分隔的数字序列

list -> list + digit
list -> list - digit
list -> digit
digit -> 0|1|2|3|4|5|6|7|8|9

Pascal语言的 begin-end

block -> BEGIN opt_stmts END
opt_stmts -> stmt_list | ε
stmt_list -> stmt_list ; stmt | stmt

分析树

  1. 树根标记为开始符号
  2. 每个叶节点由记号或者ε标记
  3. 每个内节点有一个非终结符标记
  4. 如果A是一个内节点的非终结符号标记,X1, X2,…Xn 是该节点从左到右排列的所有节点的标记,则 A -> X1X2…Xn 是一个产生式。这里 X1,X2,…Xn 是一个终结符或者非终结符。对于 A -> ε,分析树种标记为A的节点只有一个标记为ε的子节点

一个分析树从左到右的叶子节点是这棵分析树生成的结果。

一个文法生成的语言是它的其中一个分析树生成的串的集合。为给定的记号串找到一个分析树的过程称为这个串的语法分析。

二义性文法:一个文法有多棵分析树生成相同的记号串。如: string -> string + string|string - string|0|1|2|3|4|5|6|7|8|9

9 + 5 + 2(9 + 5) + 2 相等,我们说操作符 + 是左结合的,因为当一个操作数左右两侧都有 + 时,它将被其左边操作符使用。

右结合的 = 可由如下文法产生:

right -> letter = right | letter
letter -> a|b|...|ε
  • 比 + 有更高的优先级,在优先级表中,操作符按照优先级递增的次序排列,相同优先级的操作符在同一行上:
左结合:+ -
左结合:* /

使用两个非终结符 expr 和 term 分别表示两个不同的优先级层次,使用另一个非终结符 factor 产生表达式中的基本单元。表达式中的基本单元四数组和带括号的表达式。

expr -> expr + term | expr - term | term
term -> term * factor | term / factor | factor
factor -> digit | ( expr )

该文法把一个表达式看作是由 + 和 - 分隔的 term 表,把 term 看作是由 * 或 / 分隔的 factor 表。任何带括号的表达式都是一个 factor。

中缀转后缀

后缀表示:

  1. 如果 E 是一个变量或者常量,则 E 的后缀是 E 本身
  2. 如果 E 是形如 E1 op E2 的表达式,其中 op 是一个二元操作符,则 E 的后缀表示是 E1’ E2’ op,这里 E1’ E2’ 分别是 E1 和 E2的后缀表示
  3. 如果 E 是形如 (E1)的表达式,则 E1 的后缀表示是 E 的后缀表示

语法制导定义:文法和语义规则,使用上下文无关文法说明输入的语法结构,通过每个文法符号和一个属性集合相关联,通过每一个产生式和一个语义规则集合相关联。语义规则用来计算产生式中出现的符号相关联的属性的值。 假定分析树的节点 n 用文法符号 X 标识,我们用X.a 表示节点 n 上 X 的属性a 的值,节点 n 上的 X.a 的值是使用与 X 产生式相关联的属性 a 的语义规则来计算的,每个节点都具有属性值的分析树称为注释分析树。 如果分析树的其中一个节点属性值是有其子节点的属性值确定的,则我们称该属性为综合属性。

产生式 语义规则
expr -> expr1 + term expr.t := expr1.t term.t ‘+’
expr -> expr1 - term expr.t := expr1.t term.t ‘-‘
expr -> term expr.t := term.t
term -> 0 term.t := ‘0’
term -> 1 term.t := ‘1’
….
term -> 9 term.t := ‘9’

属性 t 表示该非终结符产生的表达式的后缀表示。

  1. 一个数字的后缀形式是该数字本身
  2. 产生式 expr -> expr1 + term 导出一个包含加号的表达式,加操作符的左操作数由 expr1 给出,右操作数由 term 给出

机器人指令转位置

可以向东、西、南、北移动一步,文法:

seq -> seq instr | BEGIN
instr -> EAST | NORTH | WEST | SOUTH

位置为 (x, y) 语法制导定义:

产生式 语义规则
seq -> BEGIN seq.x := 0 seq.y := 0
seq -> seq1 instr seq.x := seq1.x + instr.dx seq.y := seq.y + instr.dy
instr -> EAST instr.dx := 1 instr.dy = 0
instr -> NORTH instr.dx := 0 instr.dy = 1
instr -> WEST instr.dx := -1 instr.dy = 0
instr -> SOUTH instr.dx := 0 instr.dy = -1

Search

    Table of Contents