岁月流转,往昔空明

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 3 Stories :: 413 Comments :: 0 Trackbacks

语义:从分析树到语法树(一)

在1-7章里,我们已经建立了一个编译器所需要的绝大部分环节:词法分析、语法分析、代码生成、代码执行。前两个阶段,将会生成分析树(Parse Tree)后两个阶段,则是用语法树生成的。我们多希望语法分析后的分析树,直接就能用作语法树啊!

从结构上看,分析树和语法树几乎是如出一辙的。只可惜,如果我们再仔细的观察会发现,从分析树到语法树有一条深深的鸿沟。是的,你猜得没错,这条鸿沟,就是语义。只要有了语义,我们就可以将我们的分析树,变成可以产生代码的语法树。

本质上讲,语法树(Syntax Tree)是含有语义的。仍然用A+B这个表达式的语法树来举例子。在这里,A和B都是一个Int32的常量,例如我们这里A是5,B是10。这个语法树里面A节点,它具有以下的语义:

  • A是一个常量。
  • A是一个整型值。
  • A是5。

这些语义信息在语法树里面都具备,而在语法分析之后的分析树里面,只有“5”这样一个字符串。所以实际上,从分析树到语法树的建立,还需要经历一个附加语义的过程。

在一个常见的编译流程里,语义分析可以分为两个部分。其中一部分会跟随在词法和语法分析中,用于解析一些最基本的语义。例如输入的是不是关键字啦,是不是字面量啦,是不是运算符啦一类的信息,这些语义信息还可能用来指导后一阶段的语法分析。

还有一个部分就是例如类型推导、符号设置、函数签名分析一类的语义分析。这些分析的结果通常并不影响语法树的结构,而放在语法分析阶段又会增加分析的复杂度。这一类的语义分析,通常是在语法树建立好之后,再来对语法树进行进一步的分析,将语法树上的语义信息补完。

在SASL里,我们将语法树的建立分成三个步骤。

第一步,在词法分析和语法分析的同时,进行简单的语义解析。包括字面值、操作符、关键字的提取等。这些一方面是语义,一方面也是为了语法分析服务的。

第二步,我们将语法分析得出来的分析树,转换成我们需要的语法树的形式。我们的语法树上,拥有一些属性。通过这些属性可以给语法树节点上附加产生代码所必须的语义。

第三步,遍历语法树,填充语义,执行一些准备工作。

这样,我们就建立了一颗可以被代码生成工具所识别的语法树。

接下来,我们将运用Spirit.Lex和Spirit.Qi来完成我们前两步的工作。

第三部分,我们暂时还不需要,等需要的时候,咱们再来扩充。

posted on 2009-12-26 23:32 空明流转 阅读(1611) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理