expr.erl

-module(expr).

-export([
  parse/1,
  test/0
]).

% ------------------------------------------------------
%
%   Simple math-expressions parser
%   by Dmitry Soshnikov <[email protected]>
%   MIT Style Lycense
%
% ------------------------------------------------------
%                       Grammar
% ------------------------------------------------------
%
% <expression> ::= <additive>
%
% <additive> ::= <multiplicative>
%             |  <additive> + <multiplicative>
%             |  <additive> - <multiplicative>
%
% <multiplicative> ::= <primary>
%                   |  <multiplicative> * <primary>
%                   |  <multiplicative> / </primary>
%

%% -----------------------------------------------------
%% Parse type: LL(1), recursive descant (predictive).
%% -----------------------------------------------------

%%%
%%% parse(string) -> AST.
%%%  AST -> tuple().
%%%
parse("") -> {};

parse(Text) -> expression(Text).

expression(Text) ->
  {Ast, []} = additive(Text),
  Ast.

%% ----------------------------------------------------
%% additive: multiplicative [+ | -] multiplicative ...
%% ----------------------------------------------------

% first multiplicative part of the additive
additive(Text) ->
  {Ast, Rest} = multiplicative(Text),
  additive(Ast, Rest).

% rest additive parts: + multiplicative, or - multiplicative.
additive(Ast, [AddOp | Rest]) when AddOp == $+; AddOp == $- ->
  {Ast1, Rest1} = multiplicative(Rest),
  additive({[AddOp], Ast, Ast1}, Rest1);

% rest part that doesn't match the additive.
additive(Ast, []) -> {Ast, []};
additive(Ast, Rest) -> {Ast, Rest}.

%% ----------------------------------------------------
%% multiplicative: primary [* | /] primary ...
%% ----------------------------------------------------

%% first primary part of the multiplicative
multiplicative(Text) ->
  {Ast, Rest} = primary(Text),
  multiplicative(Ast, Rest).

%% rest multiplicative parts: * primary, or / primary.
multiplicative(Ast, [MultOp | Rest]) when MultOp =:= $*; MultOp =:= $/ ->
  {Ast1, Rest1} = primary(Rest),
  multiplicative({[MultOp], Ast, Ast1}, Rest1);

% rest part that doesn't match multiplicative.
multiplicative(Ast, []) -> {Ast, []};
multiplicative(Ast, Rest) -> {Ast, Rest}.

%% ----------------------------------------------------
%% primary: '(' sum ')' | 0-9 | a-z
%% ----------------------------------------------------

%% '(' sum ')'
primary([$( | Rest]) ->
  {Ast, [$) | Rest1]} = additive(Rest),
  {Ast, Rest1};

% 0-9 digits
primary([D | Rest]) when D >= $0, D =< $9 -> {D - $0, Rest};

% a-z symbols
primary([C | Rest]) when C >= $a, C =< $z -> {[C], Rest}.

test() ->
  1 = parse("1"),
  {"+", 1, 1} = parse("1+1"),
  {"+", 1, {"*", 1, 2}} = parse("1+1*2"),
  {"*", {"+", 1, 1}, 2} = parse("(1+1)*2"),
  ok.

%% Exercise: support whitespaces:
%% 1 + 1
%% 1 + 1 * 2