写代码来生成解析树

Question

这个问题被要求我在面试问题：

写代码来生成解析树一样的编译器对于任何给定的表达式内部完成。例如：

a+(b+c*(e/f)+d)*g 

Answer 1

我从一个简单的语法开始，就像ANTLR和JavaCC使用的语法。

Answer 2

每当你打算写一个解析器，要问的主要问题是，如果你想要做手工，或使用一个解析器生成器框架。

在这种情况下，我会说，这是一个很好的锻炼给它的所有写自己。

开始与树本身良好的代表性。这将是你的算法的输出。例如，这可能是一个对象集合，其中一个对象类型可能代表“标签”，如a,b和c。其他人可以代表数字。然后，您可以定义运算符的表示形式，例如+是一个二元运算符，它将有两个子对象，分别代表左侧和右侧子表达式。

下一步是实际的解析器，我会建议一个经典的递归体面解析器。一文描述了这一点，并提供了一个标准的伪代码实现是本文由Theodore Norvell

Answer 3

简单的办法就是你的表达转化为后缀符号（ABCEF/* ++）&则指的是这个问题的答案（ http://stackoverflow.com/questions/423898/postfix-notation-to-expression-tree）用于将后缀表达式转换为树。

这是面试官的期望:)

Answer 4

从定义语言开始。没有人可以将语法分析器或编译器实现为定义不明确的语言。你举一个例子： 'A +（B + C *（E/F）+ d）* G'，它应触发了以下问题：

1. 是对语言的单个表达，或者可以有多个语句（由“;”分隔？？？？也许
2. 什么是“A”，“b”，......“G”标记是它的变量什么是变量的语法是它类似C语言的变量，或它是一个单个字母数字字符作为你的例子可能意味着
3. 有在你的榜样3二进制表达式是所有有没有语言也支持。？“ - ”吗？您的语言支持逻辑和位运算符
4. 语言支持数字文字S'只有整数？双？该语言是否支持字符串文字？你引用字符串文字吗？
5. 评论的语法？
6. 哪个运算符优先？例如，'*'运算符是否优先于'+'？操作数是从右向左评估还是从左向右评估？
7. 任何预处理？

一旦您配备了良好的语言语法定义，就可以从实施标记器开始。令牌生成器获取一串字符并生成一个令牌列表。在上面的示例中，每个字符都是一个标记，但在var * 12（var power 12）中，有3个标记：'var'，' *'和'12'。如果允许使用正则表达式，则可以使用正则表达式执行此部分解析。

接下来，有一个按类型标识每个标记的函数：它是一个运算符，它是一个变量，数字文字，字符串文字等等。将所有包装在名为NextToken的方法中，该方法返回一个标记及其类型。

最后，开始解析。在上面的示例中，解析树的根将是具有“+”运算符的节点（其优先级高于“”）。左边的孩子是一个变量标记'a'，右边的孩子是一棵具有根元素''标记的树。以递归方式工作。