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[]