The answers have been dis-satisfactory at answering the question of "how to construct an AST".

This article archived from the series Crafting Interpreters, answers it neatly and easily for beginners. Complete with implementation. Stackoverflow is not a place for links so I will copy the main points.

Recursive Descent Parsing

There is a whole pack of parsing techniques whose names mostly seem to be combinations of “L” and “R”—LL(k), LR(1), LALR—along with more exotic beasts like parser combinators, Earley parsers, the shunting yard algorithm, and packrat parsing. For our first interpreter, one technique is more than sufficient: recursive descent.

Recursive descent is the simplest way to build a parser, and doesn’t require using complex parser generator tools like Yacc, Bison or ANTLR. All you need is straightforward hand-written code. Don’t be fooled by its simplicity, though. Recursive descent parsers are fast, robust, and can support sophisticated error-handling. In fact, GCC, V8 (the JavaScript VM in Chrome), Roslyn (the C# compiler written in C#) and many other heavyweight production language implementations use recursive descent. It kicks ass.

It is considered a top-down parser because it starts from the top or outermost grammar rule (here expression) and works its way down into the nested subexpressions before finally reaching the leaves of the syntax tree. This is in contrast with bottom-up parsers like LR that start with primary expressions and compose them into larger and larger chunks of syntax.

A recursive descent parser is a literal translation of the grammar’s rules straight into imperative code. Each rule becomes a function. The body of the rule translates to code roughly like:

Grammar notation    Code representation
Terminal            Code to match and consume a token
NonterminalCall     to that rule’s function
|                   if or switch statement
* or +              while or for loop
?                   if statement

It’s called “recursive descent” because when a grammar rule refers to itself—directly or indirectly—that translates to recursive method calls.

Side notes:

It’s called “recursive descent” because it walks down the grammar. Confusingly, we also use direction metaphorically when talking about “high” and “low” precedence, but the orientation is reversed. In a top-down parser, you reach the lowest-precedence expressions first because they may in turn contain subexpressions of higher precedence. Top-down grammar rules in order of increasing precedence.

Original image link

CS people really need to get together and straighten out their metaphors. Don’t even get me started on which direction the stack is supposed to grow.