Непреднамеренная конкатенация в грамматике Bison / Yacc - PullRequest
Новая
       43

Непреднамеренная конкатенация в грамматике Bison / Yacc

3 голосов
/ 23 апреля 2010

Я экспериментирую с lex и yacc и столкнулся со странной проблемой, но я думаю, что было бы лучше показать вам мой код, прежде чем подробно описать проблему. Это мой лексер: 

%{
#include <stdlib.h>
#include <string.h>
#include "y.tab.h"
void yyerror(char *);
%}

%%

[a-zA-Z]+ {
  yylval.strV = yytext;
  return ID;
}

[0-9]+      {
  yylval.intV = atoi(yytext);
  return INTEGER;
}

[\n] { return *yytext; }

[ \t]        ;

. yyerror("invalid character");

%%

int yywrap(void) {
  return 1;
}

Это мой парсер: 

%{
#include <stdio.h>

int yydebug=1;
void prompt();
void yyerror(char *);
int yylex(void);
%}

%union {
  int intV;
  char *strV;
}

%token INTEGER ID

%%

program: program statement EOF { prompt(); }
       | program EOF { prompt(); }
       | { prompt(); }
       ;

args: /* empty */
    | args ID { printf(":%s ", $<strV>2); }
    ;

statement: ID args { printf("%s", $<strV>1); }
         | INTEGER { printf("%d", $<intV>1); }
;

EOF: '\n'

%%

void yyerror(char *s) {
  fprintf(stderr, "%s\n", s);
}

void prompt() {
  printf("> ");
}

int main(void) {
  yyparse();
  return 0;
}

Очень простой язык, состоящий не более чем из строк и целых чисел и базового REPL. Теперь вы заметите в синтаксическом анализаторе, что args выводятся с начальным двоеточием, при этом предполагается, что в сочетании с первым шаблоном правила оператора взаимодействие с REPL будет выглядеть примерно так: 

> aaa aa a
:aa :a aaa>

Однако взаимодействие таково: 

> aaa aa a
:aa :a aaa aa aa
>

Почему идентификатор токена в следующем правиле 

statement: ID args { printf("%s", $<strV>1); }
         | INTEGER { printf("%d", $<intV>1); }
;

есть семантическое значение всей входной строки, включая перевод строки? Как переработать мою грамматику так, чтобы взаимодействие, которое я задумал?

Ответы [ 2 ]

2 голосов
/ 26 апреля 2010

Вы должны сохранять строки токенов во время их чтения, если хотите, чтобы они оставались действительными. Я изменил правило statement следующим образом: 

statement: ID { printf("<%s> ", $<strV>1); } args { printf("%s", $<strV>1); }
         | INTEGER { printf("%d", $<intV>1); }
;

Затем, с вашим вводом, я получаю вывод: 

> aaa aa a
<aaa> :aa :a aaa aa a
>

Обратите внимание, что во время считывания начального идентификатора токен точно соответствует ожидаемому. Но поскольку вы не сохранили токен, строка была изменена к тому времени, когда вы вернетесь к ее печати после анализа args.

0 голосов
/ 23 апреля 2010

Я думаю, что существует конфликт ассоциативности между аргументами и производством операторов. Это подтверждается (частичным) выводом из файла bison -v parser.output: 

Nonterminals, with rules where they appear

$accept (6)
    on left: 0
program (7)
    on left: 1 2 3, on right: 0 1 2
statement (8)
    on left: 4 5, on right: 1
args (9)
    on left: 6 7, on right: 4 7
EOF (10)
    on left: 8, on right: 1 2

Действительно, мне трудно понять, что пытается принять ваша грамматика. Как примечание, я, вероятно, перенесу вашу продукцию EOF в лексер как токен EOL; это упростит повторную синхронизацию при разборе ошибок.

Было бы полезно лучше объяснить ваши намерения.

...