Tecnologia / Artigos / Linguagens de Programação /
O princípio: gramáticas

Cléber

![dictionary.jpg](/files/168) *Photo by [Joshua Hoehne](https://unsplash.com/@mrthetrain) on [Unsplash](https://unsplash.com/s/photos/dictionary)* --- Dado que lançar-me-ei na tarefa de escrever **bibliotecas de GraphQL em diversas linguagens**, é importante já conceber um plano a respeito de como essas bibliotecas farão o *parsing* tanto dos *schemata* quanto das requisições. Inicialmente, lembrei das ferramentas clássicas, *lex* e *yacc*, além da excelente [PLY](http://www.dabeaz.com/ply/). Mas confesso que sempre achei essas ferramentas automatizadas, por mais ricas que sejam, muito complexas. Não que a ideia em si seja complexa, mas digamos que eu queira usá-las como acessório para uma nova biblioteca: o que ocorrerá é que teremos uma "segunda linguagem", uma segunda tecnologia e mentalidade que deverão ser dominados por quem quer que queira entender a fundo como essa minha nova biblioteca funciona. É um conhecimento interessante? Certamente. Mas é vital? Não. O que é vital, na verdade, é pelo menos entender como elas funcionam e como é o "jeito certo" de se fazer o "parsing" de uma linguagem. Meio que dispensando uma abordagem mais tradicional e pensando em implementar algo didático e simples de entender, para que os leitores pudessem ler **código** em uma linguagem só e, com pouco esforço, entender direito o algoritmo em si, cheguei a cogitar *fazer na unha* simplesmente usando **expressões regulares**. Mas logo percebi que (1) seria extremamente ineficiente e (2) eu acabaria implementando do mesmo jeito que "o jeito certo", meramente virando as coisas do avesso (e "virar do avesso" significa: ao invés de ler o input 1 vez, ler diversas vezes, ou seja: um grande desperdício). Enfim, seria **deselegante**. Então, por fim, decidi não seguir nem com a implementação feia e tampouco com ferramentas automatizadas: farei *lexing* e *parsing* (a técnica tradicional) **na unha**. O que é muito bom, porque se a ideia desses artigos é justamente explorar algumas linguagens de programação, será interessante ver como cada uma lida com essas duas tarefas em especial. E, ademais, acredito que usar ferramentas automatizadas sem **nunca** ter feito *na unha* é um costume estranho, uma espécie de atalho trapaceiro, porque você acaba automatizando um trabalho que não tem a menor ideia de quão difícil ou fácil é e, no fim das contas, acaba sendo incapaz de apreciá-lo devidamente. (E, devo acrescentar: **não é errado** implementar um *lexer/parser* por conta própria, também. Você ganha em alguns aspectos e perde em outros, como quase tudo nessa vida.) # Linguagens, gramática, lexers e parsers GraphQL, caso você ainda não tenha percebido, é uma **linguagem**. Não uma "linguagem de programação", mas uma linguagem, tendo seus termos e gramática bem definidos. ## Gramática Uma gramática é um conjunto de regras que nos permitem entender se determinadas frases estão corretas ou não. E nós usamos pelo menos uma gramática no nosso dia-a-dia, que é justamente a gramática de nossa língua materna. A gramática da língua portuguesa, que não é nem um pouco simples (é considerada uma das mais complexas entre a família dos idiomas românticos), nos informa que a construção "*eu cadeira*" está **errada**, enquanto a construção "*eu, cadeira*" está perfeitamente correta. As gramáticas das linguagens naturais trazem consigo todo um conjunto de complicações típicas justamente da "naturalidade" dessas linguagens, que faz com que estejam repletas de **ambiguidades** e **implicitudes**. E aqui já temos a primeira grande divisão entre as diversas gramáticas: existem (1) as gramáticas ambíguas e (2) as gramáticas não-ambíguas. O "problema" das gramáticas ambíguas é que **é impossível garantir a identificação de frases erradas**, por mais simples que possa ser definir se uma frase está correta. Ou seja: você pode "rodar uma análise" e ter como resultado "*essa frase está correta!*" muito rapidamente, e esse é o "caso feliz". Ou pode receber simplesmente "*não sei*" como resultado, que quer dizer que a frase em questão pode estar correta ou pode estar errada, mas o analisador não pode garantir que conseguirá saber. ("Não garantir que conseguirá saber" é o caso em que você pode escolher rodar mais 1.000 iterações e não chegar a um resultado definido. E agora? Roda mais 1.000? Ou mais 10.000? E se não chegar num resultado? Mais 1.000? Pode ser que funcione, mas pode ser que não, e neste último caso, você nunca saberá com certeza se a frase está errada mesmo ou se você é que deixou de rodar meramente mais 1 iteração.) As linguagens que usamos "no mundo da computação", portanto, como as linguagens de programação e linguagens de marcação, são todas não-ambíguas. Como é o caso, inclusive, de GraphQL. ## Lexer O "lexer" também pode ser chamado de "*tokenizer*" (ou "tokenizador", para os mais íntimos), e seu papel na análise de um *input* é ler "letrinha por letrinha" (ou, mais precisamente, caracter por caracter) e formar "palavras" ou "tokens" **com significado embutido**. Por exemplo: digamos que você está escrevendo um compilador de **Nim**. Essa linguagem tem uma *keyword* `if`, mas, curiosamente, nada impede que uma *string* contenha a palavra `if`, como em `s = "if"`. Tomemos o seguinte código como exemplo: ```nim var s = "if" if s == "if": echo "if is if" else: echo s, " is not if" ``` Não é de se esperar que o compilador confunda a *string* `"if"` com a *keyword* `if`, certo? Certo. E, para nossa sorte, Nim tem poderes de metaprogramação que nos ajudarão a visualizar como seu tokenizador funciona. Chamaremos a macro `dumpTree` do módulo `macros` para conseguir ver como fica a tokenização do trecho acima. (Lembre-se: Nim define blocos por meio de indentação, como Python.) ```nim import macros dumpTree: s = "if" if s == "if": echo "if is if" ``` E o resultado é o seguinte: ``` StmtList Asgn Ident "s" StrLit "if" IfStmt ElifBranch Infix Ident "==" Ident "s" StrLit "if" StmtList Command Ident "echo" StrLit "if is if" ``` "Trocando em miúdos", temos o seguinte: ``` StmtList → statement list Asgn → assignment Ident "s" → identifier "s" StrLit "if" → string literal "if" IfStmt → `if` statement ElifBranch → elif branch (Nim "economiza" tokens, repare) Infix Ident "==" → identifier "==" (interessante, mas não surpreendente) Ident "s" → identifier "s" StrLit "if" → string literal "if" StmtList → statement list Command Ident "echo" → identifier "echo" StrLit "if is if" → string literal "if" ``` Repare que Nim tem "identifiers" (que seriam *keywords*), mas as *strings* `"if"` são dadas como *string literals*. E esse é o papel do *tokenizer*: **extrair significado** de cada cadeia de caracteres. ## Parser Mas identificar cada token não bastante é o definir para linguagem uma, certo? Existe uma determinada **ordem**, uma estrutura que faz com que certas combinações de *tokens* façam sentido, enquanto outras não. Os mais observadores terão observado que Nim chama essa estrutura de *tree* (árvore). E é assim que tratamos os programas: extraímos de cada um o que chamamos de "árvore abstrata de sintaxe" ou **AST** (*abstract syntax tree*). O papel do *parser*, então, é pegar o resultado do *lexer* e permitir que se escreva um programa que transforme uma entrada em uma AST. Repare que o *input* do *lexer* **não é "código fonte"**. O *input* do *lexer* é uma **gramática**: ``` gramática → lexer → parser → programa leitor ``` A ideia é conseguir gerar, no fim do processo, um "programa leitor", ou seja, um programa capaz de ler, por exemplo, código fonte de uma linguagem de programação e gerar um binário ou mesmo fazer análise estática para detectar problemas ou brechas de segurança. E é por isso que os "programas avós" dos *lexers* e *parsers* chamam-se `lex` (*lexer*) e `yacc`, que significa "*yet another compiler of compilers*". Sim, é um "compilador de compiladores"! Por questões relacionadas às licenças desses dois, o projeto GNU acabou criando suas próprias versões, o `flex` (*fast lexer*, mas que eu aposto que, no fundo, era *free lex*) e o `bison` (entendeu? Iaque / Bisão. Hã? Hã?). ### GraphQL e um parser LR(1) "LR" significa *left-to-right, rightmost derivation in reverse*, e indica a forma de funcionamento do parser. Um parser LR(1) fará a leitura do programa **em tempo linear**, ou seja: não importa quão complexo seja o que quer que o código fonte represente, a leitura em si (ou seja: a leitura caracter por caracter) seguirá do começo (à esquerda) ao fim (à direita) **sem ter que voltar** para ler algo novamente. Direita e esquerda, obviamente, refere-se meramente à forma de escrita comum no ocidente, mas nada impede que alguém crie uma linguagem que se lê da direita para a esquerda. Ainda assim se poderá usar um parser LR. Já o (1) significa que esse processo todo ocorrerá com meramente 1 "leitura à frente". Ou seja: quando o meu "programa leitor" estiver tratando do caracter 0, no máximo precisará acessar o caracter 1 para conseguir "entender" o que se passa, mas nunca precisará acessar o caracter 2, a não ser quando estiver analisando o caracter 1. ``` void main() {} ^^ |+-- look ahead +--- current position ``` O caso mais óbvio de necessidade de leitura de um caracter à frente é o *parsing* de *strings*, já que nada proíbe, em geral, que uma *string* contenha o caracter que serve de delimitador, como em `"aspa: \"."`. Percebeu que usamos o chamado "*escape character*" para conseguir inserir uma aspa dupla sem que isso confunda o parser? Pois é. Quando ele estiver lendo `\`, fará um *look ahead* de 1 para saber qual caracter, afinal, o autor do programa quer inserir ali, agora sabendo que **pode** ser uma aspa dupla que **não será** considerada um delimitador. E GraphQL, nossa gramática alvo, pode muito bem ser tratada por um parser LR(1), conforme veremo quando formos implementá-lo. # Nosso lexer/parser Sabendo, agora, de tudo isso, já estamos prontos para começar a implementar um *lexer* e *parser* de GraphQL. O objetivo disso será gerar um programa ou "rotinas" que sirvam, elas sim, para interpretar tanto *schemata* de GraphQL quanto o conteúdo de requisições. A primeira versão será feita em Python, que não somente tem uma sintaxe fácil de ser lida, como é o que usaremos para validar nosso algoritmo base sem preocupação com nada além do algoritmo em si. Até lá.

Curti

39 visitantes curtiram esse Item.

Anterior: Go é um castigo merecido | Próximo: Artigos / Diretrizes de Desenvolvimento