In[3]:= (*
grammars
parse[g, input, succ, fail] =>
succ [result, remainingInput]
or
fail[reason, remainingInput]
*)
In[4]:= match[g_String, input_] :=
If[prefix[input, g],
ok[StringDrop[input, StringLength[g]]],
fail[expected[g], input]]
In[5]:= prefix[s_String, pre_String]:= prefix[Characters[s], Characters[pre]]
In[6]:= prefix[{s_, smore___}, {s_,premore___}]:= prefix[{smore}, {premore}]
In[7]:= prefix[s_List, {}]:= True
In[8]:= prefix[_List,_List] := False
In[9]:= match[end, ""]:=ok[""]
In[10]:= match[end, inp_]:=fail[expected[end], inp]
(* sequences *)
In[11]:= match[a_<b__, input_]:=
Replace[match[a,input],
{ ok[rem_]:>match[Precedes[b],rem],
ok[___]:>fail[0,0]}]
In[12]:= match[empty, input_]:=ok[input]
(* alternates *)
In[13]:= match[a_||b__, input_]:=
Replace[match[a, input],
{ fail[__]:>match[Or[b],input]}]
(* base cases *)
In[14]:= match[Precedes[a_],input_]:=match[a,input]
In[15]:= match[Or[a_], input_]:=match[a,input]
In[16]:= match[repeat[a_],input_] :=
Replace[match[a,input],
{ok[rem_]:> match[repeat[a], rem],
fail[__]:> ok[input]}]
In[17]:= match[Hold[a_],input_] := match[a, input]
(* example use - 4 function calculator grammar *)
In[18]:= fourFunction =
Module[{add,fact,atom,digit},
add:=fact < repeat["+" <fact];
fact := atom < repeat["*" < atom];
atom := (digit <repeat[digit])
||("("<Hold[add]<")");
digit :=("0"|| "1"||"2"||"3"||"4"||"5"||"6"||"7"||"8"||"9");
(* return grammar: *)
add<end]
Out[18]= ((((0||1||2||3||4||5||6||7||8||9)<repeat[0||1||2||3||4||5||6||7||8||9]||(<Hold[add$847]<))<repeat[*<((0||1||2||3||4||5||6||7||8||9)<repeat[0||1||2||3||4||5||6||7||8||9]||(<Hold[add$847]<))])<repeat[+<(((0||1||2||3||4||5||6||7||8||9)<repeat[0||1||2||3||4||5||6||7||8||9]||(<Hold[add$847]<))<repeat[*<((0||1||2||3||4||5||6||7||8||9)<repeat[0||1||2||3||4||5||6||7||8||9]||(<Hold[add$847]<))])])<end
In[22]:= match[fourFunction, "1+2*3"]
Out[22]= ok[]