Hierarquia de Chomsky
Keywords: Hierarquia de Chomsky, Compiladores, Expressão regular, Noam Chomsky
Hierarquia de Chomsky (criada por Noam Chomsky) é o estudo de casos particulares de aplicações mais restritas, para resolver problemas ao se projetarem compiladores para uma linguagem. Dividimos a gramática em 4 classes:
| Conteúdo |
Com estrutura de Frase ou Tipo 0
São aquelas às quais nenhuma limitação é imposta. O universo das linguagens que se podem definir através dos mecanismos gerativos definidos pela gramática correspondente exatamente ao conjunto das linguagens que esta classe de gramática é capaz de gerar.
Sensíveis ao Contexto ou Tipo 1
Se as regras de substituição for imposta à restrição de que nenhuma substituição possa reduzir o comprimento da forma sentencial à qual a substituição é aplicada, cria-se uma classe chamada sensíveis ao contexto ou tipo 1.
Livres de Contexto ou Tipo 2
São aquelas em que é levantado o condicionamento das substituições impostas pelas regras definidas pelas produções. Este condicionamento é eliminado impondo às produções uma restrição adicional, que restringe as produções à forma geral
onde 
e 
Forma Normal de Backus
Forma Normal de Backus é uma outra forma de representar as produções de Gramáticas livres de contexto.
Onde, 
é substituído por ::= e os não terminais por <"nome" >.
Ela é usada para definir gramáticas com o lado esquerdo de cada regra composto por um único símbolo não terminal.
Exemplo:
<Y> ::= y1
<Y> ::= y2
:
<Y> ::= yn
escreve-se: <Y> ::= y1| y2| ...| yn
Regulares ou Tipo 3
É uma restrição sobre a forma das produções, pode-se criar uma nova classe de gramáticas de grande importância no estudo dos compiladores por possuírem propriedades adequadas para a obtenção de reconhecedores simples. Que também podem ser denominada de Expressão regular.