Introdução às gramáticas
Last updated
Last updated
A utilização de conjuntos para definir linguagens não é frequentemente a forma mais adequada e versátil para as descrever.
Preferível identificar estruturas intermédias, que abstraem partes ou subconjuntos importantes.
Descrições recursivas são bem mais simples, sem perda da objetividade e do rigor necessários.
As gramáticas descrevem linguagens por compreensão recorrendo a representações formais e (muitas vezes) recursivas.
As gramáticas definem formalmente as sequências válidas.
"O cão ladra"
G = ({O, Um, cão, lobo, ladra, uiva}, {frase, sujeito, predicado, artigo, substantivo, verbo}, frase, P).
frase -> sujeito predicado
sujeito -> artigo substantivo
predicado -> verbo
artigo -> O | Um
substantivo -> cão | lobo
verbo -> ladra | uiva
S -> 0S
S -> 0A
A -> 0A 1
A -> epsilon
S -> aX
X -> aX
X -> bX
X -> epsilon
ou
S -> aX
X -> aX | bX | epsilon
S -> S 1 S 1 S | A
A -> 0 A | epsilon