# Pushdown automaton from given code for parsing a while statement

I was preparing for my exam and have some questions that can possibly come on the test. There is a task to make pushdown automata from a given code:

void compile_while() {
// while ( expression )
if (symbol == SYM_WHILE) {
get_symbol();

if (symbol == SYM_LPARENTHESIS) {
get_symbol();

compile_expression();

if (symbol == SYM_RPARENTHESIS) {
get_symbol();

// zero or more statements: { statement }
if (symbol == SYM_LBRACE) {
get_symbol();

while (is_not_rbrace_or_eof())
compile_statement();

if (symbol == SYM_RBRACE)
get_symbol();
else {
syntax_error_symbol();

exit(EXITCODE_PARSERERROR);
}
} else
// only one statement without {}
compile_statement();
} else
syntax_error_symbol();
} else
syntax_error_symbol();
} else
syntax_error_symbol();
}


First of all, I don't understand why we need to construct PDA for it because we can do it without stack too and second, I don't understand how the pushdown automata for it would look like.

Can someone help me to understand this task and show me how the PDA for it looks like?

• The stack is the invisible call-stack when programming top-down recursive-descent parsers. – D. Ben Knoble Jan 29 at 23:25
• How can you do it without a stack? Consider the case where the body of a while statement includes another while statement. – rici Jan 30 at 1:38

What you write is a snippet out of a recursive descent parser, one way of writing a program that parses a context free language. It is modelled on a PDA, specifically a LL(1) one. The stack is implicit in the recursive calls your parser does. Recursive descent is popular as it easy to write by hand (some tricks are needed to handle ambiguous constructs, like nested if ... then ... else and expressions, which naturally are represented by left-recursive grammars, but they are well-known) and requires no theory. More powerful parsing methods (like LALR or canonical LR) are too complex to do by hand for realistic grammars (in LL(1)/recursive descent, you can work one production at a time, other methods require considering a much larger part of the grammar). If you look at a typical (LA)LR parser generator's output (ask e.g. for --report=all for bison or -rfor byacc to get a text description, or -g for any of them to get a graphical depiction of the PDA).