Gramatica Livre de Contexto 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.
1. UsoSã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.
2. ElementosA 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.
3. PropriedadesAs 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)
link Arquivo origem: WGramaticaLivreContexto.xml. referencia