tree - 树描述的语法示例(lex/yacc)

Question

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

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

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

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

Answer 1

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

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

lexer.mll

{
  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) }

parser.mly

%{
  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) }

tree.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()))";;