从零开始写个编译器吧 - LL(1)

Tony 发布于2019-08-14 12:03 / 567人阅读

摘要：希腊字母表示空，这个产生式表明非终结符可以产生一个空。此外，对于一个文法之中的非终结符，还有集集的概念。对于一个非终结符而言，它的集指可能展开的各种形式中，位于第一的所有终结符所组成的集合。

上一章中，我说 Parser 的工作就是依据文法定义，找到一个与源代码匹配的展开方案就可以了。听起来我们只要先给出一个 tao 语言的文法定义，然后写一个找匹配方案的的程序就可以了。
然而事情情况并非如此简单。因为假如我们不对文法定义的形式加诸任何限制的话，让 Parser 找到匹配方案并非很轻易的事情。

因此，我规定，tao 语言的将用 LL(1) 文法来定义。

在简单介绍 LL(1) 文法之前，我还要说明一种比较特别的产生式。

A → ε

希腊字母 ε 表示“空”，这个产生式表明非终结符 A 可以产生一个空。具体来说，如果有如下文法。

S → αAβ

A → ε

那么：

S → αβ

非终结符可以产生空这一特性，令文法的形式更加复杂，但是却是必不可少的。少了这一特征，就很难描述 tao 语言的语法细节了。

此外，对于一个文法之中的非终结符，还有 FIRST 集、FOLLOW 集的概念。

对于一个非终结符 A 而言，它的 FIRST 集指 A 可能展开的各种形式中，位于第一的所有终结符所组成的集合。记为 FIRST(A)。

而 FOLLOW 集，指在整个文法中，非终结符 A 后面可能接的所有终结符组成的集合。记为 FOLLOW(A)。

这么描述可能有点绕，细节先不管，但有一点很重要，即无论是 FIRST 集还是 FOLLOW 集，它们都只能包含终结符。

那么，LL(1) 又是怎样一种文法呢？

对于一个文法而言，如果它的每一个非终结符的产生式

  A → α | β | γ ……

都满足如下三个条件，则将这个文法称之为 LL(1) 文法。

对于所有不能导出 ε 的表达式 α、β、γ……，都有，FIRST(α)、FIRST(β)、FIRST(γ)……两两互不相交。

最多只有一个表达式可以导出 ε。

如果有一个表达式可以导出 ε，那么对于其他不可以导出 ε 的表达式 ξ，有，FIRST(ξ) ∩ FOLLOW(A) = Φ。

最后一条有加粗，当然并非因为它对 LL(1) 本身很重要，而是因为我在实现 Parser 的时候并没有完全遵守这一条。某种意义上说，tao 语言的 Parser 并非严格遵守 LL(1) 文法，因此在此加粗这条，以便与后面的章节呼应。

GPU云服务器云服务器从零开始 linux从零开始 python从零开始从零开始php

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64261.html

从零开始写个编译器吧系列

摘要：是的，这个系列将呈现一个完整的编译器从无到有的过程。但在写这个编译器的过程中，我可不会偷工减料，该有的一定会写上的。该语言的虚拟机将运行于之上，同时编译器将使用实现。我早有写编译器的想法之前没写过，故希望一边写编译器一边完成这个系列。是的，这个系列将呈现一个完整的编译器从无到有的过程。当然，为了保证该系列内容的简洁（也为了降低难度），仅仅保证编译器的最低要求，即仅能用。但在写这个编译...

genedna 2019-08-14 11:58 评论0 收藏0
从零开始写个编译器吧 - 分析非终结符

摘要：基于这个结论，对某个非终结符展开形式的判定就变得明了起来。但严格的要求一个非终结符最多只能有一个产生式可以导出。这意味着我们必须明确知道每一个非终结符能不能导出。如果集包含这个终结符，则表明该非终结符需要导出。 tao 语言的 Parser 的语法分析是不带回溯的，自顶向下的。文法选用 LL(1)，这种文法虽然略显薄弱，但还尚可用。回顾上一章提到的 LL(1) 的定义，可以得出如下结...

snifes 2019-08-14 15:15 评论0 收藏0
从零开始写个编译器吧 - 开始写词法分析器（3）

摘要：在之前的章节第章从零开始写个编译器吧开始写词法分析器中我有说，我将函数设计成主动调用的形式，而则是被动调用的形式。接下来本系列将进入编写语法分析器的阶段，不过在此之前，我将抽出一点时间介绍一下语言本身。上周周末旅游去了，就没更新了，虽然回到海拔0m的地区，不过目前似乎还在缺氧，所以本次就少更点吧。这章将结束词法分析的部分。在之前的章节（第7章从零开始写个编译器吧 - 开始写词...

Barrior 2019-08-14 12:03 评论0 收藏0
从零开始写个编译器吧系列——将在 GitBook 上以在线电子书的形式继续连载

摘要：各位抱歉了，这个系列在多个平台的专栏上连载。所以，我把从零开始写个编译器吧弄到了上。以后更新也是先从上开始。从零开始写歌编译器吧更及时的信息可以从我的公众号上获得虽然不怎么写公众号，但是还是挂一下吧各位抱歉了，这个系列在多个平台的专栏上连载。每发一个新章节，都要同步到各个专栏上，于是可能漏掉 Segmentfault 的博客。汗，其实 Segmentfault 这边已经落后很久了。 ...

justCoding 2019-08-14 14:22 评论0 收藏0
从零开始写个编译器吧 - 编译器的结构

摘要：自然，我们还是先从语言的编译器下手吧。在动手写编译器之前，得容我将编译器的结构进行进一步的划分。这些将被语法分析器接收并进行进一步处理。由于本系列将着重于写出编译器，必要的理论和概念还是会交代的。从零开始写个编译器吧编译器的结构的博客自然，我们还是先从 tao 语言的编译器下手吧。在动手写编译器之前，得容我将编译器的结构进行进一步的划分。编译器可视为一个黑盒，从其一端输入源代码，另一...

wudengzan 2019-08-14 11:58 评论0 收藏0