2

我想从描述这棵树的文件中解析一棵树（这实际上是一个分类法）。

我正在寻找提供树描述的语法示例（最好是 lex/yacc 文件）。如果所描述的树不是二叉搜索树，而是每个节点（可能）有几个孩子的树（它称为家谱树吗？平面树？），那会更好。

理想情况下，如果这个 lex/yacc 实际包含在 OCaml 库中，那将是完美的。但是任何好的树描述语法都会让我满意。

我试图通过 Google 或 Stackoverflow 查找示例，但研究结果被与解析树相关的问题所淹没。我可以自己做一个语法，但我想先看看例子，以便有一个好的起点。

4

1 回答 1

3

这是我尝试创建解析树的最小示例：

我假设树表示为name_of_the_node(child(...), other_child(...), ...)。例如，这是一棵有根和 3 片叶子的简单树：root(first_leaf(), second_leaf(), third_leaf()).

词法分析器

{
  open Parser
  open Lexing

  exception Bad_char of char
}

rule main = parse
| ' ' | '\t' | '\n' { main lexbuf }
| ',' { COMMA }
| '(' { LP }
| ')' { RP }
| ['a'-'z' '_']+ as s { IDENT s }
| _ as c { raise (Bad_char c) }

解析器

%{
  open Tree
%}

%token <string> IDENT
%token COMMA LP RP

%start <Tree.t> tree

%%

tree:
label = IDENT LP children = separated_list(COMMA, tree) RP { T(label, children) }

树.ml

type t = T of string * t list

编译：

ocamllex lexer.mll
ocamlc -c tree.ml
menhir --infer -v parser.mly
ocamlc -c parser.mli
ocamlc -c parser.ml
ocamlc -c lexer.ml

测试到顶层：

ocaml tree.cmo parser.cmo lexer.cmo

接着：

let tree_of_string s = Parser.tree Lexer.main (Lexing.from_string s);;
tree_of_string "toto (titi(), tata(tutu()))";;
于 2013-07-27T11:09:03.143 回答