![Análise sintática MQL via ferramentas MQL](https://c.mql5.com/i/articles/overlay.png)
Análise sintática MQL via ferramentas MQL
Introdução
Basicamente, a programação consiste na criação e automação de certos processos usando linguagens gerais ou especiais. Graças à sua linguagem MQL embutida, a plataforma de negociação MetaTrader permite implementar programação para resolver as mais diversas tarefas do trader. Normalmente, o processo de programação se baseia na análise e no processamento de dados de aplicativos segundo regras já estabelecidas em códigos fonte. No entanto, às vezes, é necessário analisar e processar esses mesmos códigos fonte. Aqui estão alguns exemplos:
Uma das tarefas mais procuradas e fáceis de entender é a da pesquisa contextual em bases de códigos-fonte. Naturalmente, pode-se procurar no código fonte tanto strings como texto sem formatação, não entanto, ao fazer isso, perde-se a semântica da pesquisa. Além disso, no caso de códigos fonte, é bom distinguir as especificidades do uso de substrings. Se um programador quiser descobrir onde se usa uma determinada variável, por exemplo, "notification", uma busca simples pelo nome pode dar dados a mais se a string for encontrada em outros valores, como no nome de método, no literal ou no comentário.
Quanto a grandes projetos, normalmente, uma das tarefas mais complexas e populares é a da visualização de estruturas de código, de dependências e de hierarquia de classes. Esse trabalho está intimamente relacionado à meta-programação permitindo refatoração (aprimoramento) e geração de código. Lembre que o MetaEditor possui alguns recursos de geração de código, em particular, a criação de códigos fonte especializados usando Assistentes ou a geração de arquivos de cabeçalho de código fonte. No entanto, o potencial dessa tecnologia é muito mais amplo.
A análise da estrutura do código permite calcular várias métricas de qualidade, estatísticas e também encontrar fontes típicas de erros de tempo de execução que o compilador não pode detectar. Na verdade, é claro que o próprio compilador é a primeira ferramenta de análise de código fonte e fornece muitos tipos de avisos, mas a verificação de todos os possíveis erros geralmente não é incorporada a ele, uma vez que isso é uma tarefa muito grande e, portanto, é atribuído a programas individuais.
Além disso, a análise do código fonte é usada para formatação e ofuscação.
Para linguagens de programação industrial, existem muitas ferramentas que realizam as tarefas mencionadas acima. No caso de MQL, a escolha é limitada. Seria possível tentar realizar uma análise MQL com as ferramentas disponíveis, mas, ajustadas para que MQL fique com se fosse C++. Isso funciona de maneira muito simples no caso de algumas ferramentas, como Doxygen, porém, requer uma adaptação mais profunda para ferramentas mais poderosas, semelhantes com o lint, já que MQL não é C++.
Adicionalmente, observe que este artigo trata apenas da análise estática de código. Também há analisadores dinâmicos que permitem rastrear erros de memória, bloqueio de threads, correção de variáveis e muito mais em ambientes virtuais em tempo real.
Para análise estática do código fonte, você pode usar diferentes abordagens. No caso de tarefas simples, por exemplo, ao pesquisar variáveis de entrada de um programa MQL, basta usar a biblioteca de expressões regulares. De uma forma mais geral, a análise deve ser construída com base num analisador considerando a gramática da linguagem MQL. Neste artigo, vamos estudar essa abordagem e tentar colocá-la em prática.
Em outras palavras, vamos escrever um analisador MQL em linguaguem MQL e obter metadados de códigos fonte. Isso não só vai resolver os problemas mencionados acima, mas também vai abrir outras possibilidades fantásticas no futuro. Assim, tendo um analisador totalmente certo, podemos fazer - baseado nele - um interpretador MQL ou converter automaticamente MQL para outras linguagens de trading ou vice-versa (transpilação). Eu não estou usando a palavra "fantásticas", acidentalmente. Embora todas essas tecnologias já sejam amplamente utilizadas em outras áreas, para se aproximar delas na plataforma MetaTrader, você deve primeiro entender o básico.
Visão Geral da Técnica
Existem diversos analisadores. Não entraremos em detalhes técnicos — informações introdutórias podem ser encontradas em Wikipedia, enquanto, para um estudo mais aprofundado, existe enorme quantidade de recursos.
Apenas notemos que o analisador funciona com base na gramática que descreve uma linguagem. Uma das formas mais comuns de descrever gramáticas é a de Backus-Naur (BNF). Existem tantas modificações na BNF que vamos considerar apenas os pontos principais.
Na BNF, todos os constructos de composição da linguagem são denotados pelos não-terminais, enquanto as entidades indivisíveis por terminais. A palavra "terminal" aqui é o ponto final na análise sintática do texto, isto é, um tipo de token contendo um trecho do código fonte "tal qual" e interpretado em sua totalidade. Ela pode ser, por exemplo, uma vírgula, um colchete ou uma única palavra. Definimos a lista de terminais (alfabeto) dentro da gramática. Todas as outras partes do programa são compiladas a partir de terminais, de acordo com certas regras.
Por exemplo, numa notação BNF simplificada, pode-se especificar que um programa consiste em operadores, da seguinte maneira:
program ::= operator more_operators
more_operators ::= program | {vazio}
Aqui se fala de que um não-terminal program pode consistir num ou mais operadores, além disso, os seguintes operadores são descritos com uma referência recursiva ao programa. O caractere '|' (sem aspas na BNF) significa OU lógico — seleção de uma das opções. Para completar a recursividade na entrada introduzida, é usado um terminal especial {vazio}. Ele pode ser representado como uma string vazia ou como a capacidade de ignorar uma regra.
O caractere do operador também é um não-terminal e requer "expansão" através de outros não-terminais e terminais, por exemplo, assim:
operator ::= name '=' expression ';'
Essa entrada especifica que cada operador deve começar com o nome da variável, depois vem o caractere '=', alguma expressão e a instrução é finalizada com o caractere ';'. Caracteres '=' e ';' são terminais. O nome é composto por letras:
name ::= letter more_letters more_letters ::= name | {vazio} letter ::= [A-Z]
Aqui, como letra é permitido usar qualquer caractere de 'A' a 'Z' (seu conjunto é indicado por colchetes).
Assumamos que a expressão é construida a partir de operandos e de operações aritméticas:
expression ::= operand more_operands more_operands ::= operation expression | {vazio}
No caso mais simples, a expressão é um único operando, mas pode haver mais (more_operands), em cujo caso, eles se juntam a ele através do símbolo de operação como uma subexpressão. Suponhamos que os operandos sejam referências a variáveis ou números, enquanto as operações, '+' ou '-':
operand ::= name | number number ::= digit more_digits more_digits ::= number | {vazio} digit ::= [0-9] operation ::= '+' | '-'
Assim, descrevemos a gramática de uma linguagem simples na qual se pode realizar cálculos de números e variáveis, por exemplo:
A = 10; X = A - 5;
Quando começamos a analisar o texto, verificamos quais regras é que funcionam. Regras acionadas devem ter certo "produto" mais cedo ou mais tarde, isto é, detectar um terminal que corresponda ao conteúdo na posição atual no texto, enquanto o cursor se move para a próxima posição. Esse processo é repetido até que todo o texto seja enquadrado de acordo com os não-terminais, formando a sequência permitida pela gramática.
No exemplo acima, o analisador, com o caractere 'A' na entrada, começa a seguir as regras na seguinte ordem:
program operator nome letter 'A'
Até encontrar a primeira correspondência, o cursor se move para o próximo caractere '='. Como letter é uma letra, o analisador retorna à regra de nome. E como name pode ser composto apenas por letras, a alternativa more_letters não funciona (é escolhida como {vazio}) e o analisador retorna à regra de operator, onde o terminal ao lado do nome é '='. Esta é a segunda correspondência. Em seguida, expandindo a regra expression, o analisador localiza o operando — o inteiro 10 (como uma sequência de dois dígitos) — e, finalmente, o ponto e vírgula completa a análise da primeira string. De acordo com seus resultados, ficamos sabendo o nome da variável, o conteúdo da expressão - ou seja, que consiste num número - e seu valor. A segunda string é analisada de maneira semelhante.
É importante notar que a gramática de uma mesma língua pode ser escrita de diferentes maneiras, e formalmente elas correspondem uma à outra, mas se forem literalmente seguidas as regras, podem surgir problemas em alguns casos. Por exemplo, a descrição de um número pode ser representada da seguinte maneira:
number ::= number digit | {vazio}
Esta forma de escrita é chamada de recursividade à esquerda - o number não-terminal está tanto na parte esquerda como na direita, que define as regras de seu "produto", e ele vai primeiro à esquerda, na string (daí o nome recursividade à esquerda). Esta é a recursão mais simples e explícita. Mas ela pode ser implícita, se o não-terminal for revelado através de várias regras intermediárias numa string começando a partir dele.
A recursividade à esquerda é frequentemente encontrada em notações BNF, no entanto, alguns tipos de analisadores (dependendo da versão) podem se concentrar nessas regras. De fato, se considerarmos a regra como um roteiro de ação (algoritmo de análise), esse registro de dados repetidamente será inserido em number e não lerá novos terminais do fluxo de entrada, o que, em teoria, tem que acontecer ao abrir o não-terminal digit.
Como tentaremos criar uma gramática MQL não a partir do zero, mas, sim, usando, se possível, a notação BNF da gramática C++, precisaremos prestar atenção às recursões piratas e reescrever as regras de maneira alternativa. Ao mesmo tempo, será necessário implementar proteção contra looping — como veremos mais adiante, a gramática de linguagens de C++ ou de MQL são tão ramificadas que não é possível verificar manualmente se elas estão corretas.
É bom observar aqui que a escrita de analisadores é uma ciência completa, e é apropriado começar a dominar essa área gradualmente, do simples ao complexo. O mais simples é o analisador sintático descendente recursivo. Ele considera o texto de entrada como um número inteiro que corresponde ao não-terminal inicial da gramática. No exemplo acima, era um não-terminal program. Segundo uma regra adequada, o analisador verifica que a sequência de caracteres de entrada coincide com a do terminal e avança ao longo do texto se encontra correspondências. Se, em algum momento, o analisador encontrar uma discrepância, ele retornará às regras nas quais foi especificada a alternativa e, portanto, verificará todas os possíveis constructos de linguagem. Este algoritmo repete completamente as ações que nós realizamos de maneira abstrata no exemplo acima.
A operação de reversão é chamada de 'backtracking' em inglês e pode afetar adversamente a velocidade. Portanto, o analisador sintático descendente recursivo, no pior dos casos, gera um número exponencialmente crescente de alternativas ao examinar o texto. Para resolver este problema, existem modificações, em particular, um analisador preditivo que não requer 'backtracking'. Seu tempo de execução é linear.
Isso, no entanto, só é possível para gramáticas, para as quais, para um determinado número dos caracteres k seguintes, pode-se escolher sem ambiguidade a regra de "produto". Esses analisadores mais avançados se baseiam em tabelas de saltos especiais, calculadas previamente usando todas as regras gramaticais. Entre eles estão, por exemplo, o analisador sintático LL e analisador sintático LR (embora a lista não esteja limitada a eles).
LL significa Left-to-right, Leftmost derivation, isto é, o texto é visto da esquerda para a direita e as regras também são vistas da esquerda para a direita, do geral para o particular, e neste sentido, LL é um parente do nosso analisador sintático descendente.
LR significa Left-to-right, Rightmost derivation, ou seja, o texto é visto da esquerda para a direita, como antes, o que equivale a um constructo ascendente de linguagem — de caracteres únicos para não-terminais maiores. Na verdade, LR tem menos problemas com recursão à esquerda.
Os nomes dos analisadores LL(k) e LR(k) geralmente indicam o número de caracteres k, para o qual eles examinam o texto para frente e, na maioria dos casos, é suficiente escolher k = 1. Mas essa suficiência é muito condicional. Na verdade, muitas linguagens modernas de programação, incluindo C++ e MQL, não são linguagens com gramática livre de contexto. Em outras palavras, os mesmos fragmentos de texto podem ser interpretados de forma diferente, dependendo do contexto. Nesses casos, para decidir sobre o significado do que está escrito, é necessário vincular o analisador a outras ferramentas, por exemplo, a um pré-processador ou a uma tabela de nomes (uma lista de identificadores já reconhecidos e seu significado), porque um pequeno número de caracteres é insuficiente para saber isso.
Para C++, existe um caso simples de ambiguidade (também é adequado para MQL). O que significa a expressão abaixo?
x * y;
Esta pode ser o produto das variáveis x e y, ou pode ser a descrição da variável y como um ponteiro do tipo x. Não se preocupe com o fato de que o resultado da multiplicação, se for o caso, não é salvo em nenhum lugar, porque a operação de multiplicação pode ser sobrecarregada e ter efeitos colaterais.
Outro problema que a maioria dos compiladores de C++ sofreu no passado foi o da ambiguidade na interpretação de dois caracteres '>' consecutivos. Acontece que, após a introdução de modelos, nos códigos fonte começaram a aparecer constructos do tipo:
vector<pair<int,int>> v;
A sequência '>>' foi inicialmente definida como um operador de deslocamento. Algum tempo, antes terem sido refinados tais casos específicos em compiladores, essas expressões tinham que ser escritas usando o caractere de espaço em branco:
vector<pair<int,int> > v;
Nós em nosso analisador também precisamos contornar este problema.
Em geral, mesmo com essa breve introdução, certamente começa a ficar claro que a descrição e a implementação de analisadores avançados exigem grande esforço, tanto em termos de apresentação quanto de tempo para dominá-los. Por isso, neste artigo, vamos nos limitar ao analisador mais simples, o analisador descendente recursivo.Planejamento
A tarefa do analisador é ler o texto de entrada, dividi-lo num fluxo de fragmentos indivisíveis (tokens) e depois compará-los com os constructos de linguagem permitidos, descritos usando gramática MQL na notação BNF ou numa notação próxima a ela.
Primeiro, precisamos de uma classe que leia arquivos, nós a chamamos de FileReader. Como um projeto MQL pode consistir em vários arquivos conectados a partir do diretório principal através da diretiva #include, podem ser necessárias muitas instâncias da FileReader, e a fim de gerenciá-las, definimos outra classe FileReaderController.
O texto dos arquivos processados é uma string regular. No entanto, precisamos passá-la entre diferentes classes, e, infelizmente, a MQL não permite ponteiros para strings (não esqueça que as references não podem ser usadas ao declarar membros de classe, portanto, é pouco conveniente encaminhar uma referência para todos os métodos através de parâmetros de entrada, o que é nossa única alternativa). Sendo assim, criamos uma classe Source separada que é um wrapper para a string. Ela executa outra função importante.
Acontece que, ao conectar os include (e, como resultado, a leitura recursiva de arquivos de cabeçalho a partir de dependências), recebemos o texto combinado de todos os arquivos na saída do controlador. A fim de diagnosticar erros, para o deslocamento no código fonte combinado precisamos obter o nome e a linha do arquivo original, de onde o texto foi retirado. Este "mapa" de colocação de códigos fonte em arquivos também é mantido e armazenado pela classe Source.
Aqui é pertinente perguntar: será que era possível processar cada arquivo separadamente, em vez de combinar os códigos fonte? Sim, provavelmente seja mais correto fazer isso, mas seria necessário que cada arquivo criasse sua própria instância de analisador e, de algum modo, costurasse as árvores de sintaxe que o analisador gera na saída. Por tal razão, decidi combinar os códigos fonte e enviar para um único analisador. Os interessados podem experimentar uma abordagem alternativa.
Para que o FileReaderController encontre as diretivas #include, também é preciso fazer uma visualização prévia procurando essas diretivas. Assim, é necessário algum tipo de pré-processador. Em MQL, ele realiza outras coisas úteis, em particular, permite definir macros e, em seguida, substituí-las por expressões reais (além disso, leva em conta a potencial recursão de uma chamada de macro a partir de outra macro). Porém, no nosso primeiro analisador MQL, é melhor não começar a fazer todas as tarefas de uma só vez. Portanto, não processamos macros em nosso pré-processador, uma vez que isso exige descrever uma macro-gramática adicional, interpretá-la rapidamente para ter expressões corretas e substituir no código fonte. Você se lembra de termos falado sobre o intérprete na introdução? Pois bem, aqui ele já é necessário, mais para frente ficaremos sabendo por que razão é importante. Esta é a orientação número 2 para experimentos independentes.
Implementamos o pré-processador na classe Preprocessor. No seu nível, acontece um processo algo contraditório. Ao ler arquivos e buscar diretivas #include, a análise e o avanço no texto são executados no menor nível, quer dizer, caractere por caractere, mas o pré-processador omite tudo que não é uma diretiva e, na saída, usa os maiores blocos, isto é, arquivos inteiros ou fragmentos de arquivos entre diretivas. Mas, a seguir, a análise vai para um certo nível médio, para cuja descrição precisamos inserir um par de termos.
Em primeiro lugar, trata-se de um lexema, isto é, uma unidade mínima abstrata de análise léxica, uma subsequência de comprimento diferente de zero. Além dele, muitas vezes, é usado o termo token, que também é uma unidade de análise, que não é abstrata, mas, sim, específica. Ele é um fragmento de texto (por exemplo, um caractere, palavra ou até mesmo um bloco de comentários). A sutil diferença entre eles está no fato de, no nível dos tokens, marcarmos os fragmentos com significado. Por exemplo, se o texto contiver a palavra "int", ela é um lexema, para MQL, que denotamos pelo token INT, como um elemento na enumeração de todos os tokens MQL válidos. Em outras palavras, o conjunto de lexemas pode ser entendido como um dicionário de strings que corresponde aos tipos de tokens.
Uma das vantagens dos tokens é que eles permitem dividir o texto em fragmentos maiores do que caracteres. Como resultado, o texto é analisado em dois passos: primeiro, os tokens de nível superior são formados a partir do fluxo de letras e, em sua base, são analisados os constructos da linguagem. Isso permite simplificar significativamente a gramática da linguagem e o trabalho do analisador.
A classe especial Scanner seleciona os tokens no texto. Ela pode ser considerada como um analisador de baixo nível com uma gramática predefinida que processa o texto por letras. Abaixo consideramos os tipos de tokens que precisamos. Caso alguém queira fazer o experimento número 1 (com o carregamento de cada arquivo em analisador selecionado), pode-se combinar o pré-processador com o scanner e, ao encontrar o token "#include <algo>", criar um novo FileReader, um novo scanner, e transferir o controle para eles.
Todas as palavras-chave (reservadas), bem como a pontuação e os operações são tokens MQL. A lista completa de palavras-chave MQL está incluída no arquivo reserved.txt e está anexada ao código fonte do scanner.
Identificadores, números, strings, literais e outras constantes (por exemplo, datas) também são tokens independentes.
Ao analisar texto em tokens, todos os espaços, quebras de linha, tabulações são suprimidos (ignorados). A única exceção deve ser feita para quebras de linha, uma vez que isso permite indicar strings com erros.
Assim, ao enviar o texto combinado para a entrada do scanner, obtemos uma lista de tokens na saída. É essa lista de tokens que é processada pelo analisador, que implementamos na classe Parser.
Para interpretar os tokens de acordo com as regras da linguagem MQL, é necessário transferir a gramática na notação BNF para o analisador. Para descrevermos a gramática, tentamos de maneira simplificada repetir a abordagem usada pelo analisador boost::spirit. O que importa é descrever as regras da gramática usando expressões da linguagem MQL graças à sobrecarga de alguns operadores.
Para fazer isso, introduzimos uma hierarquia de classes Terminal, NonTerminal, e classes derivadas delas. Terminal é a classe base, que, por padrão, corresponde a um único token. Como foi dito na parte teórica, um terminal é um elemento final e indivisível para analisar regras: caso, na posição atual do texto, exista um caractere que corresponde ao token do terminal, o símbolo corresponde à gramática, e ele pode ser lido e avançar.
Usamos NonTerminal para constructos de composição, que podem usar terminais e outros não-terminais em diferentes combinações. Vejamos um exemplo.
Suponhamos que precisemos descrever uma gramática simples para avaliar expressões nas quais são implementados somente números inteiros e operações mais '+' e multiplicação '*'. Por simplicidade, nos limitamos ao caso quando há apenas dois operandos, por exemplo, 10+1 ou 5*6.
Assim, é necessário, em primeiro lugar, determinar o terminal correspondente ao número inteiro. É esse terminal que é combinado com qualquer operando válido na expressão. Como o scanner produz a cada vez que encontra no texto um inteiro que corresponde ao token CONST_INTEGER, definimos um objeto de classe Terminal fazendo referência a esse token. No pseudocódigo isso é:
Terminal value = CONST_INTEGER;
Este registro significa que criamos o objeto value da classe Terminal, que é associado ao token número inteiro.
Os terminais com os correspondentes tokens PLUS e STAR gerados pelo scanner para caracteres simples '+' e '*' também são símbolos de operação:
Terminal plus = PLUS; Terminal star = STAR;
Para usar qualquer um deles na expressão, introduzimos um não-terminal que combina duas operações usando Boolean:
NonTerminal operation = plus | star;
Aqui entra em ação a sobrecarga de operador: na classe Terminal (e em todos os herdeiros) operator| deve criar referências do objeto pai (neste caso, operation) para os filhos (plus e star), e marcar o tipo de operação — tipo de dados Boolean.
Quando o analisador verifica se operation não-terminal corresponde com o texto sob o cursor, ele delega ao objeto operation uma verificação adicional ("em profundidade") e este chama no ciclo uma verificação para os elementos filho plus e star (até a primeira correspondência, pois é Boolean). Como eles são terminais, eles simplesmente retornam seus tokens para o analisador e este determina se o caractere no texto corresponde a uma das operações.
Como a expressão pode consistir em vários valores e operações entre eles, ela deve ser "descerrada" por meio de terminais e de não-terminais.
NonTerminal expression = value + operation + value;
Aqui sobrecarregamos operator+, o que significa que os operandos devem seguir um ao outro na ordem especificada. Novamente, a implementação da função implica que, no não-terminal pai, expression deve preservar as referências aos objetos filhos value, operation e outro value, além disso, o tipo de operação é AND. De fato, nesse caso, a regra deve ser executada apenas se todos os componentes estiverem presentes.
Primeiro, o analisador verifica se o expressão é certa e corresponde e, dessa maneira, faz com que seja chamada a verificação no array de referências expression, em seguida, nos objetos value, operation (que usam recursivamente plus e minus) e finalmente, novamente no objeto value. Em qualquer etapa, caso a verificação desça até ao nível do terminal, o valor do token é comparado com o caractere atual no texto e, caso haja correspondência, o cursor se move para o próximo token, de outro modo, é preciso procurar uma alternativa. Por exemplo, neste caso, se a verificação de operação plus falhar, ela continuará com star. As regras gramaticais são violadas se todas as opções tiverem sido esgotadas e a correspondência não tiver sido encontrada.
Apesar de os operadores '|' e '+' não serem todos operadores que sobrecarregamos em nossas classes, vamos descrevê-los completamente na seção de implementação.
A declaração de objetos da classe Terminal e seus derivados, contendo referências a outras entidades, menores e menores, formam a árvore de sintaxe abstrata (AST) de uma determinada gramática. Ela é abstrata porque não se liga a tokens específicos do texto de entrada, ou seja, em teoria, a gramática descreve um número infinito de strings válidas, no nosso caso, códigos MQL.
Assim, delineamos as principais classes do projeto. Para ter uma visão geral, nós as reduzimos ao diagrama de classes UML.
Diagrama UML de classes de análise sintática MQL
Algumas classes não foram consideradas, em particular, TreeNode. Seus objetos são usados pelo analisador no processo de análise de texto de entrada, para manter todas as correspondências encontradas terminal=token. Como resultado, na saída obtemos a árvore de sintaxe concreta (CST), na qual todos os tokens são hierarquicamente incluídos nos terminais e não-terminais da gramática.
Em princípio, criar uma árvore é opcional, pois para códigos fonte reais pode ser muito grande. Em vez de obter os resultados do analisador na forma de uma árvore, consideramos uma interface de retorno de chamada (Callback). Uma vez criado nosso próprio objeto implementando esta interface, nós o transferimos para o analisador para receber notificações sobre cada "produto" concluído. Assim, podemos analisar a sintaxe e a semântica em tempo real, sem esperar pela árvore completa.
Classes de não-terminais com o prefixo Hidden são usadas para criar implícita e automaticamente grupos intermediários de objetos gramaticais, os quais discutiremos com mais detalhes na próxima seção.
Implementação
Lendo arquivos
Source
A classe Source é, antes de tudo, um repositório de uma string com texto processado. Sua base é a seguinte:
#define SOURCE_LENGTH 100000 class Source { private: string source; public: Source(const uint length = SOURCE_LENGTH) { StringInit(source, length); } Source *operator+=(const string &x) { source += x; return &this; } Source *operator+=(const ushort x) { source += ShortToString(x); return &this; } ushort operator[](uint i) const { return source[i]; } string get(uint start = 0, uint length = -1) const { return StringSubstr(source, start, length); } uint length() const { return StringLen(source); } };
A classe possui uma variável source para o texto, bem como operadores sobrepostos para as operações mais frequentes com strings. Por enquanto, relegamos o segundo papel desta classe (manter a lista de arquivos a partir dos quais é montada a string armazenada). Tendo esse "wrapper" para o texto de entrada, pode-se tentar preenchê-lo a partir de um arquivo. A classe FileReader é responsável por esta tarefa.
FileReader
Antes de começar a programar, é preciso determinar como abrir e ler o arquivo. Como estamos processando o texto, é lógico escolher o modo FILE_TXT. Isso nos libra de controlar manualmente os caracteres de quebra de linha, que, aliás, podem ser codificados diferentemente por diferentes editores (geralmente são um par de caracteres CR LF, mas em códigos fonte MQL públicos também existem alternativas, nomeadamente CR ou LF). Lembre-se de que, no modo de texto, a leitura de arquivos é feita linha a linha.
Outro problema a considerar é o suporte a textos em diferentes codificações. Como queremos ler arquivos diferentes, que podem ser salvos como ANSI e alguns como UNICODE, é aconselhável atribuir ao próprio sistema a seleção correta em termo real (de arquivo para arquivo). Além disso, os arquivos podem ser salvos como UTF-8.
Como se viu, o MQL pode ler automaticamente vários arquivos de texto na codificação adequada, se forem definidos os seguintes parâmetros de entrada da função FileOpen:
FileOpen(filename, FILE_READ | FILE_TXT | FILE_ANSI, 0, CP_UTF8);
Para frente, aplicamos mais essa combinação, adicionando, por padrão, os sinalizadores FILE_SHARE_READ | FILE_SHARE_WRITE.
Na classe FileReader, fornecemos membros para armazenar o nome do arquivo (filename), o identificador de arquivo aberto (handle), a linha de texto atual (line).
class FileReader { protected: const string filename; int handle; string line;
Além disso, rastreamos o número da linha atual e a posição do cursor na linha (coluna).
int linenumber; int cursor;
Mantemos as linhas lidas numa instância do objeto Source.
Source *text;
No construtor, fornecemos o nome do arquivo, os sinalizadores e o objeto Source pronto para receber dados.
public: FileReader(const string _filename, Source *container = NULL, const int flags = FILE_READ | FILE_TXT | FILE_ANSI | FILE_SHARE_READ | FILE_SHARE_WRITE, const uint codepage = CP_UTF8): filename(_filename) { handle = FileOpen(filename, flags, 0, codepage); if(handle == INVALID_HANDLE) { Print("FileOpen failed ", _filename, " ", GetLastError()); } line = NULL; cursor = 0; linenumber = 0; text = container; } string pathname() const { return filename; }
Verificamos a abertura bem-sucedida do arquivo e fechamos o identificador de arquivo no destruidor.
bool isOK() { return (handle > 0); } ~FileReader() { FileClose(handle); }
A leitura caractere por caractere a partir do arquivo é fornecida pelo método getChar.
ushort getChar(const bool autonextline = true) { if(cursor >= StringLen(line)) { if(autonextline) { if(!scanLine()) return 0; cursor = 0; } else { return 0; } } return StringGetCharacter(line, cursor++); }
Quando uma string com o texto line está vazia ou é lida até o final, esse método tenta ler a próxima string usando o método scanLine. Se ainda houver caracteres sem tratamento na string line, getChar simplesmente retorna o caractere sob o cursor e move o cursor para a próxima posição.
O método scanLine é definido da maneira óbvia:
bool scanLine() { if(!FileIsEnding(handle)) { line = FileReadString(handle); linenumber++; cursor = 0; if(text != NULL) { text += line; text += '\n'; } return true; } return false; }
Observe que, como o arquivo está aberto no modo de texto, as quebras de linha não são retornadas, no entanto, elas são necessárias para contagem de linhas e como sinais finais de alguns constructos de linguagem, por exemplo, comentários de linha única. Por isso, adicionamos o caractere '\n'.
Além da leitura de dados a partir do arquivo, a classe FileReader deve permitir comparar os dados de entrada sob o cursor com os lexemas. Para fazer isso, adicionamos os seguintes métodos.
bool probe(const string lexeme) const { return StringFind(line, lexeme, cursor) == cursor; } bool match(const string lexeme) const { ushort c = StringGetCharacter(line, cursor + StringLen(lexeme)); return probe(lexeme) && (c == ' ' || c == '\t' || c == 0); } bool consume(const string lexeme) { if(match(lexeme)) { advance(StringLen(lexeme)); return true; } return false; } void advance(const int next) { cursor += next; if(cursor > StringLen(line)) { error(StringFormat("line is out of bounds [%d+%d]", cursor, next)); } }
O método probe compara o texto com o lexema transmitido. O método match faz quase o mesmo, porém, ele também verifica se o lexema é mencionado como uma palavra separada, ou seja, com um separador a seguir (espaço, tabulação ou fim de linha). O método consume "absorve" a palavra-lexema transferida, ou seja, certifica-se de que o texto de entrada corresponde ao especificado e, se for bem-sucedido, move o cursor para além do final do lexema. Em caso de falha, o cursor não se move e o método retorna false. O método advance simplesmente move o cursor para frente um número especificado de caracteres.
Por fim, consideramos um método pequeno que retorna o sinal de final de arquivo.
bool isEOF() { return FileIsEnding(handle) && cursor >= StringLen(line); }
Na classe existem outros métodos auxiliares para ler os campos, eles podem ser encontrados nos códigos fonte anexados.
Os objetos da classe FileReader devem ser criados em algum lugar. Delegamos essa função à classe FileReaderController.FileReaderController
Na classe FileReaderController, é necessário manter a pilha de arquivos incluídos (includes), o mapa de arquivos já incluídos (files), o ponteiro para o arquivo atual processado (current) e também o texto de entrada (source).
class FileReaderController { protected: Stack<FileReader *> includes; Map<string, FileReader *> files; FileReader *current; const int flags; const uint codepage; ushort lastChar; Source *source;
Listas, pilhas, arrays como BaseArray e mapas Map encontrados nos códigos fonte são conectados a partir de arquivos de cabeçalho auxiliares (não descritos aqui, pois já foram usados em meus artigos anteriores). No entanto, o arquivo completo está anexado a este artigo.
O controlador cria um objeto vazio source em seu construtor:
public: FileReaderController(const int _flags = FILE_READ | FILE_TXT | FILE_ANSI | FILE_SHARE_READ | FILE_SHARE_WRITE, const uint _codepage = CP_UTF8, const uint _length = SOURCE_LENGTH): flags(_flags), codepage(_codepage) { current = NULL; lastChar = 0; source = new Source(_length); }
No destruidor acontece a liberação de source e, ao mesmo tempo, dos objetos FileReader subordinados do mapa:
#define CLEAR(P) if(CheckPointer(P) == POINTER_DYNAMIC) delete P; ~FileReaderController() { for(int i = 0; i < files.getSize(); i++) { CLEAR(files[i]); } delete source; }
Para inserir um arquivo no processamento, incluindo o primeiro arquivo de projeto com a extensão mq5, fornecemos o método include.
bool include(const string _filename) { Print((current != NULL ? "Including " : "Processing "), _filename); if(files.containsKey(_filename)) return true; if(current != NULL) { includes.push(current); } current = new FileReader(_filename, source, flags, codepage); source.mark(source.length(), current.pathname()); files.put(_filename, current); return current.isOK(); }
Ele, além do mapa files, verifica se já foi processado o arquivo especificado, e, imediatamente, retorna true se o arquivo existir. Caso contrário, o processo continua. Se este é o primeiro arquivo, criamos um objeto FileReader, atualizamo-lo (current) e mandamos no mapa files. Se este não for o primeiro arquivo, ou seja, se algum arquivo estiver sendo processado, será necessário primeiro salvá-lo na pilha includes. Quando o arquivo incluído for completamente processado, retornaremos ao processamento do arquivo atual a partir do mesmo local onde o arquivo incluído estava conectado.
Por agora, no método include, uma string não vai ser compilada:
source.mark(source.length(), current.pathname());
Ainda não existe um método mark na classe source. Neste lugar, alternamos de um arquivo para outro, e, portanto, devemos marcar em algum sitio a origem e o deslocamento no texto combinado. O método mark toma conta disso. A qualquer momento, o comprimento atual do texto de entrada é o local aonde são adicionados os dados do novo arquivo. Voltamos para a classe Source e adicionamos o mapa de arquivos:
class Source { private: Map<uint,string> files; public: void mark(const uint offset, const string file) { files.put(offset, file); }
O método getChar (que delega parte do trabalho ao objeto FileReader atual) se encarrega de ler os caracteres a partir do arquivo na classe FileReaderController.
ushort getChar(const bool autonextline = true) { if(current == NULL) return 0; if(!current.isEOF()) { lastChar = current.getChar(autonextline); return lastChar; } else { while(includes.size() > 0) { current = includes.pop(); source.mark(source.length(), current.pathname()); if(!current.isEOF()) { lastChar = current.getChar(); return lastChar; } } } return 0; }
Caso o arquivo atual esteja presente e não seja lido até o final, chamamos seu método getChar e retornamos o caractere resultante. Caso o arquivo atual seja lido até o final, verificamos se há alguma diretiva para incluir outros arquivos na pilha includes. Caso existam arquivos, extraímos o superior, fazemos com que seja o atual (current) e continuamos a ler os caracteres a partir dele. Além disso, não nos esquecemos de marcar no objeto source, que a fonte de dados foi alternada para o arquivo antigo.
A classe FileReaderController também sabe como retornar um sinal de que a leitura chegou ao fim.
bool isAtEnd() { return current == NULL || (current.isEOF() && includes.size() == 0); }
Entre outras coisas, fornecemos alguns métodos para obter o arquivo e o texto atuais.
const Source *text() const { return source; } FileReader *reader() { return current; }
Agora tudo está pronto para o pré-processador trabalhar com os arquivos.
Preprocessor
O pré-processador gerencia a única instância da classe FileReaderController (controller), bem como a decisão de carregar os arquivos de cabeçalho (sinalizador loadIncludes):
class Preprocessor { protected: FileReaderController *controller; const string includes; bool loadIncludes;
Acontece que podemos querer processar alguns arquivos sem dependências, por exemplo, para depurar ou reduzir o tempo de trabalho. Na variável de string includes, armazenamos a pasta na qual estão os arquivos de cabeçalho padrão.
O construtor recebe todos esses valores, assim como o nome do arquivo inicial (junto com o caminho) do usuário, cria um controlador e chama o método include para o arquivo.
public: Preprocessor(const string _filename, const string _includes, const bool _loadIncludes = false, const int _flags = FILE_READ | FILE_TXT | FILE_ANSI | FILE_SHARE_READ | FILE_SHARE_WRITE, const uint _codepage = CP_UTF8, const uint _length = SOURCE_LENGTH): includes(_includes) { controller = new FileReaderController(_flags, _codepage, _length); controller.include(_filename); loadIncludes = _loadIncludes; }
Agora vamos escrever o método run, que é chamado pelo cliente diretamente para iniciar o processamento de um ou vários arquivos.
bool run() { while(!controller.isAtEnd()) { if(!scanLexeme()) return false; } return true; }
Até que o controlador pare no final dos dados, lemos os lexemas.
Este é o método scanLexeme:
bool scanLexeme() { ushort c = controller.getChar(); switch(c) { case '#': if(controller.reader().consume("include")) { if(!include()) { controller.reader().error("bad include"); return false; } } break; ... } return true; // symbol consumed }
Se o programa vir o caractere "#", ele tentará "absorver" a próxima palavra include. Se ele não existir, haverá um único caractere "#" que será ignorado (getChar move o cursor uma posição para frente). Se a palavra include for encontrada, a diretiva precisará ser processada pelo método include.
bool include() { ushort c = skipWhitespace(); if(c == '"' || c == '<') { ushort q = c; if(q == '<') q = '>'; int start = controller.reader().column(); do { c = controller.getChar(); } while(c != q && c != 0); if(c == q) { if(loadIncludes) { Print(controller.reader().source()); int stop = controller.reader().column(); string name = StringSubstr(controller.reader().source(), start, stop - start - 1); string path = ""; if(q == '"') { path = controller.reader().pathname(); StringReplace(path, "\\", "/"); string parts[]; int n = StringSplit(path, '/', parts); if(n > 0) { ArrayResize(parts, n - 1); } else { Print("Path is empty: ", path); return false; } int upfolder = 0; while(StringFind(name, "../") == 0) { name = StringSubstr(name, 3); upfolder++; } if(upfolder > 0 && upfolder < ArraySize(parts)) { ArrayResize(parts, ArraySize(parts) - upfolder); } path = StringImplodeExt(parts, CharToString('/')) + "/"; } else // '<' '>' { path = includes; // folder; } return controller.include(path + name); } else { return true; } } else { Print("Incomplete include"); } } return false; }
Esse método ignora todos os espaços após a palavra include, usando skipWhitespace (não é considerado aqui), localiza a aspas de abertura ou o caractere '<', depois digitaliza o texto até as aspas duplas ou fecha '>' e, finalmente, seleciona a string com o caminho e arquivo de cabeçalho. Em seguida, vem o processamento de opções para o upload de um arquivo da mesma pasta ou da pasta padrão dos arquivos de cabeçalho. Como resultado, é gerado um novo caminho e nome para carregamento, após o qual o controlador passa a processar o arquivo.
Além de processar a diretiva #include, precisamos ignorar os blocos de comentários e strings, para não interpretá-los como instruções se o lexema "#include" estiver dentro. Portanto, adicionamos as variantes correspondentes ao operador switch no método scanLexeme.
case '/': if(controller.reader().probe("*")) { controller.reader().advance(1); if(!blockcomment()) { controller.reader().error("bad block comment"); return false; } } else if(controller.reader().probe("/")) { controller.reader().advance(1); linecomment(); } break; case '"': if(!literal()) { controller.reader().error("unterminated string"); return false; } break;
Aqui, por exemplo, são ignorados os comentários de bloco:
bool blockcomment() { ushort c = 0, c_; do { c_ = c; c = controller.getChar(); if(c == '/' && c_ == '*') return true; } while(!controller.reader().isEOF()); return false; }
Outros métodos auxiliares são implementados de maneira semelhante.
Assim, com a classe Preprocessor e outras, podemos teoricamente carregar texto a partir de arquivos de trabalho, assim:
#property script_show_inputs input string SourceFile = "filename.txt"; input string IncludesFolder = ""; input bool LoadIncludes = false; void OnStart() { Preprocessor loader(SourceFile, IncludesFolder, LoadIncludes); if(!loader.run()) { Print("Loader failed"); return; } // output entire data as it is assembled from one or many files int handle = FileOpen("dump.txt", FILE_WRITE | FILE_TXT | FILE_ANSI, 0, CP_UTF8); FileWriteString(handle, loader.text().get()); FileClose(handle); }
Por que teoricamente? Acontece que o MetaTrader nos permite trabalhar apenas com arquivos na área restrita (sandbox), o diretório MQL5/Files. No entanto, nosso objetivo é processar os códigos fonte que estão nas pastas MQL5/Include, MQL5/Scripts, MQL5/Experts, MQL5/Indicators.
Para contornar essa limitação, usamos o recurso do Windows para atribuir referências simbólicas a objetos do sistema de arquivos. No nosso caso, a melhor ferramenta para redirecionar o acesso a pastas no computador local é as junções (junction). Elas são criadas usando o comando:
mklink /J new_name existing_target
O parâmetro new_name é o nome de uma nova "pasta" virtual que aponta para a pasta real existing_target.
Para criar junções entre as pastas de origem especificadas e os códigos fonte, abrimos a pasta MQL5/Files, criamos a subpasta Sources e entramos nela. Em seguida, copiamos o arquivo makelink.bat anexado ao artigo. Este script de comando na verdade contém uma string:
mklink /J %1 "..\..\%1\"
Ele toma um parâmetro de entrada %1, isto é, o nome da pasta do aplicativo dentre os que estão dentro de MQL5 (por exemplo, "Include"). O caminho relativo "..\..\" assume que o arquivo de comando está localizado na pasta MQL5 MQL5/Files/Sources, em seguida, a pasta de destino (existing_target) é gerada como MQL5/%1. Por exemplo, se, ao estar na pasta Sources, for executado o comando
makelink Include
na pasta Sources aparecerá a pasta virtual Include, que, ao ser aberta, encaminha para MQL5/Include. Por analogia, pode-se criar "gêmeos" para a pasta Experts, Scripts e outros. A figura abaixo mostra o Explorer contendo a pasta MQL5/Include/Expert aberta com os arquivos de cabeçalho padrão disponíveis na pasta MQL5/Files/Sources.
Referências simbólicas do Windows para pastas de código fonte MQL5
Se necessário, as referências simbólicas podem ser excluídas como arquivos normais (primeiro, deve-se confirmar que está sendo excluída a pasta com o ícone de seta no canto inferior esquerdo, ou seja, a referência e não a pasta original).
É possível criar uma conexão diretamente com a pasta raiz MQL5 de trabalho, mas eu recomendo abrir o acesso por token, afinal, todos os programas MQL podem ler seu código fonte, incluindo logins, senhas e sistemas de negociação super secretos, se estiverem armazenados.Depois de criar as referências, o parâmetro IncludesFolder (mencionado acima) do script faz seu trabalho: o valor "Sources/Include/" indica a pasta real MQL5/Include. No parâmetro SourceFile, pode-se definir para análise, por exemplo, o código fonte de algum script "Sources/Scripts/test.mq5".
Dividindo em tokens
Os tipos de tokens que devem ser diferenciados em MQL são resumidos numa única enumeração TokenType, no arquivo de cabeçalho com o mesmo nome (anexado). Não vamos falar dele no artigo. Observe que há tokens de um único caractere, por exemplo, como vários tipos de colchetes ('(', '[', '{'), igual '=', mais '+' ou menos '-', também existem de dois caracteres, por exemplo, '==', '!=', etc. Além disso, tokens individuais viram números, strings, datas (isto é, constantes de tipos suportados), todas as palavras reservadas em MQL (operadores, tipos, this, modificadores como input, const, etc.), bem como identificadores (outras palavras). Adicionalmente, está o token EOF para marcar o final dos dados de entrada.
Token
Ao visualizar o texto, o scanner determina o tipo do próximo token, usando um algoritmo especial que vamos considerar abaixo, e cria um objeto da classe Token. Ela é uma classe muito simples.
class Token { private: TokenType type; int line; int offset; int length; public: Token(const TokenType _type, const int _line, const int _offset, const int _length = 0) { type = _type; line = _line; offset = _offset; length = _length; } TokenType getType() const { return type; } int getLine() const { return line; } ... string content(const Source *source) const { return source.get(offset, length); } };
O objeto armazena o tipo do token, seu deslocamento no texto e o comprimento. Se for necessário obter o valor do token, transferimos para o método content o ponteiro para a string source e recortamos seu respectivo fragmento.
Está na hora de recorrer ao scanner (também chamado de tokenizer em inglês).
Scanner (tokenizer)
Na classe Scanner, descrevemos o array estático com palavras-chave MQL:
class Scanner { private: static string reserved[];
Em seguida, no código fonte, nós o inicializamos conectando um arquivo de texto:
static string Scanner::reserved[] = { #include "reserved.txt" };
Adicionamos esse array com um mapa estático de correspondência entre a representação de string e o tipo de cada token.
static Map<string, TokenType> keywords;
Preenchemos o mapa no construtor (mostrado abaixo).
No scanner, também precisamos do ponteiro para os dados de entrada, da lista de tokens resultante, bem como de inúmeros contadores.
const Source *source; // wrapped string List<Token *> *tokens; int start; int current; int line;
A variável start sempre aponta para o início do seguinte token a ser processado. A variável current é um cursor para se mover pelo texto. Ela sempre se move a partir de start (à medida que verificado se o caractere atual corresponde a certo token), e, uma vez encontra uma correspondência, a subsequência de start a current cai no novo token. A variável line é o número da linha atual no texto geral.
Construtor da classe Scanner:
public: Scanner(const Source *_source): line(0), current(0) { tokens = new List<Token *>(); if(keywords.getSize() == 0) { for(int i = 0; i < ArraySize(reserved); i++) { keywords.put(reserved[i], TokenType(BREAK + i)); } } source = _source; }
Neste caso, BREAK é o identificador de tipo de token para a primeira palavra reservada em ordem alfabética. A ordem das strings no arquivo reserved.txt e os identificadores na enumeração TokenType devem ser os mesmos. Por exemplo, na enumeração, "break" corresponde ao elemento BREAK, obviamente.
O método scanTokens é fundamental.
List<Token *> *scanTokens() { while(!isAtEnd()) { // We are at the beginning of the next lexeme start = current; scanToken(); } start = current; addToken(EOF); return tokens; }
Em seu ciclo, são gerados novos tokens até alcançar o final do texto. Os métodos isAtEnd e addToken são simples:
bool isAtEnd() const { return (uint)current >= source.length(); } void addToken(TokenType type) { tokens.add(new Token(type, line, start, current - start)); }
O método scanToken realiza todo o trabalho auxiliar, porém, antes de o apresentar, é necessário dominar alguns métodos auxiliares simples, que são semelhantes com aqueles que vimos na classe Preprocessor, portanto, é provável que não seja necessário nos debruçar na sua função.
bool match(ushort expected) { if(isAtEnd()) return false; if(source[current] != expected) return false; current++; return true; } ushort previous() const { if(current > 0) return source[current - 1]; return 0; } ushort peek() const { if(isAtEnd()) return '\0'; return source[current]; } ushort peekNext() const { if((uint)(current + 1) >= source.length()) return '\0'; return source[current + 1]; } ushort advance() { current++; return source[current - 1]; }
Agora, votamos ao método scanToken.
void scanToken() { ushort c = advance(); switch(c) { case '(': addToken(LEFT_PAREN); break; case ')': addToken(RIGHT_PAREN); break; ...
Ele lê o próximo caractere e, dependendo do seu código, cria um token. Não listaremos todos os tokens de um caractere — sua criação é semelhante.
Se o token admitir dois caracteres, o processamento se torna mais complicado:
case '-': addToken(match('-') ? DEC : (match('=') ? MINUS_EQUAL : MINUS)); break; case '+': addToken(match('+') ? INC : (match('=') ? PLUS_EQUAL : PLUS)); break; ...
Aqui é mostrada a geração de tokens para os lexemas '--', '-=', '++', '+='.
A versão atual do scanner ignora os comentários:
case '/': if(match('/')) { // A comment goes until the end of the line while(peek() != '\n' && !isAtEnd()) advance(); }
Os interessados podem mantê-los em tokens especiais.
Construções de blocos, como strings, literais, diretivas de pré-processador são processadas em métodos auxiliares separados, nós não os consideramos em detalhes:
case '"': _string(); break; case '\'': literal(); break; case '#': preprocessor(); break;
Assim é digitalizada a string:
void _string() { while(!(peek() == '"' && previous() != '\\') && !isAtEnd()) { if(peek() == '\n') { line++; } advance(); } if(isAtEnd()) { error("Unterminated string"); return; } advance(); // The closing " addToken(CONST_STRING); }
Quando nenhum dos tipos de tokens funciona, é realizada uma verificação padrão que inclui números, identificadores e palavras-chave.
default: if(isDigit(c)) { number(); } else if(isAlpha(c)) { identifier(); } else { error("Unexpected character `" + ShortToString(c) + "` 0x" + StringFormat("%X", c) + " @ " + (string)current + ":" + source.get(MathMax(current - 10, 0), 20)); } break;
Implementações de isDigit, isAlpha são óbvias. Aqui mencionamos apenas o método identifier.
void identifier() { while(isAlphaNumeric(peek())) advance(); // See if the identifier is a reserved word string text = source.get(start, current - start); TokenType type = keywords.get(text); if(type == null) type = IDENTIFIER; addToken(type); }
Implementações completas de todos os métodos podem ser encontradas nos códigos fonte anexados. Para não reinventar a roda, tomei parte do código do livro Crafting Interpreters, embora, claro, tenha precisado de fazer algumas correções.
Eis todo o scanner. Se não houver erros, o método scanTokens retornará para o usuário uma lista de tokens que pode ser transferida para o analisador. No entanto, o analisador deve ter uma gramática para analisar a lista de tokens. Assim, antes de continuar com o analisador, é preciso considerar a descrição da gramática. Ela é gerada a partir dos objetos da classe Terminal e dos seus derivados.Descrição gramatical
Primeiro, imaginemos que, em vez da gramática MQL, é necessário descrever a gramática de uma certa linguagem para calcular expressões aritméticas, uma calculadora. Veja uma fórmula válida para o cálculo:
(10 + 1) * 2
Habilitamos apenas os inteiros e operações '+', '-', '*', '/', sem priorizar: para prioridades usamos colchetes '(' ')'.
O ponto de entrada da gramática deve ser um não-terminal que descreve a expressão inteira. Suponhamos que, para isso, baste escrever:
NonTerminal expression;
Uma expressão consiste em operandos — valores inteiros — e símbolos de operação. Todos eles são terminais, ou seja, eles podem ser criados com base nos tokens que o scanner suporta.
Suponhamos que os descrevamos assim:
Terminal plus(PLUS), star(STAR), minus(MINUS), slash(SLASH); Terminal value(CONST_INTEGER);
Como podemos ver, o construtor do terminal deve permitir a transferência do tipo de token como parâmetro.
Um número simples é a expressão mais simples que pode existir. Faz sentido colocar isso desta forma:
expression = value;
Esta é uma sobrecarga do operador de atribuição. Nela, dentro de expression em alguma variável, precisamos armazenar uma referência ao objeto value, damos a ela o nome eq (equivalence). Quando o analisador recebe a tarefa de verificar se expression corresponde à string inserida, ele delega a verificação para o não-terminal, este, por sua vez, “vê” a referência para value, solicita ao analisador verificar value, e a verificação chega ao terminal, onde acontece a comparação de tokens — token no terminal e token no fluxo de entrada.
No entanto, uma expressão pode ter adicionalmente uma operação e um segundo operando, portanto, é necessário estender a regra expression. Para isso, descrevemos preliminarmente um novo não-terminal:
NonTerminal operation; operation = (plus | star | minus | slash) + value;
Aqui acontecem muitas coisas interessantes nos bastidores. O operador '|' deve ser sobrecarregado na classe, para garantir que os elementos sejam combinados num grupo lógico por OU lógico. No entanto, o operador é chamado no terminal, num caractere simples, mas precisamos de um grupo de elementos. Portanto, o primeiro elemento do grupo (para o qual o tempo de execução chama o operador, neste caso, plus) deve verificar se é um membro de algum grupo e, se ainda não houver grupo, deve criá-lo dinamicamente como um objeto da classe HiddenNonTerminalOR. Em seguida, a implementação do operador sobrecarregado deve incluir this e o terminal star à direita (passada como um argumento para a função-operador) no grupo recém-criado. O operador retorna um link para esse grupo, a fim de que os seguintes operadores '|' (stringed) já chamados de HiddenNonTerminalOR.
Para suporte ao array com membros do grupo, na calasse consideramos o array next. Seu nome indica o próximo nível de detalhe de elementos gramaticais. Cada elemento que inserimos neste array de nós filhos deve definir a referência oposta para o nó pai, aqui ele é chamado de parent. O fato de haver um parent diferente de zero indica associação a um grupo. Como resultado da execução do código (mencionado acima) dentro dos parênteses, obtemos um HiddenNonTerminalOR com um array contendo todos os 4 símbolos de operação.
Em seguida, o operador sobrecarregado '+' entra no jogo. Ele deve funcionar de maneira semelhante como o operador '|', quer dizer, também deve criar um grupo implícito de elementos, porém, desta vez, da classe HiddenNonTerminalAND, adicionalmente, durante a análise eles devem ser verificados de acordo como o AND.
Observe que é gerada uma hierarquia subordinada de terminais e não-terminais. Neste caso, o objeto HiddenNonTerminalAND contém dois elementos filho: o grupo HiddenNonTerminalOR recém-criado e o valor. HiddenNonTerminalAND, por sua vez, é subordinado ao não-terminal operation.
A prioridade das operações '|' e '+' é tal que, na ausência de parênteses, AND é processado primeiro e OU depois. É por isso que em operation tivemos que pegar todas as variações de caracteres entre parênteses.
Definido o não-terminal operation, podemos corrigir a gramática da expressão:
expression = value + operation;
Ela supostamente descreve expressões da forma A @ B, onde A e B são inteiros, enquanto @ é uma ação. Mas, neste caso, há uma ratoeira.
Já temos duas regras das quais o objeto value participa. Isso significa que a referência ao conjunto pai definida na primeira regra é reescrita na segunda. Para evitar que isso aconteça, é necessário inserir nas regras não objetos em si, mas, sim, as suas cópias.
Para isso, contemplamos a sobrecarga de dois operadores: '~' e '^'. O primeiro, unário, é colocado antes do operando. No objeto que recebe a chamada da função-operador correspondente, criamos dinamicamente o objeto de mediação e o retornamos ao código de chamada. O segundo operador é binário. Além do objeto, passamos o número atual da string no código fonte da gramática, ou seja, a constante __LINE__ predefinida pelo compilador MQL. Assim, conseguimos distinguir instâncias descritas implicitamente de objetos, graças ao número de strings onde elas são criadas. Isso ajuda na depuração de gramáticas complexas. Em outras palavras, os operadores '~' e '^' executam o mesmo trabalho, mas o primeiro faz isso no modo de lançamento e o segundo, no modo de depuração.
As cópias intermediárias representam um objeto da classe HiddenNonTerminal, na qual a variável eq mencionada anteriormente faz referência ao objeto original.
Assim, reescrevemos a gramática de expressões considerando a criação de objetos mediadores.
operation = (plus | star | minus | slash) + ~value; expression = ~value + operation;
Como operation é usado apenas uma vez, é possível não fazer um gêmeo para ele. Cada referência lógica aumenta a recursão da unidade quando a expressão é expandida. No entanto, para evitar erros em grandes gramáticas, recomenda-se fazer referências em todos os lugares. Mesmo se agora um não-terminal for usado apenas uma vez, ele poderá aparecer posteriormente em outra parte da gramática. No código fonte, nós consideramos verificar a substituição do nó pai para gerar uma mensagem de erro.
Embora agora nossa gramática possa manipular "10+1", não pode ler um número individual. De fato, o operation não-terminal deve ser opcional. Para fazer isso, implementamos a sobrecarga do operador '*'. Se o elemento de gramática é multiplicado por 0, ele pode ser omitido durante a verificação (sua ausência não leva a erro).
expression = ~value + operation*0;
A sobrecarga de operador de multiplicação permite realizar outra coisa importante, nomeadamente a repetição de um elemento um número arbitrário de vezes. Neste caso, multiplicamos o elemento por 1. Na classe do terminal, essa propriedade — multiplicidade ou opcionalidade — é armazenada na variável mult. Casos em que um determinado elemento é opcional e pode ser repetido muitas vezes são facilmente implementados usando duas referências: a primeira deve ser opcional (optional*0) e a segunda deve ser múltiplo (optional = element*1).
Há outra falha na gramática atual da calculadora. Ela não é adequada para expressões longas com várias operações, como 1+2+3+4+5. Para corrigir essa falha, deve-se alterar o operation não-terminal.
operation = (plus | star | minus | slash) + ~expression;
Substituímos value no expression em si, permitindo, assim, uma análise cíclica de todos os finais de expressões novos.
Resta o suporte de expressões entre parênteses. Como não é difícil adivinhar, eles desempenham o mesmo papel que o valor único value. Portanto, nós o redefinimos como uma alternativa entre duas variações: um inteiro ou uma subexpressão entre parênteses. Toda a gramática fica assim:
NonTerminal expression; NonTerminal value; NonTerminal operation; Terminal number(CONST_INTEGER); Terminal left(LEFT_PAREN); Terminal right(RIGHT_PAREN); Terminal plus(PLUS), star(STAR), minus(MINUS), slash(SLASH); value = number | left + expression^__LINE__ + right; operation = (plus | star | minus | slash) + expression^__LINE__; expression = value + operation*0;
Consideremos com mais detalhes como essas classes são organizadas internamente.
Terminal
Na classe Terminal, descrevemos os campos para o tipo de token (me), as propriedades de multiplicidade (mult), o nome opcional (name, para identificar não-terminais em logs), referências ao produto (eq), ao pai (parent) e a elementos subordinados (arrau next).
class Terminal { protected: TokenType me; int mult; string name; Terminal *eq; BaseArray<Terminal *> next; Terminal *parent;
Os campos são preenchidos em construtores, bem como em métodos setter, e são lidos usando métodos getter, que omitimos aqui por brevidade.
Os operadores são sobrecarregados de acordo com o seguinte princípio:
virtual Terminal *operator|(Terminal &t) { Terminal *p = &t; if(dynamic_cast<HiddenNonTerminalOR *>(p.parent) != NULL) { p = p.parent; } if(dynamic_cast<HiddenNonTerminalOR *>(parent) != NULL) { parent.next << p; p.setParent(parent); } else { if(parent != NULL) { Print("Bad OR parent: ", parent.toString(), " in ", toString()); ... error } else { parent = new HiddenNonTerminalOR("hiddenOR"); p.setParent(parent); parent.next << &this; parent.next << p; } } return parent; }
Veja o agrupamento por OR. Por AND é tudo a mesma coisa.
Definição do sinal de multiplicidade, no operador '*':
virtual Terminal *operator*(const int times) { mult = times; return &this; }
No destruidor, consideramos exclusão correta de instâncias criadas dinamicamente.
~Terminal() { Terminal *p = dynamic_cast<HiddenNonTerminal *>(parent); while(CheckPointer(p) != POINTER_INVALID) { Terminal *d = p; if(CheckPointer(p.parent) == POINTER_DYNAMIC) { p = dynamic_cast<HiddenNonTerminal *>(p.parent); } else { p = NULL; } CLEAR(d); } }
E, finalmente, o método principal da classe Terminal responsável pela análise.
virtual bool parse(Parser *parser) { Token *token = parser.getToken(); bool eqResult = true;
Aqui obtemos uma referência ao analisador, lemos o token atual nele (a classe do analisador é discutida abaixo).
if(token.getType() == EOF && mult == 0) return true;
Quando o token é EOF e o elemento atual é opcional, significa que foi detectado o final correto do texto.
Em seguida, verificamos se há uma referência do operador '=' sobrecarregado à cópia original do elemento, se estivermos na cópia. Se houver uma referência, enviamo-la o ao analisador para verificação no método match.
if(eq != NULL) // redirect { eqResult = parser.match(eq); bool lastResult = eqResult; // if multiple tokens expected and while next tokens are successfully consumed while(eqResult && eq.mult == 1 && parser.getToken() != token && parser.getToken().getType() != EOF) { token = parser.getToken(); eqResult = parser.match(eq); } eqResult = lastResult || (mult == 0); return eqResult; // redirect was fulfilled }
Além disso, aqui é processada a situação em que o elemento pode ser repetido (mult = 1): o analisador é chamado repetidas vezes até que o método match retorne sucesso.
Um sinal de sucesso, true ou false, é retornado do método parse nesse segmento, e, em outras situações, por exemplo, para um terminal:
if(token.getType() == me) // token match { parser.advance(parent); return true; }
Para o terminal, simplesmente comparamos seu token me com o token atual nos dados de entrada, e, se houver uma correspondência, confiamos ao analisador a tarefa de mover o cursor para o próximo token de entrada usando o método de avanço. No mesmo método, o analisador informa ao programa do lado do cliente que surgiu um produto no não-terminal parent.
Para um grupo de elementos, tudo é um pouco mais complicado. Consideremos o caso do AND lógico, a variação para OU é semelhante. Usando o método virtual hasAnd (na classe Terminal ele retorna false, enquanto, nos herdeiros, é bloqueado) determinamos se o array com elementos subordinados está preenchido para verificação por AND.
else if(hasAnd()) // check AND-ed conditions { parser.pushState(); for(int i = 0; i < getNext().size(); i++) { if(!parser.match(getNext()[i])) { if(mult == 0) { parser.popState(); return true; } else { parser.popState(); return false; } } } parser.commitState(parent); return true; }
Como esse não-terminal será considerado correto, se todos os seus componentes coincidirem com a gramática, chamaremos o método match do analisador para todos eles, num ciclo. Se pelo menos acontecer um resultado negativo, a verificação inteira falhará. No entanto, há uma exceção: se o não-terminal for opcional, as regras gramaticais ainda serão satisfeitas mesmo que seja retornado false a partir do método match.
Observe que, antes do ciclo, salvamos o estado atual (pushState) no analisador, restauramos (popState) com saída antecipada e confirmamos o novo estado com um teste bem-sucedido totalmente concluído (commitState). Isso é necessário para adiar notificações (para código de cliente) sobre um novo “produto” até que toda a regra gramatical funcione inteiramente. A palavra "estado" na verdade oculta apenas a posição atual do cursor no fluxo de tokens de entrada.
Se nem o token nem os grupos de elementos subordinados funcionam dentro do método parse, só podemos verificar a opcionalidade do objeto atual:
else if(mult == 0) // last chance { // parser.advance(); - don't consume token and proceed to next production return true; }
Caso contrário, falhamos no final do método que sinaliza um erro (o texto não corresponde à gramática).
if(dynamic_cast<HiddenNonTerminal *>(&this) == NULL) { parser.trackError(&this); } return false; }
Agora descrevemos as classes herdadas da classe Terminal.
Não-terminais são ocultos e explícitos
A principal tarefa da classe HiddenNonTerminal é criar cópias dinâmicas de objetos e limpar o lixo.
class HiddenNonTerminal: public Terminal { private: static List<Terminal *> dynamic; // garbage collector public: HiddenNonTerminal(const string id = NULL): Terminal(id) { } HiddenNonTerminal(HiddenNonTerminal &ref) { eq = &ref; } virtual HiddenNonTerminal *operator~() { HiddenNonTerminal *p = new HiddenNonTerminal(this); dynamic.add(p); return p; } ... };
A classe HiddenNonTerminalOR fornece ao operador '|' sobrecarga (mais simples que na classe Terminal, porque HiddenNonTerminalOR é em si um elemento contêiner que é o proprietário de um grupo de elementos gramaticais subordinados).
class HiddenNonTerminalOR: public HiddenNonTerminal { public: virtual Terminal *operator|(Terminal &t) override { Terminal *p = &t; next << p; p.setParent(&this); return &this; } ... };
A classe HiddenNonTerminalAND é implementada de forma semelhante.
A classe NonTerminal fornece a sobrecarga do operador '=' ("produto" nas regras).
class NonTerminal: public HiddenNonTerminal { public: NonTerminal(const string id = NULL): HiddenNonTerminal(id) { } virtual Terminal *operator=(Terminal &t) { Terminal *p = &t; while(p.getParent() != NULL) { p = p.getParent(); if(p == &t) { Print("Cyclic dependency in assignment: ", toString(), " <<== ", t.toString()); p = &t; break; } } if(dynamic_cast<HiddenNonTerminal *>(p) != NULL) { eq = p; } else { eq = &t; } eq.setParent(this); return &this; } };
Finalmente, existe a classe Rule, herdeira de NonTerminal, mas todo o seu papel é, ao descrever a gramática, marcar algumas regras como básicas (se elas geram um objeto Rule) ou como acessórias (se seu o resultado é NonTerminal).
Para facilitar a descrição de não-terminais, são gerada macros:
// debug #define R(Y) (Y^__LINE__) // release #define R(Y) (~Y) #define _DECLARE(Cls) NonTerminal Cls(#Cls); Cls #define DECLARE(Cls) Rule Cls(#Cls); Cls #define _FORWARD(Cls) NonTerminal Cls(#Cls); #define FORWARD(Cls) Rule Cls(#Cls);
O argumento da macro é uma string, um nome exclusivo. A declaração 'forwad' é necessária quando os não-terminais fazem referência uns aos outros, vimos isso na gramática da calculadora.
Além disso, para gerar terminais com tokens, é implementada a classe especial Keywords com suporte a coleta de lixo.
class Keywords { private: static List<Terminal *> keywords; public: static Terminal *get(const TokenType t, const string value = NULL) { Terminal *p = new Terminal(t, value); keywords.add(p); return p; } };
Para o seu uso na descrição da gramática, existem suas macros:
#define T(X) Keywords::get(X) #define TC(X,Y) Keywords::get(X,Y)
Vejamos como a gramática da calculadora discutida anteriormente é descrita usando as interfaces de programação implementadas.
FORWARD(expression);
_DECLARE(value) = T(CONST_INTEGER) | T(LEFT_PAREN) + R(expression) + T(RIGHT_PAREN);
_DECLARE(operation) = (T(PLUS) | T(STAR) | T(MINUS) | T(SLASH)) + R(expression);
expression = R(value) + R(operation)*0;
Finalmente, estamos prontos para aprender a classe Parser.
Parser
A classe Parser possui membros para armazenar a lista de entrada de tokens (tokens), a posição atual nela (cursor), a posição máxima conhecida (maxcursor, ela é usada para diagnosticar erros), a pilha de posições antes de chamar grupos aninhados de elementos (states, para retrocesso, lembre o backtracking) e referências para o texto de entrada (source, para impressão de logs e outros fins).
class Parser { private: BaseArray<Token *> *tokens; // input stream int cursor; // current token int maxcursor; BaseArray<int> states; const Source *source;
Além disso, o analisador rastreia toda a hierarquia de chamadas por elementos gramaticais usando a pilha stack. A classe TreeNode implementada neste modelo de classe é um contêiner simples para um par (terminal,token), seu código fonte pode ser visualizado no arquivo anexado. Erros são acumulados para diagnósticos em outra pilha (errors).
// current stack, how the grammar unwinds Stack<TreeNode *> stack; // holds current stack on every problematic point Stack<Stack<TreeNode *> *> errors;
O construtor do analisador aceita uma lista de tokens, o texto de origem e o sinalizador opcional para habilitar a construção da árvore de sintaxe no processo de análise.
public: Parser(BaseArray<Token *> *_tokens, const Source *text, const bool _buildTree = false)
Quando o modo de árvore está ativado, todos os "produtos" de sucesso que se encontram na pilha na forma de objetos TreeNode são enfiados na raiz da árvore (variável tree):
TreeNode *tree; // concrete syntax tree (optional result)
Para este motivo, a classe TreeNode suporta um array de nós filhos. Após o analisador terminar, a árvore (se estiver ativada) pode ser obtida usando o método:
const TreeNode *getCST() const { return tree; }
O método do analisador principal (match) de forma simplificada se parece com isso.
bool match(Terminal *p) { TreeNode *node = new TreeNode(p, getToken()); stack.push(node); int previous = cursor; bool result = p.parse(&this); stack.pop(); if(result) // success { if(stack.size() > 0) // there is a holder to bind to { if(cursor > previous) // token was consumed { stack.top().bind(node); } else { delete node; } } } else { delete node; } return result; }
Os métodos advance e commitState, que vimos quando estávamos estudando as classes de terminal, são implementados assim (algumas nuances são omitidas).
void advance(const Terminal *p) { production(p, cursor, tokens[cursor], stack.size()); if(cursor < tokens.size() - 1) cursor++; if(cursor > maxcursor) { maxcursor = cursor; errors.clear(); } } void commitState(const Terminal *p) { int x = states.pop(); for(int i = x; i < cursor; i++) { production(p, i, tokens[i], stack.size()); } }
Advance move o cursor pela lista de tokens. Se a posição se tornou mais do que o máximo, pode-se remover os erros acumulados, porque eles são registrados com cada verificação mal-sucedida.
O método production usa uma interface de retorno de chamada para notificar o usuário do analisador sobre o “produto”, vamos aplicá-lo mais para frente nos testes.
void production(const Terminal *p, const int index, const Token *t, const int level) { if(callback) callback.produce(&this, p, index, t, source, level); }
A interface é definida como:
interface Callback { void produce(const Parser *parser, const Terminal *, const int index, const Token *, const Source *context, const int level); void backtrack(const int index); };
O objeto que implementa esta interface no lado do cliente pode se conectar ao analisador usando o método setCallback, neste caso, ele é chamado em cada “produto”. Como alternativa, esse objeto pode ser conectado individualmente a qualquer terminal graças à sobrecarga do operador [Callback *]. Isso é útil na depuração para colocar pontos de interrupção em pontos gramaticais específicos.
Usemos o analisador na prática.Prática, parte 1: calculadora
Nós já temos a gramática da calculadora. Criamos um script de depuração para ela. Complementamos para testes com gramática MQL.
#property script_show_inputs enum TEST_GRAMMAR {Expression, MQL}; input TEST_GRAMMAR TestMode = Expression;; input string SourceFile = "Sources/calc.txt";; input string IncludesFolder = "Sources/Include/";; input bool LoadIncludes = false; input bool PrintCST = false; #include <mql5/scanner.mqh> #include <mql5/prsr.mqh> void OnStart() { Preprocessor loader(SourceFile, IncludesFolder, LoadIncludes); if(!loader.run()) { Print("Loader failed"); return; } Scanner scanner(loader.text()); List<Token *> *tokens = scanner.scanTokens(); if(!scanner.isSuccess()) { Print("Tokenizer failed"); delete tokens; return; } Parser parser(tokens, loader.text(), PrintCST); if(TestMode == Expression) { testExpressionGrammar(&parser); } else { //... } delete tokens; } void testExpressionGrammar(Parser *p) { _FORWARD(expression); _DECLARE(value) = T(CONST_INTEGER) | T(LEFT_PAREN) + R(expression) + T(RIGHT_PAREN); _DECLARE(operation) = (T(PLUS) | T(STAR) | T(MINUS) | T(SLASH)) + R(expression); expression = R(value) + R(operation)*0; while(p.match(&expression) && !p.isAtEnd()) { Print("", "Unexpected end"); break; } if(p.isAtEnd()) { Print("Success"); } else { p.printState(); } if(PrintCST) { Print("Concrete Syntax Tree:"); TreePrinter printer(p); printer.printTree(); } Comment(""); }
Essência do script: ler o arquivo transferido no pré-processador, converter num fluxo de tokens usando um scanner e verificar com um analisador para a gramática especificada. A verificação é realizada chamando o método match, para o qual é passada a regra de raiz da gramática (expression).
Como uma opção (PrintCST), podemos registrar no log a árvore de sintaxe da expressão processada usando a classe auxiliar TreePrinter.
Atenção! Para programas reais, a árvore é muito grande. Esta opção é recomendada somente ao depurar pequenos fragmentos de gramática ou se a gramática inteira é pequena, como no caso da nossa calculadora.
Ao executar um script de teste para o arquivo com a expressão "(10+1)*2", obtemos a seguinte árvore (não esqueça de selecionar TestMode igual a Expression e PrintCST - true):
Concrete Syntax Tree: | | |Terminal LEFT_PAREN @ ( | | | | |Terminal CONST_INTEGER @ 10 | | | |NonTerminal value | | | | |Terminal PLUS @ + | | | | | | |Terminal CONST_INTEGER @ 1 | | | | | |NonTerminal value | | | | |NonTerminal expression | | | |NonTerminal operation | | |NonTerminal expression | | |Terminal RIGHT_PAREN @ ) | |NonTerminal value | | |Terminal STAR @ * | | | | |Terminal CONST_INTEGER @ 2 | | | |NonTerminal value | | |NonTerminal expression | |NonTerminal operation |NonTerminal expression
Linhas verticais indicam os níveis de processamento dos não-terminais que são explicitamente descritos na gramática (nomeados). Os espaços correspondem aos níveis onde os não-terminais implicitamente criados das classes HiddenXYZ "se abriram" — todos esses nós não são exibidos por padrão no log, mas na classe TreePrinter existe uma opção para ativá-los.
Observe que a opção PrintCST funciona com base numa estrutura especial de metadados, uma árvore de objetos TreeNode. Nosso analisador pode, opcionalmente, mostrá-lo após a análise em resposta a uma chamada para o método getCST. Lembre-se de que a ativação do modo de montagem da árvore é definida pelo terceiro parâmetro do construtor do analisador.
Pode-se experimentar outras expressões, inclusive incorretas, para garantir que haja tratamento de erros. Por exemplo, ao estragar uma expressão, tornando-a "10+", recebemos a mensagem:
Failed First 2 tokens read out of 3 Source: EOF (file:Sources/Include/Layouts/calc.txt; line:1; offset:4) `` Expected: CONST_INTEGER in expression;operation;expression;value; LEFT_PAREN in expression;operation;expression;value;
Assim, todas as classes funcionam. Pode-se continuar com a parte prática principal, a análise sintática da MQL.
Prática, parte 2: gramática MQL
Tecnicamente falando, tudo está pronto para começar a escrever uma gramática MQL. No entanto, ela é muito mais complicada do que a da uma pequena calculadora. Criá-la do zero é uma tarefa impossível. Para resolver o problema, usamos o fato de que a MQL é semelhante com C++.
Para C++, pode-se encontrar muitas descrições gramaticais prontas de domínio público. Um deles é anexado ao artigo como um arquivo cppgrmr.htm. Também é problemático transferi-lo completamente para nossa gramática. Em primeiro lugar, muitos constructos em MQL ainda não são suportados. Em segundo lugar, na notação está frequentemente presente a recursividade à esquerda, devido a ela as regras precisam ser alteradas. Finalmente, em terceiro lugar, é bom limitar o tamanho da gramática, porque ela afeta negativamente a velocidade de processamento: faz sentido deixar alguns recursos opcionais para aqueles que precisam deles.
A sequência na qual as alternativas OR são mencionadas é importante, uma vez que a primeira variação acionada interrompe as verificações subsequentes. Se, sob certas condições, as variações puderem coincidir parcialmente devido à omissão de elementos opcionais, elas precisam ser rearranjadas ou especificar primeiro estruturas mais longas e mais específicas, e mais gerais e curtas posteriormente.
Mostremos como algumas notações de um arquivo htm são transformadas na gramática de nossas regras e terminais.
Na gramática C++:
assignment-expression: conditional-expression unary-expression assignment-operator assignment-expression assignment-operator: one of = *= /= %= += –= >= <= &= ^= |=
Na gramática MQL:
_FORWARD(assignment_expression); _FORWARD(unary_expression); ... assignment_expression = R(unary_expression) + R(assignment_operator) + R(assignment_expression) | R(conditional_expression); _DECLARE(assignment_operator) = T(EQUAL) | T(STAR_EQUAL) | T(SLASH_EQUAL) | T(DIV_EQUAL) | T(PLUS_EQUAL) | T(MINUS_EQUAL) | T(GREATER_EQUAL) | T(LESS_EQUAL) | T(BIT_AND_EQUAL) | T(BIT_XOR_EQUAL) | T(BIT_OR_EQUAL);
Na gramática C++:
unary-expression: postfix-expression ++ unary-expression –– unary-expression unary-operator cast-expression sizeof unary-expression sizeof ( type-name ) allocation-expression deallocation-expression
Na gramática MQL:
unary_expression = R(postfix_expression) | T(INC) + R(unary_expression) | T(DEC) + R(unary_expression) | R(unary_operator) + R(cast_expression) | T(SIZEOF) + T(LEFT_PAREN) + R(type) + T(RIGHT_PAREN) | R(allocation_expression) | R(deallocation_expression);
Na gramática C++:
statement: labeled-statement expression-statement compound-statement selection-statement iteration-statement jump-statement declaration-statement asm-statement try-except-statement try-finally-statement
Na gramática MQL:
statement = R(expression_statement) | R(codeblock) | R(selection_statement) | R(labeled_statement) | R(iteration_statement) | R(jump_statement);
A regra para o declaration_statement na gramática MQL também está lá, mas é transferida. Muitas regras foram escritas de forma simplificada em comparação com C++. Em princípio, essa gramática é um organismo vivo ou, como dizem os ingleses, "a work in progress". É muito provável que existam erros ao interpretar constructos específicos em códigos fonte.
O ponto de entrada para a gramática MQL é a regra program que consiste em 1 ou mais elements:
_DECLARE(element) =
R(class_decl)
| R(declaration_statement) | R(function) | R(sharp) | R(macro);
_DECLARE(program) = R(element)*1;
Em nosso script de teste, a gramática MQL apresentada é descrita na função testMQLgrammar:
void testMQLgrammar(Parser *p) { // all grammar rules go first // ... _DECLARE(program) = R(element)*1;
Nela é executada a análise (por analogia com a calculadora):
while(p.match(&program) && !p.isAtEnd())
...
Se ocorrer um erro, deve-se localizar o elemento problemático usando os logs e depurar a regra gramatical específica num fragmento de entrada separado do texto (é recomendado um fragmento com menos de 5-6 tokens). Em outras palavras, é necessário chamar o método match do analisador para uma regra específica e inserir na entrada o arquivo com um constructo de idioma separado. Para imprimir no log os rastreios do analisador, é preciso remover a marca de comentário da diretiva no script:
//#define PRINTX Print
Atenção! A quantidade de informações de saída é muito grande.
Antes da depuração, recomenda-se distribuir diferentes elementos da regra em strings diferentes, uma vez que isso marca cópias anônimas de objetos com números exclusivos de string de origem.No entanto, o analisador é criado para extrair dados semânticos. Tentemos fazer isso.
Prática, parte 3: lista de métodos de classe e hierarquia de classes
Como a primeira tarefa, compilamos uma lista contendo todos os métodos das classes. Para fazer isso, definimos uma classe que implementa a interface Callback e registramos os "produtos" nos quais estamos interessados.
Em princípio, seria mais lógico executar a análise sintática com base numa árvore de sintaxe. Mas isso significa uma sobrecarga de memória para armazenar a árvore e um algoritmo separado para percorrer essa árvore. No entanto, um percurso na mesma ordem é feito pelo próprio analisador durante a análise do texto (afinal de contas, seria nessa sequência que a árvore seria construída se estivesse ativado o modo correspondente). Portanto, é mais fácil analisar rapidamente.
A gramática MQL possui esta regra:
_DECLARE(method) = R(template_decl)*0 + R(method_specifiers)*0 + R(type) + R(name_with_arg_list) + R(modifiers)*0;
Ela consiste em muitos outros não-terminais, que, por sua vez, são revelados através de outros não-terminais, portanto, a árvore de sintaxe do método é muito extensa. No manipulador de produto, interceptaremos todos os fragmentos pertencentes ao não-terminal "method" e os colocamos numa string comum. O momento em que o próximo produto produção for para outro não-terminal significa que a descrição do método conclui e pode-se exibir o resultado no log.
class MyCallback: public Callback { virtual void produce(const Parser *parser, const Terminal *p, const int index, const Token *t, const Source *context, const int level) override { static string method = ""; // collect all tokens from `method` nonterminal if(p.getName() == "method") { method += t.content(context) + " "; } // as soon as other [non]terminal is detected and string is filled, signature is ready else if(method != "") { Print(method); method = ""; } }
Para conectar o manipulador ao analisador, complementamos o script de teste desta forma (no OnStart):
MyCallback myc; Parser parser(tokens, loader.text(), PrintCST); parser.setCallback(&myc);
Além da lista de métodos, coletamos informações sobre a declaração de classe, ela é necessária, em particular, para definir o contexto no qual os métodos são definidos, mas também para podermos construir a hierarquia de herança.
Para armazenar meta-informações sobre uma classe arbitrária, preparamos a classe Class 😉.
class Class { private: BaseArray<Class *> subclasses; Class *superclass; string name; public: Class(const string n): name(n), superclass(NULL) { } ~Class() { subclasses.clear(); } void addSubclass(Class *derived) { derived.superclass = &this; subclasses.add(derived); } bool hasParent() const { return superclass != NULL; } Class *operator[](int i) const { return subclasses[i]; } int size() const { return subclasses.size(); } ... };
Ele tem um array de herdeiros subclasses e um link para o pai superclass. O método addSubclass trata do preenchimento desses campos inter-relacionados. Adicionamos instâncias de objetos Class a um mapa com uma chave de string na forma de nome de classe:
Map<string,Class *> map;
O mapa está todo no mesmo objeto MyCallback.
Agora podemos complementar o método produce a partir da interface Callback. Para coletar tokens relacionados a uma declaração de classe, temos que usar um pouco mais regras, porque precisamos da declaração inteira com propriedades específicas selecionadas: o nome da nova classe, o nome da classe base e seus tipos de modelo (se houver).
Adicionamos as variáveis apropriadas para a coleta de dados (note que as classes em MQL podem ser aninhadas, mas não vamos considerar isso aqui para simplificar)
static string templName = ""; static string templBaseName = ""; static string className = ""; static string baseName = "";
Identificadores no contexto do não-terminal "template_decl" são tipos de modelo:
if(p.getName() == "template_decl" && t.getType() == IDENTIFIER) { if(templName != "") templName += ","; templName += t.content(context); }
As regras gramaticais correspondentes para "template_decl", bem como os objetos usados abaixo, podem ser estudados nos códigos-fonte que os acompanham.
O identificador no contexto do não-terminal "class_name" é o nome da classe, e, se templName não é uma string vazia neste momento, estes são os tipos de template que precisam ser adicionados à descrição:
if(p.getName() == "class_name" && t.getType() == IDENTIFIER) { className = t.content(context); if(templName != "") { className += "<" + templName + ">"; templName = ""; } }
O primeiro identificador no contexto do "derivado_cláusula" (se houver) é o nome da classe base.
if(p.getName() == "derived_clause" && t.getType() == IDENTIFIER) { if(baseName == "") baseName = t.content(context); else { if(templBaseName != "") templBaseName += ","; templBaseName += t.content(context); } }
Todos os seguintes identificadores são tipos de modelo da classe base.
Quando a declaração de classe é concluída, é acionada a regra gramatical "class_decl". Neste ponto, todos os dados já foram coletados e podem ser inseridos no mapa de classes.
if(p.getName() == "class_decl") // finalization { if(className != "") { if(map[className] == NULL) { map.put(className, new Class(className)); } else { // Class already defined, maybe forward declaration } } if(baseName != "") { if(templBaseName != "") { baseName += "<" + templBaseName + ">"; } Class *base = map[baseName]; if(base == NULL) { // Unknown class, maybe not included, but strange base = new Class(baseName); map.put(baseName, base); } if(map[className] == NULL) { Print("Error: base name `", baseName, "` resolved before declaration of the class: ", className); } else { base.addSubclass(map[className]); } baseName = ""; } className = ""; templName = ""; templBaseName = ""; }
No final, limpamos todas as linhas e esperamos as seguintes declarações aparecerem.
Após a análise bem-sucedida do texto do programa, resta exibir a hierarquia de classes de qualquer maneira conveniente. No script de teste, a classe MyCallback fornece a função print para registro no log. Por sua vez, ela usa o método print nos objetos da classe Class. Deixamos esses algoritmos auxiliares para serem estudados por conta própria e, além disso, como um pequeno exercício de programador para medir habilidades (tais contendas, muitas vezes, surgem espontaneamente no fórum mql5.com). A implementação existente é puramente utilitária e não pretende ser ideal, ela simplesmente fornece o objetivo de exibir uma hierarquia de objetos do tipo Class num log da forma mais óbvia. No entanto, isso certamente pode ser feito de maneira mais eficaz.
Verifiquemos o trabalho do script de teste para analisar alguns projetos MQL. A seguir, definimos o parâmetro TestMode = MQL.
Por exemplo, para o EA padrão "MACD Sample.mq5", ao definir SourceFile = "Sources/Experts/Examples/MACD/MACD Sample.mq5", bem como LoadIncludes = true, obtemos o seguinte resultado (a lista de métodos é enormemente reduzida):
Processing Sources/Experts/Examples/MACD/MACD Sample.mq5 Scanning... #include <Trade\Trade.mqh> Including Sources/Include/Trade\Trade.mqh #include <Object.mqh> Including Sources/Include/Object.mqh #include "StdLibErr.mqh" Including Sources/Include/StdLibErr.mqh #include "OrderInfo.mqh" Including Sources/Include/Trade/OrderInfo.mqh #include <Object.mqh> Including Sources/Include/Object.mqh #include "SymbolInfo.mqh" Including Sources/Include/Trade/SymbolInfo.mqh #include <Object.mqh> Including Sources/Include/Object.mqh #include "PositionInfo.mqh" Including Sources/Include/Trade/PositionInfo.mqh #include <Object.mqh> Including Sources/Include/Object.mqh #include "SymbolInfo.mqh" Including Sources/Include/Trade/SymbolInfo.mqh #include <Trade\PositionInfo.mqh> Including Sources/Include/Trade\PositionInfo.mqh #include <Object.mqh> Including Sources/Include/Object.mqh #include "SymbolInfo.mqh" Including Sources/Include/Trade/SymbolInfo.mqh Files processed: 8 Source length: 175860 File map: Sources/Experts/Examples/MACD/MACD Sample.mq5 0 Sources/Include/Trade\Trade.mqh 900 Sources/Include/Object.mqh 1277 Sources/Include/StdLibErr.mqh 1657 Sources/Include/Object.mqh 2330 Sources/Include/Trade\Trade.mqh 3953 Sources/Include/Trade/OrderInfo.mqh 4004 Sources/Include/Trade/SymbolInfo.mqh 4407 Sources/Include/Trade/OrderInfo.mqh 38837 Sources/Include/Trade\Trade.mqh 59925 Sources/Include/Trade/PositionInfo.mqh 59985 Sources/Include/Trade\Trade.mqh 75648 Sources/Experts/Examples/MACD/MACD Sample.mq5 143025 Sources/Include/Trade\PositionInfo.mqh 143091 Sources/Experts/Examples/MACD/MACD Sample.mq5 158754 Lines: 4170 Tokens: 18005 Defining grammar... Parsing... CObject :: CObject * Prev ( void ) const CObject :: void Prev ( CObject * node ) CObject :: CObject * Next ( void ) const CObject :: void Next ( CObject * node ) CObject :: virtual bool Save ( const int file_handle ) CObject :: virtual bool Load ( const int file_handle ) CObject :: virtual int Type ( void ) const CObject :: virtual int Compare ( const CObject * node , const int mode = 0 ) const CSymbolInfo :: string Name ( void ) const CSymbolInfo :: bool Name ( const string name ) CSymbolInfo :: bool Refresh ( void ) CSymbolInfo :: bool RefreshRates ( void ) ... CSampleExpert :: bool Init ( void ) CSampleExpert :: void Deinit ( void ) CSampleExpert :: bool Processing ( void ) CSampleExpert :: bool InitCheckParameters ( const int digits_adjust ) CSampleExpert :: bool InitIndicators ( void ) CSampleExpert :: bool LongClosed ( void ) CSampleExpert :: bool ShortClosed ( void ) CSampleExpert :: bool LongModified ( void ) CSampleExpert :: bool ShortModified ( void ) CSampleExpert :: bool LongOpened ( void ) CSampleExpert :: bool ShortOpened ( void ) Success Class hierarchy: CObject ^ +--CSymbolInfo +--COrderInfo +--CPositionInfo +--CTrade +--CPositionInfo CSampleExpert
Agora experimentamos um projeto de terceiros. Eu usei o EA SlidingPuzzle2 deste artigo. Ele está no caminho SourceFile = "Sources/Experts/Examples/Layouts/SlidingPuzzle2.mq5". Também ao conectar todos os arquivos de cabeçalho (LoadIncludes = true), obtemos o resultado (reduzido):
Processing Sources/Experts/Examples/Layouts/SlidingPuzzle2.mq5 Scanning... #include "SlidingPuzzle2.mqh" Including Sources/Experts/Examples/Layouts/SlidingPuzzle2.mqh #include <Layouts\GridTk.mqh> Including Sources/Include/Layouts\GridTk.mqh #include "Grid.mqh" Including Sources/Include/Layouts/Grid.mqh #include "Box.mqh" Including Sources/Include/Layouts/Box.mqh #include <Controls\WndClient.mqh> Including Sources/Include/Controls\WndClient.mqh #include "WndContainer.mqh" Including Sources/Include/Controls/WndContainer.mqh #include "Wnd.mqh" Including Sources/Include/Controls/Wnd.mqh #include "Rect.mqh" Including Sources/Include/Controls/Rect.mqh #include <Object.mqh> Including Sources/Include/Object.mqh #include "StdLibErr.mqh" Including Sources/Include/StdLibErr.mqh #include "Scrolls.mqh" Including Sources/Include/Controls/Scrolls.mqh #include "WndContainer.mqh" Including Sources/Include/Controls/WndContainer.mqh #include "Panel.mqh" Including Sources/Include/Controls/Panel.mqh #include "WndObj.mqh" Including Sources/Include/Controls/WndObj.mqh #include "Wnd.mqh" Including Sources/Include/Controls/Wnd.mqh #include <Controls\Edit.mqh> Including Sources/Include/Controls\Edit.mqh #include "WndObj.mqh" Including Sources/Include/Controls/WndObj.mqh #include <ChartObjects\ChartObjectsTxtControls.mqh> Including Sources/Include/ChartObjects\ChartObjectsTxtControls.mqh #include "ChartObject.mqh" Including Sources/Include/ChartObjects/ChartObject.mqh #include <Object.mqh> Including Sources/Include/Object.mqh Files processed: 17 Source length: 243134 File map: Sources/Experts/Examples/Layouts/SlidingPuzzle2.mq5 0 Sources/Experts/Examples/Layouts/SlidingPuzzle2.mqh 493 Sources/Include/Layouts\GridTk.mqh 957 Sources/Include/Layouts/Grid.mqh 1430 Sources/Include/Layouts/Box.mqh 1900 Sources/Include/Controls\WndClient.mqh 2377 Sources/Include/Controls/WndContainer.mqh 2760 Sources/Include/Controls/Wnd.mqh 3134 Sources/Include/Controls/Rect.mqh 3509 Sources/Include/Controls/Wnd.mqh 14312 Sources/Include/Object.mqh 14357 Sources/Include/StdLibErr.mqh 14737 Sources/Include/Object.mqh 15410 Sources/Include/Controls/Wnd.mqh 17033 Sources/Include/Controls/WndContainer.mqh 46214 Sources/Include/Controls\WndClient.mqh 61689 Sources/Include/Controls/Scrolls.mqh 61733 Sources/Include/Controls/Panel.mqh 62137 Sources/Include/Controls/WndObj.mqh 62514 Sources/Include/Controls/Panel.mqh 72881 Sources/Include/Controls/Scrolls.mqh 78251 Sources/Include/Controls\WndClient.mqh 103907 Sources/Include/Layouts/Box.mqh 115349 Sources/Include/Layouts/Grid.mqh 126741 Sources/Include/Layouts\GridTk.mqh 131057 Sources/Experts/Examples/Layouts/SlidingPuzzle2.mqh 136066 Sources/Include/Controls\Edit.mqh 136126 Sources/Include/ChartObjects\ChartObjectsTxtControls.mqh 136555 Sources/Include/ChartObjects/ChartObject.mqh 137079 Sources/Include/ChartObjects\ChartObjectsTxtControls.mqh 177423 Sources/Include/Controls\Edit.mqh 213551 Sources/Experts/Examples/Layouts/SlidingPuzzle2.mqh 221772 Sources/Experts/Examples/Layouts/SlidingPuzzle2.mq5 241539 Lines: 6102 Tokens: 27248 Defining grammar... Parsing... CRect :: CPoint LeftTop ( void ) const CRect :: void LeftTop ( const int x , const int y ) CRect :: void LeftTop ( const CPoint & point ) ... CSlidingPuzzleDialog :: virtual bool Create ( const long chart , const string name , const int subwin , const int x1 , const int y1 , const int x2 , const int y2 ) CSlidingPuzzleDialog :: virtual bool OnEvent ( const int id , const long & lparam , const double & dparam , const string & sparam ) CSlidingPuzzleDialog :: void Difficulty ( int d ) CSlidingPuzzleDialog :: virtual bool CreateMain ( const long chart , const string name , const int subwin ) CSlidingPuzzleDialog :: virtual bool CreateButton ( const int button_id , const long chart , const string name , const int subwin ) CSlidingPuzzleDialog :: virtual bool CreateButtonNew ( const long chart , const string name , const int subwin ) CSlidingPuzzleDialog :: virtual bool CreateLabel ( const long chart , const string name , const int subwin ) CSlidingPuzzleDialog :: virtual bool IsMovable ( CButton * button ) CSlidingPuzzleDialog :: virtual bool HasNorth ( CButton * button , int id , bool shuffle = false ) CSlidingPuzzleDialog :: virtual bool HasSouth ( CButton * button , int id , bool shuffle = false ) CSlidingPuzzleDialog :: virtual bool HasEast ( CButton * button , int id , bool shuffle = false ) CSlidingPuzzleDialog :: virtual bool HasWest ( CButton * button , int id , bool shuffle = false ) CSlidingPuzzleDialog :: virtual void Swap ( CButton * source ) Success Class hierarchy: CPoint CSize CRect CObject ^ +--CWnd | ^ | +--CDragWnd | +--CWndContainer | | ^ | | +--CScroll | | | ^ | | | +--CScrollV | | | +--CScrollH | | +--CWndClient | | ^ | | +--CBox | | ^ | | +--CGrid | | ^ | | +--CGridTk | +--CWndObj | ^ | +--CPanel | +--CEdit +--CGridConstraints +--CChartObject ^ +--CChartObjectText ^ +--CChartObjectLabel ^ +--CChartObjectEdit | ^ | +--CChartObjectButton +--CChartObjectRectLabel CAppDialog ^ +--CSlidingPuzzleDialog
Aqui a hierarquia de classes é o mais interessante.
Apesar do fato de que testei o analisador em diferentes projetos, ele definitivamente não correrá bem em alguns programas. Um dos problemas está relacionado ao processamento de macros. Como mencionado anteriormente, uma análise correta envolve uma interpretação dinâmica e abertura de macros com substituição de resultados no código fonte antes do começo da análise.
Na gramática MQL atual, foi feita uma tentativa de designar uma chamada de macro como uma chamada de função menos restrita, mas isso nem sempre funciona.
Por exemplo, na biblioteca TypeToBytes, parâmetros de macro são usados para gerar meta-tipos. Veja um dos casos:
#define _C(A, B) CASTING<A>::Casting(B)
Além disso, essa macro é usada da seguinte maneira:
Res = _C(STRUCT_TYPE<T1>, Tmp);
Ao tentar iniciar o analisador neste código, ele não pode "compreender" STRUCT_TYPE<T1>, porque, na realidade, este parâmetro é um tipo de modelo, enquanto o analisador pressupõe um valor, ou, num sentido mais amplo, uma expressão (e, em particular, interpreta os caracteres '<', '>' como operação de comparação). Agora as chamadas de macros (após as quais não há ponto ou vírgula) geram um problema semelhante, que pode ser contornado inserindo um ';' no código fonte que está sendo processado.
Os interessados podem realizar o experimento número 3 (os dois primeiros foram mencionados no início do artigo), que consiste em encontrar uma solução alternativa para modificar a gramática atual com regras de macros que permitam analisar com sucesso esses casos complexos.Fim do artigo
Consideramos a maneira mais simples e eficiente de analisar dados, incluindo a análise de códigos fonte em MQL. Para fazer isso, foram apresentadas a gramática MQL e a implementação de ferramentas padrão, nomeadamente um scanner e um analisador. As estruturas de códigos fonte obtidas com a ajuda delas permitem calcular suas estatísticas, determinar indicadores de qualidade, construir dependências, alterar automaticamente a formatação.
Além disso, a implementação apresentada requer uma série de melhorias para atingir 100% de compatibilidade com projetos MQL complexos, em particular, em termos de suporte para expansão macros.
Com uma preparação mais profunda, salvando informações sobre as entidades encontradas na tabela de nomes, essa abordagem também pode permitir gerar código, monitorar erros típicos e executar outras tarefas mais complexas.
Traduzido do russo pela MetaQuotes Ltd.
Artigo original: https://www.mql5.com/ru/articles/5638
![Integração da MetaTrader 5 e Python: recebendo e enviando dados](https://c.mql5.com/2/35/mt5-3002__1.png)
![O poder do ZigZag (parte II). Exemplos de recebimento, processamento e exibição de dados](https://c.mql5.com/2/35/MQL5-avatar-zigzag_head__1.png)
![Estudo de técnicas de análise de velas (Parte II): Busca automática de novos padrões](https://c.mql5.com/2/35/Pattern_I__3.png)
![Estudo de técnicas de análise de velas (parte I): Verificação de padrões existentes](https://c.mql5.com/2/35/Pattern_I__2.png)
![MQL5 - Linguagem para estratégias de negociação inseridas no terminal do cliente MetaTrader 5](https://c.mql5.com/i/registerlandings/logo-2.png)
- Aplicativos de negociação gratuitos
- 8 000+ sinais para cópia
- Notícias econômicas para análise dos mercados financeiros
Você concorda com a política do site e com os termos de uso