exp_parser.erl

-module(exp_parser).
-export([parse/1]).

% Parse simple math expressions.
%  Currently works (for certain definitions of "works")
%  for addition, subtraction and multiplication.
%  Eventually it should handle a unary negation operator (~)

% The goal is to do the following:
% parse("(2 + 3)")        =>  {plus, {num, 2}, {num, 3}}
% parse("((2 + 3) - 4)")  =>  {minus, {plus, {num, 2}, {num, 3}, {num, 4}}}

% What actually happens is this:
% parse("(2 + 3)")        =>  {expr, {plus, {num, 2}, {num, 3}}}
% parse("((2 + 3) - 4)")  =>  {expr, {expr, {minus, {expr, {plus, {num, 2}, {num, 3}}}, {num, 4}}}}

% I can't seem to get rid of those darn outer "expr" tagged tuples

parse(Exp) ->
  Tokens = tokenize(Exp),
  {expr, Output} = inner_parse(Tokens),
  Output.

%% The parsing functions

inner_parse([{TermL, L} | [{op, Op} | [{TermR, R} | Rest]]]) ->
  inner_parse([
      {expr, {Op, {TermL, L}, {TermR, R} }} |
      Rest
    ]);

inner_parse([{TermL, L} | [{op, Op} | [lparen | Rest]]]) ->
  inner_parse([
      {expr, {Op, {TermL, L}, {expr, inner_parse(Rest) }}}
    ]);

inner_parse([lparen | Rest]) ->
  {expr, inner_parse(Rest)};

inner_parse([{expr, Exp} | [rparen | Rest]]) ->
  inner_parse([{expr, Exp} | Rest]);

inner_parse([{expr, Exp}]) -> Exp.


%% "Tokenizing" functions (I'm not 100% sure "tokenize"" is what I mean here)

tokenize([]) -> [];
tokenize([32  | Rest]) -> tokenize(Rest); % ignore space characters
tokenize([$( | RestExp]) -> [lparen | tokenize(RestExp)];
tokenize([$) | RestExp]) -> [rparen | tokenize(RestExp)];
tokenize([Op | RestExp]) when Op =:= $+; Op =:= $-; Op =:= $* ->
  [op(Op) | tokenize(RestExp)];
tokenize([Digit | RestExp]) -> [digit(Digit) | tokenize(RestExp)].


%% Tagging functions

op($+) -> {op, plus};
op($-) -> {op, minus};
op($*) -> {op, times}.

digit(Digit) -> {num, Digit - 48}.