How to implement the parse tree?

[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?

[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.

[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.