How to convert a string into a AST object with Javascript?

Question

I need to convert a string into an object (AST like) obeying rules from a specific grammar.

I basically have 3 types of expressions ('@', '$' and '#'). The expressions of type '#' are written as #something while the other two are written as @something==somethingelse and $something==somethingelse.

These expressions can be grouped using conjunctions ('and', 'or') and the order to operations can be modified using parenthesis.

Here is an example of a complete expression:

const expression = 
     `#buy
      && (@car == white || @bike == blue)
      && $user==authenticated`;

I'm looking for a way to convert that into the object (AST like) bellow using javascript or a tool based in javascript (will use in a React project).

const ast = {
    type: 'expression',
    conjunction: 'null',
    expressions: [{
            type: 'expression',
            conjunction: null,
            expressions: [{
                type: '#',
                left: 'buy',
                operator: null,
                right: null
            }]
        },
        {
            type: 'expression',
            conjunction: '&&',
            expressions: [{
                    type: 'expression',
                    conjunction: 'null',
                    expressions: [{
                        type: '@',
                        left: 'car',
                        operator: '==',
                        right: 'white'
                    }]
                },
                {
                    type: 'expression',
                    conjunction: '||',
                    expressions: [{
                        type: '@',
                        left: 'bike',
                        operator: '==',
                        right: 'blue'
                    }]
                }
            ]
        },
        {
            type: 'expression',
            conjunction: '&&',
            expressions: [{
                type: '$',
                left: 'user',
                operator: '==',
                right: 'authenticaded'
            }]
        }
    ]
};

While I do find my curiosity aroused by the question, I don't feel that it is answerable in its' current state due to the sheer size of the solution to this problem - you're asking for how to implement a custom DSL interpreter/renderer, which is usually the topic for very thick textbooks! :) Is there some approach(es) you're considering that we can help you decide upon, or something more similarly concrete? — Josh E, Oct 05 '18 at 16:12
I've tried to solve this in two different ways so far. 1) Using Regex and I found myself going down a rabbit hole. 2) Using a tool, ANTLR that is based on Java but can generate a visitor in javascript. I was looking for ideas on how to approach this more than a specific solution even though the latest would be appreciated. :) — Vinicius Santana, Oct 05 '18 at 16:15
thanks for the additional info. Hopefully my answer provides the sort of guidance you're looking for! — Josh E, Oct 05 '18 at 16:37
OP wants to parse expressions. This isn't anywhere near as hard as building a full DSL, nor does it require complex machinery. He should check out my discussion of how to build recursive descent parsers, which also discusses how to build ASTs as part of the parsing process. He'll be able to code this in JavaScript pretty easily following my examples. See https://stackoverflow.com/a/2336769/120163 — Ira Baxter, Oct 06 '18 at 03:13
Thank you for the link, @Ira Baxter. The OP requested "ideas on how to approach this more than a specific solution", I would appreciate if you could elaborate on what you mean by "...building a full DSL" - wouldn't you consider the expression syntax to be a DSL? — Josh E, Oct 08 '18 at 14:08
An "expression syntax" is a DSL. But they tend to be pretty trivial in their syntax, whereas a complex DSL ... well can have complex (useful) syntax. Expression "DSLs" trivial syntax is easy to parse by simple parsing schemes, so that makes an interesting special case; follow the link I supplied for a complete, easy answer, incluidng examples of expression parsers. Full DSLs... might require a much more sophisticated parsing scheme to process the text. — Ira Baxter, Oct 08 '18 at 14:48
Possible duplicate of [Constructing an Abstract Syntax Tree with a list of Tokens](https://stackoverflow.com/questions/25049751/constructing-an-abstract-syntax-tree-with-a-list-of-tokens) — Josh E, Oct 08 '18 at 18:35

score -1 · Answer 1 · answered Oct 05 '18 at 16:35

While there are going to be nuances specific to your situation, and though it sounds obvious, it might help to break down the problem into more manageable chunks.

One chunk of this problem is going to be the parsing of and subsequent tokenization of your expression strings. Start by writing some code that can take a string like #something and turn it into an intermediate data structure which can later be leveraged to perform more specific tasks relating to constructing your AST. The idea is that you want to wrap the Simplest-thing-that-could-possibly-work into a black-box that allows you to improve/change/add to the functionality incrementally and reliably. Try not to over-engineer at first and only add functionality relevant to the current task-at-hand to avoid falling into an analysis-paralysis trap.

Once you've done some iteration on the tokenization step, you can start thinking about the next stage, which is the implementation of a Visitor/Walker for your AST. I feel confident in saying that your design will evolve as you go through this process, so it's critically important that you engineer your code for change -- which should include testability as a primary consideration.

Though it's not javascript, this C#/Roslyn based project (full disclosure: I'm the author/maintainer of that repos) demonstrates pretty closely the types of functionality you're asking about. HTH

The 'intermediate data structure' is going to be your DSL's equivalent of the HTML DOM in many respects. Try to look for familiar patterns in the tools and frameworks you know best and then pilfer them for ideas and approaches! — Josh E, Oct 05 '18 at 16:58

How to convert a string into a AST object with Javascript?

1 Answers1