logo标签列表

解析“偏向”（基于缩进）的语言

language-designindentationcompiler-theory
11

一种离线语言是指在该语言中，声明的范围（块）由缩进表示。

...例如Python、Boo、Nemerle、YAML等语言。

那么我的问题是：我应该如何解析这些语言？如何解决制表符与空格的问题（两个制表符或8个空格是否等效）？解析器生成器是否有助于此，还是我必须手动编写词法分析器/语法分析器？

我会将此留作评论，但麻省理工学院的一位教授已经指出，“越界”语言在实际实现中是不好的想法。这只是一些值得思考的食物。 - Woot4Moo
2
@Woot 你能提供一篇文章或类似的链接吗？ - Anton Gogolev
我会再次搜索视频链接，但它来自于麻省理工学院在Youtube上发布的算法导论课程。我稍后今晚再找到它。 - Woot4Moo
哦，天啊，我完全忘记了这件事。 - Woot4Moo
@MasBagol，这是5年前的事了，所以不确定。不过似乎MIT公开课程中包括算法入门课程的内容，你可以从那里开始。 - Woot4Moo
7个回答
9
Python拥有一个生成缩进和取消缩进标记（等同于大括号“{”，“}”）的词法分析器。甚至在Stack Overflow上有一个示例，展示了如何简单实现这样的词法分析器。
关于Tab和空格之间的选择，在Python只有一项编码约定：每个缩进级别使用4个空格。虽然制表符也是合法的语法。
5
最简单的解决制表符与空格问题的方法是禁止使用空格和制表符的组合（例如，F#就是这样做的）。任何现代编辑器都可以将制表符转换为一定数量的空格。
至于是否需要放弃解析器生成器，可能不需要，但您必须在其中某个地方进行缩进标识的修改。这可能需要您进行一些创意。根据浏览F#源代码的经验，看起来他们使用后词法分析步骤创建额外的令牌来表示缩进语言元素。
4
取决于编辑器的设置，如果两个制表符等于八个空格，则可以解决制表符与空格问题。
原始作者所表达的侧面规则提到了两行代码的相对位置而不是绝对空格数量。这里是一篇很好的文章，可以帮助您更好地理解（并引用一些内容）：
“在Python源代码中，空格很重要。” 不是普遍意义上的。只有语句缩进级别很重要（即语句最左边的空格）。在其他任何地方，空格都不重要，可以像其他任何语言一样随意使用。您还可以插入什么都没有（或只包含任意空格）的空行。 此外，缩进的确切数量一点也不重要，但是嵌套块的相对缩进（相对于彼此）才是重要的。[...]
2
就此而言，Haskell 也是基于缩进的语言，并且在空格不便时可以选择使用 { foo; bar; etc } 的格式。我用 Parsec 写过一个简单的基于缩进的解析器，它被设计成类似 Lisp 的读法，但缩进表示操作符应用。括号只能在一行上使用。我写了一个简单的基于缩进的解析器，其中用到了 Parsec。请保留 HTML 标签。
(aaa bb) cc
         e fffff (ggg hhh) iii
                 jjj kkk
         ddd

这里将aaa应用于bb。结果是一个三元函数，它被应用于参数cc、应用于一个参数的e和ddd。请注意，应用是基于列对齐而不是X空格的。

解析器可能也可以更简单。

1

关于制表符和空格，您有几个选项：禁止混合使用制表符和空格，假定制表符与空格的比例固定，或允许程序员根据每个项目或每个源文件的情况来决定（一种类似于“#pragma tab(4)”样式指令，以允许使用制表符和/或更改它们所代表的空格数）。

ANTLR 3等解析器生成器可以轻松处理此问题；我自己也玩过一个示例，编译到其C#目标。DirkGently's answer中的链接解释了Python算法，可直接转换为代码。我的方法只是为空格和换行符定义单独的标记，并覆盖了词法分析器使用的“发出标记”函数，以便在运行时插入额外的缩进/取消缩进标记。这比我看到的其他方法要简单得多，但两种方法都很有效。

0
我正在为一种基于缩进的语言编写一个解析器。到目前为止，这个工作涉及了很多手动编码。我想尝试做一下Python提到的去缩进/缩进的事情，但说实话有点难。
我将它分为三个阶段：
  1. 标记化
  2. 指导
  3. 构建树结构
标记化阶段大约有100行代码，加上正则表达式的定义。它会生成一系列有用的标记。

"指导"阶段（或“折叠”阶段）获取标记并基本上生成推送和弹出，以创建树形数据结构的指令。它实际上是将列表折叠成树。

最终的"树化"阶段获取树形指令并实际构建树。事实证明这相当困难，需要进行思维上的体操来考虑如何将标记列表转换为树。我整个周末都在尝试使其工作，但仍然有很长的路要走，才能使输出树与推送和弹出正确对齐。

尽管代码水平不算太高，但它应该作为构建基于缩进的解析器的现实世界示例。

-1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接