Compiladores - Análise sintática - Exercícios

Prévia do material em texto

Compiladores - Análise sintática
Exercícios
1. A análise sintática é feita na fase da compilação, que analisa a estrutura da
linguagem baseada em uma gramática. Alguns algoritmos são implementados
dependendo da gramática.
Leia as afirmações a seguir:
I – O algoritmo LL(1) pode ser executado em gramáticas ambíguas e com
recursividade à esquerda.
II – O algoritmo com backtracking é do tipo top-down e tem um custo de execução
alto.
III – O algoritmo LR(0), tipo top-down, é executado em gramática com recursividade
à esquerda.
IV – Algoritmos baseados na precedência de operadores são do tipo ascendente e
operam com ambiguidade de gramática.
Quais estão corretas?
Você acertou!
B. II e IV.  
A gramática, na análise sintática, são as regras impostas à estrutura que derivam
em   uma   linguagem.   Uma   linguagem   de   livre   contexto   foi   derivada   de   uma
gramática   de   livre   contexto   e   alguns  algoritmos   são   implementados  de   forma
descendente (top-down) e ascendente (bottom-up).
Sendo assim, tem-se que:
I – A afirmação é falsa, pois o algoritmo da família LL não pode ser executado em
gramáticas ambíguas e com recursividade à esquerda.
II  – A afirmação é verdadeira,  pois o algoritmo com backtracking é do  tipo top-
down e tem um custo de execução alto.
III   –  A afirmação  é   falsa,   pois   os  algoritmos   da   família   LR,   tipo bottom-up,   é
executado em gramática com recursividade à esquerda.   
IV – A afirmação é verdadeira, pois o algoritmo que trabalha com precedência de
operadores   (exemplos:   *,+,   -,   /)   e   potência é   do   tipo   ascendente   e   pode   ser
executado em gramáticas ambíguas.
2. As gramáticas livres de contexto são usadas para definir linguagens de
programação, bem como os seus compiladores. Uma gramática de livre contexto é
definida por uma quádrupla G = ｛ V, T, P, S｝. Os elementos básicos que formam as
regras da gramática são os símbolos terminais, formados por elementos de um
alfabeto Σ, e os símbolos não terminais, comumente chamados de variáveis.
Agora, considere as seguintes afirmações:
I – Os algoritmos da família LR são executados de forma ascendente (bottom-up),
ou seja, partem de uma cadeia para chegar a uma variável inicial. 
PORQUE
II – Fazem uso de uma palavra de entrada, um parser, uma pilha de análise sintática
e uma tabela construída por meio de coleções canônicas de itens. 
Assinale a alternativa que apresenta a análise correta das afirmações:
Você acertou!
B. As afirmações I e II são proposições verdadeiras e a II justifica a I.
Os algoritmos da família LR podem ser LR(0), LR(1), LALR(1) e SLR(1), sendo
executados de forma ascendente (bottom-up), ou seja, partem de uma cadeia
para chegar a uma variável inicial e, como estrutura, fazem uso de uma palavra
de entrada, um parser, uma pilha de análise sintática e uma tabela construída
por meio de coleções canônicas de itens.
3. As regras sintáticas que representam a definição da linguagem, indicando como
símbolos terminais e não terminais podem ser combinados, são conhecidas como
regras de produção. Considere a expressão 1 + 2 * 3. Pode-se utilizar o algoritmo de
precedência de operadores para fazer a análise sintática dessa sentença.
Considerando o contexto, marque V para verdadeiro e F para falso:
( ) Pode existir uma ambiguidade na gramática, pois o algoritmo por precedência
de operadores consegue resolver a ambiguidade.
( ) Os níveis mais baixos da árvore sintática criada pelo algoritmo de
precedência têm maior prioridade na execução.
( ) O algoritmo de precedência faz uso de uma tabela de precedência, em que o
símbolo identificador * tem maior prioridade entre os operadores.
( ) O look-ahead do vetor da palavra de entrada aponta para somente um caractere
por vez.
Agora, assinale a alternativa que apresenta a sequência correta:
Você acertou!
A. V – F – V – V.
O algoritmo bottom-up por  precedência  de  operadores  é  utilizado  em gramática
em que há operações aritméticas e pode ser usado em gramáticas ambíguas, pois
faz uso de uma tabela de prioridades de identificadores de operação como *, +, -,
entre outros.
Sendo assim, a sequência correta é:
(V) A afirmativa é verdadeira, pois a ambiguidade na gramática é resolvida pela
tabela de precedência de prioridade utilizada pelo algoritmo.
(F)  A  afirmativa   é   falsa,   uma   vez   que   a   tabela   de   precedência   determina   a
prioridade dos operadores, sendo que os de maior prioridade estão  localizados
no nível mais baixo da árvore sintática. 
(V) A afirmativa é verdadeira,   já que uma tabela de precedência,  prioridade de
operações, é utilizada pelo algoritmo no processo de parsing. 
(V) A afirmativa é verdadeira, pois o ponteiro do vetor conhecido como look-ahead 
aponta para um caractere por vez na palavra de entrada.
4. Uma linguagem é baseada em uma gramática. A gramática determina as regras
a serem aplicadas em determinada linguagem. Uma gramática tem variáveis,
expressões e identificadores.
Considere a gramática a seguir:
E=> E+T | T
T=> T*F | F
F => a | b 
Assinale a alternativa correta.
Você acertou!
C. O  algoritmo  ascendente  de  precedência   de  operadores  pode   ser   aplicado  a  essa
gramática.
A   gramática   apresenta   uma   recursividade   à esquerda   e   operações
matemáticas. Sendo   assim, o algoritmo ascendente por precedência de
operadores é o mais indicado para essa gramática, pois resolve o problema da
associatividade pela tabela de precedência. 
As demais sentenças estão incorretas, pois o algoritmo LL(1) não é indicado para
gramáticas com recursividade à esquerda. Os algoritmos da família LR não usam
tabela de precedência. Já o algoritmo de precedência usa a tabela de precedência
de operadores.
5. Existe uma extensa literatura sobre a teoria da gramática e a análise sintática.
Possivelmente, uma das obras mais famosas nessa área seja An efficient context-
free parsing algorithm, de Earley J. (1970), sendo mais orientado para o compilador
de gramáticas livres de contexto.
Assinale a alternativa que preenche corretamente as lacunas:
Os ___________ de compiladores tendem a ser muito conservadores em sua
escolha de técnicas de análise para linguagens de programação convencionais.
Existem boas razões práticas para isso, mas há momentos em que técnicas
diferentes, e talvez mais poderosas, são requeridas. Uma ___________ livre de
contexto define recursivamente vários conjuntos de strings. Cada conjunto é
denotado por um nome, que é chamado de ___________. O conjunto de não
terminais é disjunto do conjunto de terminais. Um dos não terminais é escolhido
para denotar a linguagem descrita pela ___________. Isso é chamado de símbolo
inicial da gramática. Os sets são descritos por várias produções. Cada produção
descreve algumas das strings possíveis que estão contidas no conjunto denotado
por um não terminal. Uma ___________tem a forma do conjunto de símbolos não
terminais e terminais associados entre si e são as derivações de regras da
gramática.
Assinale a alternativa que preenche as lacunas de forma correta.
Você acertou!
A. desenvolvedores – gramática – não terminais – gramática – produção.
Os desenvolvedores de compiladores tendem a ser muito conservadores em
sua   escolha   de   técnicas   de   análise   para   linguagens   de   programação
convencionais. Existem boas razões práticas para isso, mas há momentos em que
técnicas   diferentes,   e   talvez  mais   poderosas,   são requeridas. Uma gramática
livre de contexto define recursivamente vários conjuntos de strings.Cada
conjunto é denotado por um nome, que é chamado de não terminal. O conjunto
de não terminais é disjunto do conjunto de terminais; a  maioria dos   não
terminais é escolhida para denotar a linguagem descrita pela gramática. Isso é
chamado   de   símbolo   inicial   da   gramática. Os sets são descritos por várias
produções. Cada   produçãodescreve   algumas   das strings possíveis   que   estão
contidas no conjunto denotado por um não terminal. Uma produção tem a forma
do conjunto de símbolos não terminais e terminais associados entre si e são as
derivações de regras da gramática.
	Compiladores - Análise sintática
	Exercícios