DEV Community: bingjia

Part I: Implement an expression interpreter for building DSL - Introduce the PEG parser

bingjia — Sat, 03 Aug 2024 05:36:51 +0000

In the last post I have introduced you the WHY and HOW I start the this project and WHAT the DSL looks like in the end. Starting from this post I will share the implementation of the whole project with you.

Generally, when we implement a language, the first thing comes in our mind is lexer and then parser. So in this post I will introduce to you how I implement my DSL with specified detail but less conception so that it won't be too confused I hope.

What's lexer?

In general, lexer is used for Lexical Analysis or tokenization if you will. Let's take the clause "We will rock you!" (the famous rock and roll music from Queen) as an example. After we tokenize it following the grammar rule of English, it shall output a list [Subject("We"), Auxiliary("will"), Verb("rock"), Object("you"), Punctuation("!")]. So a lexer is mostly used for classify texts into certain types by its lexical meaning. This is significant for us since a syntax is actually consist of lexical elements instead of characters or words.

Usually we implement a lexer with some code generator that can parse Regular Express like Ragel, nex and so on. But I think you will be surprised how easy it is to implement a lexer after checking Lexical Scanning in Go from Rob Pike. He had introduced an interesting pattern to implement a finite-state machine which I think is the core of an lexer.

How about the parser?

So how about a parser? What is it used for? Basically, a parser is used to identify a list of lexical elements with the specified pattern which we also called it grammar. Take the example "We will rock you!" we introduced before, it produces a sequence of [Subject("We"), Auxiliary("will"), Verb("rock"), Object("you"), Punctuation("!")] which matches the pattern of 'Future tense' grammar in English. So this is exactly what a parser do and is so called 'syntax analysis'.

Let's take another example in a more computer way, how about an expression like 1 + 2 * 3 ? It is obvious that they will be translated into [Number(1), Operator(+), Number(2), Operator(*), Number(3)] by the lexer, but what this sequence will be translated into by a parser with a common mathematical expression grammar? In general, a lexical elements sequence will got translated into an Abstract Syntax Tree(or AST in short) by parser like this:

With an abstract syntax tree we can analyze the syntax in the correct order according to the rule of our grammar.

Let's implement a parser

Now we are gonna implement an parser on our own. Well not entirely on our own, we still need some tool to help our to generate code for our parser since it is hard to implement it correctly and a hand-writing parser might be difficult to maintain, even if you do, the performance might be poor.

Luckily, there are many mature parser generative tools that helps us to generate golang code with a grammar definition file. The first choice came in my mind is go-yacc which is the official tool to generate go code for parser. I used to use it to write a SQL analyzer and the it wasn't a pleasure because it:

requires an external lexer.
lack of documentation.
union definition and value type declaration are both quite confusing.

"Why not try something new?" I think, so there we go, with the amazing tool peg I was able to implement both of the lexer and parser in one single grammar file, one single interface. Let's take a closer look at the peg.

A closer look at PEG

PEG stands for Parsing Expression Grammar introduced by Bryan Ford in 2004, which is an alternative to the traditional Context Free Grammar used for describing and expressing programming language syntax and protocol.

For the last decades, we have been using parser generative tool like yacc, bison that supports CFG to generate parser code, and if you have used them before you might find it difficult to avoid ambiguity and integrate them with the lexer or the regular expression. In fact, the syntax of a programming language is not just patterns of lexical elements but also the rules of those lexical elements which somehow the CFG is missing so when we use tools like yacc we will have to implement lexer by our self. Further more, to avoid ambiguity(like the precedence between plus and multiply, check this out) in CFG we have to define the precedence for each operator. All of these crucial fact makes it unnecessarily difficult to develop a parser.

But thanks to Bryan Ford, now we have another good choice, the PEG that allows us to define the lexical and syntax rule all in one single file with a tight DSL and resolve ambiguity in an elegant and simple way. Let me show you how easy it can be done with peg.

Example and code come first

I gonna take examples from my gendsl library which implements a lisp-like syntax(you can check it out here). Here is a simple snippet that can parse hex and decimal number literals in the golang style:

package playground

type parser Peg {
}

Script          <- Value EOF

EOF             <- !.

Value           <- IntegerLiteral

IntegerLiteral  <- [+\-]? ('0' ('x' / 'X') HexNumeral 
                           / DecimalNumeral ) [uU]?

HexNumeral      <- HexDigit ([_]* HexDigit)* / '0'

HexDigit        <- [0-9] / [A-F] / [a-f]

DecimalNumeral  <- [1-9] ([_]* [0-9])* / '0'     

# ...

The first line package gendsl is package declaration which decides which package the generated golang file belongs to. The following type declaration type parser Peg {} used to define the parser type, which we will use it later for evaluation but you can ignore it for now.

After the parser type declaration we can start to define your syntax rule till the end. This is different from the workflow I used to work with with yacc when I have to define a union type and a lot of token types before I can actually define my grammar, which could be really confusing. Anyway, let's take a quick look at the grammar definition.

The very first rule

If you have worked with CFG before you might find the definition DSL syntax quite familiar. The right hand side of the '<-' refers to the pattern of lexical elements, which could be some other patterns or character sequence, and the left hand side is the name of the pattern. Pretty easy, right?

Let's pay attention to the first pattern rule here since the first rule is always to entry point of the parser. The entry point Script here is consist of two parts, one is a rule refers to Value which is consist of a sequence of specified characters(we will get back to this later), the other one EOF is kind of interesting. Let's jump to the next rule to find the pattern of EOF. As you can see, EOF is consist of !.. What does !. mean? The !actually means NOT, and . means any character, so !. means NOTHING AT ALL or End Of File if you will. As a result whenever the parser find there is no character to read, it will stop here and treat it as an dummy rule call EOF which might produces the rule Script. This is quite a common pattern for PEG.

More about the rule syntax

So much like the regular expression(RE), the syntax of PEG is simple:

. stands for any character.
character set like [a-z] is also supported.
X matches one character if X is a character or a pattern when X is the name of an rule.
X? matches one character or pattern or none, while X* matches zero or more and 'X+' matches one or more.
X \ Y matches X or Y where X and Y could be characters, patterns or rule name.

Take the rule of DecimalNumeral as an example. The first part [1-9] means the start of an DecimalNumeral must be one of a digit ranging from 1 to 9, ([_]* [0-9])* means starting from the second position, all character, if there is any, must all be digit(0-9) that has might have no '_' or more than one '_' as its prefix so it could match string like "10_2_3". Otherwise, indicated by the operator \, it could also just be one single character '0' which means 0 obviously .

Resolving ambiguity

I'd like to spend more time to explain the or operator \, since it is quite important as the solution to the ambiguity. The PEG will always try to match the first pattern and then the second, the third and so on til it finds one matched, which is considered as earliest-match-first. For example, a string "ab" will never be able to match the grammar G <- 'a' / 'a' 'b', since the first character 'a' will be reduced to G but the 'b' left cannot match anything. By the way, CFG doesn't allow such a rule and will throw the reduce/shift conflict error.

There is no much syntax left, you can explore them yourself in the pointlander/peg README or peg doc.

Let's have a try

Now that we already have a simple syntax rule prepared above, though it is not the whole grammar for the gendsl project but it can still parse some numbers. Anyway let's generate some code and see if it works as we expect.

Preparation

First we have to install the peg binary tool for code generate following this guide, then we gonna setup our workspace directory for playing:

> mkdir peg_playground && peg_playground 
> go mod init peg_playground 
> touch grammar.peg

Paste the grammar we have before into the peg_playground/grammar.peg, now we should be able to genreate the code using the generate tool but why not make a Makefile in peg_playground/makefile

GO := go

.SUFFIXES: .peg .go

grammar.go: grammar.peg
    peg -switch -inline -strict -output ./$@ $<

all: grammar.go

clean:
    rm grammar.go

Generate and test the parser

Now that we have everything ready, let's generate the code for parser:

make grammar.go

After running the command, you should see a generated grammar.go in the workspace directory. Let's write a function to parse a string and access our parser:

// peg_playground/parser.go
package playground

func PrintAST(script string) error {
    parser := &parser{
        Buffer: script,
        Pretty: true,
    }

    if err := parser.Init(); err != nil {
        return err
    }
    if err := parser.Parse(); err != nil {
        return err
    }

    parser.PrintSyntaxTree()
    return nil
}

The snippet here is pretty simple, it initializes the parser, parses the script we pass to it and print the syntax tree in final. Let's write an unit test to see if it works:

// peg_playground/parser_test.go
package playground

import (
    "testing"
)

func TestPrintTree(t *testing.T) {
    if err := PrintAST(`0x123`); err != nil {
        t.Fatal(err)
    }
    t.Log("-----------------------------------------------------")

    if err := PrintAST(`10_2_3`); err != nil {
        t.Fatal(err)
    }
    t.Log("-----------------------------------------------------")
}

The test function TestPrintTree calls the PrintAST and check the error. Let's run it now and see what it gonna print:

go test . -v

Now we should see the whole syntax tree in the output:

=== RUN   TestPrintTree
Script "0x123"
 Value "0x123"
  IntegerLiteral "0x123"
   HexNumeral "123"
    HexDigit "1"
    HexDigit "2"
    HexDigit "3"
    parser_test.go:11: -----------------------------------------------------
Script "10_2_3"
 Value "10_2_3"
  IntegerLiteral "10_2_3"
   DecimalNumeral "10_2_3"
    parser_test.go:16: -----------------------------------------------------
--- PASS: TestPrintTree (0.00s)
PASS
ok      playground      0.649s

It looks great, right? Everything works as we expected. No syntax error thrown and it prints every rule matched and the string it matches in a format of tree, which could be really useful when debugging.

Wrap it up

In this post, I have introduced you the two basic but significant parts of interpreter programming language:

Lexer, for lexical analysis that transforms a string into a sequence of lexical elements.
Parser, for syntax analysis that identify the the pattern (so called grammar) in the lexical elements and produces a syntax tree.

And then I introduce the PEG for parser code generating, and address its advantages comparing the traditional CFG:

Lexer rule integrated, no standalone lexer need to be implemented.
Simple, regular expression like syntax to start up fast.
No ambiguity, no reduce/shift conflict, always earlier-match-first.

Finally I have a tiny demonstration of how to generate parser with PEG, which is the basis of our interpreter.
In next post, I will walk you through the gendsl grammar in detail.
Thank you for checking this post, hope you enjoy it.

Intro: Implement an expression interpreter for building DSL

bingjia — Sat, 20 Jul 2024 09:21:53 +0000

The other day I ran into a meetup recording video in Youtube presented by William Byrd(a funny and very wise guy) talking about how to write an interpreter in scheme that evaluates scheme itself, which got me fascinated immediately by the simplicity, elegance and power of the meta programing language like common-lisp, scheme and other language in lisp family(you may heard of the parenthesis joke about lisp). I think this video had provided me exactly the right way to introduce a DSL for my rule engine that I have been working on for the last few weeks. So eventually I had came out a DSL framework that enables you to write you DSL in a minutes without dealing with any lexer or parser - a general DSL

I will make a series of blog to share my work and some thoughts during my development. But first, let me show you what I think about the beauty of the idea of DSL(Domain Specified Language) and the story about how I start this project.

Why DSL?

What do we need DSL? The answer is quite simple: to have better interaction between our program and users.
Think about it! Most of our programs or apps accepts some key value pairs as an i nput. For example, a command line tool may accept users input from arguments(e.g. "--key value"), or environment variable(e.g. "KEY=VALUE ./cli"). Even for a http server, we may accept url query(e.g. "http://127.0.0.1:80?key=value"), headers(e.g. "Content-Type: application/json"), or body in json(e.g '{"key": "value"}'). But when a program's behavior depend heavily on user input, key value pairs will become insufficient. Take the famous awk for example, how could you tell awk how to query/filter/extract/format strings with key value pair? Even if you could, the user experience will be a disaster since users will have to fill a lot of key to describe his/her need.

However, with a proper designed DSL as the input of your app, you can have:
1. Better user experience. Since the DSL is domain specified, it can describe what the user want in a simple and brief way so that users won't have to input too much.
2. Decouple with protocol and types. Since a DSL expression is just nothing more than just a simple string, you can easily pass it in the command line arguments, environment variable, http query, http body or even socket. Besides, you can read it in any language(since most language support string type) and that is the beauty of SQL which adapts so many language client and different databases.
3. Readability. Not only it makes it easy for users to describe their need easily, but also frees you from all those checking and validation of users input. The interpreter will do that for you since the grammar is always of certainty.

What I need in my DSL?

Now that I have a reason to import DSL in my rule engine, I should consider what it gonna look like.
Months ago I happened to be asked by my leader to write an expression engine that can evaluate expressions into elasticsearch query or into a golang value, and I solved it by introducing the golang's standard library go/parser to turn golang expressions into an AST(Abstract Syntax Tree) and parse it into different values like elasticsearch query, a simple boolean value or something else. With a few lines of code like this you can parse a golang expression in anyway you want:

package main

import (
    "fmt"
    "go/ast"
    "go/parser"
    "go/token"
)

func main() {
    expr := "true && true"
    root, err := parser.ParseExpr(expr)
    if err != nil {
        panic(err)
    }
    fmt.Println(parseNode(root).(bool)) // => true
}

func parseNode(node ast.Node) any {
    switch v := node.(type) {
    case *ast.BinaryExpr:
        switch v.Op {
        case token.LAND:
            return parseNode(v.X).(bool) && parseNode(v.Y).(bool)
            // ...
        }
    case *ast.Ident:
        switch v.Name {
        case "true":
            return true
        case "false":
            return false
            // ...
        }
        // ...
    }
    panic("unsupported node")
}

I gotta say that the decision of using golang's standard library was a good choice then because:

Only 5 days I was given to finish this job and with the standard library I can have a stable, well-tested compiler without using any lexer or parser.
The golang expression syntax is pretty enough for me.
My colleagues are good at golang so the syntax will be easy to learn and use for them.

But there are also some downsides that I have to deal with it when writing the DSL for my rule engine:

You can't customize your own syntax. You can only have whatever the golang has, not your own keyword, not your own data types.
The readability is terrible as the expression becomes complicated.
Parsing and debugging a AST is difficult to understand for my teammates and sometimes even for me(although I was the one who wrote it).

So I decide to write my own interpreter and I want it to have:

My own syntax, since I am looking for a DSL for a specified domain problem instead of Turing complete programming language.
Accessiblity to values including functions from the host language. I should be able to access value of the host language in the DSL.
Simplicity and readability. I want everyone can pick it up and extends it in five minutes.

After checking out the presentation by William Byrd and some digging into the Racket(another dialect of Lisp), I had already been clear about my tiny DSL. It should be:

1.** It should have the S-Expression syntax.** A S-Expression is either a atom value of a list of atom values. This could make the syntax easy to learn and simple to parse.

It should allow me to access values and even functions from the host language, which is golang for my case.
It should have its own data types so that accessing values or functions in host language in the DSL or writing extension for our DSL won't be confusing.
It should be easy to extension the DSL, or in another word, to control the evaluation of an expression. It was confusing for my colleagues when I am explaining how to implement short circuit for a boolean expression.

At this time, I had realized that I can build more of a DSL for my rule engine but a general and flexible framework to build DSL with the powerful and beautiful S-Expression.

So what does it look like finally?

At the first glance, it looks just like lisp, here is a simple example that can produce a json:

(json
 (if (later-than $NOW 2012)                                  ; condition
     (kv "language" (array "c" "c++" "javascript" "elixir")) ; then
     (kv "language" (array "c" "c++" "javascript")))         ; else
 (kv "typing"
     (dict
      (kv "c" "static")
      (kv "c++" "static")
      (kv "javascript" "dynamic")))
 )

As you can see, the syntax is quite simple. Everything is basically consist of S-Expression, which is either an atomic value like integer/string/boolean/... or an expression in the format of '(X Y Z...)' where 'X' is considered as a function that produces an S-Expression and 'Y', 'Z', ... are considered as the arguments of function 'X'. All those functions like 'kv', 'dict', 'array' and even 'if' are actually implemented in golang. Take 'kv' as an example, the implementation is quite simple:

// _kv evaluate a key and its value then assemble them to a KV struct
func _kv(_ *gendsl.EvalCtx, args []gendsl.Expr, _ map[string]gendsl.Value) (gendsl.Value, error) {
    key, err := args[0].Eval()
    if err != nil {
        return nil, err
    }
    if key.Type() != gendsl.ValueTypeString {
        return nil, errors.Errorf("key is not string, but %+v", key)
    }
    val, err := args[1].Eval()
    if err != nil {
        return nil, err
    }
    return &gendsl.UserData{V: KV{K: string(key.(gendsl.String)), V: val.Unwrap()}}, nil
}

The procedure 'kv' takes two arguments which are actually expressions, evaluates them by args[n].Eval() into values, then constructs a KV struct and return it. With the powerful Eval method, we can even implement 'if' behavior that act more like a macro instead of just simple function:

// _if check the condition of the first argument,
// if condition returns not nil, evaluate the second argument, otherwise the third argument
func _if(_ *gendsl.EvalCtx, args []gendsl.Expr, _ map[string]gendsl.Value) (gendsl.Value, error) {
    condEnv := gendsl.NewEnv().
        WithProcedure("later-than", gendsl.Procedure{Eval: gendsl.CheckNArgs("2", _laterThan)}).
        WithInt("$NOW", _year())

    cond, err := args[0].EvalWithEnv(condEnv)
    if err != nil {
        return nil, err
    }
    if cond.Type() == gendsl.ValueTypeBool && cond.Unwrap().(bool) == true {
        return args[1].Eval()
    }

    return args[2].Eval()
}

You may have noticed, if the condition(first argument) returns true, the second expression will be evaluated but not the third expression! This can never be done with languages like golang that is without macro because we are actually manipulate the AST. So amazing, right?

Finally, with a few lines of code to implement functions like 'kv', 'dict', 'array', and 'if', the script above will produce a JSON output like this(full implementation is here):

{
   "language": ["c", "c++", "javascript", "elixir"],
   "typing": {
      "c": "static",
      "c++": "static",
      "javascript"": "dynamic"
   }
}

To be continue...

As you can see above, the DSL engine I came up with is:

Highly customizable.
Easy to learn and extend.
Typing that is accessible.
Full control of the syntax tree. In the following articles I will share with you about how I implement it from scratch which is really fun and great journey for me. Hope you enjoy this post ❤️