Create a gist now

Instantly share code, notes, and snippets.

A Parser Combinator in Elixir
defmodule ElxParser do
def s(prefix) do
fn input ->
if String.starts_with?(input, prefix) do
input_len = String.length(input)
prefix_len = String.length(prefix)
{:success, String.slice(input, 0..(prefix_len - 1)), String.slice(input, (prefix_len..(input_len - 1)))}
else
{:failure, input}
end
end
end
def alt(x, y) do
fn input ->
result = x.(input)
case result do
{:failure, _} -> y.(input)
otherwise -> otherwise
end
end
end
def seq(x, y) do
fn input ->
case x.(input) do
{:success, v1, next1} ->
case y.(next1) do
{:success, v2, next2} -> {:success, {v1, v2}, next2}
otherwise -> otherwise
end
otherwise -> otherwise
end
end
end
def loop(parser, rest, results) do
case parser.(rest) do
{:success, v, next} -> loop(parser, next, [v|results])
{:failure, next} -> {:success, Enum.reverse(results), next}
end
end
def rep(x) do
fn input ->
{:success, values, next} = loop(x, input, [])
{:success, values, next}
end
end
def rule(block) do
fn input ->
(block.()).(input)
end
end
def flat_map(parser, f) do
fn input ->
case parser.(input) do
{:failure, _} -> {:failure, input}
{:success, v, next} -> (f.(v)).(next)
end
end
end
def map(parser, f) do
fn input ->
case parser.(input) do
{:success, v, next} -> {:success, f.(v), next}
otherwise -> otherwise
end
end
end
def regex(literal) do
fn input ->
case Regex.run(literal, input, return: :index) do
nil -> {:failure, input}
[{first, last}] ->
if first != 0 do
{:failure, input}
else
{:success, String.slice(input, 0..(last - 1)), String.slice(input, last..(String.length(input) - 1))}
end
end
end
end
def chainl(p, q) do
map(
seq(p, rep(seq(q, p))),
fn values ->
{x, xs}= values
List.foldl(
xs,
x,
fn (r, a) ->
{f, e} = r
f.(a, e)
end
)
end
)
end
end
defmodule ElxParserTest do
use ExUnit.Case
import ElxParser
doctest ElxParser
def e do
rule(fn ->
a
end)
end
def a do
rule(fn ->
chainl(
m,
alt(
map(s("+"), fn _ ->
fn lhs, rhs ->
lhs + rhs
end
end),
map(s("-"), fn _ ->
fn lhs, rhs ->
lhs - rhs
end
end)
)
)
end)
end
def m do
rule(fn ->
chainl(
p,
alt(
map(s("*"), fn _ ->
fn lhs, rhs ->
lhs * rhs
end
end),
map(s("/"), fn _ ->
fn lhs, rhs ->
lhs * rhs
end
end)
)
)
end)
end
def p do
rule(fn ->
alt(
map(seq(seq(s("("), e), s(")")), fn result ->
{{"(", v}, ")"} = result
v
end),
n
)
end)
end
def n do
map(regex(~r/[0-9]+/), fn v1 ->
{v2, _} = Integer.parse(v1)
v2
end)
end
test "parser" do
assert {:success, 21, ""} == e.("(1+2)*(3+4)")
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment