Implementação de analisadores sintáticos - Compiladores - Exercícios

Prévia do material em texto

Implementação de analisadores sintáticos
Exercícios
1. Um analisador sintático cria uma árvore sintática para analisar se determinada
sentença faz sentido em dada gramática ou não. Essa estrutura de dados pode ser
percorrida da raiz para as folhas ou das folhas para a raiz.
Dessa maneira, a forma como esse processo é feito determina se a análise sintática
é descendente ou ascendente. Com relação à análise sintática descendente,
assinale a alternativa correta.
Você acertou!
A. Esta análise é realizada processando a entrada da esquerda para a direita, buscando
os símbolos terminais e os colocando nas posições corretas na árvore sintática antes de
andar para a próxima regra de produção.
Na análise sintática, a sentença com base na fórmula sentencial xAα é descrita por
elementos   de   significado,   denominados tokens,   em   que os   símbolos   terminais
devem sempre  ser   levados  à esquerda  da  produção.   Nessa  fórmula,  A é  um
símbolo   não   terminal,   α   pode   ser   uma   cadeia   de   símbolos   terminais   ou   não
terminais e x é uma cadeia de símbolos terminais e que pode ser nula, ou seja, a
cadeia pode se iniciar com um símbolo não terminal.
Uma   gramática   deve   ser   completamente   descrita   para   ser   funcional.   Caso
contrário, o analisador sintático pode ou não conseguir interpretar uma sentença
devido   à   falta   da   produção   relevante   ou   pode   ser   que   uma   produção   seja
interpretada de forma errada no caso de ambiguidade,  quando é possível  criar
mais de uma árvore sintática para a mesma sentença. Esse tipo de construção
pode gerar erros de precedência de operadores, dependendo de como a árvore
sintática é criada.
Assim, essa análise é realizada processando a entrada da esquerda para a direita,
buscando os símbolos terminais e os colocando nas posições corretas na árvore
sintática antes de andar para a próxima regra de produção.
2. Um dos algoritmos utilizados para a análise sintática de uma expressão é o LL,
que percorre a sentença da esquerda para a direita.
Com relação ao algoritmo LL, assinale a alternativa correta.
Você acertou!
C. É utilizado para a análise sintática e seu nome vem das suas etapas:   inicialmente,
verificando da esquerda para a direita e a derivação mais à esquerda.
Com relação ao algoritmo LL, é possível afirmar que ele é utilizado para a análise
sintática e seu nome vem das suas etapas: inicialmente, verificando da esquerda
para a direita e a derivação mais à esquerda.
O algoritmo LL realiza a análise da gramática elaborando a árvore sintática da
expressão a ser analisada e esse processamento é feito sempre da esquerda para
a direita. Para melhorar o processamento das expressões, alguns cuidados devem
ser adotados, como a fatorização à esquerda para eliminar a ocorrência de uma
sequência de símbolos em duas ou mais regras de produção, e a manipulação das
produções   para  manter   à   esquerda   sempre   um   símbolo   terminal,   eliminando,
assim, a recursão à esquerda. Ainda, deve se garantir que a gramática utilizada
não é ambígua, ou seja, que não é possível criar mais de uma árvore sintática por
sentença. O funcionamento do algoritmo, entretanto, é simples; dado um símbolo
não terminal N qualquer, com o símbolo c inicial, a regra de produção que se deve
escolher é uma regra em que c seja um dos símbolos  iniciais  ou em que é o
símbolo seguinte a uma produção vazia.
3. Uma das estratégias para a construção da árvore sintática de uma sentença é a
análise sintática ascendente.
Como relação a essa técnica, assinale a alternativa correta.
Você acertou!
B. A árvore sintática da sentença é criada a partir das folhas da árvore e chegando na
raiz. Caso seja possível realizar essa operação, a sentença é válida.
Para a criação  da árvore sintática  utilizando os algoritmos de análise  sintática
ascendente,   os   algoritmos   percorrem  a   sentença   da   direita   para   a   esquerda,
tentando   transformar   os   símbolos   terminais   em   não   terminais   por   meio   de
processos de deslocamento e redução; até mesmo o sentido de processamento
diferente   do   padrão   de   leitura   humana se   aplica   a   todo   tipo   de   sentença.  O
resultado final, porém, é que a sentença pode não ser válida dentro da gramática.
Assim, a árvore sintática é criada das folhas para a raiz e a gramática utilizada é a
mesma que a usada para outras formas de processamento. Ou seja, não precisa
ser colocada em um padrão para esse processamento.
O elemento central desse processo é o autômato de pilha, também denominado
de PDA, uma vez que consegue executar as funções de movimentação e redução
dos tokens da sentença utilizando uma pilha para o seu processamento, com a
aplicação das duas funções características dessa estrutura de dados: a inserção
de elementos na pilha; e a retirada de elementos da pilha.
4. Especificar uma linguagem, com sua gramática, léxico e sintaxe, é apenas o
primeiro passo para o desenvolvimento da linguagem. A próxima etapa é a criação
de um compilador para essa linguagem, sendo tipicamente realizada com o auxílio
de ferramentas para a construção de analisadores sintáticos.
Com relação a esses componentes, assinale a alternativa correta.
Resposta correta.
C. As ferramentas de construção de analisadores semânticos são utilizadas para gerar
formas de interpretar e validar sentenças criadas a partir de uma gramática.
Essas   ferramentas   foram   criadas   para criar   gramáticas   e   produções   próprias,
desenvolver uma   linguagem e   implementá-la   utilizando   esses softwares.
Essa liberdade é fornecida ao usuário devido ao fato de que a ferramenta provê
liberdade para o desenvolvedor   inserir  as regras de produção que desejar  nos
arquivos-fonte. Tanto o ANTLR, desenvolvido sobre a máquina virtual Java e tem
características   e   sintaxe   similares   às   orientadas   a   objetos,
quanto o Yacc, desenvolvido para o Linux e que tem características de linguagem
imperativa,
são distribuídos sob licenças de software livre. Portanto, podem ser utilizados para
qualquer propósito ou aplicação.
Ao se utilizar esse método para a criação de elementos capazes de processar
uma gramática, é possível  implementar linguagens e aplicar esses módulos em
novos softwares sem precisar realizar do zero a implementação de um analisador
sintático.  Afinal,  esses componentes  permitem que sejam escritas   funções que
serão   executadas   quando   a   sentença
for processada. O código da definição de uma linguagem tem um campo em que é
possível   inserir   as   funções   que  o   sistema   irá   executar   ao   se  deparar   com  a
produção em questão.
5. A ambiguidade em gramáticas é a possibilidade de se criar mais de uma árvore
sintática a partir de uma sentença.
Com relação a gramáticas ambíguas, assinale a alternativa correta.
Você acertou!
E. A ambiguidade é indesejada em linguagens. Quando detectada, deve ser corrigida ou
pode não ser possível dar o significado correto a um programa.
As gramáticas ambíguas estão sujeitas à criação de softwares com funcionamento
imprevisível,  uma vez que pode não ser possível verificar exatamente qual é a
função esperada pelo desenvolvedor do código-fonte. A ambiguidade não é uma
característica   intrínseca   às   linguagens   livres   de   contexto   e   é indesejada,   pois
impede que o compilador determine quais funções o código-fonte deve executar.
Ela impede o compilador de determinar exatamente o que um código-fonte diz, já
que um mesmo token pode estar  ligado a mais de uma expressão.  Logo, caso
exista essa característica em uma linguagem, deverá ser eliminada por meio das
operações corretas.
Caso   uma  produção   apresente   ambiguidade,   a   gramática   toda   é   considerada
ambígua e deve ser revista. Como uma produção nunca é aplicada isoladamente,
a produção ambígua já é o suficiente para determinar a gramática inteira como
ambígua.
	Implementação de analisadores sintáticos
	Exercícios