reduzir reduzir e mudar reduzir erro na gramática LALR

7

Eu tenho que escrever uma gramática para Pascal, e há apenas uma coisa que está causando problemas.

Digamos que temos operadores (classificados por prioridade de baixa a alta):

  1. Postfix^ .
  2. Prefixo^ .
  3. [ ], e ., (mesma prioridade e associativo à esquerda).
  4. O único terminal idé qualquer letra minúscula.

Agora vamos dizer que uma expressão é:

  1. Qualquer id.
  2. Qualquer expressão com o operador Postfix^ .
  3. Qualquer expressão com o operador Prefixo^ .
  4. Qualquer expressão com .seguida por id.
  5. Qualquer expressão com [e outra expressão e ].

Agora, gostaria de saber como fazer uma gramática LALR sem conflitos de turno-redução e redução-redução, OU, se isso não puder ser feito, como posso provar que isso não pode ser feito?

Alguns exemplos:

good:
a.b.c.d               
a.b^.c
^a.b^
a.b^^[c]^^.d.e        
^^a.b^.d.e^[]

bad:
a.^b.c

Sem o prefixo ^, esse problema é fácil de resolver, mas o sinal do prefixo continua me pegando. Alguém pode ajudar? Minhas soluções até agora:

// this works without the prefix but it does not produce a.b^.c which is wrong.
A ::= B | A ^ ;
B ::= C | ^ B ;
C ::= id | C [ A ] | C . id;

Por isso, pensei que o prefixo só pode ocorrer antes do primeiro ponto e, entre os pontos, só pode haver um postfix ^e colchetes. Então, eu vim com isso:

A ::= B | A ^ ;
B ::= C | ^ B ;
C ::= id | C [ A ] |id D;
D ::= id E;
F ::= E | F ^;
E ::= id | F . id;

Mas isso causa 3 conflitos.

zidarsk8
fonte
Não me lembro do prefixo dos meus dias de Pascal. E construções com ^^ definitivamente não. Pascal foi cuidadosamente projetado para ser analisável por descida recursiva, e LL (1) é um subconjunto estrito de LR (0).
vonbrand 27/02

Respostas:

4

Não vejo nenhum problema com sua primeira gramática e o bisonte não se queixa com a tradução que fiz dela.

Eu (e o bisonte) vejo um conflito em sua segunda gramática (que não descreve o mesmo idioma da primeira BTW). Depois de ter visto id id idcom um pendente ^, você não sabe se o seu último ide o ^deve ser um F, ou se você deve manter juntos os três id formando um A que será reunido com o '^'.


Edite após o seu comentário:

Uma renderização direta de suas regras:

EXP ::= id | EXP ^ | ^ EXP | EXP . id | EXP [ EXP ]

será ambíguo - e, portanto, terá conflito (s) - porque você não indica se a versão do prefixo ^tem prioridade sobre os outros operadores (postfix). Não me lembro como foi em Pascal, mas você pode obter os dois efeitos com

EXP ::= POST | ^ EXP
POST ::= id | POST ^ | POST . id | POST [ EXP ]

e

EXP ::= PRE | EXP ^ | EXP . id | EXP [ EXP ]
PRE ::= id | ^ PRE

Edite novamente: uma versão mista que corresponde ao meu entendimento do que você pergunta no comentário (continuo achando isso confuso e considero a complexidade da gramática - com operadores de postagem fornecidos duas vezes - como sugestão :-))

EXP ::= PRE | POST2
POST2 ::= PRE '^' | POST2 '^' | POST2 '.' id | POST2 '[' EXP ']'
PRE ::= POST | '^' PRE
POST ::= id | POST '.' id | POST '[' EXP ']'
AProgrammer
fonte
A primeira gramática não possui conflitos, mas está errada, pois não produz a.b^.c. Eu apenas o adicionei para mostrar de onde eu comecei.
Zidarsk8
Há duas coisas erradas na sua solução. O primeiro é que ele não produz todos os bons exemplos que listei na minha pergunta, como ab ^ .c segundo acho que ele não leva em consideração as prioridades e, portanto, criaria uma árvore de expressão errada.
zidarsk8
@ zidarsk8, derivação a.b^.ca partir da primeira gramática: EXP -> POST -> POST . id -> POST ^ . id -> POST . id ^ . id -> id . id ^ . id. Você poderia dar um exemplo de expressão problemática mostrando o problema prioritário?
APROGRAMMER #
Sua primeira versão: postfix ^ tem prioridade mais alta que o operador prefix ^ (isso não é bom). segunda versão: prefixo ^ tem prioridade mais alta que o operador de ponto (também não é bom). as versões combinadas são as que não podem produzir ab ^ .c. O problema com a prioridade é, então, como será analisado ab ^ .c deve ser ((ab) ^). C ... e não (a. (B ^)). C ... e ^ b ^ devem ser analisados (^ b) ^. Obrigado por tentar e desculpe, continuo recusando suas soluções, mas elas não funcionam.
precisa saber é o seguinte