使用自底向上解析为给定输入生成的输出

Question

我试着解决了这个问题，答案是选项c。但很少有教科书给出的答案是选项 b。我很困惑什么是正确答案？请帮帮我!

Answer 1

GAAAAT为正确答案；它是由解析器产生的输出，它遵循翻译规则中的动作顺序（其中一些出现在 mid-rule）。

Yacc/bison就是这样一个解析器，这使得验证变得非常容易：

%{
#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

如果我们修改语法以将所有操作放在各自规则的末尾，我们将获得答案 (b)。（除了语法，其他都和前面的例子一样，所以我只展示新的翻译规则。）

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

使用自底向上解析为给定输入生成的输出

Output produced for the given input using the bottom up parsing

compiler-construction

parsing

bottom-up