CODEWITHSUNDEEP
erlangbinary-search-tree
Paulie
Paulie

Reputation: 7015

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

I'm creating a Propositional Logic Theorem Prover in Erlang, but I'm unable to get my head around parsing a list to a tree.

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)].

Input: (A!B)

Current output: 

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

Output needed: 

[ logicNot { A, B } ]

Any help would be appreciated.

Upvotes: 1

Views: 1484

Answers (3)

Adam Lindberg
Adam Lindberg

Reputation: 16577

It looks like you are creating your own logic language via scanning and parsing. Have you looked at leex and yecc in the Erlang standard library to do this for you? (A good tutorial can be found here)

Scanner

Using leex, you can write a scanner in the file test_scanner.xrl as follows:

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.

Compile it:

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

Use it:

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}

Parser

Using yecc, you can write a parser in the file test_parser.yrl as follows:

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

Nonterminals expr.

Rootsymbol expr.

Left 100 '!'.

expr -> '(' expr ')' : '$2'.
expr -> expr '!' expr : {logicNot, '$1', '$3'}.
expr -> prop : prop('$1').

Erlang code.

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

Compile it:

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

Use it:

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

Result

This gives you a simple binary tree structure based on tuples:

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

Upvotes: 4

Jr0
Jr0

Reputation: 2173

Your output is what I would call syntactic analysis. You have transformed your input into a normalized, tree form which produced a syntactically correct expression in your language.

Next take that output and recursively walk it constructing the target output.

By the way, I would suggest that you change you operators to be a 2-tuple of {Op, operator} - {Op, logicNot}, for example. I think you will find it easier to write the next phase if you do.

So as a hint (this code is NOT good),

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].

Basically, you are going to write a a recursive method, p, that maps things like [{ A Op B}] to [Op {p(A), p(B)}]...

Upvotes: 1

Steve Vinoski
Steve Vinoski

Reputation: 20014

You currently have a lexer recognizing tokens, but you lack a parser that recognizes valid sequences of tokens and reduces them based on grammar rules. I suggest you look into using leex to construct your lexer and yecc to construct your parser.

Upvotes: 2

Related Questions