Sebesta_Texto Cap 04

Prévia do material em texto

Capítulo 4
Análise Léxica e Sintática
Conceitos de Linguagens de Programação – Robert W. Sebesta
Tópicos do Capítulo 4
Introdução
Análise léxica
O problema da análise sintática
Análise sintática descendente recursiva
Análise sintática ascendente
Conceitos de Linguagens de Programação – Robert W. Sebesta
Introdução
Sistemas de implementação de linguagem devem analisar o código de origem, independentemente da abordagem de implementação específica
Quase todas as análises sintáticas são baseadas em uma descrição formal da sintaxe da linguagem de origem (BNF)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática
A porção de análise sintática de um processador de linguagem quase sempre consiste em duas partes:
O analisador léxico (construções de linguagem de pequena escala, como nomes e literais numéricos)
O analisador sinático, ou parser (construções de larga escala como expressões, sentenças e unidades de programas)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Vantagens de usar BNF para descrever 
uma sintaxe
Fornece uma descrição da sintaxe clara e concisa, tanto para humanos quanto para os sistemas de software
Pode ser usada como a base direta para o analisador sintático
Implementações baseadas em BNF são relativamente fáceis de manter
Conceitos de Linguagens de Programação – Robert W. Sebesta
Razões para separar análises léxica e sintática
Simplicidade - técnicas para análise léxica são menos complexas do que aquelas para análise sintática; o processo pode ser mais simples se for realizado separadamente
Eficiência – separação permite otimização do analisador léxico
Portabilidade - partes do analisador léxico podem não ser portáteis, mas o analisador sintático sempre é
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise léxica
Um analisador léxico é essencialmente um casador de padrões para cadeias de caracteres
Um analisador léxico serve como o passo inicial de um analisador sintático
Coleta caracteres e os agrupa logicamente, atribuindo códigos internos de acordo com sua estrutura - lexemas
Lexema casa um padrão de caracteres, que é associado à categoria léxica chamada token
sum é um lexema; seu token pode ser IDENT
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise léxica
O analisador léxico é normalmente uma função chamada pelo analisador sintático quando esse precisa de um token
Três abordagens para construir um analisador léxico:
Escrever uma descrição formal dos tokens e usar uma ferramenta de software que constrói analisadores léxicos dirigidos por tabela que recebem essa descrição
Projetar um diagrama de transições de estado que descreva os padrões de tokens da linguagem e escrever um programa que implemente o diagrama
Descrever um diagrama de transições de estado que descreva os padrões de tokens da linguagem e construir manualmente uma implementação dirigida por tabela do diagrama de estados
Conceitos de Linguagens de Programação – Robert W. Sebesta
Diagrama de estados
Um diagrama de transição de estados, ou apenas diagrama de estados, é um grafo dirigido 
Os nós de um diagrama de estados são rotulados com nomes de estados 
Os arcos são rotulados com os caracteres de entrada que causam as transições entre os estados
Um arco pode também incluir ações que o analisador léxico deve realizar quando a transição ocorrer
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise léxica
Em muitos casos, transições podem ser combinadas para simplificar o diagrama de estado
Ao reconhecer um identificador, todas as letras maiúsculas e minúsculas são equivalentes
Use uma classe de caracteres que inclui todas as letras
Ao reconhecer um literal inteiro, todos os dígitos são equivalentes - usar uma classe dígitos
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise léxica
As palavras reservadas e identificadores podem ser reconhecidos juntos (em vez de haver uma parte do diagrama para cada palavra reservada)
Use uma tabela para determinar se um possível identificador é uma palavra reservada
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise léxica
Subprogramas utilitários:
getChar - obtém o próximo caractere de entrada do programa de entrada e o coloca na variável nextChar, determina a classe do caractere de entrada e a coloca na variável charClass
addChar – coloca o caractere de nextChar no lugar em que o lexema está sendo acumulado, lexeme
lookup – determina se a sequência de caracteres lexeme é uma palavra reservada
Conceitos de Linguagens de Programação – Robert W. Sebesta
Diagrama de estados
Conceitos de Linguagens de Programação – Robert W. Sebesta
Analisador léxico
Implementação: 
 	  Mostrar front.c (pp. 195-199)
A seguir, temos a saída do analisador léxico de
 front.c quando usado com (sum + 47) / total
Next token is: 25 Next lexeme is (
Next token is: 11 Next lexeme is sum
Next token is: 21 Next lexeme is +
Next token is: 10 Next lexeme is 47
Next token is: 26 Next lexeme is )
Next token is: 24 Next lexeme is /
Next token is: 11 Next lexeme is total
Next token is: -1 Next lexeme is EOF
Conceitos de Linguagens de Programação – Robert W. Sebesta
O problema da análise sintática
Objetivos da análise sintática:
Encontrar erros de sintaxe; para cada um, produzir uma mensagem de diagnóstico e se recuperar
Produzir uma árvore de análise sintática completa, ou ao menos percorrer a estrutura da árvore, para uma entrada sintaticamente correta
Conceitos de Linguagens de Programação – Robert W. Sebesta
O problema da análise sintática
Duas categorias de análise sintática
Descendente – constrói a árvore a partir da raiz em direção às folhas
Ascendente – constrói a árvore a partir das folhas em direção à raiz
Conceitos de Linguagens de Programação – Robert W. Sebesta
O problema da análise sintática
Analisadores sintáticos descendentes
Dada uma forma sentencial, xA , a análise sintática precisa escolher a regra sentencial correta para obter a próxima forma sentencial em uma derivação mais à esquerda, usando apenas o primeiro token produzido por A
Os algoritmos de análise sintática mais comuns:
Descendente recursivo - implementação codificada
Algoritmos LL- implementação dirigida por tabela
Conceitos de Linguagens de Programação – Robert W. Sebesta
O problema da análise sintática
Analisadores sintáticos ascendentes
Dada uma forma sentencial direita α, o analisador sintático deve determinar que subcadeia de α e a RHS da regra na gramática que deve ser reduzida para seu LHS para produzir a forma sentencial anterior na derivação mais à direita
Os algoritmos mais comuns de análise sintática ascendente estão na família LR
Conceitos de Linguagens de Programação – Robert W. Sebesta
O problema da análise sintática
A complexidade da análise sintática
Os algoritmos de análise sintática que trabalham para qualquer gramática não ambígua são complicados e ineficientes (O(n3), onde n é o comprimento da entrada)
Compiladores usam análises sintáticas que trabalham para apenas um subconjunto de todas as gramáticas possíveis (O(n), onde n é o comprimento da entrada)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
Um analisador sintático descendente recursivo é chamado assim porque consiste em uma coleção de subprogramas, muitos dos quais são recursivos, e produz uma árvore de análise sintática em uma ordem descendente 
A EBNF é idealmente adequada para analisadores sintáticos descendentes recursivos
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
Uma gramática para expressões simples:
<expr>  <term> {(+ | -) <term>}
<term>  <factor> {(* | /) <factor>}
<factor>  id | int_constant | ( <expr> )
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintáticadescendente recursiva 
Assume que temos um analisador léxico chamado lex, que coloca seu código de token na variável global nextToken
O processo de código quando há apenas um RHS:
Para cada símbolo terminal na RHS, o símbolo terminal é comparado com nextToken; se eles casam, o analisador léxico é chamado para obter o próximo token de entrada
Para cada não terminal, o subprograma de análise sintática para o não terminal é chamado
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
/* Função expr 
 Analisa sintaticamente cadeias na linguagem gerada pela regra:
 <expr> → <term> {(+ | -) <term>}
 */
void expr() {
/* Analisa sintaticamente o primeiro termo */
 
  term(); 
/* Desde que o próximo token seja + ou -, obtenha 
 o próximo token e analise sintaticamente o próximo termo */
 
  while (nextToken == ADD_OP || 
 nextToken == SUB_OP){
    lex();
    term(); 
  }
}
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
Essa rotina em particular não detecta erros
Convenção: Cada rotina de análise sintática deixa o próximo token de entrada em nextToken
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
Um não terminal que tenha mais de uma RHS requer um processo inicial para determinar qual RHS deve analisar
A RHS correta é escolhida com base no próximo token da entrada
O próximo token é comparado com o primeiro token que pode ser gerado por cada RHS
Se eles não casam, é um erro sintático
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
/* term
Analisa sintaticamente cadeias na linguagem gerada pela regra:
<term> -> <factor> {(* | /) <factor>)
*/
void term() {
 printf("Enter <term>\n");
/* Analisa sintaticamente o primeiro termo */
 factor();
/* Desde que o próximo token seja * ou /,
 obtenha o próximo token e analise sintaticamente o próximo termo */
 while (nextToken == MULT_OP || nextToken == DIV_OP) {
 lex();
 factor();
 }
 printf("Exit <term>\n");
} /* Fim da função term */
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
/* Função factor
 Analisa sintaticamente cadeias na linguagem
 gerada pela regra: 
 <factor> -> id | (<expr>) */
 void factor() {
 /* Determina qual RHS */
   if (nextToken) == ID_CODE || nextToken == INT_CODE)
 /* Para o id de RHS id, chama lex */
     lex();
/* Se a RHS is (<expr>) – chame lex para passar o parêntese esquerdo, 
 chame expr e verifique pelo parêntese direito */
    else if (nextToken == LP_CODE) {
      lex();
 expr();
    if (nextToken == RP_CODE)
 lex();
 else
 error();
 } /* Fim do else if (nextToken == ... */
 else error(); /* Neither RHS matches */
}
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
- Saída da análise sintática da expressão de exemplo(sum + 47) / total 
Next token is: 25 Next lexeme is (	Next token is: 11 Next lexeme is total
Enter <expr>			Enter <factor> 			
Enter <term>			Next token is: -1 Next lexeme is EOF
Enter <factor>			Exit <factor>
Next token is: 11 Next lexeme is sum	Exit <term>
Enter <expr>			Exit <expr>
Enter <term>
Enter <factor>
Next token is: 21 Next lexeme is +
Exit <factor>
Exit <term>
Next token is: 10 Next lexeme is 47
Enter <term>
Enter <factor>
Next token is: 26 Next lexeme is )
Exit <factor>
Exit <term>
Exit <expr>
Next token is: 24 Next lexeme is /
Exit <factor>
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
A classe de gramáticas LL
O Problema da Recursão à Esquerda
Se uma gramática tem recursão à esquerda, ela não pode ser a base para uma análise sintática descendente
Uma gramática pode ser modificada para remover a recusão à esquerda
Para cada não terminal, A, 
Agrupe as regras-A como A → Aα1 | … | Aαm | β1 | β2 | … | βn
 onde nenhum dos β’s começa com A
2. Substitua as regras-A originais por
 A → β1A’ | β2A’ | … | βnA’
 A’ → α1A’ | α2A’ | … | αmA’ | ε
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
Outra característica da gramática que desabilita a análise sintática descendente é o teste de disjunção par a par
A incapacidade de determinar o RHS correto na base de um token
Definição: FIRST() = {a |  =>* a }
 (Se  =>* ,  está em FIRST())
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
Teste de Disjunção Par a Par:
Para cada não terminal, A, na gramática que tem mais de uma RHS, para cada par de regras, A  i e A  j, deve ser verdadeiro que
 	FIRST(i) ⋂ FIRST(j) = 
Exemplos:
 A  a | bB | cAb
 A  a | aB
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
Fatoração à esquerda pode resolver o problema
	As duas regras podem ser substituídas por 
 <variable>  identifier | identifier [<expression>]
 com
 <variable>  identifier <new>
 <new>   | [<expression>]
 ou
 <variable>  identifier [[<expression>]]
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
O problema da análise sintática é encontrar a RHS correta em uma forma sentencial à direita para obter a forma sentencial anterior na derivação
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
Intuição acerca dos manipuladores:
Definição: β e o manipulador da forma sentencial direita  = w se, e somente se, S =>*rm Aw =>rm w
Definição: β e uma frase da forma sentencial a direita γ se, e somente se, S =>*  = 1A2 =>+ 12
Definição: β é uma frase simples da forma sentencial à direita γ se, e somente se, S =>*  = 1A2 => 12
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
Intuição acerca dos manipuladores:
O manipulador de uma forma sentencial mais à direita é sua frase sentencial mais à esquerda
Dada uma árvore de análise sintática, é fácil encontrar o manipulador
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
Algoritmos de deslocamento e redução
Uma ação de redução (reduce) substitui uma RHS (o manipulador) no topo da pilha do analisador sintático por sua LHS correspondente
A ação deslocar (shift) move o próximo símbolo de entrada para a pilha do analisador sintático
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
Vantagens dos analisadores sintáticos LR:
Eles podem ser construídos para todas as linguagens de programação.
Eles podem detectar erros de sintaxes o mais cedo possível em uma varredura da esquerda para a direita.
A classe de gramáticas LR é um superconjunto da classe analisável sintaticamente por analisadores LL (por exemplo, muitas gramáticas recursivas à esquerda são LR, mas nenhuma é LL).
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
Analisadores sintáticos LR precisam ser construídos com uma ferramenta
Descoberta de Knuth: uma análise sintática ascendente pode usar sua história inteira, até o ponto atual, para fazer tomar decisões de análise
Havia apenas um número relativamente pequeno de situações diferentes, então a história poderia ser registrada por um estado, em uma pilha de análise
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
Uma configuração de um analisador sintático LR é um par de cadeias (pilha, entrada), com a forma detalhada
	(S0X1S1X2S2…XmSm, aiai+1…an$)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análisesintática ascendente
Uma tabela de análise sintática LR tem duas partes, ACTION e GOTO
A parte ACTION especifica a maioria das ações do analisador sintático
Rótulos de linhas são símbolos de estado; rótulos das colunas são símbolos terminais
A parte GOTO indica qual símbolo de estado deve ser inserido na pilha da análise sintática após uma redução ser completada
Rótulos são símbolos de estado; rótulos de coluna são não terminais
Conceitos de Linguagens de Programação – Robert W. Sebesta
A estrutura de um analisador sintático LR
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
Configuração inicial: (S0, a1…an$)
Ações do analisador sintático:
Se ACTION[Sm, ai] = Deslocar S, a próxima configuração é: 
		(S0X1S1X2S2…XmSmaiS, ai+1…an$)
Se ACTION[Sm, ai] = Reduzir A   e S = GOTO[Sm-r, A], onde r = tamanho de , a próxima configuração é
(S0X1S1X2S2…Xm-rSm-rAS, aiai+1…an$)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
Ações do analisador sintático:
Se ACTION[Sm, ai] = Aceita, a análise sintática está completa e nenhum erro foi encontrado.
Se ACTION[Sm, ai] = Erro, o analisador sintático chama uma rotina de tratamento de erros.
Conceitos de Linguagens de Programação – Robert W. Sebesta
Tabela de análise sintática LR
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
Tabelas de análise sintática LR podem ser facilmente construídas usando uma ferramenta de software como o yacc
Conceitos de Linguagens de Programação – Robert W. Sebesta
Resumo
A análise sintática é uma parte comum da implementação de linguagens
Um analisador léxico é um casador de padrões que isola as partes de pequena escala de um programa
Detecta erros sintáticos
Contrói uma árvore de análise sintática
Um analisador sintático descendente recursivo é um analisador sintático LL
EBNF
Problema da análise sintática para analisadores sintáticos ascendentes: achar a subcadeia da forma sentencial atual
A família LR de analisadores sintáticos de deslocamento e redução é a abordagem de análise sintática ascendente mais usada
*