Aula06 Gramaticas LC

UNIVERSIDADE FEDERAL DO PARÁ
INSTITUTO DE CIÊNCIAS EXATAS E NATURAIS
FACULDADE DE COMPUTAÇÃO
CURSO DE BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO

Disciplina: LINGUAGENS FORMAIS, AUTÔMATOS E
COMPUTABILIDADE
Prof. Jefferson Morais
Email: [e-mail]

Agenda
Linguagens Livres de Contexto
 Gramáticas Livres de Contexto
 Árvore de derivação
 Ambiguidade
 Simplificação de GLC
 Formas Normais


2

Linguagens Livres de Contexto

3

Linguagens regulares
Descrevemos linguagens através de autômatos finitos e expressões regulares: formas diferentes, mas equivalentes
 Sabemos que algumas linguagens não são possíveis de serem descritas por eles


 Ex. {0n1n |n ≥ 0}

( ver Lema do bombeamento)

4

Introdução
Gramática Livre de Contexto: método mais poderoso de descrição de linguagens
 Estruturas recursivas
 LCC são simples e eficientes
 No estudo de linguagens humanas: GLC’s podem captar aspectos importantes da relação entre substantivos, verbos e preposições


5

Introdução


Aplicação: especificação e compilação de linguagens de programação
Elaborar uma gramática para a linguagem: primeiro passo para um compilador e interpretador  Parser: extrai o significado do programa para gerar o código compilado ou interpreta a execução
 GLC’s facilitam a produção do parser


6

Introdução




Uma Linguagem Livre de Contexto (LLC) é gerada por uma
Gramática Livre de Contexto (GLC)
LLC’s são definidas a partir de um formalismo gerador
(gramática) e um reconhecedor (autômato), como:
GLC: onde as regras de produção são definidas mais livrementes que em GR
 Autômato com Pilha (Pushdown Automata): estrutura básica e análoga ao AF, incluindo uma memória auxiliar do tipo pilha
(pode ser lida ou gravada) e a facilidade do não-determinismo


7

Gramática Livre de Contexto




Gramáticas consistem em uma coleção de regras de substituição (produção)
GLC é uma 4-tupla G=(V,T,P,S) com a restrição de conter, no lado esquerdo da produção, exatamente uma variável (não
terminal)