试析从LR(0)生成DFA及移动-规约过程分析

参考《编译原理及实践》

有如下文法：A→(A)|a

先给出该文法的DFA：

根据规定，将A'→A作为开始。

得到文法：

A'→A

A→(A)|a

-----------------

根据从左到右扫描，虚拟一个游标。当前游标在-1处，即：

A'→A

     ↑(在A前面)

让游标向右移动(第一次移动)。得到

A'→A

        ↑(在A后面)

但由于A是一个可分解的文法(A→(A)|a)。所以，要向右移一位，则必须考虑分解式的情况，即得到：

1、由于A→(A)，所以如果输入时'('时，则有：

A→(A)

      ↑(在'('后面)

同时，由于A得到文法(A)和a

则在这里需要加入另外两个文法：

A→(A)

    ↑(在'('前)

A→a

    ↑(在'a''前)

即：状态0 到 状态3的转换

2、由于A→a，所以如果输入时'a'，则有：

A→a

      ↑(在'a'后面)

即：状态0到状态2的转换

3、若输入为整个A则得到：

A→A

       ↑(在A后面)

即：状态0到状态1的转换

此时已得到4个状态。且状态1和2均已移动完成（到达规约状态）

则现在只考虑状态3。

 

状态3能接受3个输入。
1、输入'('：则图中状态3的第二条文法得到第一条文法。第三条文法不响应'('

2、输入'a'：由第三条文法响应，得到状态2（这是一个规约状态）

3、输入A：则第一条文法响应输入。得到状态4

 

状态4只接受一种输入即')'到达状态5（规约状态）

 

移动-规约过程分析：

创建一个堆栈，栈顶为$

设输入为：((a))，在该输入后添加$

从左到右扫描

1、'('。状态转到3，不是规约状态，将3加入堆栈

当前堆栈：$ ( 3

2、'('。仍回到状态3

当前堆栈 $ ( 3 ( 3

3、'a'。压入栈顶，到达状态2，其文法为A→a，从堆栈弹出a(栈顶元素)，将A压入栈顶

当前堆栈$ ( 3 ( A

4、压入栈顶后到达状态4，将')'压入堆栈

当前堆栈：$ ( 3 ( A )

5、压入堆栈后到达状态5，是一个规约状态，则使用A→(A)规约，弹出状态3，将A压入栈顶到达状态4

当前堆栈：$ ( A 4

6、')'。压入栈顶到达状态5，是一个规约状态，使用A→(A)规约

最终表达式被接受。