camila

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1390 palavras )
  • Download(s) : 0
  • Publicado : 18 de agosto de 2014
Ler documento completo
Amostra do texto
Linguagens Livres de Contexto e
Autômato com Pilha

Tópicos
• Estudo das linguagens livres de contexto.
• Estudo dos Autômatos com Pilha

Contextualização

PushDown Automata

Importância
• Compreende um universo mais amplo
de linguagens.
• Trata adequadamente questões como
parênteses balanceados, construções
bloco-estruturadas.
• Compreende a sintaxe da maioria das
linguagensde propósitos gerais como
Pascal, C e Java.

Fonte:http://www.inf.puc-rio.br/~inf1626/docs/Notas-de-Aula.pdf

Considerações
• A classe das linguagens livres de contexto
contém a classe das linguagens
regulares.
• Constitui uma classe de linguagens
relativamente restrita, sendo fácil definir
linguagens que não pertencem a esta
classe.

Formalismos abrangidos
• Gramática livre decontexto
– Restrições são definidas de maneira mais
livre que na gramática regular.

• Autômato com pilha
– Estrutura básica análoga ao AFN, adicionada
de uma memória auxiliar tipo pilha (a qual
pode ser lida ou gravada).

Tópicos abrangidos





Árvore de derivação.
Gramática Ambígua.
Simplificação de Gramática.
Forma Normal.

Linguagens Livres do contexto
• Ou Tipo 2• São definidas a partir das gramáticas
livres do contexto.

Gramática Livre do Contexto
• Definição Formal
– Uma gramática livre do contexto G é uma gramática
G = (V, T, P, S)
– Restrição para as regras
A→
onde A é uma variável de V, e , uma palavra de (V ∪ T)*

Ou seja:
– Uma gramática livre do contexto é uma gramática na qual o lado
esquerdo das produções contém exatamente umavariável.
– (Veja como era na última linguagem estudada, pág 100,
Menezes, novo)

O sentido do termo
“LIVRE DO CONTEXTO”
• Considere A → .
• A variável A deriva  sem depender (sendo
“livre”) de qualquer análise dos símbolos
que antecedem ou sucedem A (o “contexto”)
na palavra que está sendo derivada.

Exemplo 01
• Seja L = {anbn | n≥0}
• Problema: duplo balanceamento
• SejaG=({S},{a,b},P,S) em que:
P= { S→ aSb | S→}
• Apresente a derivação para a palavra
aabb.
• S →aSb →aaSbb →aabb→aabb

Consideração
• O exemplo anterior é um caso clássico e
de fundamental importância no estudo da
computação e informática, pois permite
estabelecer analogia com estruturas de
duplo balanceamento em linguagens de
programação como Pascal, C, Java, ...
– Linguagensbloco-estruturadas (begin-end)
– Linguagens com parênteses balanceados

Exemplo 02

Ver exercícios complementares !

Métodos Formais para descrever a
sintaxe de uma linguagem
• Gramáticas livres de contexto
– Desenvolvida por Noam Chomsky em 1950
– Descreve a sintaxe das linguagens naturais.

• Forma de Backus-Naur – BNF
– Desenvolvida por John Backus para descrever o
Algol 58
– Baseada nasgramáticas livres de contexto
– É uma meta-linguagem para as linguagens de
programação.
– Usa abstrações para estruturas sintáticas

• Na ciência da computação e engenharia
de software, métodos formais são
técnicas baseadas em formalismos
matemáticos para a especificação,
desenvolvimento
e
verificação
dos
sistemas de softwares e hardwares.
• Podem contribuir para a confiabilidade erobustez de um projeto executando
análises matemáticas apropriadas

--> =

Regra ou Produção

Exemplo da sentença, cuja estrutura sintática é
descrita pela regra é:
Total = sub1 + sub2

BNF
• Backus Naur Form
• Em computação e informática, uma maneira
usual de representar uma gramática livre do
contexto é o uso da forma de Backus Naur ou
BNF.
• Em uma BNF vale:
– Asvariáveis são palavras delimitadas pelos símbolos
< >
– As palavras não delimitadas são terminais
– Uma regra de produção A →  é representada por
A ::= 

Abaixo um exemplo interessante
da linguagem BNF sendo descrita
em BNF:
syntax ::= { rule }
rule
::= identifier "::=" expression
expression ::= term { "|" term }
term
::= factor { factor }
factor ::= identifier |
quoted_symbol |...
tracking img