Conflitos de Shift/Reduce

O material a seguir é uma tradução da documentação do Bison 2.3.
Desta vez, vamos começar com uma parte do glossário, necessário para entender o resto do texto, eu acho. :D

- Token
Uma básica, gramaticalmente indivisível unidade de uma linguagem. O símbolo que descreve um token na gramática é um símbolo terminal.
A entrada do parser Bison é um stream de tokens que vem de um analisador léxico.

- Terminal symbol
Um símbolo da gramática que não tem regras na gramática e portando é gramaticalmente indivisível. O pedaço de texto que ele representa é um token.

- Reduction
Substituição de uma string de não-terminais e/ou terminais com um único não-terminal, de acordo com a regra da gramática.

- Shift
Um parser diz para deslocar quando ele faz a escolha de analisar mais entradas do stream ao invés de reduzir imediatamente alguma regra já reconhecida.

- Look-ahead token
Um token já lido mas ainda não transferido.

Só para constar, no texto eu traduzi 'reduction' para 'redução'. O resto parece mais adequado usar em inglês, confira abaixo o conteúdo do tópico 5.2 da documentação:

Suponhemos que nós estamos criando um parser para uma linguagem, na qual tem comandos if-then e if-then-else, com um par de regras como estas:

     if_stmt:
               IF expr THEN stmt
             | IF expr THEN stmt ELSE stmt
             ;

Aqui nós assumimos que IF, THEN e ELSE são símbolos terminais para específicos tokens.

Quando o token ELSE é lido e torna-se o token de look-ahead, o conteúdo da stack (considerando que o input é válido) é somente certo para redução pela primeira regra. Mas ele é também legítimo para shift o ELSE, porque isto levaria para uma eventual redução pela segunda regra.

Esta situação, onde um shift ou uma redução seriam válidos, é chamado de um conflito de shift/reduce. Bison é projetado para resolver estes
conflitos por escolhendo shift, ou por outro lado, por direta declaração de precedência de operador. Para ver a razão disso, vamos verificar outras alternativas.

Desde que o parser prefere shift no ELSE, o resultado é adicionar a cláusula ELSE para o comando IF mais interno, fazendo estes dois inputs equivalentes:

     if x then if y then win (); else lose;
 
     if x then do; if y then win (); else lose; end;

Mas se o parser escolhe por reduce quando possível ao invés de shift, o resultado seria adicionar a cláusula ELSE para o comando if mais externo, fazendo estes dois inputs equivalentes:

     if x then if y then win (); else lose;
 
     if x then do; if y then win (); end; else lose;

O conflito existe porque a gramática como foi escrita é ambigua: também analisando de um simples comando if aninhado é legitimo.
A convensão estabeleceu que estas ambiguidades são resolvidas por adicionando a cláusula ELSE Para o mais interno comando IF; isto é o quê o Bison realiza por escolhendo shift ao invés de reduce. (Seria idealmente mais claro escrever uma gramática não ambigua, mas
isto é muito difícil para fazer neste caso.) Esta ambiguidade em particular foi primeiro encontrada na especificação do Algol 60 e é chamado de "dangling else" ambiguity.

Para evitar warnings do Bison sobre predicados, legítmos conflitos de shift/reduce, use a declaração %expect n. Não haverá warning
desde que o número de conflitos shift/reduce é exatamente n. Veja Suppressing Conflict Warnings.

A definição do if_stmt acima é apenas para causar o conflito, mas o conflito não aparece sem regras adicionais. Aqui está um arquivo de entrada completo para o Bison que realmente manifesta o conflito:

     %token IF THEN ELSE variable
     %%
     stmt:     expr
             | if_stmt
             ;
 
     if_stmt:
               IF expr THEN stmt
             | IF expr THEN stmt ELSE stmt
             ;
 
     expr:     variable
             ;

Fonte: http://www.gnu.org/software/bison/manual/html_mono/bison.html

Pretendo continuar postando sobre o assunto, vamos que vamos!

Post new comment

The content of this field is kept private and will not be shown publicly.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.

More information about formatting options