Do dicionário ao App: Como digitalizar um dicionário em PDF utilizando Compiladores

O analisador léxico é o primeiro componente de um compilador, ele é responsável pelo processamento do texto do programa na linguagem de origem. A saída deste componente é um conjunto de tokens na estrutura: <token,value>.

Exemplo:

Código-fonte: price = base + rate * 15

Tokens: <id,1> <=> <id,2> <+> <id,3> <*> <15>

Onde cada token é um símbolo abstrato e value aponta para uma entrada em uma Symbol Table - uma estrutura de dados utilizada em todas as fases do compilador para armazenar dados do programa.

A partir dos tokens gerados pelo analisador léxico, o analisador sintático gera uma Syntax Tree para representar a estrutura do programa. Syntax Tree's são amplamente utilizadas por IDE's e editores de texto para apontarem erros de sintaxe.

A Syntax Tree do exemplo acima pode ser representada da seguinte forma:

O analisador semântico utiliza os dados armazendos na Symbol table e a Syntax Tree para analisar a consistência semântica do programa de acordo com a definição da linguagem na gramática. Esta etapa realiza tarefas como checagem de tipos e promoção de tipos - caso a linguagem sendo analisada permita.

Se a variável rate do exemplo fosse do tipo ponto flutuante, a Syntax Tree produzida pelo analisador semântico seria enriquecida com a promoção do valor 15 de int para float:

Com a Syntax Tree pronta, é chegado o momento de produzir código em uma representação intermediária. Este código deve ser simples de produzir e de converter em código de linguagem de montagem, de modo a simplificar e tornar eficientes os próximos componentes do compilador. Um tipo comum de representação intermediária é o código de três endereços: uma sequência de instruções assembly-like com três operandos por instrução.

A representação em código de três endereços para o exemplo seria algo assim:

  t1 = intToFloat(15)
  t2 = id3 * t1
  t3 = id2 + t2
  id1 = t3

A partir da representação intermediária, inúmeras otimizações podem ser aplicadas de forma a tornar o código mais eficiente.

Seguindo com o exemplo, o conjunto de instruções gerado na etapa anterior poderia ser reduzido removendo a conversão explícita de int para float:

  t1 = id3 * 15.0
  id1 = id2 + t1

Com o código intermediário otimizado, é hora da geração do código na linguagem destino. Caso esta seja linguagem de montagem, o código gerado poderia ser um Assembly como este:

  LDF  R2, id3
  MULF R2, R2, #15.0
  LDF  R1, id2
  ADDF R1, R1, R2
  STD id1, R1

Em cada operação:

• O primeiro operando especifica o destino.
• O F indica que a operação trabalha com operandos de ponto flutuante.

Com uma visão geral de compiladores, voltemo-nos agora ao dicionário. Obviamente não criei um compilador do zero, utilizei ferramentas existentes para me auxiliar neste processo. Uma ferramenta muito conhecida no mundo Java é o ANTLR. O ANTRL permite a geração de parsers para a tradução, execução ou processamento de arquivos de texto estruturado ou binários. Tudo o que o ANTLR precisa é de uma gramática, a partir disso a ferramenta gera um parser baseado em Design Patterns como o Visitor que pode ser utilizado para a solução do problema, como por exemplo: gerar um mapa de traduções.

Para a criação da gramática, é preciso identificar a estrutura do dicionário, vejamos um exemplo:

Estamos interessados em dois elementos: a palavra de origem e sua tradução.

Do exemplo acima podemos extrair a seguinte estrutura:

• Palavra de origem;
• Classe gramatical;
• Contexto;
• Tradução;
• Sexo;
• ; seguido de exemplos.

Por sorte, tudo o que não nos interessa para a resolução do problema é demarcado com um ; facilitando a definição da gramática. A partir dessa estrutura podemos definir uma gramática inicial na linguagem utilizada pelo ANTLR:

  grammar EnPtDictionary;

  compilationUnit: (entry '\n'?)* EOF ;

  entry: enWord context? grammaticalClass ptWord examples ;

  context: '(' .*? ')' ;

  grammaticalClass: 'adj' 'adv'?
                  | 'adj' 'pp'?
                  | 'adv'
                  | 'npr' 'adj'?
                  | 'n' 'adj'?
                  | 'pp' 'adj'?
                  | 'prep'
                  | 'vr'
                  | 'vt' ('/' 'vi')?
                  | 'vt' (',' 'vi')?
                  | 'vt' ('/' 'vr')?
                  | 'vt' (',' 'vr')?
                  | 'vi'
                  ;

  enWord: word ;
  ptWord: word SEX? ;
  word: WORD | '\n' ;

  examples: ';' .*? '.' '\n'
          | '.' '\n'
          ;

  NUMBER: DIGIT+ ;
  fragment DIGIT: '0'..'9' ;

  SEX: 'm' (',' 'f')? | 'f' ;
  COMMA: ',' ;
  WORD: [a-zA-Z]+ ;

  WS: [ \t\r]+ -> skip ;

Elementos como sexo e contexto não aparecem em todas as entradas do dicionário, por isso são definidos como opcionais utilizando o caractere ?. Para detalhes da liguagem de definição da gramática, consulte a documentação.

Com mais um exemplo, percebemos que uma palavra de tradução não é o suficente, precisamos de uma lista de traduções, que é nada mais que palavras separadas por vírgula:

Podemos atender esse requisito com algumas modificações na gramática:

  entry: enWord context? grammaticalClass ptWord+ examples ;
  word: WORD | COMMA | '\n' ;
  COMMA: ',' ;

Neste exemplo estou simplificando ao máximo e incluindo a vírgula como uma palavra, sendo assim, no parser será necessário remover palavras que são vírgulas. Isto poderia ser tratado na gramática, mas serve para ilustrar que a gramática não precisa estar perfeita para resolver o seu problema, muita coisa pode ser resolvida no parser.

Após algumas iterações melhorando a gramática você terá uma que atenda as suas necessidades. Detalhes sangrentos como o tratamento de caracteres especiais foram mantidos de fora dos exemplos para facilitar o entendimento. A implementação completa você encontra no meu GitHub.

Com a gramática pronta podemos gerar o parser:

  java -cp "/tools/antlr-4.13.1-complete.jar:$CLASSPATH" org.antlr.v4.Tool -visitor -o ../src/main/java/antlr -package antlr EnPtGrammar

• -cp adiciona o ANTLR ao classath;
• -visitor instrui o comando para gerar o parser com o Design Pattern Visitor;
• -o especifica o diretório de saída para as classes geradas;
• -package especifica que todas as classes geradas devem conter a declaração package antlr;.

Após a execução do comando, você terá a seguinte estrutura:

De todos estes arquivos, o que nos interessa é a classe Java EnPtDicionaryBaseVisitor, que é uma implementação padrão do parser. Para cada elemento da gramática temos um método com a assinatura visitElement(var cx) que podemos sobreescrever:

  class EnPtDictionary extends EnPtDictionaryBaseVisitor<Void> {
      @Override
      public Void visitEntry(EnPtDictionaryParser.EntryContext ctx) {
          String enWord = ctx.enWord().getText();
          List<String> ptWords = ctx.ptWord().stream()
                        .map(RuleContext::getText)
                        .toList();
          return super.visitEntry(ctx);
      }
  }

E pronto, agora para cada entrada do dicionário, temos acesso a palavra de origem e a lista de traduções, podemos realizar qualquer processamento necessário não tratado na gramática - como a remoção das vírgulas - e então colocar os resultados em um mapa. A partir deste mapa, um arquivo JSON pode ser criado para servir como base de dados do aplicativo que pode rodar completamente offline.

Para quem chegou até aqui e está se perguntando se o tal aplicativo foi de fato criado, sim, foi, e está sendo extremamente útil nas minhas leituras 📚.

Esse é apenas um exemplo de problema que pode ser resolvido com tecnologias oriundas dos estudos de compiladores. Basta utilizar a sua criatividade.

Isso é tudo pessoal 🐰🥕!

Referências

Parr, T. (2013). Definitive ANTLR 4 Reference (2nd ed.). Pragmatic Programmers.

Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, techniques, and tools (2nd ed.). Pearson.