-
Em uma gramática de livre contexto, uma árvore de derivação é uma árvore composta e os nós interiores da árvore são sempre rotulados por nós não terminais.
Forma árvores derivada onde:
- A raiz tem como rótulo o símbolo inicial
- A cada nó rotulado por um não terminal da forma da gramática corresponde uma regra de gramática.
- Um nó rotulado por um terminal é sempre uma folha da árvore, e não tem filhos.
Serão criadas duas árvores distintas seguindo as regras da gramatica e a sequência descrita acima. Gabarito Certo.
-
Eu só não consegui entender como essa gramática consegue gerar o número 10. Sendo que nos terminais temos apenas números de 1 dígito e não tem nenhuma regra geradora que permita a repetição de dígitos.
-
Concordo com o Ewerton, na prática essa gramática não é capaz de gerar o número 10.
As duas árvores de derivação possíveis ficariam assim:
i) -
10 +
4 3
ii) +
- 3
10 4
-
Prezados,
Nesse caso as 2 árvores de derivação distintas seriam (10 - 4) +3 e 10 - ( 4+3 ).
O cespe se pronunciou sobre os recursos interpostos nessa questão com a seguinte justificativa para manter o gabarito :
Argumentação: Uma gramática pode ter mais de uma árvore de uma árvore de derivação gerando determinada cadeia de terminais. Quando uma
gramática permite esta característica ela é dita ambígua. A gramática apresentada neste item é ambígua porque permite gerar duas árvores de derivação
distintas. Mais informações podem ser obtidas em Alfred V. Aho. Compiladores: princípios, técnicas e ferramentas. São Paulo. Pearson Addilson-Wesley,
2008. Pág 30. Uma árvore: (10 -4 ) + 3 e a outra: 10 - (4 + 3)
Portanto a questão está correta.
-
Questão retirada diretamente do livro "Compiladores: Princípios, Técnicas e Ferraments" Alfred V. Aho
-
Explicação da CESPE:
"Uma gramática pode ter mais de uma árvore de uma árvore de derivação gerando determinada cadeia de terminais. Quando uma gramática permite esta característica ela é dita ambígua. A gramática apresentada neste item é ambígua porque permite gerar duas árvores de derivação distintas. Mais informações podem ser obtidas em Alfred V. Aho. Compiladores: princípios, técnicas e ferramentas. São Paulo. Pearson Addilson-Wesley, 2008. Pág 30. Uma árvore: (10 -4 ) + 3 e a outra: 10 - (4 + 3)"
-
Acho que o 10 é permitido porque a questão fala que a string pode ser um digito ou uma sentença, no caso, relacionda ao alfabeto numerico apresentado.