使用flex/bison构建类似于Lisp/Scheme的解析树

Question

我尝试解析类似Lisp/Scheme的简单代码

E.g. (func a (b c d) )

并从中构建一棵树， 我可以在C中完成解析，而不使用（即仅使用flex返回记号，并使用递归构建树）。 但是，对于bison的语法，我不确定在哪里添加代码来构建列表（即与累积终端符号相关联的规则以及将构建的列表链接到父节点的位置）。

我的语法类似于这里的语法： Lisp grammar in yacc 该语法是正确的，并且可以识别代码。

- Ani

---

我将标签从flex改为gnu-flex，尽管这里有反对意见：http://meta.stackexchange.com/questions/26460/tag-for-two-flexes/26708#26708，但这是因为在标签上看到Adobe图标会让许多访问者感到困惑。希望这个问题能够很快得到解决。祝你好运，希望你的问题能够得到答案。 - mechanical_meat

解释：S-expression是一种基于括号的表达式表示法，常用于LISP编程语言中。翻译：对于简单的S表达式，你几乎不需要使用flex或bison进行解析。你可以使用手写词法分析器来处理原子、括号和空格，并编写一个类似递归下降解析器的简单程序，代码量在100行以下即可。最初的LISP解释器就是只用了很少的代码实现的。 - Ira Baxter

Ira: 没有解析器的需求是正确的，但“手动编写的词法分析器”仅适用于人们通常最终使用的常规玩具子集。一些 Lisp/Scheme 中的记号可能非常棘手。为了您的娱乐，这里是一个在 Racket 中有效的数字常量示例：＃e＃x+e＃s+e @ -e＃l-e。 - Eli Barzilay

@Ira：是的，我可以用纯C编写解析器（我在我的问题中提到了这一点）。但我想知道如何从flex/bison构建真正的解析器。 - Ani

@Eli Barzley：也许你需要一个词法分析器来处理像Racket这样的现代Lisp。OP说：“简单”。 - Ira Baxter

Answer 1

您尝试过将向当前列表添加元素的代码放置在每个原子中，并在处理括号时管理列表树的代码吗？除非遇到其他问题，否则这似乎是最简单的方法：

listend: members ')'        { cur = cur->parent; }
       | ')'                { cur = cur->parent; }
       ;

list: '(' listend           { cur = newList(cur);}
    ;

atom: ID                    { appendAtom(cur, "ID"); }
    | NUM                   { appendAtom(cur, "NUM");}
    | STR                   { appendAtom(cur, "STR");}
    ;

这假设你在每个列表结构中都保留了一个父节点指针。

- Andrew

---

嗨，Amoss，我还没有尝试过使用父指针，会尝试这种方法。谢谢。 - Ani

vjom：它有用吗？如果有，请通过接受答案来给Amoss他应得的尊重 :) - Baggers