语法制导翻译

发表于 更新于

定义

通过定义一个文法并使用该文法让翻译过程结构化的方式来翻译源文本。

语法制导翻译使用文法定义如何创建语法分析器，语法分析器可以将输入的文本转换成语法分析树，语法分析树具有类似于文法规则的结构。

运行机制

文法

文法的定义

文法是定义编程语言的合法语法的一种方式。

如下 DSL 定义

1
2
3
4
5
6
7
8
9
10
events
  doorClosed D1CL
  drawerOpened D2OP
  # ...
end
commands
  unlockPanel PNUL
  lockPanel PNLK
  # ...
end

这些声明遵循一定的语法形式，该语法形式可以用如下文法来定义：

1
2
3
4
5
declarations : eventBlock commandBlock;
eventBlock : Event-keyword eventDec* End-keyword;
eventDec : Identifier Identifier;
commandBlock : Command-keyword commandDec* End-keyword;
commandDec : Identifier Identifier;

文法为语言提供了一种人类刻度的定义，文法通常以 BNF 编写

文法的处理方式

  • 把文法当做手写语法分析器的规则和实现指南
    • 递归下降语法分析器
    • 语法分析器组合子
  • 把文法当做 DSL，然后用语法分析器生成器根据文法文件本身自动构建语法分析器。我们无须自己编写代码，代码是根据文法生成的。

文法只处理部分问题：如何将输入文本转换为语法分析树这种数据结构。

词法分析器

词法分析器将输入字符分解成记号(token)，记号表示对输入进行的更合理的划分块。

下面词法规则定义了命令和事件，词法分析器将输入转换成一系列记号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
event-keyword: 'events';
command-keyword: 'commands';
end-keyword: 'end';
identifier: [a-z A-Z 0-9]*;

events
  doorClosed D1CL
  drawOpened D2OP
end

[Event-keyword: "events"]
[Identifier: "doorClosed"]
[Identifier: "D1CL"]
[Identifier: "drawOpened"]
[Identifier:"D2OP"]
[End-keyword: "end"]

记号

每个记号都是一个有两个基本属性的对象：类型和内容(payload)。类型是记号的种类，内容是匹配为部分词法分析器的文本

使用原因

  • 让语法分析器更简单，其可以根据记号来编写，而非原始字符
  • 效率问题：词法分析器与语法分析器实现方式不同，词法分析器通常是一个状态机，语法分析器是一个下推栈机。

语法分析器

语法分析器分为 2 个部分，分别是语法分析和动作。语法分析将记号流组织成语法分析树，暂且忽略动作部分

语法分析树

文法定义

1
2
3
4
5
declarations : eventBlock commandBlock;
eventBlock : Event-keyword eventDec* End-keyword;
eventDec : Identifier Identifier;
commandBlock : Command-keyword commandDec* End-keyword;
commandDec : Identifier Identifier;

语法分析将这些记号和文法组织成下图所示的树结构。

为了形成语法分析树，语法分析引入了额外的节点（用矩形表示），这些节点都是由文法定义的。

任何给定的语言都可以由多个文法匹配

1
2
3
eventBlock : Event-keyword eventList End-keyword;
eventList : eventDec*
eventDec : Identifier Identifier;

其会产生不同的语法分析树

因此，使用语法制导翻译，文法定义了如何将输入文本转换成语法分析树

语法树概念区别

  • 语法分析树：带有所有出现的记号，是一棵完整的原始树。
  • 抽象语法树：一棵简化过的树，丢弃了不必要的记号，经过重新组织以便于后续处理。