Левая ассоциативная грамматика для парсера - PullRequest
Новая
       22

Левая ассоциативная грамматика для парсера

0 голосов
/ 06 ноября 2018

У меня есть вопрос, касающийся моего парсера, который я пишу на C. Предполагается использовать левую рекурсию (дает левую ассоциативность для операторов), а затем вернуть выражение в постфиксной нотации. Специально для моих правил Expr и Term. В настоящее время я сталкиваюсь с проблемой, когда я считаю, что это не происходит. Вот моя грамматика: 

extern int yylex(); /* The next token function. */
extern char *yytext; /* The matched token text. */
extern int yyleng; /* The token text length. */
void yyerror(char *s);
#define YYSTYPE long /* 64 bit so can hold pointer and int */
%}

// These token definitions populate y.tab.h
// Single character tokens are their own token numbers (e.g. scanner returns
// the value ';' for the semicolon token)
%token INT_TOK 1
%token CHR_TOK 2
%token ASSIGN_TOK 3
%token INTLIT_TOK 4
%token IDENT_TOK 5

%%
Prog    : IDENT_TOK '{' StmtSeq '}'    { $$ = (long) strdup(yytext); }  ;
StmtSeq : Stmt ';' StmtSeq                                                        ;
StmtSeq :                                                                         ;

Assign  : LHS ASSIGN_TOK Expr         { printf("%s =\n",(char *)$1); } ;
LHS     : IDENT_TOK                   { $$ = (long) strdup(yytext);  } ;

Stmt    : Decl;
Stmt    : Assign;
Decl    : Type IDLst;
Type    : INT_TOK;
Type    : CHR_TOK;
IDLst   : IDENT_TOK MLst;
MLst    : ',' IDLst;
MLst    : ;
Expr    : Term MExpr;
MExpr   : AddOp Term MExpr            { printf("%s ",(char *)$1); } ;
MExpr   : ;
Term    : Factor MTerm;
MTerm   : MultOp Factor MTerm         { printf("%s ",(char *)$1); } ;
MTerm   : ;
Factor  :  '(' Expr ')';
Factor  :  '-' Factor;
Factor  : INTLIT_TOK                  { printf("%s ",yytext); }
Factor  : IDENT_TOK                   { printf("%s ",yytext); }
AddOp   : '-'                                               { $$ = (long) strdup(yytext); }  ;
AddOp   : '+'                                               { $$ = (long) strdup(yytext); }  ;
MultOp  : '*'                                               { $$ = (long) strdup(yytext); }  ;
MultOp  : '/'                                               { $$ = (long) strdup(yytext); }  ;
%%

Используемый мной тестовый файл: 

test1 {
  int amt, box;
  int x, y, w;
  x := 4 - 2 - 1;             // 4 2 - 1 - x =
  amt := 5 * y - 2;           // 5 y * 2 - amt =
  x := 5 * (y - 2);           // 5 y 2 - * x =
  box := 5 * x / amt + 3 * 4; // 5 x * amt / 3 4 * + box =
  y := z; w:= 1;              // z y =    1 w =
  }

Закомментированные выражения обозначают вывод, который я должен получить. Таким образом, моя грамматика должна вернуться, 

  1. x := 4 - 2 - 1; should produce 4 2 - 1 - x =
  2. amt := 5 * y - 2; should produce 5 y * 2 - amt =
  3. x := 5 * (y - 2); should produce 5 y 2 - * x =
  4.box := 5 * x / amt + 3 * 4; should produce 5 x * amt / 3 4 * + box =
  5. y := z; w:= 1;   should produce z y =    1 w =

Моя грамматика возвращается, 

1. 4 2 1 - - x =
2. I get the correct output
3. I get the correct output
4. I get the correct output
5. 5 x amt / * 3 4 * + box =

Насколько я понимаю, мои операторы не являются ассоциативными. Кто-нибудь знает, почему это будет?

1 Ответ

0 голосов
/ 06 ноября 2018

Лево-рекурсивное производство - это производство, в котором производимый нетерминал является первым (крайним левым) символом с правой стороны. Например, 

MTerm: MTerm MultOp Factor

Право-рекурсивное производство - это то, в котором производимое нетерминала является последним (самым правым) символом с правой стороны. Например, 

MTerm: MultOp Factor MTerm

Ваша грамматика не имеет леворекурсивных правил и многих праворекурсивных правил. Поэтому неудивительно, что он не производит левую ассоциативность.

Грамматика, по-видимому, является результатом попытки удалить левую рекурсию, чтобы создать грамматику LL, хотя вы, похоже, используете yacc / bison, и назначение предполагает, что возможна левая рекурсия, оба из которых предполагают что вам требуется грамматика LR. LR грамматики не требуют ни левого факторинга, ни устранения левой рекурсии.

...