Construindo um PARSER em javascript - I

Entender a filosofia e a construção de um PARSER de expressões aritméticas é muito importante para aqueles que pretendem fazer programas parametrizados ou com algumas macros ou scripts de configuração e até execução.

Expressão aritmética

As expressões aritméticas são compostas de operandos (números) e de operadores ("+", "-", "*", "/" e exponencial ["^"]).

O sinal dos operandos

Um dos dificultadoreS, que iremos constatar no momento da programação de um Parser, é que os operandos podem ter o sinal negativo. Isto poderá fazer com que dois operadores ("*-" ou "/-" ou "^-") apareçam juntos na expressão, quebrando a lógica natural esperada de OPERANDO-OPERADOR. Em nosso Parser, vamos armazenar os operandos conjuntamente com os seus sinais, e considerar que, na última prioridade de execução das operações, SÓ EXISTEM SOMAS.

A teoria em um diagrama

Percorrer expressões aritméticas é um procedimento cujo esquema geral está representado no diagrama a seguir:

Vamos percorrer a expressão aritmética geral mostrada em (1), caracter a caracter, discernindo, a cada um que é lido, se é um numeral, sinal ou operador aritmético (op1, op2, op3, ...), até alcançarmos o fim da expressão. Na primeira passada, o sinal do operando estará expresso como um operador. E como dissemos, quando encontrarmos o operador da subtração ("-"), o que faremos é colocá-lo como sinal do operando internamente em uma variável de memória, conjuntamente com o operando, e transformar o operador em operador de soma. Esta filosofia de interpretação da expressão aritmética vai economizar um operador, e impedirá a colisão de dois operadores, como ressaltamos mais acima ("O sinal dos operandos").

A prática em um diagrama exemplo

A seguir mostramos um exemplo prático do que falamos no item anterior, expresso em um diagrama:

Aqui estamos tratando das expressões seguindo a ordem de prioridade. Em outro post vamos tratar dos níveis de parênteses, assunto que vai fechar esta série.

Algumas diretrizes para um PARSER:

1. O rastreamento é feito da esquerda para a direita;
2. O rastreamento é feito caracter a caracter;
3. Os espaços entre os caracteres devem ser evitados e, caso existam, suprimidos;
4. A cada OPERADOR detectado, uma nova variável é reservada em um array;
5. O operador da subtração é convertida em sinal do número que o sucede;

A razão da diretriz 5 se explica pelo fato citado no item "O sinal dos operandos".

Fluxograma do Parser para expressões

Para deixar o procedimento bem explicado, vamos apresentar um fluxograma misto de instruções e dados:

EXPRESSAO - Variável do tipo string que armazena toda a expressão.
SINAL - Sinal do operando, levando em consideração a regra 5 citada.
[i] - Caracter sendo lido (indice i).
[i+1] - Caracter seguinte ao lido (índice i+1).
PROX_SINAL - Armazena o sinal do próximo operando, pois o sinal precede um operando.
ind - Indice para o array de variáveis que armazenam os operandos.
S - Variável que armazena os caracteres, um a um, rastreados de um operando. Quando é achado um operador, esta variável é esvaziada.

Resultado em debug

Executando o código (listagem completa no último post desta série) em javascript, obtemos o seguinte resultado no navegador:

O array exibido mostra os operandos tanto em itens sequenciais quanto em itens indexados pelos nomes das variáveis ("V01", "V02", ...).

Conclusão

O PARSE de expressões é uma operação simples, mas que exige a observância de sinais e operadores.

PARTE 2