Next: As gramáticas de cláusulas
Up: Gramáticas Previous: A estrutura de uma
Existem muitas classes de gramáticas. Cada uma delas tem a sua própria notação. Uma
classe familiar de gramáticas são as gramáticas independentes do contexto. As
linguagens de programação são muitas vezes especificadas com estas gramáticas,
geralmente usando a notação BNF (Backus-Naur Form).
O seguinte exemplo mostra uma gramática independente do contexto, na forma BNF, que
aceita a frase ``o homem vira o disco'':
<frase> ::= <sintagma_nominal> <sintagma_verbal>
<sintagma_nominal> ::= <determinante> <nome>
<sintagma_verbal> ::= <verbo> <sintagma_nominal>
<determinante> ::= o
<nome> ::= homem | disco
<verbo> ::= vira
As palavras que podem aparecer nas frases são os símbolos terminais da
gramática. Os outros símbolos, que aparecem nas regras de produção da gramática entre
< e >, são os símbolos não terminais. Para o exemplo
acima, os símbolos terminais são: o, homem, vira, e disco;
enquanto os símbolos não terminais são: frase, sintagma_nominal, sintagma_verbal,
determinante, nome e verbo.
Uma árvore de derivação é uma representação gráfica, em forma de árvore, da
sequência de derivação de uma frase a partir de uma gramática independente do
contexto. Essa árvore mostra a estrutura da frase e as relações hierárquicas entre as
várias frases possíveis. A um programa que constrói árvores de derivação chamamos analisador
sintáctico (``parser''). A seguinte figura ilustra uma árvore de derivação para
uma frase simples, como ``o homem vira o disco''.
Numa árvore de derivação os nós interiores estão associados a símbolos não
terminais e as folhas estão associadas a símbolos terminais.
Next: As gramáticas de cláusulas Up: Gramáticas Previous: A estrutura de uma