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):
- Postfix
^
. - Prefixo
^
. [ ]
, e.
, (mesma prioridade e associativo à esquerda).- O único terminal
id
é qualquer letra minúscula.
Agora vamos dizer que uma expressão é:
- Qualquer id.
- Qualquer expressão com o operador Postfix
^
. - Qualquer expressão com o operador Prefixo
^
. - Qualquer expressão com
.
seguida porid
. - 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.
programming-languages
parsers
formal-grammars
zidarsk8
fonte
fonte
Respostas:
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 id
com um pendente^
, você não sabe se o seu últimoid
e 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:
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 come
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 :-))
fonte
a.b^.c
. Eu apenas o adicionei para mostrar de onde eu comecei.a.b^.c
a 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?