LR1 Parser e Epsilon
-
20-08-2019 - |
Pergunta
Eu estou tentando entender como LR1 Analisadores trabalho, mas eu vim com um problema estranho: E se a gramática contém Epsilons? Por exemplo: se eu tiver a gramática:
S -> A
A -> a A | B
B -> a
É claro como começar:
S -> .A
A -> .a A
A -> .B
... e assim por diante
mas eu não sei como fazê-lo para tal gramática a:
S -> A
A -> a A a | \epsilon
É correto fazer:
S -> .A
A -> .a A a
( A -> .\epsilon )
E, em seguida, fazer este Estado no DFA aceitar?
Qualquer ajuda seria muito apreciada!
Solução
Sim, exatamente (pense na epsilon como espaço vazio, onde não há dois lugares para o ponto nas laterais).
Em um LR (0) autômato, você faria o estado de aceitação e reduzir a A. No entanto, devido à produção A->a A a
, haveria uma mudança / reduzir os conflitos.
Em um LR (1) autômato, você iria determinar se a mudança ou reduzir usando lookahead (a
-> mudança, nada em FOLLOW(A)
-> reduzir a)
Veja o artigo Wikipedia