Hierarquia de Chomsky

Origem: Wikipédia, a enciclopédia livre.
Hierarquia de Chomsky

Hierarquia de Chomsky é a classificação de gramáticas formais descrita em 1959 pelo linguista Noam Chomsky. Esta classificação possui 4 níveis, sendo que os dois últimos níveis (os níveis 2 e 3) são amplamente utilizados na descrição de linguagem de programação e na implementação de interpretadores e compiladores. Mais especificamente, o nível 2 é utilizado em análise sintática (computação) e o nível 3 em análise léxica.

A classificação das gramáticas começa pelo tipo 0, com maior nível de liberdade em suas regras, e aumentam as restrições até o tipo 3. Cada nível é um super conjunto do próximo. Logo, uma gramática de tipo n é consequentemente uma linguagem de tipo n - 1.

Gramática com estrutura de frase[editar | editar código-fonte]

Ver artigo principal: Gramática com estrutura de frase

Também conhecida como 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 corresponde exatamente ao conjunto das linguagens que esta classe de gramática é capaz de gerar.

Gramáticas sensíveis ao contexto[editar | editar código-fonte]

Também conhecida como Tipo 1. Se as regras de substituição forem sujeitas à 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.

Gramáticas livres de contexto[editar | editar código-fonte]

Ver artigo principal: Gramáticas livres de contexto

Também conhecida como de 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[editar | editar código-fonte]

Ver artigo principal: Forma Normal de Backus

Backus-Naur Form ou somente BNF, é 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

Gramáticas regulares[editar | editar código-fonte]

Ver artigo principal: Gramáticas regulares

Também conhecida como de 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.

Teoria de autômatos: linguagem formal e gramática formal
Hierarquia
Chomsky
Gramática Linguagem Reconhecedor
Tipo-0 Irrestrita Recursivamente enumerável Máquina de Turing
-- -- Recursiva Máquina de Turing que sempre para
Tipo-1 Sensível ao contexto Sensível ao contexto Autômato linearmente limitado
Tipo-2 Livre de contexto Livre de contexto Autômato com pilha
Tipo-3 Regular Regular Autômato finito