What's a good resource for starting to write a programming language, that's not context free?我希望编写一种有趣的编程语言，但是我所看到的大部分资源都是用于编写上下文无关的语言，但是我希望编写一种像python一样使用缩进的语言，据我所知，它可以 不受上下文限制。 简单来说，上下文无关的语法就是不需要符号表即可正确解析代码的语法。上下文相关的语法可以。 D编程语言是上下文无关语法的一个示例。 C ++是上下文相关的一种。 (例如，T * x是将x声明为指向T的指针，还是将T乘以x？我们只能通过在符号表中查找T来确定它是类型还是变量来辨别。) 空格与它无关。 D使用上下文无关的语法来极大地简化对其的解析，从而使简单的工具可以对其进行解析(例如语法高亮显示编辑器)。 您可能想阅读这篇有关解析Python的写得不错的文章，《 Python：关于缩进的神话》。 虽然我还没有尝试使用yacc之类的东西来编写上下文无关的解析器，但我认为使用条件词法分析器可以返回缩进更改标记(如url中所述)是可能的。 顺便说一下，这是来自python.org的官方python语法：http://www.python.org/doc/current/ref/grammar.txt 首先，我会通读一些有关该主题的文献，以使自己熟悉这个问题。 Aho等人撰写的经典编译器书。等可能在数学和比较科学上比较繁琐，但更具可理解性的文本是Jack Crenshaw的"让我们构建编译器"文章。这是Crenshaw先生在80年代后期写回的一系列文章，这是有史以来关于编译器的最被低估的文字。这种方法很简单并且很关键：Crenshaw先生展示了一种有效的" A"方法。您可以在几个晚上的时间内轻松浏览内容，并更好地了解编译器的用途。需要注意的是，本文中的示例是用Turbo Pascal编写的，编译器发出了68K汇编程序。这些示例很容易移植到最新的编程语言，我为此推荐Python。但是，如果您想按照示例进行操作，则至少需要Turbo Pascal 5.5和68K汇编器和仿真器。今天的文字仍然有意义，使用这些旧技术真的很有趣。我强烈建议将其作为任何有关编译器的第一篇文章。好消息是Python和Ruby之类的语言都是开源的，您可以下载和研究C源代码，以便更好地了解它的完成方式。 "无上下文"是一个相对术语。大多数无上下文解析器实际上都解析该无上下文语言的超集，然后检查生成的解析树以查看其是否有效。例如，根据C的上下文无关文法，以下两个C程序是有效的，但是在上下文检查期间一个很快就会失败：
不受上下文限制， 可以用键盘产生的任何东西都可以解析为上下文无关；至少您可以检查所有使用的字符是否有效(仅包含可显示Unicode字符的所有字符串的集合是无上下文语法)。唯一的限制是语法的实用性以及对生成的分析树必须执行多少与上下文相关的检查。 诸如Python之类的依赖于空格的语言使您的无上下文语法没那么有用，因此以后需要进行更多与上下文相关的检查(大部分检查是在运行时通过动态类型在Python中完成的)。但是，在需要上下文相关检查之前，上下文无关的解析器仍然可以做很多事情。 如果您真的想在语言设计和实现上大吃一惊，则可能需要在书架上添加以下内容：
Gentler的介绍，例如：
您还应该考虑您的实现语言。这是不同语言所提供的便利差异很大的领域之一。您应该考虑使用LISP，F＃/ OCaml和Gilad Bracha的新语言Newspeak等语言。 在语言中使用缩进并不一定意味着该语言的语法不能与上下文无关。即缩进将确定语句在哪个范围内存在。无论在哪个范围内定义，一条语句仍将是一条语句(作用域通常可以在语义解析过程中由编译器/解释器的不同部分处理)。 这就是说antlr工具(http://www.antlr.org)是一个很好的资源。该工具的作者还编写了一本书，内容涉及使用antlr为语言创建解析器(http://www.pragprog.com/titles/tpantlr/the-definitive-antlr-reference)。有相当不错的文档和大量示例语法。 我不知道任何教程/指南，但是您可以尝试查看tinypy的源代码，它是python这样的语言的很小的实现。 如果您以前从未编写过解析器，请从简单的事情开始。解析器令人惊讶地微妙，如果您从未学习过编程语言的结构，则可能会遇到编写它们的各种麻烦。 读Aho，Sethi和Ullman(被称为"龙书")是一个不错的计划。与其他贡献者相反，我说您应该首先使用诸如Yacc和Bison之类的更简单的解析器生成器，并且仅当您因为无法使用该工具执行某些操作而被烧毁时，才应继续尝试使用LL(* )解析器，如Antlr。 您是否读过Aho，Sethi，Ullman："编译器：原理，技术和工具"？这是一本古典语言参考书。 /艾伦 我建议您手动编写解析器，在这种情况下，如果空格很大，则不会出现任何实际问题。 使用解析器生成器的主要问题是很难在解析器中获得良好的错误恢复。如果您计划为您的语言实现IDE，那么良好的错误恢复对于使诸如Intellisence之类的功能至关重要。智慧始终适用于不完整的语法结构，并且解析器越能弄清用户要键入的结构，就可以提供更好的智能体验。 如果您编写了一个手写的自上而下的解析器，则几乎可以实现所需的任何规则，无论您要在哪里。这就是使错误恢复变得容易的原因。它还将使您轻松实现大量的空白。您可以简单地将当前缩进级别存储在解析器类内的变量中，并且当您在换行符的列位置小于当前缩进级别的情况下遇到令牌时，可以停止解析块。同样，您很可能会在语法中遇到歧义。大多数被广泛使用的"生产"语言都具有句法歧义。一个很好的例子是C＃中的泛型(表达式上下文中" <"周围有歧义，它可以是"小于"运算符，也可以是"泛型参数列表"的开头)。在手写解析器中，解决此类歧义是微不足道的。您可以在需要的地方添加一些不确定性，而对其余解析器的影响相对较小， 此外，因为您是自己设计语言，所以应该假设它的设计将快速发展(对于某些带有标准委员会的语言，例如C ++，情况并非如此)。更改自动生成的解析器以处理歧义或发展语言，可能需要您对语法进行大量重构，这既烦人又耗时。手写解析器(尤其是自上而下的解析器)的更改通常非常本地化。 我要说的是，解析器生成器仅在以下情况下是一个不错的选择： 上下文相关的语言？这个不缩进：Protium(http://www.protiumble.com) 仅仅因为一种语言使用了重要的缩进并不意味着它本质上是上下文相关的。例如，Haskell使用了重要的缩进，并且(据我所知)其语法是上下文无关的。 需要上下文相关语法的源代码示例可能是来自Ruby的以下代码段：
另一个示例是Scala的XML模式：
通常，上下文敏感的语言在任何精确意义上都难以想象，因此不那么常见。甚至Ruby和Scala也不算什么，因为它们的上下文相关功能仅包含该语言的一小部分子集。如果我是你，我会按照灵感的指示来表达我的语法，然后担心以后再解析方法论。我想您会发现，无论您想出什么，都自然会与上下文无关，或者非常接近上下文。 最后一点，如果您确实需要上下文相关的解析工具，则可以尝试一些不太严格的形式化技术。解析器组合器用于Scala的解析中。它们有一些烦人的限制(没有词法)，但是它们并不是一个坏工具。像ANTLR这样的LL(*)工具似乎也更擅长表达这种"临时"解析转义。不要尝试将Yacc或Bison与上下文相关的语法一起使用，它们对于严格表达此类概念非常严格。 |
