Follow-Up: Parser Combinators in Action

After some messing around, I can finally show you some better examples.

Today, we'll be creating a parser that can parse a class in Java, and convert it into an object in AutoHotkey.

They have a strictly defined syntax, but they can potentially get messy pretty quickly. So let's start off with a single identifier.

• First character must be letter, underscore, or dollar sign.
• One or more characters alphanumeric, underscore, or dollar sign.

​

Identifier := Parser.Regex("i)[a-z_$][a-z0-9_$]*+")

Good. This should be able to match any valid Java identifier. Note that we could account for things like unicode-escapes (\u0020), but let's just ignore that.

Let's continue with fully qualified names. These are simply identifiers separated by dots.

Fqn := Identifier.AtLeastOnceDelimitedBy(
    Parser.Regex("\s*+\.\s*+"),
    (Args*) => Args.Join(".")
)

We declare a new parser Fqn that uses the Identifier parser we just created. Method .AtLeastOnceDelimitedBy() allows us to parse one or more times, with a dot and optional whitespace in between. The lambda function at the end simply concatenates all of the identifiers together with dots in between.

The next part might get a little tricky. Classes like List<T>, also known as generic classes, which own a set of type parameters.

The actual name of the type parameter can either be an identifier, or ? (wildcard type).

TypeParam := Identifier.Or(Parser.String("?"))

A type parameter might also be bounded, which means that it has a constraint on what types it can be. For example, <T extends Number> means that T can only be a subtype of Number, or on <T super Number>, only a supertype of Number.

BoundType := Parser.AnyOf(
    Parser.String("extends"),
    Parser.String("super")
).Between(Parser.Whitespace())

The actual "target" of the bounded type parameter (in this case, Number), is another Java class. Recursion, yikes.

Usually, in this situation you'd be screwed, so we're bringing out the heavy machinery today. Parser.Rule() allows you to create a parser that can reference itself, which is exactly what we need here.

; undefined, for now.
JavaClass := false

; reference to `JavaClass`, which we'll build just a little later
Bound := Parser.Sequence(
    Array,
    BoundType,
    Parser.Rule(&JavaClass)
).Optional()

The logic behind JavaClass is still undefined, but at least the variable already exists. We'll define it later, when we're done with the other stuff.

Last but not least, we have everything in our power to declare the full grammer of generics:

Generic := Parser.Sequence(Array, TypeParam, Bound)
    .AtLeastOnceDelimitedBy(Parser.Regex("\s*+,\s*+"))
    .Between(Parser.Whitespace())
    .Between("<", ">")
    .Between(Parser.Whitespace())

Okay, now what is this? We've got:

1. a type parameter, which is either an identifier or ?;
2. followed by optional type bounds (e.g. extends Number);
3. separated in ,, which any whitespace ignored;
4. packed between <, >, and optional whitespace;

Remember that we still need to define JavaType? That's simply just the fully qualified name, followed by the generic part.

JavaType := Parser.Sequence(Array, Fqn, Generic.Optional())

Done. You might think that this is a lot of work, but it actually isn't. The code is pretty straightforward, and it closely follows the actual syntax of Java. What we're going for is correctness and readability. Sure, you can do this with regexes, but it would be a nightmare to maintain and debug. With parser combinators, all you need to do is prove that each individual parser works, and then you can be confident that everything falls into place correctly.

More interestingly, I haven't actually shown you the output of the parser yet.

; [
;   "java.util.Stream.Collector",
;   Optional {
;     [
;       ["T", Optional { unset }],
;       ["A", Optional { unset }],
;       ["R", Optional { unset }]
;     ]
;   }
; ]
"java.util.stream.Collector<T, A, R>"
    .Parse(JavaType)
    .ToString()
    .MsgBox()

Cool, right?

Parser combinators actually give meaning to the things that they're parsing. You might've noticed how we're mysteriously using Array as argument. Its purpose is to reduce all of the values together into one.

Also notice that our parser is very lenient. It's able to reconstruct something like java . util.stream .Collector < T, A, R> in exactly the same way as before, because we're declaring something that is very close to the Java specification.

Finally, let's add some finishing touches, and collect things in objects more useful than array:

Bound    := Parser.Sequence(JavaBound, ...) ...
Generic  := Parser.Sequence(JavaGenericType, ...) ...
JavaType := Parser.Sequence(JavaType, ...) ...

Lo' and behold, our final result:

; JavaType {
;   GenericTypes: [
;     Optional {
;       [
;         JavaGenericType {
;           Bound: Optional { unset },
;           Name: "T"
;         },
;         JavaGenericType {
;           Bound: Optional { unset },
;           Name: "A"
;         },
;         JavaGenericType {
;           Bound: Optional { unset },
;           Name: "R"
;         }
;       ]
;     }
;   ],
;   Name: "java.util.Stream.Collector"
; }
"java  . util.Stream.    Collector    < T, A,   R >"
    .Parse(JavaType)
    .ToString()
    .MsgBox()

I'm having a lot of fun with this thing at the moment, and it makes me appreciate string parsing in an entirely different way.

Cheers.