基于flex+bison的Newick解析器Bison递归规则使用与节点关系处理问题
Newick格式flex+bison解析器开发问题
我正在开发面向Newick文件格式树的flex+bison扫描器与解析器,用于对树结构执行各类操作。所实现的语法参考示例的简化版本(其中标签与长度均为flex返回的同类型值),参考Newick官方格式文档。
该解析器用于解析一类以递归子树和/或叶子节点序列表示树结构的文件格式,核心规则为:
- 主树始终以*;*结尾
- 主树及内部所有子树的节点均包裹在*( *与)*之间
- 右括号右侧可附加节点名称与长度,分别由name和*:length指定,二者均为可选项:可全部省略、仅指定名称或仅指定长度、或同时以name:length*形式指定
若任意节点缺失名称或长度,将自动应用默认值(例如默认名称为*'missingName',默认长度为'1'*)。
格式示例包括:
- (child1:4, child2:6)root:6;
- ((child1Of1:2, child2Of1:9)child1:5, child2:6)root:6;
上述语法的实现代码如下(注:以下内容已移除大量无关冗余逻辑便于展示,核心代码逻辑与原始实现一致):
struct node { char* name; /*the node's assigned name, either from the file or from default values*/ float length; /*node's length*/ } dataOfNode; } %start tree %token<dataOfNode> OP CP COMMA SEMICOLON COLON DISTANCE NAME %type<dataOfNode> tree subtrees recursive_subtrees subtree leaf %% tree: subtrees NAME COLON DISTANCE SEMICOLON {} // with name and distance | subtrees NAME SEMICOLON {} // without distance | subtrees COLON DISTANCE SEMICOLON {} // without name | subtrees SEMICOLON {} // without name nor distance ; subtrees: OP recursive_subtrees CP {} ; recursive_subtrees: subtree {} // just one subtree, or the last one of the list | recursive_subtrees COMMA subtree {} // (subtree, subtree, subtree...) subtree: subtrees NAME COLON DISTANCE { $$.NAME= $2.name; $$.length = $4.length; $$.lengthAcum = $$.lengthAcum + $4.length; } // group of subtrees, same as the main tree but without ";" at the end, with name and distance | subtrees NAME { $$.name= $2.name; $$.length = 1.0;} // without distance | subtrees COLON DISTANCE { $$.name= "missingName"; $$.length = $3.length;} // without name | subtrees { $$.name= "missingName"; $$.length = 1.0;} // without name nor distance | leaf { $$.name= $1.name; $$.length = $1.length;} // a leaf leaf: NAME COLON DISTANCE { $$.name= $$.name; $$.length = $3.length;} // with name and distance | NAME { $$.name= $1.name; $$.length = 1.0;} // without distance | COLON DISTANCE { $$.name= "missingName"; $$.length = $2.length;} // without name | { $$.name= "missingName"; $$.length = 1.0;} // without name nor distance ; %%
当前核心需求:区分每个子树与叶子节点的父节点,以便通过递归方式,将父子树的长度与其最长子节点的长度进行累积计算。
当前存在的疑问:
- 现有语法仅能完成各子树(及被归类为子树的叶子节点)的名称与长度赋值操作
- 无法突破现有逻辑实现父子节点的识别
- 对语法匹配过程中如何利用递归特性定位父节点的逻辑存在理解困惑
内容的提问来源于stack exchange,提问作者Lightsong
相关产品推荐
相关产品推荐

