Embed Size (px)
Citation preview
Gramáticas, Autômatos eCompiladores
Aula 1Paulo Eduardo e Silva Barbosa
Adaptado de:Isabel Dillmann Nunes
} Formato da disciplina} Introdução} Linguagens e Gramáticas◦ Alfabeto◦ Palavra◦ Linguagem◦ Gramática
} Exemplos
Roteiro
} Paulo Eduardo e Silva Barbosa◦ [email protected]
} Página da disciplina◦ https://sites.google.com/site/pesbarbosa/
} Bibliografia básica} AHO, Alfred V.; LAM, Mônica S.; SETHI, Ravi;
ULLMAN, Jeffrey D. Compiladores: Princípios, Técnicas e Ferramentas. Pearson Addison Wesley, 2007.
Formato da disciplina
SIPSER,Michael. Introdução à Teoria da Computação. 2ª ed. São Paulo: Thomson Pioneira, 2007. MENEZES, Paulo Blauth. Linguagens Formais e Autômatos. Ed. Bookman Companhia, 1a edicao, 2008.
PRICE, Ana Maria de Alencar; TOSCANI, Simão Sirineo Implementação de Linguagens de Programação: Compiladores. 3a ed. Bookman, 2008
LOUDEN, Keneth C. Compiladores: Princípios e Práticas. São Paulo: Thomson Learning, 2004.
Bibliografia
} Avaliações◦ 1º Estágio� Prova (5)� Lista de exercícios (2)� Projeto de Compiladores (analisador léxico e sintático) (3)◦ 2º Estágio� Prova� Projeto de Compiladores (analisador léxico e sintático)◦ 3º Estágio� Integrador� Projeto de Compiladores (analisador léxico e sintático)
Formato da disciplina
} Teoria das Linguagens Formais◦ 1950◦ Desenvolvida para Linguagens Naturais◦ Aplicadas para Linguagens da Computação
} Sintaxe◦ Verificação gramatical de programas
} Semântica◦ Interpretação para a linguagem (significado ou valor para
um determinado programa)
Introdução
} Como definir uma linguagem em Computação? } Alfabeto (Σ)◦ Conjunto finito de símbolos ou caracteres.◦ Exemplos: � {a, b, c}� ø
Linguagens e Gramáticas
} Palavra, cadeia de caracteres ou sentenças sobre um alfabeto. É uma sequência finita de símbolos (do alfabeto) justapostos.
} Exemplos:◦ Considere o alfabeto {a, b, c}◦ Palavras:� ab� cab� aabcabb
Palavra
} Σ*◦ Denota o conjunto de todas as palavras possíveis sobre
Σ
} Σ+
◦ Denota Σ* - {ε} ◦ ε� Palavra vazia, sem símbolos
Palavra
} Uma linguagem formal L sobre um alfabeto Σ é um conjunto de palavras sobre Σ* :◦ L ⊆ Σ*
} Exemplo:◦ Σ = {a, b}◦ Linguagem: conjunto de palíndromos sobre Σ◦ Palavras desta linguagem (infinito):� a, bb, aba, abba, bbbb, ...
Linguagem Formal
É formalmente definida pelo conjunto de todos os
programas (palavras) da linguagem.
Linguagem de Programação
} Conjunto finito de regras nas quais, quando aplicadas sucessivamente, geram palavras;
} O conjunto de todas as palavras geradas por uma
gramática define a linguagem.
Gramática
} Gramática de Chomsky, Gramática Irrestrita ou simplesmente Gramática
◦ G = (V, T, P, S)
◦ V = conjunto finito de símbolos variáveis ou não-terminais;◦ T = conjunto finito de símbolos terminais disjunto de V;◦ Regra de Produção = P: (V ∪ T)+ (V ∪ T)*◦ S = elemento de V chamado de símbolo inicial
Gramática
} Gramática Regular (Linguagens Regulares) } G = ({S, A, B}, {0, 1}, P, S) } P = { S → 0B, S → 1A, A → 0, A → 0S, B → 1, B → 1S }
Exemplos de Gramática
} G = ({S, R}, {0, 1}, P, S) } P = { S → 0S, S → 1R, R → 1R, R → ε }
Exemplos de Gramática
