Linguagens • Capítulo 5

O que é uma linguagem de programação?


Uma linguagem de programação é bem parecida a uma linguagem real. Existe uma estrutura por trás dela, e algumas regras que ditam o que é e o que não é válido dizer. Quando lemos e escrevemos linguagem natural, estamos subconscientemente aprendendo estas regras, e o mesmo é verdade para linguagens de programação. Nós podemos utilizar essas regras para entender os outros, e gerar nosso próprio discurso, ou código.

Nos anos 1950, o linguista Noam Chomsky formalizou algumas observações importantes sobre linguagens. Muitas delas formam a base do nosso entendimento de linguagem hoje. Uma delas foi a observação que linguagens naturais tendem a ser construídas a partir de subestruturas recursivas e repetidas.

cat

Gato • não sabe falar ou programar

Como exemplo disto, vamos examinar a frase:

Os gatos caminhavam no carpete.

Usando as regras do Português, o substantivo gatos pode ser substituído por dois substantivos separados por e.

Os gatos e cachorros caminhavam no carpete.

Cada um dos dois substantivos podem também ser substituídos novamente. Poderíamos usar a mesma regra anterior, e substituir gatos por dois novos substantivos juntados com e. Ou poderíamos usar uma outra regra e substituir cada substantivo por um substantivo mais um adjetivo, para adicionar descrição à eles.

Os gatos e ratos e cachorros caminhavam no carpete.

Os gatos brancos e cachorros pretos caminhavam no carpete.

Estes são apenas dois exemplos, mas o Português tem muitas outras regras diferentes sobre como os tipos de palavras podem ser mudados, manipulados e substituídos.

Nós notamos este exato comportamento em linguagens de programação também. Em C, o corpo de um comando if contém uma lista de novos comandos. Cada um destes novos comandos podem ser eles mesmos um outro comando if. Estas estruturas e substituições repetidas se refletem em todas as partes da linguagem. Elas são às vezes chamadas de regras de reescrita (em inglês, re-write rules), porque elas dizem como uma coisa pode ser reescrita como alguma outra coisa.

if (x > 5) { return x; }

if (x > 5) { if (x > 10) { return x; } }

A consequência desta observação por Chomsky é importante. Ela significa que embora exista um número infinito de coisas diferentes que podem ser ditas, ou escritas em uma linguagem particular, ainda é possível processar e entender todas elas com um número finito de regras de reescrita. Um conjunto de regras de reescrita é chamado de gramática.

Nós podemos descrever regras de reescrita de várias maneiras. Uma delas é textual. Nós podemos dizer algo como, "uma sentença deve ser uma frase verbal", ou "uma frase verbal pode ser ou um verbo, ou um advérbio e um verbo". Este método é bom para humanos mas é muito impreciso para os computadores entender. Ao programar, precisamos escrever uma descrição mais formal duma gramática.

Para escrever uma linguagem de programação como Lisp nós vamos precisar entender gramáticas. Para ler a entrada do usuário nós precisamos escrever uma gramática que a descreva. Então nós podemos usá-la juntamente com a entrada do usuário, para decidir se a entrada é válida. Nós também podemos usá-la para construir uma representação interna estruturada, o que fará bem mais fácil o trabalho de entendê-la, e então avaliá-la, executando a computação codificada nela.

É aí que entra uma biblioteca chamada mpc.

Parser Combinators


mpc é uma biblioteca combinadora de analisadores sintáticos (em inglês, Parser Combinator) que escrevi. Isto significa que ela é uma biblioteca que permite a você construir programas que entendem e processam linguagens específicas. Eles são conhecidos como parsers, ou analisadores sintáticos. Há muitas maneiras diferentes de construir parsers, mas o legal de usar uma biblioteca combinadora de parsers é que ela permite você construir parsers facilmente, simplesmente especificando a gramática ... ou quase isso.

Muitas bibliotecas combinadoras de parsers funcionam deixando você escrever código normal que se parece um pouco com uma gramática, não deixando você especificar uma gramática diretamente. Em muitas situações isto não é um problema, mas às vezes pode ficar desajeitado e complicado. Para nossa sorte, mpc nos permite escrever código normal que se parece com uma gramática, OU podemos usar uma notação especial para escrever a gramática diretamente!

Codificando gramáticas


Então, com o que se parece um código que se parece com uma gramática? Vamos dar uma olhada no mpc, tentando escrever código para uma gramática que reconhece a linguagem do cachorro Shiba Inu. Mais conhecido coloquialmente como Doge, nos memes da Internet. Esta linguagem nós vamos definir como segue:

Nota do tradutor: mantendo os nomes em inglês, para simetria com o código e proximidade do meme

› Um Adjective é ou "wow", "many", "so" ou "such".

› Um Noun (substantivo, em inglês) é ou "lisp", "language", "c", "book" ou "build".

› Um Phrase é um Adjective seguido de um Noun.

› Um Doge é zero ou mais Phrases.

Podemos começar tentando definir Adjective e Noun. Para fazer isso, a gente cria dois parsers, representados pelo tipo mpc_parser_t*, e os armazenamos nas variáveis Adjective e Noun. Nós usamos a função mpc_or para criar um parser onde uma de muitas opções podem ser usadas, e a função mpc_sym para envolver nossas strings iniciais.

Se você semicerrar os olhos, pode tentar ler o código como se fosse as regras que especificamos acima.

/* Constroi um parser 'Adjective' para reconhecer descricoes */
mpc_parser_t* Adjective = mpc_or(4, 
  mpc_sym("wow"), mpc_sym("many"),
  mpc_sym("so"),  mpc_sym("such")
);

/* Constroi um 'Noun' para reconhecer coisas */
mpc_parser_t* Noun = mpc_or(5,
  mpc_sym("lisp"), mpc_sym("language"),
  mpc_sym("book"),mpc_sym("build"), 
  mpc_sym("c")
);

Como posso acessar essas funções mpc?

Por enquanto não se preocupe sobre compilar ou rodar qualquer dos exemplos de código neste capítulo. Apenas foque em entender a teoria por trás das gramáticas. No próximo capítulo vamos nos acertar com a mpc e usá-la para uma linguagem próxima do nosso Lisp.

Para definir Phrase nós podemos referenciar nossos parsers existentes. Nós precisaremos usar a função mpc_and, que especifica que alguma coisa é requerida e a seguir uma outra. Como entrada nós passamos Adjective e Noun, nossos parsers definidos anteriormente. Esta função também recebe os argumentos mpcf_strfold e free, que dizem como juntar ou deletar os resultados desses parsers. Ignore esses argumentos por enquanto.

mpc_parser_t* Phrase = mpc_and(2, mpcf_strfold, 
                               Adjective, Noun, free);

Para definir Doge nós precisamos especificar que zero ou mais de algum parser é necessário. Para isso, precisamos usar a função mpc_many. Como antes, esta função requer a variável especial mpcf_strfold para dizer como os resultados serão juntados, o que podemos ignorar.

mpc_parser_t* Doge = mpc_many(mpcf_strfold, Phrase);

Depois de criar um parser que procura por zero ou mais ocorrências de um outro parser, uma coisa interessante aconteceu. Nosso Doge aceita entrada de qualquer tamanho. Isto significa que sua linguagem é infinita. Aqui estão apenas alguns exemplos de possíveis strings Doge poderia aceitar. Da mesma forma que descobrimos na primeira seção deste capítulo, nós usamos um número finito de regras de reescrita para criar uma linguagem infinita.

"wow book such language many lisp"
"so c such build such language"
"many build wow c"
""
"wow lisp wow c many language"
"so c"

Se usarmos mais funções mpc, podemos devagarinho construir parsers que analisam ("parseiam") linguagens mais e mais complicadas. O código que usamos lê-se mais ou menos como uma gramática, mas se torna mais bagunçado com complexidade adicional. Devido a isso, usar essa abordagem nem sempre é uma tarefa fácil. Um conjunto de funções auxiliares que usam construções simples para tornar fáceis algumas tarefas frequentes estão todas documentadas no repositório Git da mpc. Essa é uma boa abordagem para linguagens complicadas pois ela permite um controle fino, mas não serão necessários para nosso caso.

Gramáticas naturais


mpc nos permite escrever gramáticas numa maneira mais natural também. Em vez de usar funções C que se parecem menos com uma gramática, nós podemos especificar a coisa toda em uma grande string. Ao usar este método, não precisamos nos preocupar de como juntar ou descartar as entradas, com funções como mpcf_strfold ou free. Tudo é feito automaticamente para nós.

Eis aqui como poderíamos recriar os exemplos anteriores usando este método.

mpc_parser_t* Adjective = mpc_new("adjective");
mpc_parser_t* Noun      = mpc_new("noun");
mpc_parser_t* Phrase    = mpc_new("phrase");
mpc_parser_t* Doge      = mpc_new("doge");

mpca_lang(MPCA_LANG_DEFAULT,
  "                                           \
    adjective : \"wow\" | \"many\"            \
              |  \"so\" | \"such\";           \
    noun      : \"lisp\" | \"language\"       \
              | \"book\" | \"build\" | \"c\"; \
    phrase    : <adjective> <noun>;           \
    doge      : <phrase>*;                    \
  ",
  Adjective, Noun, Phrase, Doge);

/* Faz algum parsing aqui... */

mpc_cleanup(4, Adjective, Noun, Phrase, Doge);

Sem ter um entendimento preciso da sintaxe para essa longa string, deve ser óbvio como a gramática fica muito mais clara nesse formato. Se aprendermos tudo o que os símbolos especiais significam, mal precisamos semicerrar os olhos.

Uma outra coisa a notar é que o processo agora está em duas etapas. Primeiro nós criamos e nomeamos várias regras usando mpc_new e a seguir as definimos usando mpca_lang.

O primeiro argumento para mpca_lang são as opções da linha de comando. Para isso, simplesmente usamos os defaults (valores padrões preestabelecidos). O segundo é uma longa string multi-line (isto é, em múltiplas linhas) em C. Esta é a especificação da gramática. Ela consiste de um certo número de regras de reescrita. Cada regra tem o nome da regra à esquerda, um dois pontos :, e à direita sua definição terminada com um ponto e vírgula ;.

Os símbolos especiais usados para definir as regras ao lado direito funcionam da seguinte forma:

"ab"A string ab é requerida.
'a'O caractere a é requerido.
'a' 'b'Primeiro 'a' é requerido, a seguir 'b' é requerido.
'a' | 'b'Ou 'a' é requerido, ou 'b' é requerido.
'a'*Zero ou mais 'a' são requeridos.
'a'+Um ou mais 'a' são requeridos.
<abba>A regra chamada abba é requerida.

Parece familiar...

Você notou que a descrição da string de entrada para mpca_lang soa como se estivesse especificando uma gramática? É porque ela está mesmo. mpc usa a si mesma para analisar ("parsear") a entrada que você fornece para mpca_lang. Ela faz isso especificando uma gramática em código usando o método anterior. Quão elegante é isso, hein?

Usando a tabela descrita acima, verifique que o que eu escrevi acima é igual ao que está especificado no código.

Este método de especificar uma gramática é o que vamos usar nos próximos capítulos. Ele pode parecer um pouco consternante no começo. Gramáticas podem ser difíceis de entender. Mas à medida que continuamos você se tornará mais e mais familiarizado com como criá-las e editá-las.

Este capítulo é sobre teoria, então se você vai tentar alguma das tarefas bônus, não se preocupe muito sobre estarem corretas. Pensar com a mentalidade certa é mais importante. Fique à vontade para inventar símbolos e notação para certos conceitos para fazê-los mais simples de escrever. Alguma tarefa bônus pode precisar de estruturas de gramática cíclicas ou recursivas, então não se preocupe caso tenha que usá-las!

Referência


#include "mpc.h"

int main(int argc, char** argv) {

  /* Build a parser 'Adjective' to recognize descriptions */
  mpc_parser_t* Adjective = mpc_or(4, 
    mpc_sym("wow"), mpc_sym("many"),
    mpc_sym("so"),  mpc_sym("such")
  );

  /* Build a parser 'Noun' to recognize things */
  mpc_parser_t* Noun = mpc_or(5,
    mpc_sym("lisp"), mpc_sym("language"),
    mpc_sym("book"), mpc_sym("build"), 
    mpc_sym("c")
  );
  
  mpc_parser_t* Phrase = mpc_and(2, mpcf_strfold, 
    Adjective, Noun, free);
  
  mpc_parser_t* Doge = mpc_many(mpcf_strfold, Phrase);

  /* Do some parsing here... */
  
  mpc_delete(Doge);
  
  return 0;
  
}
#include "mpc.h"

int main(int argc, char** argv) {

  mpc_parser_t* Adjective = mpc_new("adjective");
  mpc_parser_t* Noun      = mpc_new("noun");
  mpc_parser_t* Phrase    = mpc_new("phrase");
  mpc_parser_t* Doge      = mpc_new("doge");

  mpca_lang(MPCA_LANG_DEFAULT,
    "                                           \
      adjective : \"wow\" | \"many\"            \
                |  \"so\" | \"such\";           \
      noun      : \"lisp\" | \"language\"       \
                | \"book\" | \"build\" | \"c\"; \
      phrase    : <adjective> <noun>;           \
      doge      : <phrase>*;                    \
    ",
    Adjective, Noun, Phrase, Doge);

  /* Do some parsing here... */

  mpc_cleanup(4, Adjective, Noun, Phrase, Doge);
  
  return 0;
  
}

Metas bônus


  • › Escreva mais alguns exemplos de strings que a linguagem Doge contém.
  • › Por que há barras invertidas \ em frente das aspas " na gramática?
  • › Por que há barras invertidas \ ao fim da linha na gramática?
  • › Descreva textualmente uma gramática para números decimas como 0.01 ou 52.221.
  • › Descreva textualmente uma gramática para endereços de URLs como https://construa-seu-proprio-lisp.herokuapp.com/.
  • › Descreva textualmente uma gramática para sentenças em Português simples como o gato sentou no tapete.
  • › Descreva mais formalmente as gramáticas acima. Use |, *, ou qualquer símbolo que você mesmo invente.
  • › Se você está familiarizado com JSON, descreva textualmente uma gramática para ele.

Navegação

‹ Um Prompt Interativo

• Conteúdo •

Análise Sintática ›