blocks|key|469262|text|我将从一个简单的语法开始，类似于ANTLR和JavaCC所使用的语法。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|469263|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

I'd start with a simple grammar, something like those used by ANTLR and JavaCC.

blocks|key|3530361|text|每当您打算编写解析器时，要问的主要问题是您是想手动完成，还是使用解析器生成器框架。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3530362|在这种情况下，我会说这是一个很好的练习，把它全部写出来。|3530363|从树本身的良好表示开始。这将是你的算法的输出。例如，这可能是一个对象集合，其中一个对象类型可以表示一个“标签”，如示例中的a、b和c。其他人可以代表数字。然后，您可以定义运算符的表示形式，例如，%2B是一个二元运算符，它将有两个子对象，分别表示左子表达式和右子表达式。|offset|length|style|CODE|3530364|下一步是实际的解析器，我建议使用一个经典的递归解析器。描述这一点并提供标准伪代码实现的一个文本是由Theodore+Norvell编写的文本|3530365|entityMap|0|LINK|mutability|MUTABLE|url|http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm^0|0|0|1P|1|1R|1|1T|1|2P|1|0|1D|G|0|0^^$0|@$1|2|3|4|5|6|7|T|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|U|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|V|8|@$F|W|G|X|H|I]|$F|Y|G|Z|H|I]|$F|10|G|11|H|I]|$F|12|G|13|H|I]]|9|@]|A|$]]|$1|J|3|K|5|6|7|14|8|@]|9|@$F|15|G|16|1|17]]|A|$]]|$1|L|3|-4|5|6|7|18|8|@]|9|@]|A|$]]]|M|$N|$5|O|P|Q|A|$R|S]]]]

Whenever you intend to write a parser, the main question to ask is if you want to do it manually, or to use a parser generator framework.

In this case, I would say that it's a good exercise to write it all yourself.

Start with a good representation for the tree itself. This will be be output of your algorithm. For example, this could be a collection of objects, where one object kind could represent a "label" like <code>a</code>, <code>b</code>, and <code>c</code> in your example. Others could represent numbers. You could then defined a representation of operators, for example <code>+</code> is a binary operator, which would have two subobjects, representing the left and right subexpression.

Next step is the actual parser, I would suggest a classical recursive decent parser. One text describing this, and provides a standard pseudo-code implementation is this text by <a href="http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm" rel="nofollow">Theodore Norvell</a>

blocks|key|3530372|text|简单的解决方法是将表达式转换为后缀表示法(abcef/*%2B%2B)+&然后参考这个问题的答案(http://stackoverflow.com/questions/423898/postfix-notation-to-expression-tree)，将后缀表达式转换为树。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|3530373|这是面试官所期望的:)|3530374|entityMap|0|LINK|mutability|MUTABLE|url|http://stackoverflow.com/questions/423898/postfix-notation-to-expression-tree^0|19|25|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]]|C|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|C|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]]]

Simple way out is to convert your expression into postfix notation (abcef/*++) &amp; then refer to the answer to this question (http://stackoverflow.com/questions/423898/postfix-notation-to-expression-tree) for converting the postfix expression to a Tree. 

This is what the interviewer expected :)

blocks|key|469297|text|从定义语言开始。没有人可以为没有很好定义的语言实现解析器或编译器。您给出一个示例：'a%2B(b%2Bc*(e/f)%2Bd)*g'，它应该会触发以下问题：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|469298|469299|是一种语言，可以是单个表达式，也可以有多个语句(用';‘或许？|ordered-list-item|469300|什么是'a'，'b'，...“G”代币？它是可变的吗？变量的语法是什么？它是一个类似C的变量，还是像你的例子所暗示的那样，它是一个单一的字母数字字符。|469301|在你的例子中有3个二进制表达式。就这些吗？该语言是否也支持'-‘。您的语言是否支持逻辑和逐位operators?|469302|Does语言支持数字文字？仅整型？双倍?该语言是否支持字符串文字？你引用的字符串literals?|469303|Syntax对于comments?|469304|Which运算符有优先权吗？“*”运算符是否像示例中那样优先于“%2B”？操作数的计算是从右到左还是从左到右？|469305|Any+Pre-processing?|469306|469307|一旦您对语言语法有了良好的定义，就可以从实现记号赋予器开始。标记器获取字符流并生成标记列表。在上面的示例中，每个字符都是一个标记，但在var*12+(var+power+12)中有3个标记：'var‘、'*’和'12‘。如果允许使用正则表达式，则可以使用正则表达式完成这一部分的解析。|469308|接下来，有一个函数通过类型来标识每个令牌:是操作符，还是变量，数字文字，字符串文字等。将所有内容打包到一个名为NextToken的方法中，该方法返回一个令牌及其类型。|469309|最后，开始解析。在您的示例中，解析树的根将是一个带有'%2B‘运算符的节点(它优先于'')。左边的孩子是一个变量标记'a‘，右边的孩子是一个带有根元素'’标记的树。递归工作。|469310|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|10|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|11|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|12|8|@]|9|@]|A|$]]|$1|F|3|G|5|E|7|13|8|@]|9|@]|A|$]]|$1|H|3|I|5|E|7|14|8|@]|9|@]|A|$]]|$1|J|3|K|5|E|7|15|8|@]|9|@]|A|$]]|$1|L|3|M|5|E|7|16|8|@]|9|@]|A|$]]|$1|N|3|O|5|E|7|17|8|@]|9|@]|A|$]]|$1|P|3|Q|5|E|7|18|8|@]|9|@]|A|$]]|$1|R|3|-4|5|6|7|19|8|@]|9|@]|A|$]]|$1|S|3|T|5|6|7|1A|8|@]|9|@]|A|$]]|$1|U|3|V|5|6|7|1B|8|@]|9|@]|A|$]]|$1|W|3|X|5|6|7|1C|8|@]|9|@]|A|$]]|$1|Y|3|-4|5|6|7|1D|8|@]|9|@]|A|$]]]|Z|$]]

Start by defining the language. No one can implement a parser or a compiler to a language that isn't very well defined. You give an example: 'a+(b+c*(e/f)+d)*g', which should trigger the following questions:

<ol>
<li>Is the language a single expression, or there may be multiple statements (separated by ';' maybe?</li>
<li>what are the 'a', 'b', ... 'g' tokens? Is it variable? What is the syntax of variables? Is it a C-like variable, or is it a single alphanumeric character as your example may imply.</li>
<li>There are 3 binary expression in your example. Is that all? Does the language also support '-'. Does your language support logical, and bit-wise operators?</li>
<li>Does the language support number literals? integer only? double? Does the language support string literals? Do you quote string literals?</li>
<li>Syntax for comments?</li>
<li>Which operator has precedence? Does '*' operator has precedence over '+' as in the example? Does operands evaluated right to left or left to right?</li>
<li>Any Pre-processing?</li>
</ol>

Once you are equipped with a good definition of the language syntax, start with implementing a tokenizer. A tokenizer gets a stream of characters and generates a list of tokens. In the example above, each character is a token, but in var*12 (var power 12) there are 3 tokens: 'var', '*' and '12'. If regular expression is permitted, it is possible you can do this part of the parsing with regular expressions.

Next, have a function that identify each token by type: is it an operator, is it a variable, a number literal, string literal, etc. Package all in a method called NextToken that returns a token and its type.

Finally, start parsing. In your sample above the root of the parsing tree will be a node with the '+' operator (which has precedence over the ''). The left child is a variable token 'a' and the right child is a tree with a root element the '' token. Work recursively.

This question was asked to me in an interview question:

Write a code to generate the parse tree like compilers do internally for any given expression. For example:

<pre><code>a+(b+c*(e/f)+d)*g 
</code></pre>

Write a code to generate the parse tree

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

在一次面试中，我被问到这个问题：编写一段代码来生成解析树，就像编译器在内部为任何给定表达式所做的那样。例如：a+(b+c*(e/f)+d)*g 

问编写生成解析树的代码
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问编写生成解析树的代码EN