0

I have written a code in C to implement LR(1) parse table, however now I am facing a problem in printing the parse tree. How do we do that in C? The tree can have variable children and since the parsing algorithm is bottom-up, I am not sure where to begin. I want to make it look like the output of the pstree command or something of that sort.

Thank You

4

1 回答 1

0

您会发现在解析器中构造解析树更容易，并在解析完成后自上而下递归地打印它。这有几个优点：首先，您不限于解析树，而是可以生成抽象语法树，这通常更清晰。其次，您可以以任何您喜欢的形式生成树。

我打算插入一个证明，证明在你进行从左到右的解析时不可能绘制解析树，但令我惊讶的是，我说服自己只要你稍微放松一下规则，这是可能的：你必须能够上下左右移动光标，但你可以做到这一点，而无需每次套印任何东西。为此，您必须在左侧边缘或顶部绘制带有叶子（终端）的树，然后您可以通过从每个子节点绘制线来绘制缩减，并记住“连接点”是什么结果节点是。我不知道这是否适合刚开始解析的人的编程练习，但即使使用控制台应用程序也是可能的。

这是“反向 pstree”图的示例：

(41*x) + (27/y) - sin(2*pi*z);

(───────────────────────┐
41─factor─term┐         │
*─────────────┤         │
x─factor──────┴term─expr┤
)───────────────────────┴factor─term─expr┐
+────────────────────────────────────────┤
(───────────────────────┐                │
27─factor─term┐         │                │
/─────────────┤         │                │
y─factor──────┴term─expr┤                │
)───────────────────────┴factor─term─────┴expr┐
-─────────────────────────────────────────────┤
sin─────────────────────────┐                 │
(───────────────────────────┤                 │
2─factor─term┐              │                 │
*────────────┤              │                 │
pi─factor────┴term┐         │                 │
*─────────────────┤         │                 │
z─factor──────────┴term─expr┤                 │
)───────────────────────────┴factor─term──────┴expr

用于生成保持每个堆栈项的宽度和高度的算法；终端以 1 的高度和终端本身的宽度开始。在每个缩减规则中：

  • 光标向右移动，直到它在每个孩子的右边；

  • 光标向上移动到第一个孩子的底部

  • 对于每个孩子，从其右下角到光标所在的列绘制一条水平线，然后绘制一条垂直线，直到到达下一个孩子所在的行。在最后一个孩子处，打印缩减的非终结符名称，并记录生成的非终结符的高度和宽度。

于 2013-04-21T06:17:57.877 回答