Analisadores iniciais com PEG.js

PEG ou gramáticas de expressão de análise são semelhantes a CFG (gramáticas livres de contexto) com algumas modificações. Há uma excelente biblioteca chamada PEG.js que vou apresentar aqui; Descobri que ele é um gerador de analisador incrível para a maioria das minhas necessidades de análise de linguagens simples. A coisa mais incrível com PEG.js é que ele permite o uso de javascript embutido, então, em vez de apenas gerar árvores de análise enfadonhas, etc., você pode até mesmo resolver problemas de dentro do analisador.

Eu escrevi um longo post antes de escrever este parágrafo. Era muito técnico e eu o excluí. Espero que esta versão continue. Além disso, este é meu primeiro post aqui, então qualquer feedback seria muito apreciado.

Preparando-se

Em vez de explicar, definir e seguir o caminho certo. Eu recomendo que você passe pelo corredor peg.js online e comece a falar um pouco de gramática.

Você encontrará à esquerda uma área de texto e, só porque deseja seguir minha orientação, exclua todo o texto. Agora você descobrirá que o Peg.js não gostou disso e está nos dando um aviso abaixo da área de texto. Vamos consertar isso. Digitar:

myspecialrule = ""

Isso faria o aviso desaparecer, mas você ainda está recebendo outro aviso com a entrada de teste. Por enquanto, não estamos fazendo nada, então vamos excluir isso também. Adicionaremos nossa entrada de teste mais tarde.

Ok, agora que tínhamos uma lousa limpa, é hora de pensar no que fazer. Para nossa primeira experiência, vamos tentar fazer um contador de palavras simples funcionar.

Minha primeira gramática PEG.js

Aqui está o que queremos: Para a entrada ‘este é meu primeiro post no coderwall’, devemos obter 7 como resultado. Agora eu sei, eu sei, é estupidamente fácil fazer isso em javascript, mas tenha paciência comigo.

Vamos começar com a regra inicial. A primeira regra que PEG.js encontra em seu texto é a regra ‘principal’. Toda a análise começa a partir daí. Então, primeira regra

wordCounter = word*

Agora, se você estiver familiarizado com Expressões regulares, isso se parece muito com elas, mas aqui wordrepresenta outra regra. Para aqueles que não estão familiarizados com as expressões regulares, por favor, leia e aprenda como usá-las, elas são incríveis. Em Expressões regulares, a *significa que o token precedente (digamos, em alguns casos , é o token) pode estar presente 0 ou muitas vezes na string de entrada (0-n). A mudança aqui é que está referenciando outra regra e PEG.js espera que seja definida, então, se você digitar isso, encontrará PEG.js reclamando que não consegue encontrar a regra.a*awordword

Vamos fazer essa regra, então. No momento, não estamos realmente nos importando com a internacionalização, então vamos tornar isso muito simples. (Da última vez que verifiquei, não havia nenhum suporte para internacionalização dentro do PEG.js, mas pode ser feito. Se você quiser ajuda com isso, pode me perguntar ou verificar os exemplos no código- fonte do peg.js )

word = letter+

Novamente, como expressões regulares, estamos usando o +operador. O +operador significa que o token deve estar presente pelo menos uma vez, mas pode ser repetido várias vezes (1 – n). Agora resolvemos o problema da wordregra, mas criamos outra regra letterque não está presente. Se movendo…

letter = [a-zA-Z0-9]

O []operador basicamente significa que qualquer caractere dentro dos colchetes pode ser correspondido. É como um conjunto. Qualquer coisa dentro é compatível. Se você olhar de perto, verá que há uma sintaxe ainda mais funky. Dentro do operador set [], permitiria que PEG.js soubesse (e a maioria dos mecanismos de expressão regular também, já que essa também é uma sintaxe de expressão regular válida) para interpolar os caracteres. Portanto, em resumo, significa literalmente caracteres de a a z .a-za-z

Agora estamos recebendo o sinal verde de que está tudo bem. Vamos adicionar uma entrada de teste. Diga olá’. Esperávamos magicamente obter 1. Infelizmente, não está funcionando assim; em vez disso, Hello foi desmontado e esse é o resultado. Nada de bom.

Vamos adicionar algum javascript embutido aqui para contar as palavras. Já que estamos falando sobre contar palavras, a única regra que sabe quantas palavras são correspondidas é a wordCountregra. Vamos adicionar algum javascript a ele.

Para adicionar javascript, anexe a expressão {}contendo o javascript que você deseja. Então, nós modificamos wordCountpara ser:

wordCount = word* { return 1; }

Então, estamos obtendo o resultado desejado, mas estamos trapaceando. Para contar as palavras, precisamos ser capazes de referenciá-lo dentro do javascript. Para fazer referência a algo, prefixamos com um rótulo como este:

wordCount = w:word* { return 1; }

A sintaxe permite que você acesse o texto real correspondido em seu código javascript. Muito legal né? Agora, para fazer um bom uso.label:

wordCount = w:word* { return w.length; }

Tokens combinados *ou +automaticamente se tornam matrizes javascript dentro do código javascript, o que é ótimo.

Você pode ver que estamos obtendo 1 como resultado. Agradável! No entanto, se adicionarmos mais palavras, você verá que obteremos um erro. Após uma inspeção mais detalhada, você verá que o PEG.js estava esperando a letterregra, mas em vez disso ficou perplexo quando obteve um ” (espaço). Uma vez que as palavras são separadas por espaços, precisamos adicionar isso ao nosso conjunto de regras. Novamente, a única regra que trata de palavras inteiras é wordCountque precisamos modificá-la. Mas antes, precisamos realmente adicionar uma regra que corresponda aos espaços. (Poderíamos ter apenas adicionado “” à wordCountregra, mas, na prática, extrair trechos comuns em regras torna a gramática mais legível)

space = " "

e então precisamos adicioná-lo à wordCountregra. Mas há outro truque surgindo. Se escrevermos,

wordCount = w:word* space { return w.length; }

ele não fará nada além de esperar um espaço após uma palavra. Várias palavras ainda não estão sendo correspondidas. Para corrigir isso, precisamos explicar melhor nossas necessidades ao PEG.js. Não queremos muitas palavras e a entrada deve terminar com um espaço, precisamos de palavras separadas por espaços.

wordCount = w:(word space)* { return w.length; }

Isso nos ajuda na maior parte do caminho, mas ainda estamos vendo um erro. O PEG.js ainda espera que a última palavra seja seguida por um espaço. Não precisamos disso, para consertar:

wordCount = w:(word space?)* { return w.length; }

O ?operador aqui significa que esperamos que a regra spaceesteja presente algumas vezes, e não esteja presente em outras vezes (0-1). Agora, experimente a entrada e você verá que o analisador está funcionando conforme o esperado. Yay!

Um exemplo um pouco mais complexo

Agora que terminamos, vamos tentar fazer algo que seria um pouco mais difícil de fazer com javascript puro. Vamos adicionar um sistema de comando aqui. Digamos que se alguém digitar devemos retornar 2. Mas se alguém disser que devemos retornar o número de letras do texto, neste caso 10 (não 11, não estamos contando espaços). Até agora, lidamos apenas com regras simples para combinar a mesma coisa, mas agora temos que lidar com um sistema muito mais complexo. Aqui está o analisador até agora:wc: Hello worldlc: Hello world

wordCount = w:(word space?)* {return w.length;}
word = letter+
letter = [a-zA-Z0-9]
space = " "

Vamos adicionar uma nova regra de nível superior, que irá analisar a string de entrada, detectar que tipo de operação executar no texto restante e executar essa regra.

textWorks 
  = "wc:" space* wc:wordCount { return wc; }
  / "lc:" space* lc:letterCount { return lc; }

Sempre que trabalho com analisadores, gosto de gerar as regras mais importantes primeiro, para ter uma ideia de como tudo se conecta. A única coisa nova na sintaxe acima é o uso do /operador. Pense no /operador como um ORoperador. Se o analisador não puder corresponder à primeira opção, ele examinará a próxima opção e assim por diante até encontrar a primeira opção que corresponda, ou nenhuma, caso em que volta para a regra pai e repete. Se todas as rotas se esgotarem e a string de entrada não corresponder totalmente, ela retorna e informa onde falhou. Portanto, neste caso, se iniciarmos um texto de entrada com ‘pc:’, o analisador falhará. Vamos fazer a letterCountseguir.

letterCount = w:(iw:word space? {return iw;})* {
   var total = 0;
   for (var i = 0; i < w.length; i++) {
       total += w[i].length;
   }
   return total;
 }

Agora, isso é um pouco mais complexo, mas o que está essencialmente fazendo é

• Dentro ()se houver mais do que um símbolo, PEG.js converte-lo em uma matriz de resultados, no entanto, cada um ()pode ter sua própria javascript in-line, então eu usei isso para apenas retornar o resultado da wordregra, ignorando texto correspondente da regra espaço.
• iterando pelas palavras combinadas, continuamos contando as letras em cada palavra e retornamos o total

Isso funciona porque definimos wordcomo qual, por padrão, retorna uma matriz de letras correspondentes.letter+

Agora, experimente. Você verá que, ao digitar ‘wc: Hello World’, ele retorna 2 e altera ‘wc’ para ‘lc’ e você obtém 10.

Ainda há muitas coisas que não abordei aqui, mas espero ter dado uma ideia sobre o poder do PEG.js e como começar a usá-lo. Você pode baixar o analisador resultante da versão online após terminar de criá-lo. Você também pode baixá-lo usando se tiver o nó. Você também pode executar o analisador no navegador em tempo de execução, mas acho que tem usos limitados. Apenas pré-compile o analisador para melhor desempenho, a menos que você planeje gerar dinamicamente a própria gramática.npm install -g pegjs

Links

PEG.js
PEG.js Versão Online
PEG.js Documentação
Projeto Github

PEG.js é desenvolvido por David Majda (@dmajda).