LearnLog

Ch2 A Simple Syntax-Directed Translator

编译原理的第二章笔记, 描述了一个例子. 讲道理这个例子看得人非常迷惑.

基于一个例子讲述了各种概念. 是后面章节(CH3-6)的一个导论.

analysis phase: 将源程序转换为各种中间概念(如语法树), 并据此生成中间代码.

语法vs语义 syntax vs semantics

The syntax of a programming language describes the proper form of its programs, while the semantics of the language de nes what its programs mean

2.2

  • 我们用上下文无关语法, 或者说BNF(Backus-Naur Form)来表示syntax.
  • 而语义的形式化表示就困难得多, 没有类似的简洁符号进行表达

2.3 介绍syntax-directed translation
Parsing or syntax analysis is introduced in Section 2.4.

A model of a compiler front end:

  1. 词法分析器: 将源程序转换为一个个token
  2. Parser: 将token组织成语法树
  3. 中间代码生成器: 将语法树转换为three-address code

某些时候, 中间代码也可以用树的形式表示.

Syntax Definition

Definition of Grammars

一个上下文无关语法由下面的四元组构成:

  1. 一个终止符的集合
  2. 一个非终止符的集合
  3. 一个productions的集合
  4. 将某个非终止符标记为起始符号

Derivations

从起始符号开始, 不断通过productions替换其中的非终止符, 直至收敛.

Parsing: 给定一系列终止符, 指出如何将其构建为起始符号. (类似自厎向上). 在第四章中讨论.

Parse Trees

解析树: 具有如下性质

  1. 根节点标记为start symbol
  2. 叶子标记为terminal or epsilon
  3. 中间节点标记为nonterminal
  4. 节点的父子关系符合production的要求

给定一个字符串, 给出解析树的过程, 称为parsing that string. (The process of nding a parse tree for a given string of terminals is called parsing that string.)

Ambiguity 模糊性
一个string可以由多个parse tree生成.

Associativity of Operators
操作符的结合性.

Precedence of Operators
操作符的优先级

Syntax-Directed Translation

前面做了许多定义作为准备工作,

backtop