摘要：基于这个结论，对某个非终结符展开形式的判定就变得明了起来。但严格的要求一个非终结符最多只能有一个产生式可以导出。这意味着我们必须明确知道每一个非终结符能不能导出。如果集包含这个终结符，则表明该非终结符需要导出。
tao 语言的 Parser 的语法分析是不带回溯的，自顶向下的。文法选用 LL(1)，这种文法虽然略显薄弱，但还尚可用。
回顾上一章提到的 LL(1) 的定义，可以得出如下结论。
在不考虑 ε 时，对于一个非终结符，它的每一个产生式都有一个FIRST 集与之对应。而这些 FIRST 集彼此不相交。
这个特征很有用，因为这个特征很容易得出以下结论。
对于某个非终结符的所有产生式而言，任取一个终结符，该终结符……
要么不属于任何一个 FIRST 集；
要么仅属于某一个FIRST集，从而找到唯一的一个产生式与之对应。
基于这个结论，Parser 对某个非终结符展开形式的判定就变得明了起来。将从 Tokenizer 处读取到的 Token（即非终结符）递归的与非终结符产生式的 FIRST集做比较，一旦找到一个 FIRST 包含该 Token，即挑选该 FIRST 集对应的产生式。
整个过程可一气呵成，不需要进行任何回溯。
但这么做之前，我们必须知道每一个非终结符的所有产生式的 FIRST 集。嗯，这是必要的，赶紧记在小本子上吧，在将来的章节中我们必须要写求 FIRST 集的程序。
好，假设我们已经求出所有非终结符产生式的 FIRST 集了，是不是就可以开始写 Parser 了呢？非也，之前的结论是建立在“不考虑 ε”的前提下。
所以，让我们来讨论允许 ε 的情况。
如果产生式中可能出现 ε，那么每一个产生式中的非终结符都有可能导出 ε 的嫌疑。但 LL(1) 严格的要求一个非终结符最多只能有一个产生式可以导出 ε。这意味着我们必须明确知道每一个非终结符能不能导出 ε。好在这并非难事，让我们观察，对于。
A → α | β | ε
而言，不用说 A 肯定能导出 ε，我都抓到现行了你还说没有？！不解释，它就可以导出 ε。
对于，
B → abide
可以肯定，不能导出 ε，因为产生式右边全是终结符，终结符是不可能再展开的，因此我眼睛没看到 ε，它就导不出 ε。
但是，这种情况就比较暧昧了，
C → αβγ
因为 α、β、γ 三个是式子，能不能导出 ε 真说不准。不过可以肯定的是，只要有一个式子不能导出 ε，那么 C 一定无法导出 ε。因为那个导不出 ε 的式子永远不会“消失掉”，它霸占的位置最终会变成一组终结符串，故 C 绝不可能为空。反过来，只有当所有的式子都能导出 ε 的时候，C 才能导出 ε。
于是，判断式子是否可以导出 ε 的条件呼之欲出。
终结符一定不能导出 ε。
如果存在产生式 A → ε，则非终结符 A 能导出 ε。
如果 A 的一个产生式 A → αβγ... 右侧所有符号都可以导出 ε，则 A 可以导出 ε。
当某个非终结符可以导出 ε 时，Parser 在发现一个终结符的时候，在与其所有产生式的 FIRST 集比较过一次无果后，还可以与 FOLLOW 集比较。如果FOLLOW 集包含这个终结符，则表明该非终结符需要导出 ε。
至此，看来我们不但要事先求出每个非终结符的所有产生式的 FIRST 集，还要判断每一个非终结符是否能导出 ε。这样，我又要在笔记本上多记一条了。
嗯，到这里我已经连续讲了3章理论了，虽然我原本打算尽量少讲理论的，但是现在发现这些东西似乎避免不了。因为之后我要写的东西全部来自这里头。不过，下一章我还会继续讲理论，然后开始写 Parser。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/65505.html
摘要：一个非终结符可以被展开称为一个串，如上定义便是将这个非终结符展开称为一个又终结符和非终结符混合而成的串。特别注意我定义的方法仅仅用于修饰非终结符，而非展开式，虽然这个例子中我的方法更靠近方法，但并意味着用于修饰展开式。 各位久等了，本系列在新一年的连载中，形式会加入少许变化。首先，我会将 tao 语言编译器（以及运行环境）的全部内容贴在 GitHub 上，在阅读本系列的时候，需要对照 ...
摘要：对于而言，终结符与的是对应的。这些内容，我将其称之为终结符的值。对于一个非终结符的产生式对于非终结符，其对象的字段则会表现成如下形式。对于里面的数组，其元素可能为终结符对象非终结符对象或表达式枚举对象。 首先是 TerminalSymbol.java 即终结符。 package com.taozeyu.taolan.analysis; import java.util.HashSet...
摘要：希腊字母表示空，这个产生式表明非终结符可以产生一个空。此外，对于一个文法之中的非终结符，还有集集的概念。对于一个非终结符而言，它的集指可能展开的各种形式中，位于第一的所有终结符所组成的集合。 上一章中，我说 Parser 的工作就是依据文法定义，找到一个与源代码匹配的展开方案就可以了。听起来我们只要先给出一个 tao 语言的文法定义，然后写一个找匹配方案的的程序就可以了。 然而事情情况...
摘要：考虑一个非终结符，如果对于另一个符号，存在如下产生式。则对于而言，它可以表示非终结符重复多次的各种形式。以上三个式子展现了将任意非终结符关于重复次数的多种形式。 式子中的符号，我还允许使用数量词来修饰。考虑一个非终结符 A，如果对于另一个符号 α，存在如下产生式。 α → αA | ε 则对于 α 而言，它可以表示非终结符 A 重复 0 、1、多次的各种形式。 现在稍稍改变这个式子，使...
摘要：而，称之为非终结符。而这个展开方案中对各个非终结符产生式的选择过程，即是对源代码中每一个部分的定性过程。这个过程让能够理解源代码各个部分表示的含义，并以此生成对应的语法树。 我需要定义出 tao 语言的细节，在此，需要引出文法这一概念。所谓文法，即是用于描述语言的一种工具。 例如，一个赋值语句可能写成如下形式： variable = 1 + 3 如何充分定义这个赋值语句的形...
阅读 3325·2021-11-22 12:04
阅读 2707·2019-08-29 13:49
阅读 483·2019-08-26 13:45
阅读 2242·2019-08-26 11:56
阅读 999·2019-08-26 11:43
阅读 589·2019-08-26 10:45
阅读 1267·2019-08-23 16:48
阅读 2158·2019-08-23 16:07
