何时使用抽象语法树或具体语法树?

2023-12-26

我一直在研究编译器。词法分析器似乎非常简单:取一个“句子”并将其分解为单词(或标记)。为了确保语法正确,需要解析器。解析器通常采用标记并构建一棵树,该树产生根节点(单词到句子、段落、页面等)。

From 这个问题 https://stackoverflow.com/questions/1888854/what-is-the-difference-between-an-abstract-syntax-tree-and-a-concrete-syntax-tre解析器似乎会构建 AST。 AST 仅包含执行代码所需的内容,因此不需要括号之类的内容,因为运算符优先级内置于 AST 中。 AST 可能就是编译器所需要的全部。

但是如何将代码从一种语言转换为另一种语言呢?采用一种虚构的语言(语法)或现有的语法并将其转换为另一种语言,其中运算符优先级规则可能会或可能不会不同?运算符优先级是否也“内置”到 CST 中?

举个例子,假设我编写了一种语言并想将其翻译成 PHP 代码。大多数语言中的三元运算符具有从右到左的结合性。 PHP 错误地使用从左到右的关联性(在这里查看更多相关信息 http://en.wikipedia.org/wiki/?:#PHP)。我希望“我的语言”使用从右到左的顺序,但生成的 PHP 代码必须应用括号才能在 PHP 中获得正确的结果(使用链接到维基百科 http://en.wikipedia.org/wiki/?:#PHP,结果需要是“火车”而不是“马”)。

那么对于语言翻译来说,CST 会更好吗?运算符优先级通常内置于 CST 中吗?中间有什么东西吗?是否有任何例子将两棵树与简单的代数方程进行比较?有说明三元运算符的示例吗?

(“转码”是“编程语言翻译”的正确术语吗?谷歌搜索会显示转换媒体。)

我想弄清楚的是:什么时候使用其中一种比另一种更合适?


您所需要的就是对源语言的所有语义细节进行建模的 AST。根据定义,如果它确实正确地建模了语义,并且您的语言包含三元运算符,那么它也将正确地建模应用运算符的特定顺序(例如,优先模覆盖的结果,例如括号)。

所以你的问题不在 AST 中。它使用优先级不同的类似(三元)运算符生成另一种语言。

这是代码生成中的一个古老问题:目标的运算符与源的运算符不太匹配,因此输出不能是一对一的。在您的情况下,您应该能够通过生成带有括号的 PHP 三元运算符来控制顺序以实现原始语义来解决问题,因此这不是一个大问题。

一般来说,生成实现所需结果的代码序列可能非常复杂,并且有很多方法可以实现。这就是为什么编译器书籍厚而不薄的原因。你似乎已经隐含地选择了“获取 AST、行走 AST、吐出代码”;这几乎是一个即时代码生成器。如果您不关心生成的代码是否特别好,并且目标语言与源语言非常接近,那么这种方法就足够了。

如果代码生成问题更复杂,通常会发生的情况是 AST 用于生成计算的数据流模型,由产生结果的运算符组成,并使用先前运算符的结果,以“运算符”为基础获取变量值和常量。然后遍历数据流表示生成代码;这样做的优点是,您可以在数据流表示中选择一个运算符,在目标语言中找到一个匹配的代码序列,生成它,然后担心如何收集操作数。更好的方案将数据流子图(表示等效的复合目标语言结构)与生成的数据流图相匹配;这可以产生明显更好的代码。通常,可以在生成原始代码后应用目标语言特定的优化来生成更好的代码。在这两种情况下,您都必须担心管理运算符结果;它们可以直接输入到下一个目标语言运算符,还是必须进入某种临时存储(对于机器代码,这可以是另一个寄存器或内存位置)。做这一切并不容易;再说一遍,这就是编译器书籍不薄的原因。

这个想法的一个变体是源到源的程序转换。这将源代码中的构造“直接”映射到目标代码中的构造,尽管这通常是通过操作 AST 在幕后完成的,因为未解析的编程语言文本很难匹配。我们的DMS 软件再造工具包 http://www.semanticdesigns.com/Products/DMS/DMSToolkit.html是这种系统的一个例子。使用这样的工具,您可以用源语言编写模式(隐式匹配解析树),并用目标语言编写相应的模式(隐式生成目标语言 AST)。您可以编写复杂的源或目标构造,从而实现上述数据流图匹配的大部分效果。生成后优化包含更多将目标代码转换为目标代码的重写规则。

底线:只有 AST 还不够,除非您的翻译确实很简单。 您可以在这个 SO 答案中详细了解您需要什么:https://stackoverflow.com/a/3460977/120163 https://stackoverflow.com/a/3460977/120163

警告:强烈的意见随之而来。

关于“转码器”:我更喜欢术语“编译”、“翻译”或“源到源”编译器。我构建程序分析和操作工具已有近 40 年的历史。我从来没有听说过“转码器”这个词,直到我遇到这个问题:将旧版 Cobol/PL1 迁移到 Java 的经验 https://stackoverflow.com/q/1029974/120163恕我直言,一个响应描述了一个名为 NACA 的真正糟糕的代码翻译方案。从那以后我就听说这个词越来越受欢迎。我不明白为什么当我们已经有了完全足够的术语时我们还必须发明另一个术语。通常这是某人发明了高级祭司的标志。 “让我们发明一个闪亮的新术语,这样人们就不会真正理解我们在做什么”。我很高兴把这个词留给如此糟糕的翻译。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

何时使用抽象语法树或具体语法树? 的相关文章

  • 最好的 C++ 编译器是哪个? [关闭]

    就目前情况而言 这个问题不太适合我们的问答形式 我们希望答案得到事实 参考资料或专业知识的支持 但这个问题可能会引发辩论 争论 民意调查或扩展讨论 如果您觉得这个问题可以改进并可能重新开放 访问帮助中心 help reopen questi
  • 错误:在 Java 中声明布尔值时不是一个语句

    下面的代码 boolean continue false 返回以下错误 error not a statement boolean continue false 为什么会发生这种情况 我对布尔值非常熟悉 试试这个 boolean cont
  • 字节码和位码有什么区别[重复]

    这个问题在这里已经有答案了 可能的重复 LLVM 和 java 字节码有什么区别 https stackoverflow com questions 454720 what are the differences between llvm
  • 警告:格式“%d”需要类型“int *”,但参数 2 的类型为“int”

    所以我是 C 的新手 并且对这个警告发生的情况遇到了麻烦 该警告是什么意思以及我该如何解决它 我写的代码在这里 void main void char name int age 0 printf input your name n scan
  • 特殊名称属性还允许哪些其他巧妙的技巧?

    研究中一个问题 https stackoverflow com questions 13259162 vb net power operator overloading from c sharp关于实现 Visual Basic Power
  • 是否可以用 C# 为 Android 编写应用程序?

    我们都知道Android运行Dalvik VM程序 通常开发人员用 Java 编写程序并将其编译为 Dalvik 字节码 我想知道是否有可能创建一个可以接受 C 代码并将其编译为 Dalvik 字节码的编译器 嗯 这是一种选择 或者您可以在
  • Flash Builder 条件编译变量

    我正在使用 Flash Builder 4 5 并且我想在调试和发布版本之间使用条件编译 我了解如何使用条件编译以及如何定义编译器常量 我需要的是 IDE 在调试和发布版本之间设置的预定义常量 一种在调试和发布版本之间为编译器指定不同参数的
  • C# 编译器如何决定发出可重定向的程序集引用?

    NET Compact Framework 引入了可重定向程序集引用 现在用于支持可移植类库 基本上 编译器会发出以下 MSIL assembly extern retargetable mscorlib publickeytoken 7C
  • 可以读取目标文件吗?

    我很好奇 obj文件 我几乎不知道它们是什么 或者它们包含什么 所以我用 Vim 文本编辑器打开它们 我在里面发现了一种类似外星人的语言 有什么办法可以理解它们代表什么以及它们的内容是什么 另外 它们的用途是什么 Thanks Sure 但
  • C# 中的 C/C++ 代码编译器

    在 C 中 我可以使用下面的代码编译 VB 和 C 代码 但无法编译 C C 代码 有什么办法可以做到这一点吗 C 编译器 public void Compile string ToCompile string Result null st
  • ubuntu 的 CSS 更少(并且自动编译)? [关闭]

    很难说出这里问的是什么 这个问题是含糊的 模糊的 不完整的 过于宽泛的或修辞性的 无法以目前的形式得到合理的回答 如需帮助澄清此问题以便重新打开 访问帮助中心 help reopen questions 我尝试过 simples 但现在 l
  • 来自行号的方法名称

    给定特定类源代码 Java C 的行号 是否有一种简单的方法来获取它所属的方法的名称 如果它落入其中 大概使用抽象语法树 这对于将 checkstyle 的输出限制为仅触及的方法很有用 我假设您必须使用抽象语法树来执行 Line gt Me
  • BISON + FLEX 语法 - 为什么标记被连接在一起

    我想了解为什么 BISON 按照以下规则连接两个标记 stmt declaration assignment exp ID lt this rule fprintf stderr n my id is s 1 如果你检查输出就会明白我的意思
  • C# 编译器不会优化不必要的强制转换

    前几天 在写答案的时候这个问题 https stackoverflow com questions 2208315 why is any slower than contains在这里 关于溢出 我对 C 编译器感到有点惊讶 它没有按照我的
  • 为什么 VC++ 编译器 MOV+PUSH args 而不是仅仅 PUSH 它们? x86

    在 VC 的反汇编中 正在进行函数调用 编译器在压入本地指针之前将其 MOV 到寄存器 memcpy nodeNewLocation pNode sizeCurrentNode 0041A5DA 8B 45 F8 mov eax dword
  • Android Studio错误的含义:未注释的参数覆盖@NonNull参数

    我正在尝试 Android Studio 创建新项目并添加默认值后onSaveInstanceState方法创建 MyActivity 类 当我尝试将代码提交到 Git 时 我收到一个我不明白的奇怪错误 代码是这样的 我得到的错误是这样的
  • 什么是应用程序二进制接口 (ABI)?

    我从来没有清楚地理解什么是 ABI 请不要向我指出维基百科文章 如果我能理解的话 我就不会在这里发这么长的帖子了 这是我对不同接口的看法 电视遥控器是用户和电视之间的接口 它是一个现有的实体 但本身没有用 不提供任何功能 遥控器上每个按钮的
  • 为什么在 Java 7 中使用方法重载时,自动装箱不会推翻可变参数?

    我们的 Java 项目中有一个 LogManager 类 如下所示 public class LogManager public void log Level logLevel Object args do something public
  • 编译过程

    谁能解释一下编译是如何工作的 我似乎无法弄清楚编译是如何工作的 更具体地说 这是一个例子 我正在尝试在 MSVC 6 中编写一些代码来加载 Lua 状态 我已经 设置库的附加目录并将文件包含到正确的目录中 使用 extern C 因为 Lu
  • 为什么使用小于 32 位的整数?

    我总是喜欢使用最小尺寸的变量 这样效果就很好 但是如果我使用短字节整数而不是整数 并且内存是 32 位字可寻址 这真的会给我带来好处吗 编译器是否会做一些事情来增强内存使用 对于局部变量 它可能没有多大意义 但是在具有数千甚至数百万项的结构

随机推荐

  • 具有身份服务器 4 的 asp.net Web 表单客户端

    我有一个 asp net 解决方案 其中包括 1 asp net identity server rc 3 2 asp net Core web api 3 asp net webform not in asp net core clien
  • Magento Checkout:无需迭代即可获取小计价值

    有什么办法可以直接得到小计吗 根据这个网站 http sleekd com general how to set up tax rules for sales within canada in magento 您可以通过以下方式获取小计 t
  • 子域和本地安装的 Rails 应用程序

    我不明白我忽略了什么 也许它是显而易见的或缺乏理解 我正在使用的应用程序使用托管服务器上正常工作的子域 我认为本地安装会引发一些有关路由的问题 因此我阅读了有关更改 etc hosts 和使用 Ghost gem 的内容 两者似乎都工作正常
  • 即使在 CallBase = true/false 之后,原始方法仍然会在 Moq 中被调用

    这是我的code public class Bar public class Foo public string Name get set public Bar TheBar get set public class Dependency
  • 为什么对依赖单例的系统进行单元测试很困难?

    我读过支持和反对使用单例模式的案例 一种常见的反对案例描述了单例单元测试的困难 但我不清楚这是为什么 如果单元测试是构建的一部分 您难道不能只引用单例并在需要时使用它吗 我从java的角度思考 但我想这不重要 关于此的一篇很棒的文章是单身人
  • C 和 C++ 中的静态变量

    声明为的变量之间有什么区别吗static在 C 和 C 之间的任何函数之外 我读到了static意味着文件范围和变量在文件之外不可访问 我还读到 在 C 中 全局变量是static 那么这是否意味着C中的全局变量不能在另一个文件中访问 不
  • 使用 foreach 循环来初始化变量

    我构建了一个空关联数组 其键名引用提交的帖子数据 我可以很好地捕获后数据 但在尝试实例化名称与数组键匹配的变量时遇到了麻烦 例如 insArray array rUsername gt rPass gt rQuestion gt rAnsw
  • 永久修改启动 Activity 的 Intent

    我想发送一个意图来启动一个活动 我希望能够修改该意图 然后 当活动被销毁并重新创建时 我希望当我调用时这些修改仍然存在getIntent 目前 只要 Activity 没有被销毁 修改意图就可以正常工作 如果有 那么当重新创建 Activi
  • 根据拖放位置对 firestore 中的文档进行排序

    我的目标是呈现我的LinkContainer组件 以便它们位于我的拖放上下文中
  • 如何修复 MSSQL 上的“无效列名”SQL 异常

    我试图在运行时传递要在代码中检查的列名称和值 不过我得到的是 无效的列名 例外 代码如下 cmd new SqlCommand con Open cmd Connection con cmd CommandText INSERT INTO
  • ASP.NET MVC3 RC2 不工作

    我的输入装饰如下
  • 如何获取 Java Hashmap 上冲突数量的指标?

    我正在实现一个自定义哈希函数 如果我在 HashMap 存储桶中发生多次冲突 我如何知道存储桶中存储了多少元素 API 中没有对此直接支持 成员变量table用于存储存储桶的 甚至不是公共的 因此扩展该类不会让您走得太远 假设您正在评估哈希
  • 从数据列表中选择项目时,为什么值末尾的空格会消失?

    我遇到了一个奇怪的问题 当使用数据列表时 值末尾的空格消失了 这让我想知道为什么 我使用的是谷歌浏览器 我可以确保末尾的空格将包含在 通过将最终结果分配给值属性 而不是介于
  • CSS中first-line和first-child的特殊性?

    我有以下 html 代码 p asdasdasdsad br sdfsdfs p 输出是 asdasdasdasd sdfsdfs 但是 我的想法是 p 标签是 body 的第一个子标签 first child 是一个伪类 其特异性为 10
  • $authWithPassword 不是 AngularFire 2.x 中的函数

    我以前看过有关此问题的帖子 但它们要么已经过时 要么提供与我的设置非常相似的解决方案 基本上 我的控制器中有两个函数 authCtrl login 和 authCtrl register 寄存器对 Auth createUserWithEm
  • javascript 相当于 java 的 Map.getKey()

    我有一个地图 或者说 JavaScript 中的关联数组类型的结构 var myMap one 1 two 2 three 3 要获取与给定值相对应的键 我必须迭代映射 function map test value var myMap o
  • 删除 Mac 上的 Qt 库

    我想删除已安装的 Qt 4 8 库并在我的 Mac 上安装 Qt 4 6 库 但是当我尝试安装它们时 我得到 Qt 库无法安装在此磁盘上 较新版本的 该软件已存在于该磁盘上 我删除了 usr local Qt4 8 x文件夹 但消息仍然存在
  • Rmd 文件中的 knit_child 正在打印不需要的输出

    我已经成功使用了knit child生成pdf文件 遵循以下代码http yihui name knitr demo child http yihui name knitr demo child 但是当我尝试在 Rmd file r res
  • 如何将复杂的 T-SQL 转换为 Linq

    我正在使用 EntityFramework Core 2 0 从事 Asp NET Core 2 0 项目 我正在尝试将现有的遗留 SQL 存储过程转换为 EntityFramework Core 中的 Linq 但我在处理 T SQL 的
  • 何时使用抽象语法树或具体语法树?

    我一直在研究编译器 词法分析器似乎非常简单 取一个 句子 并将其分解为单词 或标记 为了确保语法正确 需要解析器 解析器通常采用标记并构建一棵树 该树产生根节点 单词到句子 段落 页面等 From 这个问题 https stackoverf