% $Id: ParserFunctions.oz,v 1.9 2011/08/22 20:17:56 leavens Exp $ % Oz version of some of Graham Hutton's % "Higher-order functions for parsing", from the % Journal of Functional Programming, 2(3):323-343, July 1992. % Translated into Oz by Gary T. Leavens. declare %% type = }: >>> local % Compose : }: > fun {Compose F G} fun {$ X} {F {G X}} end end % Fst: }: A> % Snd: }: B> fun {Fst A#_} A end fun {Snd _#B} B end % Lazy versions of append and Map % LAppend: }: > fun lazy {LAppend L1 L2} case L1 of X|Xs then X|{LAppend Xs L2} else L2 end end % LMap: }: > fun lazy {LMap Ls F} case Ls of X|Xs then {F X}|{LMap Xs F} else nil end end % LAppendMap: }: > fun lazy {LAppendMap Ls F} case Ls of X|Xs then {LAppend {F X} {LAppendMap Xs F}} else nil end end in % Pair2List: }: % was called cons in Haskell fun {Pair2List X#Xs} X|Xs end %% primitive parsers (2.1) % P_Succeed : > fun {P_Succeed V} fun lazy {$ Inp} [(V#Inp)] end end % P_Fail : fun lazy {P_Fail _} nil end % P_Satisfy : }: > fun {P_Satisfy Pred} fun lazy {$ Inp} case Inp of nil then {P_Fail nil} [] X|Xs then if {Pred X} then {{P_Succeed X} Xs} else {P_Fail Xs} end end end end % P_Literal : > fun {P_Literal S} {P_Satisfy fun {$ X} X == S end} end %% combinators (2.2) % P_Debug : }: > fun {P_Debug DBP Parsr} fun lazy {$ Inp} {DBP} {Parsr Inp} end end % P_Alt : }: > fun {P_Alt P1 P2} fun lazy {$ Inp} {LAppend {P1 Inp} {P2 Inp}} end end % P_Then : }: >> fun {P_Then P1 P2} fun lazy {$ Inp} {LAppendMap {P1 Inp} fun {$ V1#Out1} {LMap {P2 Out1} fun {$ V2#Out2} (V1#V2)#Out2 end} end} end end % Haskell abbreviations for the above %($|) = P_Alt %($~) = P_Then %% manipulating values (2.3) % Using : }}: > fun {Using P F} fun lazy {$ Inp} {LMap {P Inp} fun {$ (V#Out)} {F V}#Out end} end end % P_Many: }: >> fun {P_Many P} {P_Alt {Using {P_Then P fun lazy {$ Inp} {{P_Many P} Inp} end} % anti-eta, otw. loops! Pair2List} {P_Succeed nil}} end % P_Some: }: >> fun {P_Some P} {Using {P_Then P {P_Many P}} Pair2List} end % other names for the above P_Star = P_Many P_Plus = P_Some % P_XThen : }: % P_ThenX : }: fun {P_XThen P1 P2} {Using {P_Then P1 P2} Snd} end fun {P_ThenX P1 P2} {Using {P_Then P1 P2} Fst} end % I added the following for the common case of lists separated by some token, % where we don't care about the separators % P_Some_Sep_By : }: }: % >>> fun {P_Some_Sep_By SeparatorParser} fun {$ P} {Using {P_Then P {P_Many {P_XThen SeparatorParser P}}} Pair2List} end end % The following also throws away the separators. % P_Many_Sep_By : }: }: % >>> fun {P_Many_Sep_By SeparatorParser} fun {$ P} {P_Alt {{P_Some_Sep_By SeparatorParser} P} {P_Succeed nil}} end end %% lexical analysis % P_Number : P_Number = {P_Some {P_Satisfy Digit}} % Digit: fun {Digit X} (&0 =< X) andthen (X =< &9) end % P_Word : P_Word = {P_Some {P_Satisfy Letter}} fun {Letter X} if {Not {IsChar X}} then raise notAChar(X isAtom: {IsAtom X}) end end ((&a =< X) andthen (X =< &z)) orelse ((&A =< X) andthen (X =< &Z)) end % P_Alphanum P_Alphanum = {P_Some {P_Satisfy fun {$ X} {Letter X} orelse {Digit X} orelse X == &_ end}} % I changed "string" to "P_These_Lits" as it wasn't just for string literals % P_These_Lits : }: >> fun {P_These_Lits Ls} case Ls of nil then {P_Succeed nil} [] X|Xs then {Using {P_Then {P_Literal X} {P_These_Lits Xs}} Pair2List} end end % Haskell abbreviations for the above % (/$~) = xthen % ($~/) = thenx % ($->) = p_return %% free-format input (3.1) % P_Nibble : }: > fun {P_Nibble P} local P_White = {P_Many {{P_Any P_Literal} " \t\n"}} in {P_ThenX {P_XThen P_White P} P_White} end end % P_Any is satisfied by any parser generated from the list % P_Any : >}: }: >> fun {P_Any AtoP} fun {$ LsOfA} {FoldR LsOfA fun {$ A ResP} {P_Alt {AtoP A} ResP} end P_Fail} end end % P_Symbol : > P_Symbol = {Compose P_Nibble P_These_Lits} %% syntax analysis (4.5) % P_Opt : B}: > fun {P_Opt P V} {P_Alt P {P_Succeed V}} end %% Parser Monad operations (5.4) % P_Return : }: >> fun {P_Return P} fun {$ V} {Using P fun {$ Y} V end} end end % The combinator `into` first parses using p, then sends the result to f, % which parses the remaining input. % It acts like bind (i.e., >>=) of a Haskell monad. % P_Into : }: > fun {P_Into P F} local fun {G X} case X of (V#Inp2)|Others then {LAppend {F V Inp2} {G Others}} else nil end end in fun lazy {$ Inp} {G {P Inp}} end end end end