Parsing markdown with functions

Created: 2017-04-10 Mon 23:35

Parsing a char

We would like to parse the character a.

Design

The parser of a is a function that, given an input string s:

succeds parsing a
or fails parsing a

Implemenentation #1

(defn parse-a [s]
  (if (= \a (first s))
    {:success ["a" (subs s 1)] }
    {:error s }))

Demo

Refactor

Hide implementation

(defn- as-str
  "Ensures wathever is returned as string"
  [whatever]
  (cond (char? whatever) (str whatever)
        (empty? whatever) ""
        (string? whatever) whatever))

(defn- success
  "Creates a success"
  [parsed nonparsed]
  {:success [(as-str parsed) (as-str nonparsed)]})

(defn- fail
  "Creates a failure"
  [s]
  {:failure (as-str s)})

(defn- advance [s]
  (subs s 1))

Implementation #2

(defn parse-a [s]
  (if (= \a (first s))
    (success \a (advance s))
    (fail s)))

Generalize

Now that we know how to parse the a character, we can generalize a bit.

Parsing any character

Given a character c, return a parser that parses c.

(defn p-char
  "Returns a char parser"
  [c]
  (fn [s]
    (if (= c (first s))
      (success c (advance s))
      (fail s))))

Implementation #3

(def parse-a (parse-char \a))

Paradigm shift

From:

(defn parse-a [s]
  (if (= \a (first s))
    {:success ["a" (subs s 1)] }
    {:error s }))

(def parse-a (parse-char \a))

Parsers

Now parsers (a special kind of functions) are the objects we deal with (we use def, not defn).

But we're not there yet.

We have to climb another level.

Next level

We now want to parse either a or b.
We want a single parser that is capable of parsing any of the two.

Implementation #1

(defn parse-a-or-b [a b]
  (fn [s]
    (let [f (first s)]
      (if (or (= a f)
              (= b f))
        (success f (advance s))
        (fail s)))))

Works?

Yes

Are you listening to me?

Parsers are the objects, not characters!
We have left those behind!

We should deal with parsers, not charaters.

(def parse-a (p-char \a))

(def parse-b (p-char \b))

(def parse-a-or-b (p-or parse-a parse-b))

WHAT?!

I have not told you about this p-or yet :$

But we're on the next level, right?

Move on.

p-or

We want a parser that given two parsers p1 and p2 returns a parser that parses what p1 parses or what p2 parses.

(defn p-or [p1 p2]
  (fn [s]
    (let [r1 (p1 s)]
      (if (failure? r1)
        (p2 s)
        (best-match r1 (p2 s))))))

(defn failure? [result]
  (contains? result :failure))

(defn- best-match
  [r1 r2]
  (let [len1 (count (get-parsed r1))
        len2 (count (get-parsed r2))]
    (if (> len1 len2)
      r1
      r2)))

Parser combinators

p-or is a function that given 2 parsers returns another parser.

It is a parser combinator.

This is functional programming, right?

(defn p-apply
  "Returns a parser that parses as p and applies f to
  the parsed result if p succeeds. Fails otherwise, of course."
  [p f]
  (fn [s]
    (let [r (p s)]
      (if (success? r)
        (success (f (get-parsed r))
                 (get-nonparsed r))
        r))))

Review

(defn- as-str
  "Ensures wathever is returned as string"
  [whatever]
  (cond (char? whatever) (str whatever)
        (empty? whatever) ""
        (string? whatever) whatever))

(defn- success
  "Creates a success"
  [parsed nonparsed]
  {:success [(as-str parsed) (as-str nonparsed)]})

(defn- fail
  "Creates a failure"
  [s]
  {:failure (as-str s)})

(defn- advance [s]
  (subs s 1))

(defn- get-parsed
  "Extracts parsed part from success"
  [suc]
  (let [[parsed nonparse] (:success suc)]
    parsed))

(defn- get-nonparsed
  "Extracts next string to be parsed from a success"
  [suc]
  (let [[parsed nonparsed] (:success suc)]
    nonparsed))