python - 什么是开始编写编程语言的好资源，不是上下文无关的？

Question

我正在寻找一种有趣的编程语言，但是我所看到的大部分资源都是用于编写无上下文语言的，但是我希望编写一种像 python 一样使用缩进的语言，据我所知，这意味着它可以不要与上下文无关。

score 19 · Accepted Answer

简单地说，上下文无关文法是不需要符号表即可正确解析代码的文法。上下文相关的语法可以。

D 编程语言是上下文无关文法的一个例子。C++ 是一种上下文敏感的。（例如，T*x 是声明 x 是指向 T 的指针，还是将 T 乘以 x ？我们只能通过在符号表中查找 T 来判断它是类型还是变量。）

空白与它无关。

D 使用上下文无关文法是为了大大简化解析它，以便简单的工具可以解析它（例如语法高亮编辑器）。

score 6 · Accepted Answer

您可能想阅读这篇写得很好的关于解析 Python 的文章，Python: Myths about Indentation。

虽然我没有尝试使用 yacc 之类的东西编写上下文无关解析器，但我认为可以使用条件词法分析器来返回 url 中描述的缩进更改标记。

顺便说一下，这里是来自 python.org 的官方 python 语法：http: //www.python.org/doc/current/ref/grammar.txt

score 5 · Accepted Answer

我会首先通过阅读有关该主题的一些文献来熟悉该问题。Aho 等人的经典编译器书籍。人。可能对数学和comp sci 很重，但更平易近人的文本是Jack Crenshaw 的Let's Build a Compiler文章。这是 Crenshaw 先生在 80 年代后期写的一系列文章，也是有史以来关于编译器最不被重视的文章。方法简单明了：Crenshaw 先生展示了“ A" 可行的方法。您可以在几个晚上轻松浏览内容，并且更好地理解编译器的全部内容。需要注意的是，文本中的示例是用 Turbo Pascal 编写的，并且编译器发出 68K 汇编程序。这些示例很容易移植到更新的编程语言，为此我建议使用 Python。但如果您想按照示例进行操作，您至少需要Turbo Pascal 5.5和68K 汇编程序和模拟器. 该文本在今天仍然具有相关性，使用这些旧技术真的很有趣。我强烈推荐它作为任何人关于编译器的第一本书。好消息是 Python 和 Ruby 等语言是开源的，您可以下载和研究 C 源代码，以便更好地了解它是如何完成的。

score 3 · Accepted Answer

“上下文无关”是一个相对术语。大多数无上下文解析器实际上解析了一个无上下文语言的超集，然后检查生成的解析树以查看它是否有效。例如，以下两个 C 程序根据 C 的上下文无关文法是有效的，但在上下文检查过程中一个很快就失败了：

int main()
{
    int i;
    i = 1;
    return 0;
}

int main()
{
    int i;
    i = "Hello, world";
    return 0;
}

没有上下文，i = "Hello, world";是一个完全有效的赋值，但在上下文中你可以看到类型都是错误的。如果上下文是char* i;，那就没问题了。因此，上下文无关解析器不会发现该分配有任何问题。直到编译器开始检查类型（取决于上下文）它才会捕获错误。

任何可以用键盘产生的东西都可以被解析为上下文无关的；至少您可以检查所有使用的字符是否有效（仅包含可显示 Unicode 字符的所有字符串的集合是上下文无关语法）。唯一的限制是您的语法有多有用，以及您必须对生成的解析树进行多少上下文相关检查。

像 Python 这样的依赖于空格的语言会降低上下文无关语法的用处，因此以后需要更多的上下文相关检查（其中大部分是在 Python 中通过动态类型在运行时完成的）。但是在需要上下文相关检查之前，上下文无关解析器仍然可以做很多事情。

score 2 · Accepted Answer

我不知道任何教程/指南，但您可以尝试查看tinypy的源代码，它是类似 python 的语言的一个非常小的实现。

score 2 · Accepted Answer

在语言中使用缩进并不一定意味着该语言的语法不能是上下文无关的。即缩进将确定语句存在的范围。无论在哪个范围内定义语句，它仍然是一个语句（范围通常可以由编译器/解释器的不同部分处理，通常在语义解析期间）。

也就是说，一个很好的资源是 antlr 工具 ( http://www.antlr.org )。该工具的作者还制作了一本关于使用 antlr ( http://www.pragprog.com/titles/tpantlr/the-definitive-antlr-reference ) 创建语言解析器的书。有很好的文档和很多示例语法。

score 2 · Accepted Answer

如果您真的要在语言设计和实现方面有所尝试，您可能需要将以下内容添加到您的书架中：

编程语言语用学，斯科特等人。
编程语言中的设计概念，Turbak 等人。
现代编译器设计，Grune 等。（比起 Aho 等人的《龙之书》，我更喜欢这本书。）

更温和的介绍，例如：

Crenshaw 的教程（这里由@'Jonas Gorauskas' 建议）
Parr 的权威 ANTLR 参考
Martin Fowler 最近在 DSL 方面的工作

您还应该考虑您的实现语言。这是不同语言在它们所促进的方面有很大差异的领域之一。您应该考虑 LISP、F#/OCaml 和 Gilad Bracha 的新语言 Newspeak 等语言。

score 1 · Accepted Answer

你读过 Aho、Sethi、Ullman：“编译器：原理、技术和工具”吗？这是一本经典的语言参考书。

/艾伦

score 1 · Accepted Answer

我建议您手动编写解析器，在这种情况下，有大量空白不应出现任何实际问题。

使用解析器生成器的主要问题是很难在解析器中获得良好的错误恢复。如果您计划为您的语言实现 IDE，那么良好的错误恢复对于让 Intellisence 之类的东西正常工作很重要。智能总是在不完整的句法结构上工作，解析器越能弄清楚用户试图输入什么结构，你就能提供更好的智能体验。

如果你编写一个手写的自上而下的解析器，你几乎可以在任何地方实现你想要的任何规则。这使得提供错误恢复变得容易。它还将使您实现重要的空白变得微不足道。您可以简单地将当前缩进级别存储在解析器类中的变量中，并且当您在新行上遇到列位置小于当前缩进级别的标记时，可以停止解析块。此外，您可能会在语法中遇到歧义。大多数广泛使用的“生产”语言都有语法歧义。一个很好的例子是 C# 中的泛型（在表达式上下文中“<”周围存在歧义，它可以是“小于”运算符，也可以是“泛型参数列表”的开头）。在手写解析器中，解决这样的歧义是微不足道的。您可以在需要的地方添加一点不确定性，而对解析器的其余部分影响相对较小，

此外，由于您自己设计语言，您应该假设它的设计将迅速发展（对于一些有标准委员会的语言，例如 C++，情况并非如此）。对自动生成的解析器进行更改以处理歧义或改进语言可能需要您对语法进行重大重构，这既烦人又耗时。对手写解析器的更改，尤其是自上而下的解析器，通常是相当本地化的。

我会说解析器生成器只有在以下情况下才是一个不错的选择：

你从来没有打算写一个 IDE，
该语言的语法非常简单，或者
您需要一个非常快速的解析器，并且可以接受糟糕的用户体验

score 1 · Accepted Answer

如果您以前从未编写过解析器，请从简单的东西开始。解析器非常微妙，如果您从未研究过编程语言的结构，您可能会在编写它们时遇到各种麻烦。

阅读 Aho、Sethi 和 Ullman（被称为“龙之书”）是一个不错的计划。与其他贡献者相反，我说您应该首先使用更简单的解析器生成器，例如 Yacc 和 Bison，并且只有当您因为无法使用该工具做某事而被烧毁时，您才应该继续尝试使用 LL(* ) 像 Antlr 这样的解析器。

score 0 · Accepted Answer

0

A context-sensitive language? This one's non-indented: Protium (http://www.protiumble.com)

于 2008-09-16T05:04:33.503 回答

score 0 · Accepted Answer

仅仅因为一种语言使用重要的缩进并不意味着它本质上是上下文相关的。例如，Haskell 使用了重要的缩进，并且（据我所知）它的语法是上下文无关的。

需要上下文相关语法的源代码示例可能是来自 Ruby 的以下代码段：

my_essay = << END_STR
This is within the string
END_STR

<< self
  def other_method
    ...
  end
end

另一个例子是 Scala 的 XML 模式：

def doSomething() = {
  val xml = <code>def val <tag/> class</code>
  xml
}

作为一般规则，上下文相关语言在任何精确意义上都稍微难以想象，因此不太常见。甚至 Ruby 和 Scala 也不算数，因为它们的上下文敏感特性只包含该语言的一小部分。如果我是你，我会根据灵感来制定我的语法，然后再担心以后的解析方法。我想你会发现你想出的任何东西都会自然地与上下文无关，或者非常接近它。

最后一点，如果你真的需要上下文相关的解析工具，你可以尝试一些不太严格的正式技术。解析器组合器用于 Scala 的解析。它们有一些烦人的限制（没有词法分析），但它们不是一个坏工具。像 ANTLR 这样的 LL(*) 工具似乎也更擅长表达这种“临时”解析转义。不要尝试将 Yacc 或 Bison 与上下文相关的语法一起使用，它们对于轻松表达这些概念来说太严格了。

python - 什么是开始编写编程语言的好资源，不是上下文无关的？

12 回答 12

Related

Reference