内容


构建基于 CDT 的编辑器,第 3 部分

基本的 CDT 解析

理解 CDT 解析器及其抽象语法树

Comments

系列内容:

此内容是该系列 # 部分中的第 # 部分: 构建基于 CDT 的编辑器,第 3 部分

敬请期待该系列的后续内容。

此内容是该系列的一部分:构建基于 CDT 的编辑器,第 3 部分

敬请期待该系列的后续内容。

在本系列的 第 2 部分 中, 解释了 CDT 编辑器如何通过响应每次击键来更新其文本表示。但它能做到的远比仅仅用特定颜色及字体显示关键字要多得多:它还能分析代码结构并记录每个函数、语句及变量。

这种分析,称做解析,它是计算机科学家们所不断研究的一个十分宽泛的主题。本文将简要地介绍一些解析背后的理论,并将重点介绍 CDT 运行的机制。本文的目的是要提供足够的信息,这样,如果您今后想要改进或修改 CDT 解析器,就会知道要改变哪些类和方法以及如何进行改变。

我已经将这些类添加到精简版的 C/C++ 开发工具(BBCDT)中了,所以您将能够看到解析在本文的样例中是如何执行的。大多数新类都处理 CDT 解析过程,可以在 org.bbcdt.dworks.core 插件(特别是在 org.bbcdt.dworks.core.parser 包及其子包中)中找到它们。

CDT 实际上有两个 解析器 —— 一个使用持久文档对象模型(Persisted Document Object Model,PDOM),另一个不使用,记住这一点很重要。这两个解析器对当前的(V3.1)CDT 来说都很重要,但根据 Doug Schaefer 的观点,PDOM 解析器将逐渐取代另一个解析器。我将在本系列的第 4 部分讨论 PDOM 解析器,但由于没有使用 PDOM 的那种解析器更易于理解,所以我会在这里先对其进行探讨。我将特别地讨论从 Document 接收更新到新抽象语法树(Abstract Syntax Tree,AST)的创建这段时间内,在 CDT 中会发生的事情。这一过程可以用以下 4 个部分进行解释:

协调器(Reconciler)及其协调策略
解析器如何从 Document 中接收事件
构建解析器
解析器是如何创建并初始化的
解析过程
解析器如何分析 WorkingCopy 文本的结构
AST
解析器的源代码模型以及如何访问该模型

协调器及其协调策略

第 2 部分 描述了 PresentationReconciler 如何通过对编辑文档的改变做出响应而开始样式化文本的过程。同样的,CDT 解析开始于 Reconciler 对象,该对象监听相同类型的事件。不要将这两个类弄混。PresentationReconciler 类根据每次击键更新文本的外观,而 Reconciler 类运行一个守护线程,不必将用户界面(UI)挂起就能解析该文档。这就是在使用 Eclipse 时为什么语法着色比错误检测运行起来要快得多的原因。

当其监听程序检测到一个新 Document 时,Reconciler 的线程开始。用户更新 Document 后,该线程告知它的 CReconcilingStrategy 开始协调。CDT Reconciler 是一个 MonoReconciler,这意味着它只能有一个策略。同样,Reconciler不是 增量的,这意味着一发生改变,该策略就会运行于整个 Document 之上。

CReconcilingStrategy 访问 WorkingCopy,并让它在 WorkingCopyInfo 对象(像 CDT 模型中其他信息对象一样运行)中组织其子对象。但 WorkingCopy 并没有任何子对象,—— 它只是一个未被保存且未被结构化的文本的缓冲区。WorkingCopy 调用 parse() 方法以清理这种混乱。这个调用并没有启动解析,但它开始了创建并初始化解析器的过程。

创建解析器

WorkingCopy 通过构建一个用于管理解析过程的 CModelBuilder 对象来开始解析器的创建。此对象根据对象的性质确定要解析的语言并从 WorkingCopy 的文本中构建一个字符缓冲区。它还通过调用 ParserFactory.createScanner() 方法创建一系列对象(IProblemRequestorIScannerInfoProviderCodeReaderSourceElementRequestorParserLogService)用于构造 Scanner2 对象。此方法分析缓冲区中的字符并为解析器提供标记(token)。

扫描程序创建好后,CModelBuilder 通过调用 ParserFactory.createParser() 方法构造 Parser。此方法让 ProblemRequestor 在错误发生时开始更新编辑器的注释。然后,它调用 Parserparse() 方法。

好戏开始了。但在深入探讨前,先来快速介绍一下解析理论。

插曲:解析的简短介绍

以输入语句 “Matt likes pizza”为例,您也许明白单个的单词,但如果不熟悉主语-动词-对象这一句子结构,就不会明白它的意思。只有当输入的元素和抽象的结构( “Matt”= 主语,“likes”= 动词,“pizza”= 对象)匹配起来,这个句子才有意义。当然,还有许多其他的句子结构和其他的语言。表明在一门特定的语言中如何构建合适句子的主体规则就是该语言的语法

在程序语言中,语法包含了一个抽象的模型,所有格式良好的代码单元(即源文件)都必须匹配这个模型。执行此匹配的第一步叫做扫描词法分析。扫描程序读取缓冲中的单个字符并返回解析器能理解的记号(称做标记 ) —— 如关键字、操作符及针对特定语言的标点符号。例如,当 C 扫描程序读取到 c、o、n、s、t 时,它会返回一个代表关键字 const 的单个标记对象。解析器不关心空白或注释,因而扫描程序会忽略了这些。

匹配过程的第二步是解析。在这里,解析器检测标记间的结合同其语法中的抽象元素的匹配程度。总的来说,这远比上述主语-动词-对象的例子复杂得多。例如,如果语句以一个与 “enum”(声明一个枚举)相应的标记作为开始,CDT 解析器会试图将该语句同 enum 语句的抽象模型匹配起来。即,在 ENUM 标记后,它会寻找一个可选的 name,随后在 L_BRACER_BRACE 标记之间寻找一个 enumerated_list 和一个最终的 enumerated_list。每一个斜体的术语表示引用该语法中的一个抽象元素。

许多解析器,包括 CDT 解析器在内,所完成的任务都不仅仅是检测格式良好性。在解析完输入后,它们将其结构信息以一种适于分析、索引和搜索的格式存储。这种格式通常是一种叫做 AST 的树。例如,如果您将一篇 developerWorks 的文章做了标记并通过一个英语解析器将其发送,结果也许是如图 1 中所示的树结构。

图 1. AST 示例
AST 示例
AST 示例

正如您所看到的那样,树中的元素都是一般性的在顶部(developerWorks Article ),每一个向下的节点处则较为详细一些。如果不是空间所限,我还将展示底部的节点如何包含句子及最终的特定的单词。对一门编程语言来说,这些终端的节点包含单个的关键字、操作符及变量。通过搜索一个 AST 来寻找函数名或变量名比起对整篇文档进行重解析要简单得多。接下来介绍 CDT 解析器如何生成 AST 以及如何用您自己的代码对其进行遍历。

解析过程

我没找到关于 CDT 的语法文件,但我们可以根据 Parser 类的方法以及这些方法之前的注释确定其抽象模型元素。这个类位于 org.dworks.bbcdt.internal.core.parser 包中。如前所述,第一个解析方法是 translationUnit(),因为 TranslationUnit 元素代表了整个源文件,正如在本文例子中的 Article 元素代表了整篇文章一样。

translationUnit() 方法前的注释中的一个隐秘的语句如下:

translationUnit : (declaration)*

如果您熟悉扩展巴科斯范式(Extended Backus Naur Form,EBNF),就会明白这个规则意味着一个 TranslationUnit 包含任意数目的 Declaration 元素。这些注释并不提供完整的 CDT 语法,但如果试图使用或修改 Parser 类,它们将会很有帮助。

因为 Declaration 元素恰在 TranslationUnit 之下, translationUnit() 方法调用 declaration() 方法。EBNF 规则告诉我们声明可以是下列六种形式之一:

集合声明
其后跟 ASMDefinition 元素的 asm 标记
名称空间声明
其后跟 NamespaceDefinition 元素的 namespace 标记
使用声明
其后跟 UsingDeclaration 元素的 using 标记。
模板声明
其后跟 TemplateDeclaration 元素的 templateexport 标记
链接声明
其后跟 LinkageSpecification 元素的 extern 标记
简单声明
SimpleDeclaration 元素

为确定一个给定声明的类型,declaration() 方法使用一个 switch 语句,该语句的执行依赖于扫描程序的下一个标记的类型。每个标记实现 IToken 并将其类型(在 1 至 141 之间的一个 int )、被扫描的文件及其偏移量和长度存储到被扫描的 Document 中。

如果一个声明不在前五种之列,将调用 simpleDeclaration() 方法,并附带对该声明性质的猜测。首先猜测该声明是一个构造函数,但如果该方法抛出 BackTrackException,接下来将猜测该声明是一个函数声明。如果失败,会第三次调用该方法,此时将猜测该声明是一个变量声明。如果仍抛出异常,该方法会返回 null

解析器会继续调用方法以将代码同模型元素相匹配,但分析的深度取决于其模式 。五种解析模式为:

QUICK_PARSE
不解析内部函数及包含的文件
STRUCTURAL_PARSE
不解析内部函数,但解析包含的文件
COMPLETE_PARSE
解析内部函数及包含的文件
COMPLETION_PARSE
解析内部函数及包含的文件,在偏移量处停止,并优化符号查询
SELECTION_PARSE
解析内部函数及包含的文件,在偏移量处停止,并提供选定范围的语义信息。

模式也决定了 Parser 在解析时使用什么回调对象来存储信息。在 QUICK_PARSE 模式中,QuickParseCallback 记录宏、函数、声明及任何发生的错误。在其他的模式中,StructuralParseCallback 存储诸如 Parser 的当前范围、变量、namespace 语句、enum 声明等这类额外信息。但由于额外的分析需要额外的时间,Parser 的默认模式是 QUICK_PARSE

无论您使用哪种回调对象,其携带的最重要的信息是 ASTCompilationUnit。下面将介绍一下它的重要性。

AST

第一个解析方法 translationUnit() 通过创建一个 ASTCompilationUnit 对象来开始其执行。该对象不仅是 AST 中最高的节点,也是它下面所有节点的容器。Parser 识别源文件中的一个声明后,将 ASTDeclaration 的一个子类添加到 ASTCompilationUnit 的声明 List中。如果源文件中第一个声明是 typedefASTCompilationUnitList 中第一个元素将为 ASTTypedefDeclaration

同样,每一个 ASTDeclaration 对象存储构成该声明的 AST 对象。例如,一个由 ASTFunction 表示的函数声明包含了代表其返回类型、参数和其中包含的所有函数的 AST 对象。当 Parser 结束分析后,ASTCompilationUnit 将包含一个代表了文件结构的完整的 AST。那时,在文件中寻找一个特定的元素就和树的遍历算法一样简单。

更新 BBCDT

如果在 Eclipse 中打开 BBCDT 项目,会发现还有更多代码,特别是在 org.dworks.bbcdt.core 插件项目中。这些新类中的许多类都是设置及执行解析所必需的,但它们中的大多数代表了 C/C++ 源文件或 C/C++ AST 的元素。

org.dworks.bbcdt.ui 插件也有新类。它们大多数都处理协调过程,但 org.dworks.bbcdt.ui.action 包中的 ASTAction 类却实现 IEditorActionDelegate 接口。该类在 BBCDT 编辑器可视时出现。当单击工具条 “contribution”,该类访问 IASTCompilationUnit 并在其声明的对象间迭代。如果它们中的任何一个声明了函数或变量,或者以 namespaceusingextern 开头,ASTAction 就会显示一个窗口,该窗口列出了每一个声明的类型以及该声明类型的特定信息。清单 1 显示了所需的代码。

清单 1. 访问 CDT AST 中的声明
IASTCompilationUnit unit = CCorePlugin.getCompilationUnit();
Iterator iter = unit.getDeclarations();
    while(iter.hasNext()) {
        IASTDeclaration decl = (IASTDeclaration)iter.next();

        if (decl instanceof IASTFunction)
            output += "Function declaration: " + 
                ((IASTFunction)decl).getName();
					
        else if (decl instanceof IASTLinkageSpecification)
            output += "Linkage declaration: " + 
                ((IASTLinkageSpecification)decl).getLinkageString();
					
        else if (decl instanceof IASTNamespaceDefinition)
            output += "Namespace definition: " + 
                ((IASTNamespaceDefinition)decl).getName();
					
        else if (decl instanceof IASTUsingDeclaration)
            output += "Using declaration: " + 
                ((IASTUsingDeclaration)decl).getName();
					
        else if (decl instanceof IASTVariable)
            output += "Variable declaration: " + 
                ((IASTVariable)decl).getName();

在 CDT 中找不到此代码;我将它们修补到一块,以使访问并遍历 IASTCompilationUnit 变得简单。通过修改 ASTAction,您能够在节点间进行搜索并创建整个树。图 2 显示了在单击 ASTAction 按钮后 BBCDT 的输出。

图 2. BBCDT AST 分析的输出
BBCDT AST 分析的输出
BBCDT AST 分析的输出

结束语

本文先是解释了 CDT Parser 如何对编辑器文本的改变做出响应,然后用 C/C++ 元素创建了 AST。本文还对解析理论进行了总结。但是需要了解的有关解析的内容还有很多;请参阅 参考资料 中给出的一些优秀的在线解析教科书。

本文所描述的 Parser 实现了其目标,但它也有缺点。它很慢,其分析只局限于一次一个源文件。在本系列的第 4 部分中将会介绍 CDT 中的另一个更为强大也更为复杂的解析器。


下载资源


相关主题


评论

添加或订阅评论,请先登录注册

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=Open source
ArticleID=187271
ArticleTitle=构建基于 CDT 的编辑器,第 3 部分: 基本的 CDT 解析
publish-date=01082007