Python 中的微小 DSL 实现

Question

我正在研究在 Python 中实现 DSL，我正在寻找一种小型 DSL 语言，它对没有设计和实现语言经验的人很友好。到目前为止，我回顾了 Hy 和 Mochi 两个实现。Hy 实际上是 lisp 的一种方言，而 Mochi 似乎与 Elixir 非常相似。两者对我来说都很复杂，因为我现在的目标是对语言进行原型设计并进行尝试，以找出它是否真的有助于解决问题并适合问题所需的风格。我知道 Python 通过标准库中提供的语言工具得到了很好的支持。到目前为止，我实现了一种确实非常简单的 lisp 方言，我没有使用过任何 python AST，它完全是通过字符串处理实现的，这对于我正在寻找的内容来说绝对不灵活。

是否有任何实现而不是上面提到的两种语言，小到可以研究？

有哪些关于这个主题的好书（从某种意义上说是实用的，不仅限于理论和学术方面）？

学习 Python AST 并使用它的好方法是什么？

就实际生成的字节码的开销而言，是否存在与基于 Python 构建的语言（如 Hy）相关的重大性能问题？

谢谢

Answer 1

您实际上不需要了解很多有关解析的知识来编写自己的语言。

我写了一个库，可以让你轻松做到这一点：https ://github.com/erezsh/lark

这是我的一篇博客文章，解释如何使用它来编写自己的语言：http://blog.erezsh.com/how-to-write-a-dsl-in-python-with-lark/

我希望你不要介意我无耻的插件，但这似乎与你的问题非常相关。

Answer 2

您可以将创建（又一种！）新语言的任务分为至少两个大步骤：

• 句法
• 语义和解释

句法

您需要为您的语言定义语法，并使用产生式规则指定如何从简单的表达式创建复杂的表达式。

示例：LISP 的语法：

expression ::= atom   | list
atom       ::= number | symbol    
number     ::= [+-]?['0'-'9']+
symbol     ::= ['A'-'Z''a'-'z'].*
list       ::= '(' expression* ')'

如何阅读：一个表达式要么是一个原子要么是一个列表；一个原子是一个数或一个符号; 一个数字是……等等。

通常您还会定义一些标记化规则，因为大多数语法在标记级别工作，而不是在字符级别工作。

一旦你定义了你的语法，你需要一个解析器，给定一个句子（一个程序）能够构建派生树或抽象语法树。

例如，对于表达式x=f(y+1)+2，您要获取树：

有几个解析器（LL、LR、递归下降，...）。您不一定需要自己编写语言解析器，因为有一些工具可以根据语法规范生成解析器（LEX & YACC、Flex & Bison、JavaCC、ANTLR；还可以查看可用于 Python 的解析器列表）。

如果你想跳过设计新语法的步骤，你可能想从一个简单的开始，比如 LISP 的语法。在Pyperplan项目中甚至还有一个用 Python 编写的 LISP 解析器。他们使用它来解析PDDL，这是一种基于 LISP 的用于规划的领域特定语言。

有用的读物​​：

• 书籍：编译器：原理、技术和工具，作者： Alfred Aho、Jeffrey Ullman、Monica S. Lam 和 Ravi Sethi，也被称为The Dragon Book（因为封面上有龙）
• https://en.wikipedia.org/?title=Syntax_(programming_languages)
• https://en.wikibooks.org/wiki/Introduction_to_Programming_Languages/Grammars
• 如何定义编程语言的语法
• https://en.wikipedia.org/wiki/LL_parser
• https://en.wikipedia.org/wiki/Recursive_descent_parser
• https://en.wikipedia.org/wiki/LALR_parser
• https://en.wikipedia.org/wiki/LR_parser

语义和解释

一旦你有了程序的抽象语法树，你就想执行你的程序。有几种形式可以指定执行（部分）程序的“规则”：

• 操作语义：一种非常流行的语义。它分为两类：
  • 小步语义：描述计算的各个步骤
  • Big Step Semantics：描述计算的整体结果
• 约简语义：一种基于 lambda 演算的形式主义
• 转换语义：如果您将解释器视为转换系统，则可以使用转换语义来指定其语义。这对于不终止（即连续运行）的程序尤其有用，例如控制器。

有用的读物​​：

• 书：操作语义的结构方法[ pdf 链接] 作者 Gordon D. Plotkin
• 书：Gerald Jay Sussman 和 Hal Abelson的计算机程序的结构和解释
• 书：语义工程与 PLT Redex (SEwPR)，作者 Matthias Felleisen、Robert Bruce Findler 和 Matthew Flatt
• https://en.wikipedia.org/wiki/Semantics_(computer_science)
• https://en.wikipedia.org/wiki/Operational_semantics
• https://en.wikipedia.org/wiki/Transition_system
• https://en.wikipedia.org/wiki/Kripke_structure_(model_checking)
• https://en.wikipedia.org/wiki/Hoare_logic
• https://en.wikipedia.org/wiki/Lambda_calculus