语法制导的概念问题

Question

目前看龙书第5章 反复看了几遍感觉还是头晕了

请问大侠能否用简单易懂的话概括以下问题：
与LL语法分析器结合，实现一个SDT
与LR语法分析器结合，实现一个SDT

这是怎么实现的？
是否有具体的代码例子?

抽象语法树知道了怎么实现，但不知道到底用在哪里？

请高手赐教啊～～

Answer 1

> 抽象语法树知道了怎么实现，但不知道到底用在哪里？

比如gcc中的tree。

Answer 2

我不清楚你指的实现的意思，所以下面的回答未必是你想要的。

"与LL语法分析器结合，实现一个SDT"
"与LR语法分析器结合，实现一个SDT "

参考yacc,所谓动作其实可以是任何东西，不一定是代码片段，也可以是一个函数，就是说分析到某个点的时候需要执行的东西，比如
E -> E + E {printf xxxxx}等等。

我假定你知道LR的原理，那么上面的动作就可以认为当识别出 E + E 并把它reduce到E的时候执行那个{printf xxxx}  也可以是一个函数，例如
static psrNode_t*        AR_STDCALL __def_reduce_handler(psrNode_t **nodes, size_t count, const wchar_t *name, void *ctx)
{
            for(int i = 0; i < n ; ++i)printf(nodes);
           return tree(nodes, count);
}

至少我的LALR实现是用一个stack记录节点,把 E + E 记录在stack上，之后通过类似上面的函数替换成一个节点E,这个函数就是语法动作，当然我的实现不一定是唯一途径或者最有效率的，例如yacc一类的都是直接生成源码。

"抽象语法树知道了怎么实现，但不知道到底用在哪里？"

语法树这东西我推荐你自己手动实现个简单点的regex引擎，其实就是，先把平面的代码变成具有层次的树状结构之后，还需要对一些节点做某些动作，比如一个regex引擎需要对一个模式所涉及到的字符的范围做统计和分裂等等，之后会把某些叶节点做替换。然后后续阶段可以根据这个在内存或者外存中的tree做下一步操作，比如regex引擎根据这个生成转移表等等。

以上所说的这些东西没有一定之规，纯粹是数据结构和编码方式问题，我讲的也是我所做过的，但未必是有效率的～

[ 本帖最后由 Solidus 于 2009-11-9 19:14 编辑 ]