语法定向翻译是什么意思？

问题描述 投票：9回答：2

任何人都可以简单地解释“语法定向翻译”的含义吗？我开始从Dragon Book中阅读该主题，但听不懂。 Wiki article也没有帮助。

syntax language-agnostic compiler-construction
2个回答
19
投票

最简单地说，“语法定向翻译”是指使用语法识别器（解析器）驱动整个编译（翻译）过程。

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

此视图在理论上虽然不错，但有一个缺点，如果您尝试直接实现它，则需要足够的内存来容纳整个树或图的至少两个副本。早在编写《龙书》时（以及大量散布该理论的时候），计算机内存的测量单位为千字节，而64K则很多。因此，编译大型程序可能很棘手。

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

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

[如今，记忆并不是那么重要，因此，将所有内容强制放入一个通道的压力较小。取而代之的是，您通常只在前端使用“语法直接转换”，解析语法，进行类型检查和其他语义检查，以及从解析器进行的一些简单转换，并产生某种内部形式（三种地址代码，树或某种形式的dags ），然后分别进行独立的优化和后端传递（因此不针对语法）。即使在这种情况下，您也可能会声称这些较晚的传递至少部分是针对语法的，因为编译器可以组织为对大块输入（例如整个函数或模块）进行操作，在继续所有传递之前先遍历所有传递下一个输入。

诸如yacc之类的工具是围绕语法定向翻译的概念设计的-该工具生成一个语法识别器，该语法识别器在识别出生产（语法树的片段）时直接运行代码片段（在工具术语中为“ actions”），而无需曾经创建过一个真正的“树”。这些操作可以直接调用逻辑上稍后在编译器中传递的内容，然后返回继续解析。驱动所有这些的命令性主循环是解析器的令牌读取状态机。

1
投票

实际上不是。从历史上看，《龙书》之前就有语法定向编译器。参加1960年代后期的ACM SEGPlan会议时，我了解了几种定向翻译。还讨论了树导向和图导向翻译。我认为这些东西在Dragon Book中混在一起了，尽管我从未拥有过Dragon Book。我最喜欢的书是Saul Rosen撰写的《编程系统和语言》。它是关于编译器，操作系统和计算机系统的论文的集​​合。我将尝试解释早期的语法指导的编译器解析器编程语言。后来的树生成器与树定向代码生成语言结合在一起。

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

A *（B + C）-> A，B，C，ADD，MPY

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

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

基于后来的Schorre的元语言编译器使用基于堆栈的树转换运算符转换为树：<< [节点名称] >>和！<< [数字] >>。EXPR = TERM $(('+':ADD|'-':SUB) TERM!2); 除了使用[<< [number] >>]的TREEMETA代替！<< [number] >>。上面的EXPR公式基本上与META II EXPR相同，除了我们已经对运算符+和-进行了因子分解，从而创建了相应的节点并将该节点推入节点堆栈。然后，在认识到正确的TERM时，树构造器！2会创建一棵树，从节点堆栈中弹出顶部的2个解析堆栈<< [TERM] >>和顶部节点，以形成树：

    ADD    or    SUB
   /   \        /   \
TERM   TERM  TERM   TERM

令牌由提供的识别器.ID .NUMBER和.STRING识别。后来由CWIC中的标记“ ..”和字符类“：”公式代替：id .. let $(leter|dgt|+'_'); 树导向的编译器语言与语法导向的编译器结合在一起以生成代码。在Systems Development Corporation开发的CWIC编译器编译器包括基于LISP 2的树定向生成器语言。可以在ACM档案中找到CWIC的简短论文。在解析器编程语言中，您正在编程一种递归的体面解析器。当您进入CWIC时，如今归因于递归体面解析器的所有问题都已消除。没有零递归问题，因为$零或更多的构造和编程的树构造消除了左递归的需要。您控制树的构造。循环构造用于生成左手树，而尾递归则用于右手树。尽管解析公式可能根本不生成任何树：

program = $declarations;

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

declarations = linkage_decl | data_decl | code_decl;

每个声明的类型都是一个单独的公式。语法语言控制何时进行语义处理和代码生成。上面的程序和声明公式不会生成树。他们只是在控制何时以及什么语言结构被解析。这些都不是LL oe 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|+'_');
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.