Pushdown automaton from given code for parsing a while statement

Question

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?

Answer 1

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

Tl;dr: Undestanding PDAs and their relation to the grammar is
useful, but not essential to use the technology.