Mudar reduzir os conflitos
https://stackoverflow.com/questions/196179
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu estou tendo um problema em entender a mudança / reduzir confict para uma gramática que eu sei que não tem nenhuma ambiguidade. O caso é um dos tipos mais se, mas não é o problema 'pendurado else' desde que eu tenho cláusulas END obrigatórias que delimitam os blocos de código.
Aqui está a gramática para GPPG (É um Bison como compilador compilador ... e isso não era um eco):
%output=program.cs
%start program
%token FOR
%token END
%token THINGS
%token WHILE
%token SET
%token IF
%token ELSEIF
%token ELSE
%%
program : statements
;
statements : /*empty */
| statements stmt
;
stmt : flow
| THINGS
;
flow : '#' IF '(' ')' statements else
;
else : '#' END
| '#' ELSE statements '#' END
| elseifs
;
elseifs : elseifs '#' ELSEIF statements else
| '#' ELSEIF statements else
;
Aqui está a saída de conflitos:
// Parser Conflict Information for grammar file "program.y"
Shift/Reduce conflict on symbol "'#'", parser will shift
Reduce 10: else -> elseifs
Shift "'#'": State-22 -> State-23
Items for From-state State 22
10 else: elseifs .
-lookahead: '#', THINGS, EOF
11 elseifs: elseifs . '#' ELSEIF statements else
Items for Next-state State 23
11 elseifs: elseifs '#' . ELSEIF statements else
// End conflict information for parser
Já trocou tudo espalhados, e eu sei como resolvê-lo, mas que a solução consiste em dar-se a recursão à esquerda na 'elseif' para uma recursão direita.
Ive sido através de toda a documentação scarse eu encontrei na internet sobre este assunto (eu postar alguns links no final) e ainda não encontrou uma solução elegante. Eu sei sobre ANTLR e eu não querer considerá-lo agora. Por favor, limite a sua solução para analisadores Yacc / Bison.
Eu apreciaria soluções elegantes, eu consegui fazê-lo por eleminating os / * vazios * / regras e duplicação tudo o que precisava de uma lista vazia, mas na gramática maior Im trabalhando nisso apenas acaba como 'síndrome da gramática sparghetti'.
Aqui estão alguns links:
http://nitsan.org/~maratb/cs164/bison.html
http://compilers.iecc.com/comparch/article/98- 01-079
Solução
Sua regra ELSEIF revista não tem marcadores para uma condição -. Deve nominalmente têm '(' e ')' adicionado
Mais a sério, agora você tem uma regra para
elsebody : else
| elseifs else
;
e
elseifs : /* Nothing */
| elseifs ...something...
;
Não é necessária a 'nada'; é implicitamente cuidado de pelo 'elsebody' sem o 'elseifs'.
eu estaria muito inclinado a regras usam 'opt_elseifs', 'opt_else' e 'end':
flow : '#' IF '(' ')' statements opt_elseifs opt_else end
;
opt_elseifs : /* Nothing */
| opt_elseifs '#' ELSIF '(' ')' statements
;
opt_else : /* Nothing */
| '#' ELSE statements
;
end : '#' END
;
Eu não tenho executar este através de um gerador de analisador, mas eu acho isso relativamente fácil de entender.
Outras dicas
Eu acho que o problema é na cláusula elseifs.
elseifs : elseifs '#' ELSEIF statements else
| '#' ELSEIF statements else
;
Eu acho que a primeira versão não é necessária, uma vez que a cláusula else remete para elseifs de qualquer maneira:
else : '#' END
| '#' ELSE statements '#' END
| elseifs
;
O que acontece se você mudar elseifs:?
elseifs : '#' ELSEIF statements else
;
A resposta de Jonathan acima parece que ele iria ser o melhor, mas desde que não o seu trabalho para você eu tenho algumas sugestões que você pode tentar que vai ajudá-lo na depuração de erros.
Em primeiro lugar você já pensou em fazer o hash / símbolo sustenido uma parte dos próprios (ou seja #END, #IF, etc) fichas? Assim que eles se retirado pela lexer, o que significa que não tem que ser incluída no analisador.
Em segundo lugar peço-lhe para reescrever as regras sem duplicar quaisquer fluxos de token. (Parte da Do not Repeat Yourself princípio.) Portanto, a regra " '#' ELSEIF else" só deve existir em um lugar em que arquivos (não dois como você tem acima).
Por último, sugiro que você olhar para precedência e associatividade dos if / elseif / fichas ELSE. Eu sei que você deve ser capaz de escrever um analisador que não requer isso, mas pode ser a coisa que você precisa neste caso.
Eu ainda estou mudando coisa espalhados, ea minha pergunta original tinha alguns erros desde o elseifs seqüência tiveram um else hair no final o que estava errado. Aqui está outra tomada com a pergunta, desta vez eu recebo dois turnos / reduzir conflitos:
flow : '#' IF '(' ')' statements elsebody
;
elsebody : else
| elseifs else
;
else : '#' ELSE statements '#' END
| '#' END
;
elseifs : /* empty */
| elseifs '#' ELSEIF statements
;
Os conflitos agora são:
// Parser Conflict Information for grammar file "program.y"
Shift/Reduce conflict on symbol "'#'", parser will shift
Reduce 12: elseifs -> /* empty */
Shift "'#'": State-10 -> State-13
Items for From-state State 10
7 flow: '#' IF '(' ')' statements . elsebody
4 statements: statements . stmt
Items for Next-state State 13
10 else: '#' . ELSE statements '#' END
11 else: '#' . END
7 flow: '#' . IF '(' ')' statements elsebody
Shift/Reduce conflict on symbol "'#'", parser will shift
Reduce 13: elseifs -> elseifs, '#', ELSEIF, statements
Shift "'#'": State-24 -> State-6
Items for From-state State 24
13 elseifs: elseifs '#' ELSEIF statements .
-lookahead: '#'
4 statements: statements . stmt
Items for Next-state State 6
7 flow: '#' . IF '(' ')' statements elsebody
// End conflict information for parser
regras vazias apenas agravar a GPPG i tenho medo. Mas eles parecem tão natural para usar Eu continuo tentando-los.
Eu já sei resolve recursão direito o problema como 1800 INFORMATION disse. Mas eu estou procurando uma solução com recursão esquerda na elseifs cláusula .
elsebody : elseifs else
| elseifs
;
elseifs : /* empty */
| elseifs '#' ELSEIF statements
;
else : '#' ELSE statements '#' END
;
Eu acho que isso deve deixado recurse e sempre terminar.
OK - aqui é uma gramática (não o mínimo) para se blocos. Cavei-lo para fora de algum código que eu (chamado ad hoc, com base em hoc de Kernighan & Plauger "The UNIX Programação Ambiente"). Esta gramática esboço compila com Yacc, sem conflitos.
%token NUMBER IF ELSE
%token ELIF END
%token THEN
%start program
%%
program
: stmtlist
;
stmtlist
: /* Nothing */
| stmtlist stmt
;
stmt
: ifstmt
;
ifstmt
: ifcond endif
| ifcond else begin
| ifcond eliflist begin
;
ifcond
: ifstart cond then stmtlist
;
ifstart
: IF
;
cond
: '(' expr ')'
;
then
: /* Nothing */
| THEN
;
endif
: END IF begin
;
else
: ELSE stmtlist END IF
;
eliflist
: elifblock
| elifcond eliflist begin /* RIGHT RECURSION */
;
elifblock
: elifcond else begin
| elifcond endif
;
elifcond
: elif cond then stmtlist end
;
elif
: ELIF
;
begin
: /* Nothing */
;
end
: /* Nothing */
;
expr
: NUMBER
;
%%
Eu usei 'número' como o elemento fictício, em vez das coisas, e eu usei ELIF vez de ELSEIF. Ele inclui um ENTÃO, mas isso é opcional. O 'começar' e operações de 'fim' foram usadas para agarrar o contador de programa no programa gerado - e, portanto, deve ser removível desta sem afetar it
.Houve uma razão que eu pensei que eu precisava usar recursão direita em vez da recursão esquerda normal - mas eu acho que foi a ver com a estratégia de geração de código que eu estava usando, em vez de qualquer outra coisa. O ponto de interrogação no comentário no original; Lembro-me de não ser feliz com ele. O programa como um todo funciona - é um projeto que tem sido em segundo plano durante a última década ou assim (hmmm ... Eu fiz algum trabalho no final de 2004 e início de 2005 e, antes disso, era 1992 e 1993).
Eu não passei o tempo de trabalho por que isso compila livre de conflitos e que eu descrito anteriormente não. Espero que ajude.
