eventos

topico

nome

Gramatica Livre de Contexto

titulo

WGramatica Livre de Contexto

descritor

Gramatica Livre de Contexto

lead

Ferramenta para realizar a análise sintática de linguagens de programação. Indica quais cadeias de caracteres estão contidas em uma linguagem particular. Gera uma linguagem livre de contexto.

link

link

origem

WGramaticaLivreContexto.xml

referencia

referencia

topico

titulo

Uso

desc

São usadas tanto para a sintaxe quanto para a semântica de muitas linguagens, tais como: expressões matemáticas, Java, português.

Sintaxe

• Indica quais as cadeias de simbolos que são senteças válidas. A analise sintaxe determina os erros de escrita.
  

Semantica

• Indica o significado associado aàs cadeias. A analise semantica determina quais partes da cadeia são substantivos, verbos, expressões e termos.

topico

titulo

Elementos

desc

A gramática consiste de um conjunto de regras e um simbolo inicial não terminal.

Regra

• Cada regra especifica uma maneira de substituir um simbolo não terminal na cadeia atual com uma cadeia de simbolos terminais e não terminais.
• Quando uma cadeia resultante consiste apenas de simbolos terminais, paramos.
• Qualquer cadeia resultante desse processo foi gerada pela gramática
• Pode ter dois tipos de representação:
  BNF (Backus-Naur Form) - forma textual de representar as regras de uma gramatica
  Grafos sintáticos - forma visual de representar as regras de uma gramática livre de contexto.
  
  Exemplo:
  
  Notação BNF:
  <expressão> ::= (<expressao>)
  O operando do lado esquerdo do operador é o símbolo não-terminal;
  O operando do lado direito, a sua expansão, que pode conter símbolos terminais e não-terminais.
  Operadores  das regras da gramática envolvem:
       equivalencia       ::=        N::=A B
       alternativas         |            N::= A | B
       opção                 [ ]          N::= [A]
       repetições           *            N::=A*
       combinações       ( | )
       concatenação      { || }*    N::= {A||B}
  
  
  Notação grafos sintaticos:
  

             

 
Simbolo 

• S   simbolo
• ==>  derivação   ou seja substitui o lado direito da regra
• S ==>0S1 ==> 00S11 ==> 0011
• A sequencia 0011 foi construida por uma serie de derivações, tirando o S da string no final.

topico

titulo

Propriedades

desc

As gramaticas livres de contexto tem como propriedades:

• A linguagem gerada pela gramatica livre de contexto é composta por expressões aritméticas contendo colchetes balanceados, dois operandos e um operador: 
• Trata questões de linguagens de programação como:
  Parenteses Balanceados,
  Construções Bloco-Estruturadas
  Outras estruturas próprias de linguagens como C, Pascal, etc. 
• Pode ser convertida em gramatica regular
• Formalismo axiomático ou gerador: Gramáticas Livres de Contexto são gramáticas (tipo 2) onde as regras de produção são definidas de forma mais livre do que nas gramáticas regulares (tipo3)
• Formalismo operacional ou reconhecedor: São autômato com Pilha ou seja possui a estrutura basica de um automato finito deterministico ao qual é associado uma memória auxiliar na forma de pilha e a facilidade de não determinismo. Pode ser lida ou gravada.
• Árvore de derivação
   representaa derivação de uma palavra na forma deárvore
   parte do símbolo inicial como araiz
   termina em símbolos terminais como folhas 
• Pode ser reconhecida por autômato com pilha com um estado
• Estados não são necessários para "memorizar" o passado 
• Gramatica ambígua ou seja uma palavra associada a duas ou mais árvores de derivação (a esquerda ou a direita)