Output produced for the given input using the bottom up parsing

Question

I tried solving this question and the answer comes out to be option c. But in few textbooks answer given is option b. I am confused what would be the correct answer? Plz help me out!

Answer 1

GAAAAT is the correct answer; it is the output produced by a parser which honours the order of the actions in the translation rules (some of which occur in mid-rule).

Yacc/bison is one such parser, which makes it very easy to verify:

%{
#include <ctype.h>
#include <stdio.h>
void yyerror(const char* msg) {
  fprintf(stderr, "%s\n", msg);
}
int yylex(void) {
  int ch;
  while ((ch = getchar()) != EOF) {
    if (isalnum(ch)) return ch;
  }
  return 0;
}
%}
%%
S: 'p'    { putchar('G'); } P 
P: 'q'    { putchar('A'); } Q
P: 'r'    { putchar('T'); } 
P: %empty { putchar('E'); } 
Q: 's'    { putchar('A'); } P
Q: %empty { putchar('O'); }
%%
int main(void) {
  yyparse();
  putchar('\n');
}

$ bison -o gate.c gate.y
$ gcc -std=c99 -Wall -o gate gate.c
$ ./gate<<<pqsqsr
GAAAAT

If we modify the grammar to put all of the actions at the end of their respective rule, we obtain answer (b). (Other than the grammar, everything is the same as the previous example, so I'm only showing the new translation rules.)

S: 'p'    P { putchar('G'); } 
P: 'q'    Q { putchar('A'); }
P: 'r'    { putchar('T'); } 
P: %empty { putchar('E'); } 
Q: 's'    P { putchar('A'); } 
Q: %empty { putchar('O'); }

$ bison -o gate_no_mra.c gate_no_mra.y
$ gcc -std=c99 -Wall -o gate_no_mra gate_no_mra.c
$ ./gate_no_mra<<<pqsqsr
TAAAAG