• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

taviroquai

parser de expressoes logicas

6 mensagens neste tópico

Olá a todos.

Coloco a questão aqui porque é independente da liguagem que se quer implementar, embora possa dizer que estou a fazer em php (é pratico pois não tenho que compilar).

A questão é a seguinte, estou a fazer um simples parser.

INPUT 1 (string): '1 AND 0 OR 1 IF 0 OR NOT 1'

Para este input tenho um algoritmo recursivo (arvore) tendo as seguintes precedencias: 'NOT', 'OR', 'AND' e por fim 'IF'.

E parte-se do principio de que não existem erros de sintaxe. Isto não verifica sintaxe.

1.  função validar ($string)

2.        caso existe ' IF ' em $string:

3.              se validar ($if_arg1) então return validar ($if_arg2)

4.              senão return

5.        caso existe ' AND ' em $string

6.              return validar ($and_arg1) AND validar ($and_arg2)

7.        caso existe ' OR ' em $string

8.              return validar ($or_arg1) OR validar ($or_arg2)

9.        caso existe 'NOT ' em $string

10.            return NOT validar ($not_arg)

11.      return (int) $string

Sei que isto funciona mas sei que tem limitações defenindo estas precedencias... qual é a melhor forma de fazer uma arvore de expressões lógicas? E se tiver que permitir parentesis?

Obrigado  :confused:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

É mesmo isso...

Exemplos de algoritmos... encontrei alguns em http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

Pode-se resolver usando uma pilha (ou chamadas recursivas como fiz acima) e com restrinções definidas - regras.

Mais alguma observação, sugestão, ou cuidado a ter em conta? Performance?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não estás a pensar em implementar o algoritmo à mão, pois não? :confused:

Penso que qualquer linguagem hoje em dia deve ter ferramentas que te permitam apenas definir a gramática, e as operações a efectuar em cada passo do parsing, e a partir gerar o código.

De qualquer forma, penso que o algoritmo mais usado é o LR.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não estás a pensar em implementar o algoritmo à mão, pois não? :P

:confused: Não. Já vi que essa área de compiladores ainda é "muita fruta para a minha camioneta"...

Penso que qualquer linguagem hoje em dia deve ter ferramentas que te permitam apenas definir a gramática, e as operações a efectuar em cada passo do parsing, e a partir gerar o código.

Sim. É isso que vou tentar fazer... obrigado!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O lex/yac flex/bison e afins não serve?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora