这个树相关操作的BNF怎么写? [英] How to write the BNF for this tree-related operation?

问题描述

我们有一棵这样的树:

我们可以将其转换为点串表示，即

We can convert it to a dotstring representation, i.e.,

这样的树可以用其节点的前序序列表示其中点 (.) 插入空子树 (nil) 所在的位置在树遍历过程中遇到.

Such a tree can be represented by the preorder sequence of its nodes in which dots (.) are inserted where an empty subtree (nil) is encountered during the tree traversal.

这样我们就可以将图片中的树转换成'abd..e..c.fg...'.

So we can convert the tree in the picture to 'abd..e..c.fg...'.

如果我要编写一个函数来进行这种转换，它的 BNF 或 syntax diagrams 是什么?

If I am about to write a function to do this conversion, what's the BNF or syntax diagrams of it?

推荐答案

不清楚你在问什么.如果您将字符串视为语言中的句子，将树视为用于解析的 AST，那么下面的 BNF 可能是正确的:

It's not clear what you're asking. If you think of the string as a sentence in a language and the tree as an AST for a parse, maybe the following BNF would be right:

tree ::= empty | node
empty ::= '.'
node ::= letter tree tree
letter ::= 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | ...

这篇关于这个树相关操作的BNF怎么写?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！