-
-
Save mrvicadai/0fd9fea97a7f8cd30be34239c4ea38be to your computer and use it in GitHub Desktop.
Really barebones start of a parser combinator in ReasonML/OCaml
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| type result('a) = | |
| | Success('a) | |
| | Failure(string); | |
| /* Encapsulate a parsing function in a type */ | |
| type parser('a) = | |
| | Parser(string => result(('a, string))); | |
| let reduce = (fn, list) => | |
| switch list { | |
| | [] => raise(Not_found) | |
| | [x, ...xs] => List.fold_left(fn, x, xs) | |
| }; | |
| let parse_char = charToMatch => { | |
| let innerFn = str => | |
| if (String.length(str) == 0) { | |
| Failure("No more input!"); | |
| } else { | |
| let first = str.[0]; | |
| if (first == charToMatch) { | |
| let remaining = str |> Js.String.sliceToEnd(~from=1); | |
| let strChar = String.make(1, charToMatch); | |
| let res = (strChar, remaining); | |
| Success(res); | |
| } else { | |
| let msg = | |
| Printf.sprintf("Expected '%c'. Got '%c'", charToMatch, first); | |
| Failure(msg); | |
| }; | |
| }; | |
| /* Return the inner function in a Parser type */ | |
| Parser(innerFn); | |
| }; | |
| /* Helper function that extracts innerFn and runs it against the input */ | |
| let run = (parser, input) => { | |
| let Parser(innerFn) = parser; | |
| innerFn(input); | |
| }; | |
| /* helper function that lifts a normal function into a Parser function*/ | |
| let mapP = (f, parser) => { | |
| let innerFn = input => { | |
| /* run parser with input*/ | |
| let result = run(parser, input); | |
| /* test for failure or success*/ | |
| switch result { | |
| | Failure(err) => Failure(err) | |
| | Success(x) => | |
| let (value, remaining) = x; | |
| let newValue = | |
| f(value); /* On success return the value transformed by f */ | |
| let res = (newValue, remaining); | |
| Success(res); | |
| }; | |
| }; | |
| Parser(innerFn); | |
| }; | |
| /* Compose two parsers into a sequence */ | |
| let andThen = (parser1, parser2) => { | |
| let innerFn = input => { | |
| let result1 = run(parser1, input); | |
| switch result1 { | |
| | Failure(err) => Failure(err) | |
| | Success(x) => | |
| let (value1, remaining1) = x; | |
| let result2 = run(parser2, remaining1); | |
| switch result2 { | |
| | Failure(err) => Failure(err) | |
| | Success(x) => | |
| let (value2, remaining2) = x; | |
| let newValue = (value1, value2); | |
| let res = (newValue, remaining2); | |
| Success(res); | |
| }; | |
| }; | |
| }; | |
| Parser(innerFn); | |
| }; | |
| /* orElse matches `A` or `B` */ | |
| let orElse = (parser1: parser('a), parser2: parser('a)) : parser('a) => { | |
| let innerFn = input => { | |
| let result1 = run(parser1, input); | |
| switch result1 { | |
| | Success(_result) => result1 | |
| | Failure(_err) => | |
| let result2 = run(parser2, input); | |
| result2; | |
| }; | |
| }; | |
| Parser(innerFn); | |
| }; | |
| /* returnP transforms a normal value into a Parser value*/ | |
| let returnP = x => { | |
| let innerFn = input => { | |
| let res = (x, input); | |
| Success(res); | |
| }; | |
| Parser(innerFn); | |
| }; | |
| let applyP = (fP, xP) => andThen(fP, xP) |> mapP(((f, x)) => f(x)); | |
| /* Choose from a list of parsers*/ | |
| let choice = listOfParsers => reduce(orElse, listOfParsers); | |
| /* Choose any of a list of chars */ | |
| let anyOf = listOfChars => listOfChars |> List.map(parse_char) |> choice; | |
| /* Test it out */ | |
| let parseA = parse_char('A'); | |
| let parseB = parse_char('B'); | |
| let parseA_then_B = parseB |> andThen(parseA); | |
| let parseA_OrElse_B = parseB |> orElse(parseA); | |
| let firstTest = run(parseA_then_B, "ABC"); /* test the andThen combinator */ | |
| let secondTest = run(parseA_OrElse_B, "AFD"); /* test the orElse combinator */ | |
| /* Testing choosing from a list of parsers */ | |
| let parseLowercase = anyOf(['a', 'b', 'c', 'd', 'e', 'z']); | |
| let parseDigit = anyOf(['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']); | |
| let parseThreeDigitsAsStr = { | |
| let parsedfirst = andThen(parseDigit, parseDigit); | |
| let tupleParser = andThen(parsedfirst, parseDigit); | |
| let transformTuple = (((c1, c2), c3)) => Js.Array.join([|c1, c2, c3|]); | |
| mapP(transformTuple, tupleParser); | |
| }; | |
| let parseThreeDigitsAsInt = mapP(int_of_string, parseThreeDigitsAsStr); | |
| let thirdTest = run(parseLowercase, "aBC"); | |
| let fourthTest = run(parseDigit, "1ABC"); | |
| Js.log(firstTest); | |
| Js.log(secondTest); | |
| Js.log(thirdTest); | |
| Js.log(fourthTest); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment