Compiladores

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1301 palavras )
  • Download(s) : 0
  • Publicado : 6 de maio de 2012
Ler documento completo
Amostra do texto
Linguagens Formais e Autômatos
P. Blauth Menezes
blauth@inf.ufrgs.br

Departamento de Informática Teórica Instituto de Informática / UFRGS

Linguagens Formais e Autômatos - P. Blauth Menezes

1

Linguagens Formais e Autômatos
P. Blauth Menezes 1 2 3 4 5 6 7 8 9 Introdução e Conceitos Básicos Linguagens e Gramáticas Linguagens Regulares Propriedades das Linguagens Regulares AutômatoFinito com Saída Linguagens Livres do Contexto Propriedades e Reconhecimento das Linguagens Livres do Contexto Linguagens Recursivamente Enumeráveis e Sensíveis ao Contexto Hierarquia de Classes e Linguagens e Conclusões

Linguagens Formais e Autômatos - P. Blauth Menezes

2

9 - Hierarquia de Classes de

Linguagens e Conclusões

9.1 Hierarquia de Chomsky 9.2 Conclusões 9.3 LeituraComplementar: Gramática de Grafos

Linguagens Formais e Autômatos - P. Blauth Menezes

3

9 - Hierarquia de Classes de Linguagens e Conclusões
Linguagens Formais e Autômatos - P. Blauth Menezes

4

9 Hierarquia de Classes de Linguagens e Conclusões
9.1 Hierarquia de Chomsky


Constituída pelas classes & inclusões próprias
• • • • Regulares ou Tipo 3 Livres do Contexto ou Tipo 2Sensíveis ao Contexto ou Tipo 1 Recursivamente Enumeráveis ou Tipo 0

Linguagens Formais e Autômatos - P. Blauth Menezes

5

Linguagens Recursivamente Enumeráveis ou Tipo 0 Linguagens Sensíveis ao Contexto ou Tipo 1 Linguagens Livres do Contexto ou Tipo 2

Linguagens Regulares ou Tipo 3



Noam Chomsky definiu estas classes como (potenciais) modelos para linguagens naturais
6

LinguagensFormais e Autômatos - P. Blauth Menezes



Linguagens de programação
• nem sempre são tratadas adequadamente na Hierarquia de Chomsky



Existem linguagens que não são livres do contexto para as quais
• poder dos formalismos sensíveis ao contexto é excessivo • inadequados principalmente no que se refere à complexidade



Conhecimento das linguagens sensíveis ao contexto
•relativamente limitado • dificulta o seu tratamento

Linguagens Formais e Autômatos - P. Blauth Menezes

7



Exemplos de problemas que não Livres do Contexto
• múltiplas ocorrências de um mesmo trecho de programa ∗ como a declaração de um identificador e suas referências de uso ∗ análogo a { wcw  w é palavra de {a, b}* } • alguns casos de validação de expressões com variáveis de tiposdiferentes • associação de um significado (semântica) de um trecho de programa ∗ análise de um conjunto de informações (dependentes de contextos) ∗ como identificadores, ambientes, tipos de dados, localização, seqüências de operações, etc

Linguagens Formais e Autômatos - P. Blauth Menezes

8



Para algumas linguagens de programação
• Classe das Linguagens Livres do Contexto é excessiva •Classe das Linguagens Regulares, insuficiente



Linguagem Livre do Contexto Determinística
• pode ser denotada por um Autômato com Pilha Determinístico • é possível implementar (facilmente) um reconhecedor com tempo de processamento proporcional a 2n ∗ n é o tamanho da entrada ∗ muito mais eficiente que o melhor algoritmo conhecido para as linguagens livres do contexto

Linguagens Formaise Autômatos - P. Blauth Menezes

9



De qualquer forma, o estudo das Linguagens Livres do Contexto tem sido de especial interesse
• permitem uma representação simples da sintaxe • adequada para estruturação formal e para análise computacional



Entretanto, o estudo das Linguagens Livres do Contexto tem mostrado problemas não-solucionáveis
• determinar se uma gramática é ambígua ∗existem duas ou mais árvores de derivação distintas para uma mesma palavra • não existe um algoritmo que verifique a igualdade de duas linguagens ∗ dificulta otimização e teste de processadores de linguagens

Linguagens Formais e Autômatos - P. Blauth Menezes

10



Portanto, dependendo da linguagem e dos objetivos do trabalho
• estudos específicos ∗ eventualmente fora da Hierarquia...
tracking img