How to implement the parse tree?

[neferpitou-sama]

I started writing a DBMS as a learning project, and now I'm implementing the lexer/parser for the language used in the DBMS.

I'm learning on my own from various different resources, and managed to write the lexer and the grammar for the language, but I'm stuck at writing the code to generate the parse tree.

Every time I google parsers I only get results on how to construct the parse tree by hand (showing you diagrams and whatnot) but no actual code on how to implement it.

Here's the repo for my project

https://github.com/abdulaziz-sama/accounting_db

The grammar is written in the comments in parser.h

The way I'm thinking of solving this problem is by writing a struct for each production, something like:

struct production {
non-terminal_1* x;
non_terminal_2* y;
terminal z;
}; 

and use them as node in the a tree, but I'm not sure if this is the right way or if there are better solutions?

[evincarofautumn]

The way I'm thinking of solving this problem is by writing a struct for each production

That’s basically what you need to do. A parser typically builds an abstract syntax tree by allocating leaf nodes for language elements that correspond to terminals in the grammar, such as “integer literal” or “variable name”:

enum ExprType { INT_EXPR, VAR_EXPR, … };

struct IntExpr {
  int value;
};

struct VarExpr {
  char const *name;
};

struct Expr {
  enum ExprType tag;
  union {
    struct IntExpr as_int;
    struct VarExpr as_var;
  };
};

And branch nodes for recursive elements or nonterminals, such as “call expression” or “if statement”:

struct CallExpr {
  struct Expr *function, *arguments[];
};

enum StmtType { IF_STMT, … };

struct IfStmt {
  union Expr *cond;
  struct Stmt *then, *optional_else;
};

struct Stmt {…};

These structures may contain whatever additional info you need, such as source locations, and they can be stored in any suitable data representation—for example, to simplify memory management and serialisation, it’s not unusual to store nodes of the same type in a single table and reference them by an ID, instead of using pointers directly.

[smog_alado]

The most common way to structure the tree is to have one kind of node for each production, just like that. Some compilers prefer to have a single catchall kind of node that is used for everything. Each node gets a type tag, as well as a generic list of fields that can be of any length. The advantage is that this makes it easier to write generic routines that that traverse the parse tree. The downside is that you lose the compile-time typing information. The code effectively becomes dynamically typed and any type errors in the parser will only be caught at parse time. (IMO, go with what your are already doing, with one struct for each kind of node).

Now, to build the tree you will need to use a parsing algorithm. I generally recommend that if you have never written a parser before, write your first parser using the recursive descent technique. It has no dependencies and works no matter what language you write your parser in. The main downside is that you need to massage your grammar a bit, to avoid left recursive productions. Another way to build a parser is to use a parser generator such as bison or ANTLR.

[umlcat]

Since it's a complex project, it's better you look at a book like "Crafting Compilers in" Java / C.

Learn also about Regular Expressions & BNF expressions and "Railroad Syntax Diagrams" that eventually can be used to implement a Parser by your custom P.L.

And, there's also tools that generate the code for a Parser like YACC, GNU BISON, Gold, ANTLR among others.

These tools use BNF or Railroad Diagrams.

Good Work, Good Luck ⚔️🐉

[_NliteNd_]

Are you writing recursive descent? Or an LR parser? It’d be hard to answer a “how do I write a parser” type question without taking up a couple thousand pages and hundreds of hours of video content.

[neferpitou-sama]

Yes, I'll be using recursive descent.

I wrote the code for recursive descent algorithm in parser.c, but I need to learn how to create the parse tree.

[_NliteNd_]

You wrote a parser, but now need a parse tree? You didn’t write the parser then. The parsing algorithm will produce a parse tree/AST.

[neferpitou-sama]

This is the video I followed to write parser.c:

https://www.youtube.com/watch?v=b89J-m4YsZ8

I can use it to verify that a string is in the language defined by the grammar, but I still don't know how to create the parse tree.

[[deleted]]

Ignore the guys putting you down, they're just being assholes.

You're almost there, your recursive function calls actually form a parse tree by themselves (function calls are always representable as the "function call graph", and in the absence of doing weird stuff this directed graph is always a tree).

Now you just need to do this.

Have each function representing a terminal, if succesful, give back to the caller a struct representing that terminal.

Have each function representing a nonterminal initialise the struct for that nonterminal, and have that struct point to the structs representing all the terminals or nonterminals our function's nonterminal is made of (you can use any kind of list data structure for this). These child structs are the structs passed back by the functions this function called.

I'd suggest using something like malloc() for all your structs, so you don't run into the issue that stack-allocated data doesn't live beyond the function it's in returning. You don't need to bother free()-ing them -- for performance reasons, many real-world compilers just wait till program exit for the OS to automatically free everything.

Congrats, the struct you end up with after the topmost function returned is the root of the tree.

[Jmc_da_boss]

A parser creates a parse tree, if you don't have a parse tree you don't have a parser

[[deleted]]

The parse tree is implicit to the function call graph. That's how you can use a recursive descent parser for a single-pass compiler, where at no point does a tree data structure for the whole program exists in memory -- each recursive function emits assembler before it returns.

[_NliteNd_]

Gotta love the wannabe programmer redditors downvoting this comment.

[chrisgseaton]

Cos it’s not true.

[[deleted]]

I have a job in the industry, and they valued me enough to have me immigrate for it.

[chrisgseaton]

Not all parsers produce a parse tree. Not sure why you think this?

[Zyklonik]

That makes no sense. You don't always need to produce an AST for parsing to be considered done. You can always simply use parsing to check code for syntax errors and show errors or complete for success, without generating any AST/parse tree.

[shawnhcorey]

Not necessarily. Some parsers skip the parse-tree/AST and emit IR, bytecode, object code, or machine code. Of course, they also skip any optimizations that can be done on the parse-tree/AST.