如何从 erlang 中的列表创建二叉搜索树

Question

我正在用 Erlang 创建一个命题逻辑定理证明器，但我无法集中精力将列表解析为树。

tokenise([]) -> [];

tokenise([$( | T]) -> [{bracket, left}| tokenise(T)];
tokenise([$) | T]) -> [{bracket, right}| tokenise(T)];

tokenise([$& | T]) -> [{logicAnd} | tokenise(T)];
tokenise([$| | T]) -> [{logicOr} | tokenise(T)];
tokenise([$! | T]) -> [{logicNot} | tokenise(T)];

tokenise([X | T]) -> [{prop, X} | tokenise(T)].

输入：(A!B)

当前输出：

[{bracket,left},
 {prop,65},
 {logicNot},
 {prop,66},
 {bracket,right}]

需要输出：

[ logicNot { A, B } ]

如有任何帮助，我们将不胜感激。

Answer 1

您目前有一个识别标记的词法分析器，但您缺少一个能够识别有效标记序列并根据语法规则减少它们的解析器。我建议您考虑使用 leex to construct your lexer and yecc 来构造您的解析器。

Answer 2

你的输出就是我所说的句法分析。您已将输入转换为规范化的树形形式，从而以您的语言生成语法正确的表达式。

接下来获取该输出并递归遍历它以构建目标输出。

顺便说一句，我建议您将运算符更改为 {Op, operator} - {Op, logicNot} 的二元组，例如。我想如果你这样做，你会发现写下一个阶段会更容易。

作为提示（这段代码不好），

do([]) -> 
   "";
do({prop,C}) ->
  [C];

do([{bracket,left} | Tl]) ->
   lists:append(["[ ", do(Tl),"] "]);

do([A, {logicNot}|Tl]) ->
  lists:append(["logicNot { ", do(A), ",", do(Tl), " }"]);

do([{prop, C}, {bracket, right}]) ->
  [C].

基本上，您将编写一个递归方法 p，它将 [{ A Op B}] 映射到 [Op {p(A), p(B)}]...

Answer 3

看起来你正在通过扫描和解析创建自己的逻辑语言。你看过leex and yecc in the Erlang standard library to do this for you? (A good tutorial can be found here)

扫描仪

使用leex，可以在文件test_scanner.xrl中写一个扫描器，如下：

Definitions.

W = [a-zA-Z0-1]

S = [\s\t\n\r\f\v\d]

Rules.

{W}+ : {token, {prop, TokenChars, TokenLine}}.
\(   : {token, {'(', TokenLine}}.
\)   : {token, {')', TokenLine}}.
\!   : {token, {'!', TokenLine}}.
{S}+ : skip_token.

Erlang code.

编译它：

$ erlc test_scanner.xrl # This produces an normal Erlang file
$ erlc test_scanner.erl # This compiles the actual beam file

使用它：

1> l(test_scanner).
{module,test_scanner}
2> {ok, Tokens, _EndLine} = test_scanner:string("(a ! b) ! c").
{ok,[{'(',1},
     {prop,"a",1},
     {'!',1},
     {prop,"b",1},
     {')',1},
     {'!',1},
     {prop,"c",1}],
    1}

解析器

使用yecc，可以在文件test_parser.yrl中编写解析器如下：

Terminals prop '!' '(' ')'.

Nonterminals expr.

Rootsymbol expr.

Left 100 '!'.

expr -> '(' expr ')' : ''.
expr -> expr '!' expr : {logicNot, '', ''}.
expr -> prop : prop('').

Erlang code.

prop({prop, Name, _Line}) -> Name.

编译它：

$ erlc test_parser.yrl # This produces an normal Erlang file
$ erlc test_parser.erl # This compiles the actual beam file

使用它：

3> test_parser:parse(Tokens).
{ok,{logicNot,{logicNot,"a","b"},"c"}}

结果

这为您提供了一个基于元组的简单二叉树结构：

{logicNot,
    {logicNot,
        "a",
        "b"},
    "c"}}

如何从 erlang 中的列表创建二叉搜索树

How to create a binary search tree from a list in erlang

erlang

binary-search-tree

扫描仪

解析器

结果