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