1-module(arithmetic).
2-export([parse/1,file/1]).
3-compile(nowarn_unused_vars).
4-compile({nowarn_unused_function,[p/4, p/5, p_eof/0, p_optional/1, p_not/1, p_assert/1, p_seq/1, p_and/1, p_choose/1, p_zero_or_more/1, p_one_or_more/1, p_label/2, p_string/1, p_anything/0, p_charclass/1, line/1, column/1]}).
5
6
7
8file(Filename) -> {ok, Bin} = file:read_file(Filename), parse(binary_to_list(Bin)).
9
10parse(Input) ->
11  setup_memo(),
12  Result = case 'additive'(Input,{{line,1},{column,1}}) of
13             {AST, [], _Index} -> AST;
14             Any -> Any
15           end,
16  release_memo(), Result.
17
18'additive'(Input, Index) ->
19  p(Input, Index, 'additive', fun(I,D) -> (p_choose([p_seq([fun 'multitive'/2, p_string("+"), fun 'additive'/2]), fun 'multitive'/2]))(I,D) end, fun(Node, Idx) ->
20case Node of
21  Int when is_integer(Int) -> Int;
22  [A, "+", B] -> A + B
23end
24 end).
25
26'multitive'(Input, Index) ->
27  p(Input, Index, 'multitive', fun(I,D) -> (p_choose([p_seq([fun 'primary'/2, p_string("*"), fun 'multitive'/2]), fun 'primary'/2]))(I,D) end, fun(Node, Idx) ->
28case Node of
29  Int when is_integer(Int) -> Int;
30  [A,"*",B] -> A * B
31end
32 end).
33
34'primary'(Input, Index) ->
35  p(Input, Index, 'primary', fun(I,D) -> (p_choose([p_seq([p_string("("), fun 'additive'/2, p_string(")")]), fun 'decimal'/2]))(I,D) end, fun(Node, Idx) ->
36case Node of
37  Int when is_integer(Int) -> Int;
38  List when is_list(List) -> lists:nth(2,List)
39end
40 end).
41
42'decimal'(Input, Index) ->
43  p(Input, Index, 'decimal', fun(I,D) -> (p_one_or_more(p_charclass("[0-9]")))(I,D) end, fun(Node, Idx) -> list_to_integer(Node) end).
44
45
46
47
48
49
50p(Inp, Index, Name, ParseFun) ->
51  p(Inp, Index, Name, ParseFun, fun(N, _Idx) -> N end).
52
53p(Inp, StartIndex, Name, ParseFun, TransformFun) ->
54  % Grab the memo table from ets
55  Memo = get_memo(StartIndex),
56  % See if the current reduction is memoized
57  case dict:find(Name, Memo) of
58    % If it is, return the result
59    {ok, Result} -> Result;
60    % If not, attempt to parse
61    _ ->
62      case ParseFun(Inp, StartIndex) of
63        % If it fails, memoize the failure
64        {fail,_} = Failure ->
65          memoize(StartIndex, dict:store(Name, Failure, Memo)),
66          Failure;
67        % If it passes, transform and memoize the result.
68        {Result, InpRem, NewIndex} ->
69          Transformed = TransformFun(Result, StartIndex),
70          memoize(StartIndex, dict:store(Name, {Transformed, InpRem, NewIndex}, Memo)),
71          {Transformed, InpRem, NewIndex}
72      end
73  end.
74
75setup_memo() ->
76  put(parse_memo_table, ets:new(?MODULE, [set])).
77
78release_memo() ->
79  ets:delete(memo_table_name()).
80
81memoize(Position, Struct) ->
82  ets:insert(memo_table_name(), {Position, Struct}).
83
84get_memo(Position) ->
85  case ets:lookup(memo_table_name(), Position) of
86    [] -> dict:new();
87    [{Position, Dict}] -> Dict
88  end.
89
90memo_table_name() ->
91    get(parse_memo_table).
92
93p_eof() ->
94  fun([], Index) -> {eof, [], Index};
95     (_, Index) -> {fail, {expected, eof, Index}} end.
96
97p_optional(P) ->
98  fun(Input, Index) ->
99      case P(Input, Index) of
100        {fail,_} -> {[], Input, Index};
101        {_, _, _} = Success -> Success
102      end
103  end.
104
105p_not(P) ->
106  fun(Input, Index)->
107      case P(Input,Index) of
108        {fail,_} ->
109          {[], Input, Index};
110        {Result, _, _} -> {fail, {expected, {no_match, Result},Index}}
111      end
112  end.
113
114p_assert(P) ->
115  fun(Input,Index) ->
116      case P(Input,Index) of
117        {fail,_} = Failure-> Failure;
118        _ -> {[], Input, Index}
119      end
120  end.
121
122p_and(P) ->
123  p_seq(P).
124
125p_seq(P) ->
126  fun(Input, Index) ->
127      p_all(P, Input, Index, [])
128  end.
129
130p_all([], Inp, Index, Accum ) -> {lists:reverse( Accum ), Inp, Index};
131p_all([P|Parsers], Inp, Index, Accum) ->
132  case P(Inp, Index) of
133    {fail, _} = Failure -> Failure;
134    {Result, InpRem, NewIndex} -> p_all(Parsers, InpRem, NewIndex, [Result|Accum])
135  end.
136
137p_choose(Parsers) ->
138  fun(Input, Index) ->
139      p_attempt(Parsers, Input, Index, none)
140  end.
141
142p_attempt([], _Input, _Index, Failure) -> Failure;
143p_attempt([P|Parsers], Input, Index, FirstFailure)->
144  case P(Input, Index) of
145    {fail, _} = Failure ->
146      case FirstFailure of
147        none -> p_attempt(Parsers, Input, Index, Failure);
148        _ -> p_attempt(Parsers, Input, Index, FirstFailure)
149      end;
150    Result -> Result
151  end.
152
153p_zero_or_more(P) ->
154  fun(Input, Index) ->
155      p_scan(P, Input, Index, [])
156  end.
157
158p_one_or_more(P) ->
159  fun(Input, Index)->
160      Result = p_scan(P, Input, Index, []),
161      case Result of
162        {[_|_], _, _} ->
163          Result;
164        _ ->
165          {fail, {expected, Failure, _}} = P(Input,Index),
166          {fail, {expected, {at_least_one, Failure}, Index}}
167      end
168  end.
169
170p_label(Tag, P) ->
171  fun(Input, Index) ->
172      case P(Input, Index) of
173        {fail,_} = Failure ->
174           Failure;
175        {Result, InpRem, NewIndex} ->
176          {{Tag, Result}, InpRem, NewIndex}
177      end
178  end.
179
180p_scan(_, [], Index, Accum) -> {lists:reverse( Accum ), [], Index};
181p_scan(P, Inp, Index, Accum) ->
182  case P(Inp, Index) of
183    {fail,_} -> {lists:reverse(Accum), Inp, Index};
184    {Result, InpRem, NewIndex} -> p_scan(P, InpRem, NewIndex, [Result | Accum])
185  end.
186
187p_string(S) ->
188  fun(Input, Index) ->
189      case lists:prefix(S, Input) of
190        true -> {S, lists:sublist(Input, length(S)+1, length(Input)), p_advance_index(S,Index)};
191        _ -> {fail, {expected, {string, S}, Index}}
192      end
193  end.
194
195p_anything() ->
196  fun([], Index) -> {fail, {expected, any_character, Index}};
197     ([H|T], Index) -> {H, T, p_advance_index(H, Index)}
198  end.
199
200p_charclass(Class) ->
201  fun(Inp, Index) ->
202     {ok, RE} = re:compile("^"++Class),
203      case re:run(Inp, RE) of
204        {match, _} ->
205          {hd(Inp), tl(Inp), p_advance_index(hd(Inp), Index)};
206        _ -> {fail,{expected, {character_class, Class}, Index}}
207      end
208  end.
209
210line({{line,L},_}) -> L;
211line(_) -> undefined.
212
213column({_,{column,C}}) -> C;
214column(_) -> undefined.
215
216p_advance_index(MatchedInput, Index) when is_list(MatchedInput) -> % strings
217  lists:foldl(fun p_advance_index/2, Index, MatchedInput);
218p_advance_index(MatchedInput, Index) when is_integer(MatchedInput) -> % single characters
219  {{line, Line}, {column, Col}} = Index,
220  case MatchedInput of
221    $\n -> {{line, Line+1}, {column, 1}};
222    _ -> {{line, Line}, {column, Col+1}}
223  end.
224