0
$\begingroup$

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?

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

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.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.