Turmas - 2º Semestre de 2025(Enade, 2017) Em um compilador, um analisador sintático descendente preditivo pode ser implementado com o auxílio de uma tabela construída a partir de uma gramática livre de contexto. Essa tabela, chamada tabela LL(k), indica a regra de produção a ser aplicada olhando-se o k-ésimo próximo símbolo lido, chamado lookahead(k). Por motivo de eficiência, normalmente busca-se utilizar k = 1. Considere a gramática livre de contexto G = ({X, Y, Z}, {a, b, c, d, e}, P, X), em que P é composto pelas seguintes regras de produção:
P = {X → aZbXY | c
Y → dX | ε
Z → e}Considere, ainda, a seguinte tabela LL(1), construída a partir da gramática G, sendo $ o símbolo que representa o fim da cadeia. Essa tabela possui duas produções distintas na célula (Y, d), gerando, no analisador sintático, uma dúvida na escolha da regra de produção aplicada em determinados momentos da análise.
| a | b | c | d | e | $ | |
|---|---|---|---|---|---|---|
| X | X → aZbXY | X → c | ||||
| Y | Y → dX Y → ε | Y → ε | ||||
| Z | Z → e |
Considerando que o processo de construção dessa tabela LL(1), a partir da gramática G, foi seguido corretamente, a existência de duas regras de produção distintas na célula (Y, d), neste caso específico, resulta:
a. da ausência do símbolo de fim da cadeia ($) nas regras de produção.
b. de um não-determinismo causado por uma ambiguidade na gramática.
c. do uso incorreto do símbolo de cadeia vazia (ε) nas regras de produção.
d. da presença de duas regras de produção com um único terminal no corpo.
e. da presença de duas regras de produção com o mesmo não terminal na cabeça.
A questão envolve a análise de uma tabela LL(1) para a gramática fornecida e, especificamente, o fato de haver duas produções distintas na célula (Y, d), o que gera uma ambiguidade no analisador sintático.
A tabela LL(1) é usada para decidir qual produção aplicar, dado o símbolo atual de entrada e o próximo símbolo a ser lido, chamado de lookahead.
A célula (Y, d) é problemática, pois ela contém duas produções para o símbolo Y quando o próximo símbolo da entrada é d. As duas produções para Y são dX ou ε.
Essas duas produções geram uma dúvida para o analisador, já que ele não pode decidir qual das produções deve aplicar com base apenas no símbolo de lookahead(d).
Diante do exposto, vamos analisar cada uma das afirmações a seguir.
a. da ausência do símbolo de fim da cadeia ($) nas regras de produção.
O símbolo de fim de cadeia ($) não é o problema aqui, pois a ambiguidade ocorre com o símbolo d, não com o fim de cadeia. Ademais, o símbolo $ não pode pertencer ao conjunto de terminais da gramática, pois conforme apresentado no próprio enunciado da questão, $ é o símbolo que representa o fim da cadeia.
b. de um não-determinismo causado por uma ambiguidade na gramática.
A ambiguidade na gramática é de fato a causa da dúvida, já que existem duas produções possíveis para Y no mesmo lookahead(Y, d). Isso é um exemplo de não-determinismo na tabela LL(1), que resulta da ambiguidade na gramática.
c. do uso incorreto do símbolo de cadeia vazia (ε) nas regras de produção.
O uso de ε não está incorreto, mas sua presença na produção Y → ε pode gerar a ambiguidade, pois o analisador pode escolher entre consumir d e aplicar Y → dX ou decidir que Y pode ser ε, ou seja, não consumir nada.
d. da presença de duas regras de produção com um único terminal no corpo.
As produções X → c e Z → e estão corretas, com lookahead(X, c) e lookahead(Z, e) conduzindo a exatamente uma possibilidade na tabela de análise, ou seja, não é o que causa a ambiguidade.
e. da presença de duas regras de produção com o mesmo não terminal na cabeça.
Isso não é o que causa a ambiguidade. Embora Y apareça em ambas as produções, o problema é que o mesmo lookahead(d) leva a duas opções válidas de produção. O mesmo não ocorre com X, que também possui duas produções (aZbXY ou c), mas com cada produção ocupando uma célula individual na tabela de análise.
Ybadoo - Soluções em Software Livre • Copyright 2009/2026 • 