在通用编程语言里，符号表是一个极其关键的对象。在编译的不同阶段，它所起到的作用存在差异。一般而言，它主要服务于标识符，像变量名、函数名、类名等，为编译器提供了一种高效的方法来组织和访问与标识符相关的各类属性。在实现方面，符号表的数据结构常常是哈希表，它保存了某类符号（通常是标识符对应的词素）和标识符对象之间的映射关系。这些信息一般是在语法分析阶段由语法分析器收集起来的，并且在后续过程中会不断得到完善。

        在DSL的语境下，符号表的概念和通用编程语言类似，通常也会采用哈希表结构。其中，键的部分存储的是语义模型的名称，值的部分则是语义模型或者语义模型构建器的实例。

        正如前面所提到的，本文的重点是符号表。笔者会通过一个十分简单的案例，向大家展示如何在语法分析过程中使用符号表。同时，笔者还打算展示如何针对不同的作用域设置不同的符号表对象。虽说在DSL领域很少会用到作用域的概念，但这类扩展性的知识说不定在某个时候就会派上用场，所以读者有必要对这方面的内容多一些了解。

        笔者曾在前面文章中对符号表的作用进行了简单的说明。作用上，它就像一个数据库，存储了源代码中的各种标识符信息，如变量名、方法名等，其主要功能如下列表所示：

1. 记录标识符信息。主要包括标识符的名称、作用域、类型等内容。有些语言如C++或Java，要求标识符在使用前必须先进行声明，这种情况下就需要使用到符号表来帮助判断标识符是否已经存在。
2. 语义检查。对于大部分静态语言而言，如Java、C#等都不允许在同一作用域内对标识符进行重复性地声明。此外，变量类型的转换也存在一定的限制。以Java为例，我们不可以使用这样的语句进行赋值操作：int x = "lexeme"，因为整形类型的变量x不可以接受字符串类型的对象作为它的值。由于符号表中存储了标识的属性信息，比如声明位置、类型等，所以针对上述两种情况，都可以借用它来辅助变量重复声明检查和类型转换检查。

        为加深读者对符号表的理解，笔者将通过一个最简单的例子——Maven配置文件解析，向您展示何时、何地以及如何使用符号表对象。需要注意的是，后文所展示的代码仅仅是笔者个人的一种假设与猜想，并非Maven源代码。

        书归正文。如果您经常使用Maven来构建项目的话，一定会对代码4-1所示的内容感到熟悉，其被用于配置项目的依赖项（即类库），不过内容有所省略。

代码4-1


<project>
	<properties>
		<ehcache>3.0.0</ehcache>
	</properties>
	...
	<dependencies>
		<dependency>
			<groupId>org.ehcache</groupId>
			<version>${ehcache}</version>
		</dependency>
	<dependencies>
</project>

        代码4-1虽然使用XML写成，但其在当前场景中也是一种外部DSL，这一点相信读者不会有任何疑问。下面，笔者将以上述代码为例，展示如何对其进行语法解析，以及解析过程中符号表是如何被创建和使用的。

        首先展示的当然还是语义模型，如图 4.1所示。简单起见，笔者只展示当前案例所关注的内容，毕竟Maven配置文件的结构还是很复杂的，我们不可能在一张图中将所有的语义模型全部展示出来。值得注意的是，尽管笔者一直强调语义模型应该是充血模型，但在本案例中，它们当中的大部分却是贫血的。不过这种情况也实属正常，配置文件主要用于表现数据，而语义模型的形态也是由业务特性来决定的。

图 4.1 Maven依赖项配置语义模型 

        图 4.1所示的语义模型之中，Config是聚合根对象，其包含了两个成员变量：表示依赖信息集合的DependencySet和表示属性信息集合的PropertySet，所对应的是代码4-1中的dependencies和properties两个节点。DependencySet对象聚合了多个Dependency类型的对象，后者对应于dependency节点。PropertySet的设计思路同DependencySet，我们不做过多赘述。可以看到，语义模型的结构与DSL代码的结构是可以匹配得上的。

        本案例所涉及的语义模型代码片段如代码4-2所示：

代码4-2

class Config {
    PropertySet properties = new PropertySet();
    DependencySet dependencies = new DependencySet();
}

class DependencySet {
    List<Dependency> dependencies = new ArrayList<>();
}

class Dependency {
	Dependency(String groupId, String version) {
		this.groupId = groupId;
		this.version = version;
		if (!StringUtils.hasLength(groupId)
				|| !StringUtils.hasLength(version)) {
			throw new SemanticsException("no groupId or version");
		}
	}
}

class PropertySet {
    Map<String, Property> properties = new HashMap<>();
}

class Property
	Property(String key, String value) {
		this.key = key;
		this.value = value;
		if (!StringUtils.hasLength(key)
				|| !StringUtils.hasLength(value)) {
			throw new SemanticsException("no property name or value");
		}
	}
}

        上述代码中,有两处值得注意的点：类Dependency和类Property构造函数的实现。笔者在其中加入了用于语义检查的逻辑，即当输入参数为空字符串的时候，抛出语义异常SemanticsException。那么问题来了，当前实现在是语义模型中进行信息的检查，这一操作是否可以转移到语法分析逻辑中呢？技术上是可以实现的，不过笔者觉得目前的设计要更好一点，具体原因如下：

1. 语法分析器只应负责检查语法格式是否正确。以依赖项配置（即dependency节点）这一部分代码为例，语法分析所要检查的是dependency节点下面是否包含了groupId和version这两个子节点，而节点值是否合法并不需要它来负责检验。类似上一章对词法分析器责任的论述，它的责任就是Token分解，不负责对代码的语法进行检查。
2. 由语义模型负责检查业务数据的正确性。涉及业务信息的校验，比如version的值是否是个非空的字符串，是否在properties中存在该值的定义等应该是语义模型的任务，我们应该将这一责任从语法分析器中拆分出来。

        当然，就当前案例来说，确实没必要过于严格。我们也完全可以把“groupId节点中必须包含值”当作语法的一部分，然而这种做法并不具有普遍适用性。例如，对于version节点值的验证，我们完全能够设置一个在properties中不存在的信息。这样的代码能够通过语法分析，但是语义分析却通不过。所以，笔者更想要强调的是责任的划分，而不是具体的实现方式，读者在实现过程中也要留意语义检查和语法检查的分离，特别是当DSL的结构较为复杂的时候。

        在完成语义模型的设计之后，接下来要呈现的是DSL解析程序的实现。请读者思考这样一个问题：对于XML格式的DSL，是否还需要我们自己去实现词法分析器和语法分析器呢？答案是否定的。XML语法分析器是现成的，比如JDK中所提供的基于DOM（文档对象模型，简称：DOM）的XML解析器。我们真正需要做的，是语法分析之后的步骤，也就是如何把DSL解析成语义模型。

        针对当前案例，既然JDK已经提供了解析XML的库，我们只需要拿来使用就可以了。一切不符合XML语法的问题如缺少结束元素符号等都会被自动检测出来，这一点不需要研发人员去操心。因此，我们可以跳过语法分析的环节（XML解析相关的代码也进行了省略），直接进入到语义模型的构建阶段，代码4-3展示了DSL分析程序的定义：

代码4-3

class ConfigParser {
	Map<String, Property> properties = new HashMap<>();
	Map<String, Dependency> dependencies = new HashMap<>();

	Config parse() {
		this.parseProperties();
		this.parseDependencies();
         ...
		return config;
	}
}

        ConfigParser类中引入了两个关键字段：properties和dependencies，分别用来存储语义模型Property和Dependency的实例。这两个对象就是我们的主角：符号表。是不是简单的出乎意料？其实很多东西本来也没有想象的那么深奥。编译原理这门学科所涉及的内容的确比较多，但很多概念到了DSL领域之中就变得简单了。符号表就是典型的案例，大部分情况下其所承担的角色也许仅仅是个临时存储区。

        回归正文。为什么要将这两个符号表对象引入到分析程序中呢？因为我们在version节点中引用了属性节点properties中定义的值，即${ehcache}，该引用符号需要在语义模型的构建过程中被替换为真实的值。虽然方法parse()在其执行过程中会建立一棵如图 4.2所示语法分析树，同时由于DOM树的存在，也允许我们在执行parseDependencies()方法的时候访问properties中的信息，但如果每次需要引用属性信息的时候都去进行DOM树的遍历，性能就未免太过低效了。针对这一问题，最简单的解决思路就是在解析图 4.2中的左子树的时候，将构建出的语义模型暂存起来。也就是说将Property类型的实例放到符号表中，当实例化Dependency模型的时候，只需要根据version节点中引用的属性名（针对当前案例，属性名为ehcache）直接从符号表中检索对应的Property实例即可。通过该实例，就可以获取到引用的实际值。符号表dependencies的作用也是类似的，构建语义模型聚合根对象Config的时候会被使用到。

图 4.2 Maven配置案例语法分析树（局部）

        对于当前案例，“符号表”实际上就是一个语义模型实例的缓存区域。但需注意，符号表的功能不止于此，其应用场景也较为灵活。目前，我们仅在语义模型构建阶段运用了符号表。后续内容中，笔者将进一步介绍如何在词法分析和语法分析阶段使用符号表。

        让我们继续对代码进行分析。parse()方法内部调用了两个子方法来构建语义模型，其中parseProperties()方法主要用于构建Property的实例，逻辑比较简单，让我们直接将其跳过，着重看一下方法parseDependencies()的实现。其被用于构建Dependency的实例，如代码4-4所示：

代码4-4

void parseDependencies() {
	List<Node> dependencies = this.getChildNodes("dependencies");
	for (Node dependency : dependencies) {
		List<Node> childNodes = this.getChildNodes(dependency);
		String groupId = parseGroupId(childNodes);
		String version = parseVersion(childNodes);
		this.dependencies.put(groupId, new Dependency(groupId, version));
	}
}

        方法内部又分别调用了两个方法对version、groupId的节点值进行解析。结合parse()方法，您会发现笔者所给出的解析方式是按层展开的，这种解析手段类似于自顶向下语法分析。不过，也仅仅是“类似”，类ConfigParser的整体运行逻辑并不包括语法分析，所有使用到的方法都是用于构建语义模型，或者更确切地说，是在遍历抽象语法树的过程中建立语义模型实例。这样的说法让人感到奇怪，并没有看到抽象语法树，怎么又说是对其进行遍历呢？

        对上述问题进行解答之前，请读者首先看一下代码4-5：

代码4-5

Document document = DocumentBuilderFactory.newInstance()
		.newDocumentBuilder()
		.parse(new File("mavenConfig.xml"));

        上述代码的逻辑比较简单，主要用于解析XML文件。每当调用parse()方法的时候，程序都会对XML的格式进行校验并在内存中建立出一棵树形结构，如图 4.3所示。这棵树就是文档对象模型，不过在DSL的上下文中，笔者更愿意称其为抽象语法树。当您选择JSON或XML作为DSL实现语言的时候，其最大的优势就是不需要我们手写语法分析代码，仅需“动动手指”便可得到一棵结构良好的抽象语法树（如DOM解析）或现成的语义模型实例（如JSON反序列化）。读者可能会问：既然优势这么明显，为什么还要费劲自己设计一套全新的DSL呢？具体原因有二：

1. 使用XML和JSON作为DSL载体的时候，里面会充斥着很多的语言噪声，这使得实现代码看起来非常的不简洁。
2. XML和JSON虽然标准化程度很高，但对于DSL而言还是过于笨拙了，灵活度存在着明显的不足。

图 4.3 案例DSL解析过程中所建立的DOM树（即抽象语法树）

        有些跑题，让我们继续代码4-4的学习。简单起见，笔者仅对其中的parseVersion()方法片段进行展示，如代码4-6所示：

代码4-6

String parseVersion(List<Node> childNodes) {
	String version = parseNodeValue(childNodes, "version");
	if (version.matches("^\\$\\{[a-zA-Z0-9-\\.]+\\}$")) {
		version = version.substring(2, version.indexOf("}"));
		Property property = this.properties.get(version); //重点代码
		if (property == null) {
			throw new SemanticsException("cannot find property for version:" + version);
		}
		return property.value;
	}
	return version;
}

String parseNodeValue(List<Node> childNodes, String nodeName) {
	Node node = getByName(childNodes, nodeName);
	if (node == null) {
		throw new ParseException("cannot find node:" + nodeName);
	}
	return node.getTextContent();
}

        在上述示例的两个方法中，均包含了语义规则检测的代码，当检测未通过时会抛出异常以终止整个分析过程。需要注意的是，这样的设计是合理的，因为我们的代码处于语义模型构建环节，而非语法分析环节，所以并不违反笔者多次强调的“不应在语法分析阶段抛出语义异常”这一原则。

        “重点代码”注释所标识的代码是另一个值得关注的地方，它引用了符号表properties来查询属性信息。读者可能会对另一个符号表dependencies产生疑问，既然它仅在构建Config对象时被使用，那么是否真的有必要为其建立一个符号表呢？对于当前案例而言，这样的设计确实可能显得有些多余，但笔者更倾向于采用一致的编程模型，即在分析属性信息时建立一张包含属性对象的符号表，在分析依赖信息时建立一张包含依赖对象的符号表。也就是说，如果DSL中还存在其他类型的节点，我们都会为其建立相应的符号表。这种设计并不会消耗过多的精力，反而更有助于语法分析器后续的扩展。此外，笔者所展示的内容仅仅是代码片段，完整的Maven配置解析代码必然会存在对依赖项对象的引用，显然，在这种情况下为其引入对应的符号表是非常必要的。

        还需提醒读者，使用多个符号表仅是一种设计选择，实际上也可采用统一的单符号表方案。当然，若遇到符号名重复的情况则需额外处理。Java语言提供了灵活的解决方案，可构建嵌套结构的符号表，具体形式为：Map<String, Map<String, Object>>。其中外层String表示语义模型类型（建议使用枚举替代），内层String表示符号名。通过简单封装即可构建功能强大的符号表管理器，该方案不仅使用便捷，还具备更强的通用性，是笔者极力推荐的实现方式。

        关于符号表的数据结构，案例中采用了哈希表，但这并非唯一选项，数组、链表或树结构均可作为替代方案。通常，符号名的类型会选择字符串，而值的类型则需根据实际场景确定。例如，在词法分析阶段，值的类型可能为Token；在语法分析阶段，则可能是语义模型或语义模型构建器。需注意，这些设定是针对DSL的场景，而通用编程语言的符号表通常会使用指针作为值的类型，该指针指向一个描述变量属性（如类型、内存占用、存储位置等）的数据结构。

        最后要探讨的是符号表的替代方案。若在语法分析过程中构建了抽象语法树，在某些情况下可用其替代符号表。前文提到，抽象语法树是记录有意义程序结构信息的实际语法树，本案例的结构可参考图 4.3。分析dependencies节点时，可通过root节点导航至properties节点查询所需信息。这种方式虽比使用符号表慢，但可节省符号表占用的空间。需注意，符号表和语法树在功能上有交集，但不能相互替代。语法树仅表示程序语法结构，通常不包含标识符的类型、作用域等信息，而符号表则相反。

上一章  下一章