# Generate an AST from an indefinite grammar and logic

As said in the title, I have to generate an AST from a grammar and logic (or a"syntax" if you prefer). This grammar and syntax are both indefinite in the program, meaning that it is the user (a developer in this case, because it would not be useful to a"normal" user) must write what it takes in a file for the program to get the necessary elements in order to be able to analyze and produce an AST from code (or other) written in the logic and grammar defined by the user. I've already done AST for a predefined syntax and grammar, but now I don't see how I could do it...

Here is what a user-defined grammar and logic file might look like:

=== grammar ===

.number:
| valid as <-(0-9)*> // Number between 0 and 9, positive or negative taken * times
.sign:
| substraction   '-' as <->
| multiplication '*' as <*>
| division       '/' as </>

=== logic ===

.CorrectFollowing:
| follow [number; sign] with \ {[0]: sign; [-1]: sign} // Must strictly start with a number and end with a number with interval

=== program ===
.MyTest:
| 4+2-1 // --> 5


As you can guess, this grammar and syntax form a simple calculator. We can see an example in the === program === .

I explain you quickly to put you in context:

In the part === grammar ===, we define 2 things :

1. number
2. sign


In these labels, we can find the definition of a token between two' and the name that accompanies it, so that we can identify it in the file (the names and tokens are chosen by the user). So here :

- valid (see explanation above)

- substraction ('-')
- multiplication ('*')
- division ('/')


From all this, the program must be able to analyze and produce an AST from a code following the syntax and grammar defined. So, here, === program === contains the example.

Here is what the AST of the program given in the last part of the code should look like:

     -
/ \
+   1
/ \
4   2


(The priority of the operations (must be) / is respected: the program identifies that it is indeed a calculation.)

The problem is, I don't have any ideas how to implement this (C++). I've already managed to segment the different labels in a std::map<std::string, std::vector<std::string>>, but for the rest...

PS: Sorry, I already asked this question in SO, but I was advised to go here. What I did.

• Are you trying to reinvent the parser generator? Why not use an existing one? Mar 19, 2018 at 13:57
• @reinierpost: Yeah, kind of. I know, it may seem complicated (and it is), but I can only use the standard C++ libraries (+ boost, but I prefer not to, because I never knew how to use it correctly).
– Foxy
Mar 19, 2018 at 19:49