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.