Бесполезные правила и нетерминалы в грамматике зубров

У меня есть следующий файл Bison, описывающий мою грамматику языка сценариев:

%error-verbose
%{
#include "node.h"NBlock *programBlock;

#define YYDEBUG 1

extern int yylex();
void yyerror(const char *) { printf("Error: %s\n", s); }
%}

%union {
Node *node;
NBlock *block;
NBody *body;
NHeader *header;
NExpression *expression;
NStatement *statement;
NIdentifier *identifier;
NVariableDeclaration *variableDeclaration;
NDoWhileStatement *doWhileStatement;
NWhileStatement *whileStatement;
NIfStatement *ifStatement;
NForStatement *forStatement;
std::vector<NVariableDeclaration*> *variableDeclarations;
std::vector<NExpression*> *expressions;
std::vector<NStatement*> *statements;
std:string *string;
int token;
}%token <string> TIDENTIFIER TINTEGER TDOUBLE
%token <token> TCEQ TCNE TCLT TCLE TCGT TCGE TEQUAL
%token <token> TLPAREN TRPAREN TLBRACE TRBRACE TCOMMA TDOT
%token <token> TPLUS TMINUS TMUL TDIV TDO TDOUBLE_TYPE TINT_TYPE
%token <token> TELSE TFOR TIF TSEMICOLON TTHEN TWHILE

%type <expression> expression term factor
%type <block> program body header tail statements
%type <statement> statement forStatement ifStatement doWhileStatement whileStatement variableDeclaration
%type <token> comparison
%type <string> identifier_type%left TPLUS TMINUS
%left TMUL TDIV

%start program

%%

program:                TLBRACE body TRBRACE { printf("Reduce body to program\n"); }
;

body:                   header TLBRACE block TRBRACE tail { printf("Reduce header block tail to body\n"); }
;

header:                 TLBRACE variableDeclarations TRBRACE { printf("Reduce variableDeclarations to header\n"); }
| TLBRACE TRBRACE { printf("Reduce empty to header\n"); }
;

variableDeclarations:   variableDeclaration TSEMICOLON { printf("Reduce variable declaration to header\n"); }
| variableDeclarations variableDeclaration TSEMICOLON { printf("Reduce variable declaration list to header\n"); }
;

tail:                   TLBRACE statements TRBRACE { printf("reduce statement list to tail\n"); }
| TLBRACE TRBRACE { printf("Reduce empty to tal\n"); }
;

statements:             statement TSEMICOLON { printf("Reduce statement to statement list\n"); }
| statements statement TSEMICOLON { printf("Reduce statement list to statement list\n"); }
;

statement:              ifStatement { printf("Reduce if to statement\n"); };
| forStatement { printf("Reduce for to statement\n"); };
| doWhileStatement { printf("Reduce doWhile to statement\n"); };
| whileStatement { printf("reduce while to statement\n"); }
| expression { printf("Reduce expression to statement\n"); };
;

forStatement:           TFOR TLPAREN expression TSEMICOLON expression TSEMICOLON expression TRPAREN block { printf("Reduce for to for statement\n"); }
;ifStatement:            TIF expression TTHEN block { printf("Reduce if to if statement\n"); }
| TIF expression block TELSE block { printf("Reduce ifelse to if statement\n"); }
;

doWhileStatement:       TDO block TWHILE expression { printf("reduce dowhile to while statement\n"); }
;

whileStatement:         TWHILE block expression { printf("Reduce while to while statement\n"); }
;

block:                  TLBRACE statements TRBRACE { printf("Reduce statement list to block\n"); }
| TLBRACE TRBRACE { printf("Reduce empty to block\n"); }
;

variableDeclaration:    identifier_type TIDENTIFIER { printf("reduce uninitialized identifier to variable declaration\n"); }
| identifier_type TIDENTIFIER TEQUAL expression { printf("Reduce initialized identifier to variable declaration\n"); }
;

identifier_type:        TINT_TYPE { printf("Reduce int to identifier type\n"); }
| TDOUBLE_TYPE { printf("Reduce double to identifier type\n"); }
| { printf("Reduce empty to identifier type\n"); }
;expression:             TIDENTIFIER TEQUAL expression { printf("Reduce assignment to expression\n"); }
| TIDENTIFIER { printf("reduce identifier to expression\n"); }
| expression comparison expression { printf("Reduce comparison to expression\n"); }
| TLPAREN expression TRPAREN { printf("Reduce nested expression to expression\n"); }
| expression TPLUS term { printf("Reduce addition to expression\n"); }
| expression  TMINUS term { printf("Reduce subtraction to expression\n"); }
| term { printf("Reduce term to expresson\n"); }
| factor { printf("Reduce factor to expression\n"); }
;

term:                   term TMUL factor { printf("Reduce multiplication to term\n"); }
| term TDIV factor { printf("Reduce division to term\n"); }
;

factor:                 TIDENTIFIER { printf("Reduce identifier to factor\n"); }
| TINTEGER { printf("Reduce integer to numeric\n"); }
| TDOUBLE { printf("Reduce double to numeric\n"); }
;

comparison:             TCEQ { printf("Reduce eq to comparison\n"); }
| TCNE { printf("Reduce ne to comparison\n"); }
| TCLT { printf("Reduce lt to comparison\n"); }
| TCLE { printf("Reduce le to comparison\n"); }
| TCGT { printf("reduce gt to comparison\n"); }
| TCGE { printf("Reduce ge to comparison\n"); }
| TPLUS { printf("Reduce plus to comparison\n"); }
| TMINUS { printf("Reduce minus to comparison\n"); }
| TMUL { printf("Reduce mul to comparison\n"); }
| TDIV { printf("Reduce div to comparison\n"); }
;

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

Выполнение команды:

bison -d -o parser.cpp parser.y

Я получаю следующие ошибки:

$ bison -d -o parser.cpp parser.y
parser.y: attention: 1 nonterminal useless in grammar
parser.y: attention: 5 rules useless in grammar
parser.y:52.31-34: attention: nonterminal useless in grammar: term
parser.y:135.51-118: attention: rule useless in grammar: expression: expression TPLUS term
parser.y:136.51-123: attention: rule useless in grammar: expression: expression TMINUS term
parser.y:137.51-96: attention: rule useless in grammar: expression: term
parser.y:141.41-103: attention: rule useless in grammar: term: term TMUL factor
parser.y:142.51-107: attention: rule useless in grammar: term: term TDIV factor
parser.y: conflicts: 20 shift/reduce, 14 reduce/reduce
parser.y:145.41-96: attention: rule useless in parser due to conflicts: factor: TIDENTIFIER

1

Решение

Я думаю, что конфликт в том, что парсер не будет знать, какое правило выбрать, когда он найдет ТИДЕНТИФИКАТОР. Причина в том, что

TIDENTIFIER может быть уменьшен до expression
factor может быть уменьшен до expression
TIDENTIFIER может быть уменьшен до factor

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

TIDENTIFIER -> expression
TIDENTIFIER -> factor -> expression

Я тонкий в вашем случае вы можете безопасно удалить TIDENTIFIER от фактора с factor сводится к ТОЛЬКО expression тем не мение.

Однако более правильный способ (по крайней мере, для большинства распространенных языков) может быть, чтобы сохранить TIDENTIFIER в factor и обрабатывать остальное в statement, Например TIDENTIFIER ASSIGN expression может быть действительным statement,

Кстати ваш statement включает в себя expression, Что, вероятно, не то, что вы хотели. statement всегда должен отличаться от expression (в конце концов, поэтому вам нужно два правила).

Я думаю, что вы должны проверить такие случаи. Если у вас есть правило, использующее только другое правило (без каких-либо других токенов или других правил), то это, вероятно, неправильно. Неправильно в том смысле, что это не то, что вы намеревались.

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]