9

任何人都可以简单地解释“语法定向翻译”是什么意思吗？我开始阅读龙书的主题，但无法理解。维基文章也没有帮助。

4

2 回答 2

19

简单来说，“语法定向翻译”意味着使用语法识别器（解析器）驱动整个编译（翻译）过程。

从概念上讲，编译程序（将其从源代码转换为机器代码）的过程从生成解析树的解析器开始，然后通过一系列树或图转换来转换该解析树，每个转换在很大程度上是独立的，生成最终的简化树或图，遍历该树或图以生成机器代码。

这种观点虽然在理论上很好，但有一个缺点，如果您尝试直接实现它，则需要足够的内存来保存整个树或图的至少两个副本。早在编写《龙之书》的时候（当这个理论的很多内容都被散列出来时），计算机内存以千字节为单位，而 64K 已经很多了。所以编译大型程序可能会很棘手。

使用语法定向翻译，您可以按照解析器识别解析树的顺序组织所有图形转换。您的解析器不会生成完整的解析树，而是构建它的一小部分，然后将这些位提供给编译器的后续传递，最终生成一小段机器代码，然后继续解析过程以构建下一段解析树。由于任何时候都只存在少量的解析树（或后续图），因此需要的内存要少得多。由于语法识别器是控制所有这些（决定事情发生的顺序）的主音序器，这称为语法定向翻译。

由于这是一种减少内存使用的有效方法，人们甚至重新设计了语言以使其更容易做到——理想的情况是拥有一个“单通道”编译器，它实际上可以完成从解析到机器代码生成的整个过程一次通过。

如今，内存已不再那么珍贵，因此将所有内容强制一次通过的压力较小。相反，您通常只在前端使用语法直接翻译，解析语法，进行类型检查和其他语义检查，以及一些简单的转换，全部来自解析器并产生一些内部形式（三个地址代码、树或某种类型的 dag )，然后具有独立的优化和后端通道（因此不是语法指导的）。即使在这种情况下，您也可能声称这些后面的传递至少部分是语法指导的，因为编译器可能被组织为对输入的大块（例如整个函数或模块）进行操作，在继续执行之前推动所有传递下一段输入。

yacc 之类的工具是围绕语法定向翻译的思想设计的——该工具生成一个语法识别器，它直接运行代码片段（工具用语中的“动作”），因为识别出产品（解析树的片段），而无需创建一棵真正的“树”。这些动作可以直接调用编译器中逻辑后传的内容，然后返回继续解析。驱动所有这些的命令式主循环是解析器的令牌读取状态机。

于 2013-04-13T06:21:10.397 回答
1

实际上没有。在 Dragon Book 之前的历史上，有语法导向的编译器。在 1960 年代后期参加 ACM SEGPlan 会议时，我了解到了几种类型的定向翻译。还讨论了树导向和图导向翻译。虽然我从来没有拥有过龙书，但我认为这些在龙书中混在一起了。我最喜欢的书是 Saul Rosen 的 Programming Systems and Languages。它是关于编译器、操作系统和计算机系统的论文集。我将尝试解释早期的语法导向编译器解析器编程语言。后来产生树的语言与树导向代码生成语言相结合。

早期的语法导向编译器，直接将源代码翻译成堆栈机器代码。Borrows B5000 ALGOL 编译器就是一个例子。

A*(B+C) -> A,B,C, ADD , MPY

Schorre 在 1960 年代开发的 META II 领域特定解析器编程语言编译器编译器是语法导向编译器的一个示例。您可以在 ACM 档案中找到原始的 META II 论文。META II 使用 $ 后缀零个或多个序列运算符和 ( ) 分组来避免左递归。

EXPR = TERM $('+' TERM .OUT 'ADD'|'-' TERM .OUT 'SUB');

后来基于 Schorre 的元语言编译器使用基于堆栈的树转换运算符 :< node name > 和 !< number > 转换为树。

EXPR = TERM $(('+':ADD|'-':SUB) TERM!2);

除了使用 [< number >] 而不是 !< number > 的 TREEMETA。上面的 EXPR 公式与 META II EXPR 基本相同，只是我们已经分解了运算符 + 和 - 识别创建相应的节点并将节点推入节点堆栈。然后在识别正确的 TERM 时，树构造函数 !2 创建一棵树，弹出顶部 2 个解析堆栈 < TERM >s 和节点堆栈中的顶部节点以形成一棵树：

    ADD    or    SUB
   /   \        /   \
TERM   TERM  TERM   TERM

令牌由提供的识别器 .ID .NUMBER 和 .STRING 识别。后来被 CWIC 中的记号“..”和字符类“:”公式代替：

id .. let $(leter|dgt|+'_');

树导向编译器语言与语法导向编译器相结合以生成代码。Systems Development Corporation 开发的 CWIC 编译器编译器包括基于 LISP 2 的树导向生成器语言。CWIC 的一篇简短论文可以在 ACM 档案中找到。

在解析器编程语言中，您正在编写一种递归体面的解析器。当你来到 CWIC 时，今天归因于递归体面解析器的所有问题都被消除了。不存在左递归问题，因为 $ 零或更多构造和编程树构造消除了左递归的需要。您控制树的构造。循环构造用于生成左手树，尾递归用于生成右手树。尽管解析公式可能根本不会生成树：

program = $declarations;

在上面的声明之前的 $ 零个或多个循环运算符指定声明将被重复调用，只要它返回成功。正在编译的输入源代码由任意正数的声明组成。然后声明公式将定义声明的类型。您可能需要外部链接声明、数据声明、函数或过程代码声明。

declarations = linkage_decl | data_decl | code_decl;

每个声明的类型都是一个单独的公式。语法语言控制何时发生语义处理和代码生成。上面的程序和声明公式不会生成树。他们只是控制何时以及什么语言结构被解析。这些都不是 LL 或 LR 解析器。提供无限（仅受可用内存限制）程序回溯。他们提供程序化的前瞻性和峰值提前测试。

作为最后一个示例，以下示例包括标记和字符类公式说明了生成左手树和右手树。特别是使用尾递归求幂。

assign = id '=' expr ';' :ASSIGN!2 arith_gen[*1];
expr   = term $(('+':ADD | '-':SUB) term !2);
term   = factor $(('*':MPY | '//' :REM | '/':DIV) factor!2);
factor = ( id ('(' +[ arg $(',' arg ]+ ')' :CALL!2 | .EMPTY)
         | number 
         | '(' expr ')'
         )  ('^' factor:EXP!2 | .EMPTY);

bin: '0'|'1';
oct: bin|'2'|'3'|'4'|'5'|'6'|'7';
dgt: oct|'8'|'9';
hex: dgt|'A'|'B'|'C'|'D'|'E'|'F'|'a'|'b'|'c'|'d'|'e'|'f';
upr: 'A'|'B'|'C'|'D'|'E'|'F'|'G'|'H'|'I'|'J'|'K'|'L'|'M'|
     'N'|'O'|'P'|'Q'|'R'|'S'|'T'|'U'|'V'|'W'|'X'|'Y'|'Z';
lwr: 'a'|'b'|'c'|'d'|'e'|'f'|'g'|'h'|'i'|'j'|'k'|'l'|'m'| 
     'n'|'o'|'p'|'q'|'r'|'s'|'t'|'u'|'v'|'w'|'x'|'y'|'z';
alpha:    upr|lwr;
alphanum: alpha|dgt;

number .. dgt $dgt MAKENUM[];
id .. alpha $(alphanum|+'_');
于 2014-10-22T21:41:20.797 回答