Share via

Gramáticas, Linguagens e Compiladores: um retorno às bases.

  • Article

Olá pessoal, tudo certo?

No post anterior iniciamos nossa discussão sobre guias e DSL's. E já que o assunto envolve a definição de linguagens e geração de código, pensei em voltar um pouco às bases.

Quando pensamos em linguagens, podemos citar duas formas básicas para a formalização de linguagens de programação: as gramáticas (com suas leis de formação) e as regras de testes ou reconhecedores (com suas regras de validação).

Podemos definir uma gramática como um conjunto de leis de formação que definem de maneira rigorosa o modo de geração de textos corretos de uma linguagem. Assim, partindo-se de uma gramática, é possível gerar textos válidos na linguagem-alvo. Da mesma forma, uma linguagem é um conjunto de todos os textos que podem ser gerados a partir da gramática que define aquela linguagem.

Logo, gramáticas são mecanismos geradores, que permitem a síntese de textos pertencentes a uma determinada linguagem. A base desse assunto é a Hierarquia de Chomsky. Algumas referências sobre o assunto você encontra aqui:

Chomsky Hierarchy
Ref.: https://en.wikipedia.org/wiki/Chomsky_hierarchy

A Hierarquia de Chomsky define tipos diferentes de linguagens, de acordo com a rigidez de suas gramáticas e regras de formação. De forma resumida, citamos 4 tipos de gramáticas:

  • Gramáticas Irrestritas ou de tipo 0 (zero)
  • Gramáticas Sensíveis ao Contexto ou de tipo 1
  • Gramáticas Livres de Contexto ou de tipo 2
  • e finalmente as Gramáticas Lineares ou de tipo 3, as que possuem maior importância para o estudo e desenvolvimento de compiladores.

Durante o processo de definição de uma linguagem, podemos usar as chamadas meta-linguagens. Por exemplo, pense numa meta-linguagem quando temos um texto escrito em português para definir a gramática inglesa. Nesse caso, português é a meta-linguagem, usada para explicar a gramática alvo, a gramática inglesa. Em computação, uma meta-linguagem muito conhecida é a BNF ou "BACKUS-NAUR FORM". Veja um exemplo de BNF abaixo:

<syntax> ::= <rule> | <rule> <syntax>
<rule> ::= <opt-whitespace> "<" <rule-name> ">" <opt-whitespace> "::="
<opt-whitespace> <expression> <line-end>
<opt-whitespace> ::= " " <opt-whitespace> | ""
<expression> ::= <list> | <list> "|" <expression>
<line-end> ::= <opt-whitespace> <EOL> | <line-end> <line-end>
<list> ::= <term> | <term> <opt-whitespace> <list>
<term> ::= <literal> | "<" <rule-name> ">"
<literal> ::= '"' <text> '"' | "'" <text> "'"

Outro exemplo simples de definição em BNF, para formação de expressões como 000101, 010101, 11100101, etc, é dada abaixo:

<integer> ::= <digit><integer> | <digit>
<digit> ::= 0 | 1

Conceitos como terminais, símbolos, vocabulários, entre outros, são elementos da definição de linguagens de programação. Veja alguns links sobre BNF aqui:

Backus–Naur form
Ref.: https://en.wikipedia.org/wiki/Backus-Naur_form

Finalmente, temos o desafio de construir nosso gerador de código ou compilador. Entenda os geradores de código como programas específicos, que trazem alguma sofisticação, mas que na verdade são baseados em rotinas simples e bem definidas. Tipicamente, um compilador apresenta os seguintes componentes:

  • Funções de acesso a arquivos (acesso físico ao disco)
  • Funções de acesso lógico
  • Funções para extração de caracteres
  • Analisador Léxico
  • Analisador Sintático
  • Otimizador ou analisador semântico
  • e o Gerador de código

Veja maiores detalhes sobre cada componente de uma compilador aqui:

Ref.: https://en.wikipedia.org/wiki/Compiler

A figura abaixo apresenta um mapa das principais atividades realizadas por um compilador, para ilustrarmos melhor esse post.

image 

E uma leitura importante sobre compiladores sempre é o livro do dragão :)

Compilers: Principles, Techniques, and Tools (2nd Edition)
Ref.: https://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811

Durante o processo de definição e construção de nossos guias de automação ou mesmo nossas DSL's não vamos precisar aplicar toda a rigidez do processo envolvido na construção de compiladores, interpretadores ou mesmo geradores de código para linguagens formais. Porém, muitos dos elementos da teoria de compilação são ferramentas importantes para o arquiteto nesse processo. Conhecer essas teorias e manter uma leitura constante desses assuntos é sem dúvida um diferencial.

Como arquitetos, retornar as bases de tempos em tempos é uma prática saudável. :)

Por enquanto é só! Até o próximo post :)

Waldemir.

Comments

  • Anonymous
    January 21, 2008
    Excelente post wcamb! Acho que muita gente que está na faculdade vai acabar batendo neste artigo por meio de ferramentas de search (leia-se live.com :-D). Quando eu fiz faculdade, tinha uma carência enorme deste tipo de artigo. O meu professor de compiladores certa vez pediu que desenvolvessemos um analisador léxico. Era uma tarefa simples, mas foi um pouco trabalhoso. Concluimos esta, mas nunca chegamos às demais etapas do desenvolvimento de um compilador. A galera abendou! Queremos mais textos acadêmicos!

  • Anonymous
    January 21, 2008
    Obrigado procha! :) Realmente, resgatar os conceitos acadêmicos de tempos em tempos é crucial para a manutenção de uma boa arquitetura. E as disciplinas relacionadas a linguagens de programação são muito ricas para isso. Recomendo fortemente buscar uma boa leitura sobre esses conceitos, de construção de modelos, linguagens formais e autômatos, construção de compiladores e afins. Ao final, teremos a grata satisfação de entender melhor as bases de nossos sistema, em seus fundamentos. Um abraço! Waldemir. Nota: novos posts "acadêmicos" estarão nascendo em breve...aguarde!