随笔-341  评论-2670  文章-0  trackbacks-0

刚刚发了上一篇文章之后就发现状态机画错了。虽然LiveWriter有打开博客并修改文章的功能,不过为了让我留下一个教训,我还是决定发一篇勘误。这个教训就是,作分析的时候不要随便“跳步”,该一步一步来就一步一步来。其实人呢,就是很容易忘掉以前的教训的了。第一个告诉我不能这么干的人其实是小学三年级的数学老师。当时我因为懒得写字,所以计算应用题的时候省了几步,被批评了。

故事就从状态机开始。文法我就不重复了,见上一篇文章。现在我们从状态机开始。第一个状态机是直接从文法变过来的:

image

然后我们把所有的非终结符跳转都通过Shift和Reduce连接到该非终结符所代表的状态机的状态上面,就会变成下面的图。具体的做法是,对于每一条非终结符的跳转,譬如说S0 –> Symbol –> S1。首先抹掉这条跳转。然后增加两条边,分别是S0到Symbol的起始节点,操作是Shift<S0>。还有从Symbol的终结节点到S0,操作是Pop<S0> Reduce。Shift<S>等于把状态S给push到堆栈里,然后Pop<S>等于在状态里面弹出内容是S的栈顶元素。如果失败了怎么办呢?那就不能用这条跳转。跟上图一样,所有输入$跳转到Finish的边,操作都是要Pop<Null>的。在刚开始分析的时候,堆栈有一个Null值,用来代表“语法分析从这里开始”。

image

这个图的粗虚边代表所有跟左递归有关的跳转。这些边是成对的,分别是左递归跳转的Shift和Reduce。如果不是为了实现高性能的语法分析的话,其实这个状态机已经足够了。这个图跟语法分析的“状态跳转轨迹”有很大的关系。虽然IDList0你不知道第一步要跳转到IDList0还是ID0,不过没关系,现在我们先假设我们可以通过某种神秘的方法来预测到。那么,当输入是A,B,C$的时候,状态跳转轨迹就会是如下的样子:

image

为什么要这么做呢?我们把这幅图想象成为
1:想做的箭头表示push一个状态
2:向下的箭头表示修改当前状态
3:向右的状态表示pop一个状态并修改当前状态

因此当输入到B的时候,到达ID1,并跳转到IDList1。这个时候IDList1【左边】的所有【还留在堆栈里】的状态时Null和IDList0,当前状态IDList1,输入剩下,C$。这个图特别的有用。当我们分析完并且把构造语法树的指令附着在这些箭头上面之后,按顺序执行这些指令就可以构造出一颗完整的语法树了。

但是在实际操作里面,我们并没有办法预测“这里要左递归两次”,也没办法在多次reduce的时候选择究竟要从哪里跳到哪里。所以实际上我们要学习从EpsilonNFA到DFA的那个计算过程,把Shift和Reduce当成Epsilon,把吃掉一个token当成非Epsilon边,然后执行我之前写的《构造可配置词法分析器》一文中的那个去Epsilon边算法(如何从Nondeterministic到Deterministic,以及相关的Look Ahead,是下一篇文章的内容),然后就可以把状态机变成这样:

image

上面粗体的Pop<IDList0>表示,这一个Pop是对应于那个左递归Shifting操作的。实际上这是做了一个怎样的变化呢?从“物理解释”上来讲,其实是把“状态跳转轨迹”里面那些除了左递归shifting之外的所有不吃掉token的边都去掉了:

image

在这里我们可以看到,为什么当堆栈是IDList0, IDList0和IDList0, IDList3的时候,从ID0都可以通过吃掉一个”,”从而跳转到IDList3。在上面这张“状态跳转轨迹”里面,这两个事情都发生了,分别是第一条向左的箭头和第二条向左的方向。而且这两条边刚好对应于上图带有蓝色粗体文字的跳转,属于左递归Reducing操作。

所以,其实在这个时候,我们同时解决了“应该在什么时候进行左递归Shifting”的问题。只要当左递归Reducing已发生,我们立刻在轨迹上面补上一条左递归Shifting就好了。因此,我们在一开始做parsing的时候,根本不需要预先做左递归Shifting。所以当刚刚输入A的时候,“状态跳转轨迹”是这样子的:

image

然后遇到一个”,”,发现之前“做漏”了一个左递归Shifting,因此就变成下面这个样子:

image

这也就是上一篇文章那个Fake-Shift所做的事情了。

posted on 2012-12-07 18:49 陈梓瀚(vczh) 阅读(4377) 评论(2)  编辑 收藏 引用 所属分类: C++

评论:
# re: 可配置语法分析器开发纪事(三点五)&mdash;&mdash;生成下推自动机的具体步骤 2012-12-07 19:54 | DiryBoy
orz  回复  更多评论
  
# re: 可配置语法分析器开发纪事(三点五)&mdash;&mdash;生成下推自动机的具体步骤 2012-12-16 00:17 | Zblc(邱震钰)
~~~  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理