Árvores de Análise Sintática

Prévia do material em texto

ÁRVORES DE ANÁLISE 
SINTÁTICA 
Marcelo Guerra 
ÁRVORE DE ANÁLISE SINTÁTICA 
 Representação intuitiva e útil para derivações. 
 
 É uma árvore ordenada na qual os nós são rotulados com os lados 
esquerdos das produções. 
 
 Os filhos de cada nó representam seus correspondentes lados direitos. 
 
 Mostra como os símbolos de uma string de terminais estão agrupados em 
substrings. 
 Cada substring pertencendo a linguagem de uma das variáveis da 
gramática. 
 
 Estrutura de dados usada pelos compiladores para representar e 
manipular a estrutura de programas-fonte. 
 
 A existência de uma AAS está ligada às derivações e inferências 
recursivas. 
CONSTRUÇÃO DE ÁRVORES DE ANÁLISE 
SINTÁTICA 
 As AAS respeitam as seguintes condições para 
uma gramática G = (V, T, P, S) 
 
1. Cada nó interior é rotulado por uma variável  V. 
 
2. Cada folha é rotulada por uma variável, um terminal 
ou  
• Se a folha for rotulada por , ela deve ser o único filho de 
seu pai. 
 
3. Se um nó interior é rotulado por A e seus filhos por 
X1, ..., Xn respectivamente a partir da esquerda, 
então A  X1...Xn é uma produção em P. 
EXEMPLO 
  
 
E 
E * E 
I 
P 
O P 0 
1 P 1 
 
EIE *
*
 0110
*
P
O RESULTADO DE UMA ÁRVORE DE 
ANÁLISE SINTÁTICA 
 É uma string resultante da concatenação dos 
símbolos contidos nos nós folhas de uma AAS. 
 
 Essa string é sempre derivada da variável raiz. 
 
 São de especial importância as AAS tais que: 
1. O resultado é uma string de terminais. 
2. A raiz é rotulada com o símbolo de início. 
EXERCÍCIO 
 Construir uma árvore de análise sintática que 
represente a derivação para a string a * (a + b00). 
E lm E * E lm I * E lm a * E lm a * (E) 
lm a * (E + E) lm a * (I + E) lm a * (a + E) 
lm a * (a + I) lm a * (a + I0) lm a * (a + I00) 
lm a * (a + b00) 
EXERCÍCIO 
 Construir uma árvore de análise sintática que 
represente a derivação para a string a * (a + b00). 
E lm E * E 
lm I * E 
 lm a * E 
lm a * (E) 
 lm a * (E + E) 
lm a * (I + E) 
lm a * (a + E) 
lm a * (a + I) 
lm a * (a + I0) 
lm a * (a + I00) 
lm a * (a + b00) 
E E 
E 
E E 
* 
E 
I 
a 
( ) 
+ 
a 
0 
I 
0 
b 
I 
I 
I 
DERIVAÇÕES, INFERÊNCIA, AASS 
 Os seguintes fatos são equivalentes: 
 
1. O procedimento de inferência recursiva determina 
que o string de terminais w está na linguagem da 
variável A 
 
2. A * w 
 
3. A w 
 
4. A w 
 
5. Existe uma AAS com raiz A e resultado w 
 
EQUIVALÊNCIAS 
 Se uma string w satisfizer a condição no início do 
arco, então ela satisfará no final. 
 Exemplo: se inferirmos que w está na linguagem de A por 
inferência recursiva, então existe uma AAS com raiz A e 
resultado w. 
Árvore de 
Análise 
Sintática 
Derivação mais 
à direita 
Derivação mais 
à esquerda 
Inferência 
recursiva 
 
Derivação 
APLICAÇÕES DAS GLCS 
APLICAÇÕES DAS GLCS 
 As GLC’s são usadas para definir linguagens de 
programação. 
 Existe uma forma automatizada de transformar uma 
descrição de uma linguagem na forma de uma GLC em um 
analisador sintático. 
 O analisador sintático descobre a estrutura do programa-
fonte e a representa por uma AAS. 
 
 eXtensible Markup Language: convenções para a troca 
de informações em e-commerce. 
 A definição de tipo de documento é parte essencial: trata-se 
de uma GLC definindo as tags permissíveis e as formas como 
elas podem estar aninhadas. 
 Diferente da HTML, as tags não tratam da apresentação do texto, 
mas sim do seu significado. 
 
ANALISADORES SINTÁTICOS 
 Muitos aspectos de uma linguagem de programação 
têm uma estrutura que pode ser descrita por 
expressões regulares. 
 Por exemplo, a definição de tokens como identificadores. 
 
 No entanto, outros aspectos necessitam da aplicação 
de GLCs 
 Utilização de parênteses e colchetes de forma balanceada, 
por exemplo: 
 B  BB | (B) |  
 Essa linguagem não é regular, assim como a gramática que 
define IF-ELSE possivelmente não balanceados numa 
linguagem qualquer: 
 S   | SS | iS |iSeS 
GERADORES DE ANALISADORES 
SINTÁTICOS 
 O YACC (yet another compiler compiler) foi um 
sistema pioneiro na automação da produção de 
compiladores. 
 
 A entrada para o YACC é uma GLC em notação 
semelhante àquela que usamos. 
 
 Associada a cada produção existe uma ação, 
fragmento de código C executado sempre que um 
nó da árvore sintática é criado usando o corpo 
daquela produção. 
AMBIGÜIDADE 
 Uma gramática capaz de produzir mais de uma 
AAS para a mesma sentença é ambígua. 
 
 Considere a gramática 
 
DERIVAÇÕES “LM” PARA DETECTAR 
AMBIGÜIDADE 
 Derivações não são necessariamente únicas para 
uma gramática não-ambígua. 
 
 No entanto, para estas gramáticas: 
 
 Uma derivação mais à esquerda é única; 
 Uma derivação mais à direita é única 
 
 para uma mesma cadeia de entrada. 
 
 
 
TEOREMA 
 Para G=(V,T,P,S) e w em T*, w tem duas árvores 
de análise sintáticas distintas se e somente se w 
tem duas derivações mais à esquerda distintas a 
partir de S. 
 
 
 
TEOREMA 
 Para G=(V,T,P,S) e w em T*, w tem duas árvores 
de análise sintáticas distintas se e somente se w 
tem duas derivações mais à esquerda distintas a 
partir de S. 
 
 
 A ambiguidade é inadequada para linguagens de 
programação. 
 O compilador não poderia determinar a estrutura de 
certos programas-fonte e, portanto, não poderia 
deduzir com certeza qual seria o código executável 
apropriado para o programa. 
 
ELIMINAÇÃO DA AMBIGÜIDADE 
 Algumas vezes, é possível reescrever uma 
gramática de modo a obter uma GLC equivalente 
não-ambígua. 
 
 Um modo de resolver a ambiguidade é por meio 
da associação de regras de precedência de 
operadores. 
 
 Construir AAS para a+a*a, usando: 
ELIMINAÇÃO DA AMBIGÜIDADE 
E T 
* 
+ 
E 
T 
F 
T F 
id 
a 
F 
id 
a 
id 
a 
EXEMPLO 
 
 
 
 O comando 
 if E1 then S1 else if E2 then S2 else S3 
 Possui a árvore de derivação abaixo: 
 Agora, testando a cadeia 
 if E1 then if E2 then S1 else S2 
 Temos as árvores de derivação a seguir: 
 
 
 
 
 
 
 
 
 
 
 O que nos leva a concluir que a gramática é ambígua. 
 Temos as árvores de derivação a seguir: 
 
 
 
 
 
 
 
 
 
 
 
 
 O problema com a esta gramática: 
 Trata todas as instruções como se tivessem um 
significado sintático igual. 
 Ela não contempla a existência de ifs sem else 
 Ela não contempla que quando o else está presente, ele 
depende de um then imediatamente anterior a ele. 
ELIMINANDO A AMBIGUIDADE DA 
GRAMÁTICA DO COMANDO IF-THEN-ELSE 
stmt coincidente | livre 
coincidente if expr then coincidente else coincidente 
| other 
livre if expr then stmt 
| if expr then coincidente else livre 
 
 
 Para a gramática acima, há apenas uma análise 
possível. 
ELIMINANDO A AMBIGUIDADE DA 
GRAMÁTICA DO COMANDO IF-THEN-ELSE 
stmt coincidente | livre 
coincidente if expr then coincidente else coincidente 
| other 
livre if expr then stmt 
| if expr then coincidente else livre 
 
 
 A regra para construções if é que uma cláusula else, 
quando presente, é coincidida com a then anterior 
mais próximaainda não utilizada. Portanto, entre 
uma then e sua else coincidente, não pode haver 
uma instrução if sem uma clausula else. Sendo 
assim, para essa situação, as instruções devem ser 
distinguidas entre as coincidentes e as livres. As 
livres são ifs sem else e todas as outras instruções 
são coincidentes. 
AMBIGÜIDADE INERENTE 
 Uma linguagem livre de contexto é dita 
inerentemente ambígua se todas as suas 
gramáticas são ambíguas. 
 
 Podemos construir muitas gramáticas para uma 
certa linguagem L que podem ser ambíguas. 
 
 Mas, basta uma gramática para essa linguagem 
L ser não-ambígua para concluirmos que a 
linguagem não é ambígua.