Análise sintática incremental

[P.]

Estou experimentando um programa baseado num "parser reiniciável"; um
parser que "pausa" quando a entrada está incompleta.

Alguém já trabalhou com algo do tipo antes?

Estou buscando formas de representar esse tipo de algoritmo em código.
Meu único exemplo útil por enquanto é baseado em máquina de estados.

--
P.

[Felipe Magno de Almeida]

2008/10/20 P. <pedro....@member.fsf.org>:

Cara, eu comecei a ver isso no boost.spirit.
Mas meu problema na época, era que nem eu mesmo sabia
se a entrada tinha acabado ou não. Isso complicava
um pouco, depois de fazer alguns profiles, decidi
que o custo de reiniciar era minimo, e que a necessidade
de faze-lo era ainda menor (a entrada era quase sempre
completa). Entao deixei de lado.

http://mail.google.com/mail/#search/from%3Ame+spirit/1087c327b811a72f

> --
> P.

[snip]

--
Felipe Magno de Almeida

[Bru++]

On 20 out, 16:20, "Felipe Magno de Almeida"
<felipe.m.alme...@gmail.com> wrote:
> 2008/10/20 P. <pedro.lama...@member.fsf.org>:

Deixa eu ver se entendi... Você quer algo como o parser do
interpretador Python, por exemplo??

[]'s

[Thiago Silva]

2008/10/20 P. <pedro....@member.fsf.org>:

Eu, particularmente, nunca vi algo sobre "parser reiniciável
(agradeceria algumas referências :)

Além de fazer o parser como uma máquinas de estados, acho que vc pode
"memoizar" os resultados. Ou seja, na medida em que a entrada é
aceita, armazenar os resultados de cada regra, a regra em si e a
posição da entrada atual em uma tabela. A reinicialização então usaria
as informações da tabela ao invés de percorrer a entrada, enquanto
tais informações existem (do contrário, o parsing normal volta a
ocorrer). Já que utilizar os resultados anteriores é mais rápido do
que refazer o parsing novamente, isso poderia dar a sensação de
"resume".

[]'s
--
Thiago Silva,
mailto: tsilva at sourcecraft info
jabber: tsi...@jabber.org
http://sourcecraft.info/blog

[P.]

On 21 out, 14:46, "Thiago Silva" <tsilva...@gmail.com> wrote:

> Além de fazer o parser como uma máquinas de estados, acho que vc pode
> "memoizar" os resultados. Ou seja, na medida em que a entrada é
> aceita, armazenar os resultados de cada regra, a regra em si e a
> posição da entrada atual em uma tabela. A reinicialização então usaria
> as informações da tabela ao invés de percorrer a entrada, enquanto
> tais informações existem (do contrário, o parsing normal volta a
> ocorrer). Já que utilizar os resultados anteriores é mais rápido do
> que refazer o parsing novamente, isso poderia dar a sensação de
> "resume".

O que eu estou fazendo agora é representar toda a gramática como
máquina de estados "interrompível".

Quando o programa alimenta o parser com dados parciais, o parser
procura em uma "tabela" que ação tomar para aquele token, o que pode
simplemente acumular dados em algum elemento da estrutura final ou
mudar para algum outro estado.
Quando a entrada acaba, o parser mantém o último estado visto, de modo
que a próxima atualização reinicia o processo do ponto onde parou.

Essa técnica funcionou bem para uma gramática pequena; não tenho
certeza se será viável para uma gramática grande.
A "tabela" no meu programa é na prática um switch da linguagem de
programação.

Creio que a minha abordagem realiza sua idéia, já que a "estrutura
parcial" mantida pelo parser enquanto o estado final não chega pode
ser entendida como os dados "memoized".

Estou interessado em outras abordagens para realizar esse tipo de
coisa.

--
P.

[Rodrigo Kumpera]

Ou você não está sabendo explicar o problema, ou não sabe como implementá-lo da forma correta - usando a abstração errada.

A não ser que teu parser seja implementado como recursivo descendente, o final da entrada é marcado
por um símbolo próprio, oque torna trivial usar um processo incremental. Flex/Bison geram lexer/parsers dessa forma.

O lexer é um NFA para regex - construir ou gerar um é trivial - um pouco mais difícil se o estado não for codificado na pilha de ativação.
O parser é LARL implementado com uma máquina de pilha para poder fazer shift/reduce. Não faz sentido produzir um na mão quanto tem ferramentas para isso.

Toda ferramenta de geração lexer/parser que eu trabalhei é capaz de produzir código que consome a entrada de forma progressiva.

2008/10/20 P. <pedro....@member.fsf.org>

[P.]

On 21 out, 18:22, "Rodrigo Kumpera" <kump...@gmail.com> wrote:

> Ou você não está sabendo explicar o problema, ou não sabe como implementá-lo
> da forma correta - usando a abstração errada.

> Toda ferramenta de geração lexer/parser que eu trabalhei é capaz de produzir
> código que consome a entrada de forma progressiva.

Eu provavelmente sou bastante ignorante sobre o universo de
ferramentas disponíveis.

Meu problema é que, como eu obtenho dados para análise em blocos
distintos, preciso chamar a função responsável por análise sintática
diversas vezes, a cada vez que um novo bloco de dados é obtido.
Meu objetivo é não necessitar acumular dados parciais para re-análise
enquanto a "mensagem" completa não chega.

Qualquer ferramenta de geração de lexer/parser é capaz de gerar esse
tipo de programa?

Todos os exemplos que eu conheço produzem código que "fracassa" para
uma entrada incompleta, exigindo acumulação de dados e uma "nova
tentativa" posterior.

--
P.

[Thiago Silva]

2008/10/21 P. <pedro....@member.fsf.org>:

> Creio que a minha abordagem realiza sua idéia, já que a "estrutura
> parcial" mantida pelo parser enquanto o estado final não chega pode
> ser entendida como os dados "memoized".
>

Sim, eu não vejo muito sentido em tentar casar o que propus com uma
implementação de parser com máquina de estados. Acho que a memoização
seria útil caso vc, por algum motivo, mudasse a abordagem de
implementação do parser para, por exemplo, preditivo recursivo. Ou
seja, uma outra abordagem, por completo.

Por outro lado, se já se tem uma máquina de estados, não estou
entendendo o porquê de buscar uma outra forma de fazer o que procura,
afinal, imagino que manter o registro de elementos como a posição de
entrada, o estado atual e a pilha seja suficiente para reiniciar o
processo de um ponto arbitrário.

[P.]

On 21 out, 23:40, "Thiago Silva" <tsilva...@gmail.com> wrote:

> Por outro lado, se já se tem uma máquina de estados, não estou
> entendendo o porquê de buscar uma outra forma de fazer o que procura,
> afinal, imagino que manter o registro de elementos como a posição de
> entrada, o estado atual e a pilha seja suficiente para reiniciar o
> processo de um ponto arbitrário.

Eu não posso manter "posição de entrada" -- essa noção não existe.
Minha entrada ocorre na forma de blocos dispersos de dados.

Acho que eu devo uma explicação mais prolongada.

Considere um objeto data_source que, periodicamente, obtém dados de um
dispositivo qualquer.
Este objeto possui uma referência para um objeto transport_analyzer,
para o qual entrega estes dados.

A responsabilidade do objeto transport_analyzer é reconstituir
"mensagens"; como os dados são obtidos em pedaços, uma mensagem pode
estar em pedaços, composta por vários blocos.
Este objeto possuirá uma operação da forma:

void update ( buffer_ptr data );

que data_source usa para notificá-lo da chegada de novos dados.

Considere o problema de reconstituição de uma "mensagem".
Após a chegada do primeiro pedaço de dados, podemos ter ou não ter uma
mensagem completa.

Com um analisador simples, capaz de analisar tudo ou nada, é
necessário acumular os dados parciais em caso de fracasso de análise
em algum lugar.
Quando novos dados chegarem, é preciso concatená-los com os dados
acumulados e tentar análise novamente.
Este processo deve ser repetido até que se obtenha o sucesso.

Quando se obtém o sucesso, dados podem restar no acúmulo.
É preciso retirar do acúmulo os dados da mensagem recém-completada.

Eu desejo evitar todo esse procedimento com um analisador não-trivial
capaz de "pausa" ou "interrupção" por conta de dados incompletos.
Algo funcionalmente análogo à forma típica de uma função de digest
criptográfico, análoga mesmo ao próprio transport_analyzer acima, com
uma função do tipo:

parse_info update ( buffer_ptr data );

que retomasse a análise do estado onde parou continuamente até que
encontrasse o estado final, significando "mensagem completa".

Minha implementação, para um certo protocolo de rede, do esquema acima
é baseada em uma máquina de estados; o analisador atua sobre um token
consultando uma tabela de ações para o estado atual. Quando a entrada
se esgota, o analisador retorna, mantendo o conhecimento sobre o
estado; quando uma nova entrada surge, a análise reinicia
naturalmente, atuando sobre o primeiro novo token com base no estado
memorizado.

O uso deste analisador é, aproximadamente:

void update ( data_range_ptr data ) {

result r = m_parser.update( data->begin(), data->end() );

while ( r.message != NULL ) {

this->notify( r.message );

r = m.parser( r.position, data->end() );

}

}

--
P.

[Cesar Mello]

 

http://sentinelas.org/mello/ulbra/tcc1/Artigo_TC1_Cesar.pdf

[]

Mello

 

2008/10/21 P. <pedro....@member.fsf.org>

[Rodrigo Kumpera]

2008/10/21 P. <pedro....@member.fsf.org>

 Não vou dizer que qualquer ferramenta é capaz, porém flex/bison conseguem.
No caso do flex basta definir yywrap e YY_INPUT.

Recomendo ver o antlr também, pois ele possui uma sintaxe muito mais fácil de trabalhar.

[P.]

On 22 out, 01:06, "Rodrigo Kumpera" <kump...@gmail.com> wrote:

>  Não vou dizer que qualquer ferramenta é capaz, porém flex/bison conseguem.
> No caso do flex basta definir yywrap e YY_INPUT.

lex com yywrap não satisfaz o meu requisito.
Não há nada que yywrap possa fazer diante de um esgotamento de dados
que ocorra antes do parser estar completamente satisfeito.
O parser é acionado periodicamente pelo surgimento de dados parciais.

Meu sistema exige que o parser "interrompa" e retorne o controle, para
ser "reiniciado" posteriormente em novas condições.

--
P.

[Cesar Mello]

Isso não tem a ver com o algoritmo de análise, mas sim com a persistência de estado... Mas, não vamos começar aqui mais um caso de resolver dever de casa.

 

[]

Mello

2008/10/22 P. <pedro....@member.fsf.org>

[Thiago Silva]

2008/10/22 P. <pedro....@member.fsf.org>:

> Meu sistema exige que o parser "interrompa" e retorne o controle, para
> ser "reiniciado" posteriormente em novas condições.

E a sua abordagem não está funcionando?

[P.]

On 23 out, 02:16, "Thiago Silva" <tsilva...@gmail.com> wrote:
> 2008/10/22 P. <pedro.lama...@member.fsf.org>:

>
> > Meu sistema exige que o parser "interrompa" e retorne o controle, para
> > ser "reiniciado" posteriormente em novas condições.
>
> E a sua abordagem não está funcionando?

Funciona para o meu único caso de estudo atual, mensagens para um
protocolo simples cuja forma não é length-prefixed.
Entendo que protocolos com mensagens length-prefixed não se
beneficiariam muito desse tipo de otimização.

Como eu disse antes, estou buscando diversas formas de representar em
código esta idéia.

A única discussão sobre esse assunto que encontrei até agora indica
que uma segunda alternativa seria representar a análise como
"delimited continuations", sendo que a computação encontraria o
"limite" quando a entrada esgotasse, retornando uma "continuation
function" representativa do resto da análise.

A minha dúvida é a viabilidade de representar analisadores com esta
característica para gramáticas mais complexas.

Em breve vou publicar o estudo de caso completo que integra esta
sacanagem.

--
P.

[Cesar Mello]

Se quatro décadas de Ciência de Computação não são o suficiente pra convencer o Lamarão, quem sou eu pra dar conselhos...

 

É muito trabalho persistir uma pilha de inteiros representando os estados de um parser LR. Uma centena de inteiros para uma linguagem com a complexidade do Pascal será?

 

[]

Mello

2008/10/23 P. <pedro....@member.fsf.org>

[Rodrigo Kumpera]

2008/10/22 P. <pedro....@member.fsf.org>

 

Pois ai que você se engana. Basta aceitar EOF como um elemento de cada token e usá-lo para
parar o processo de scanning. O flex mantem o estado interno quando uma ação execute return.

É trivial, eu já fiz isso, a descrição do lexer fica mais complicada porém nada impossível.

Os dois únicos problemas de trabalhar dessa forma é que você deverá gerar um EOF sintético para
reduzir a produção para o símbolo inicial - se precisar.

O outro é o acúmulo do payload de cada token, que precisará ser feito manualmente, oque é problema
trivial que dificilmente tem como se escapar caso a gramática não permita tokens de tamanho arbitrário -
ambas funcionam bem com soluções de livro - olhe o dragon book.

Porém se você precisa trabalhar com zero copying, ai fica mais difícil pois tem que coordenar todo o
uso dos buffers.

Agora se você quer construir um parser manualmente e introduzir isso nele, a solução é aplicar CPS, seja
via corrotinas, uma linguagem com suporte adequado ao algum transformador de código.

[P.]

On 24 out, 18:15, "Rodrigo Kumpera" <kump...@gmail.com> wrote:
> 2008/10/22 P. <pedro.lama...@member.fsf.org>

> > Meu sistema exige que o parser "interrompa" e retorne o controle, para
> > ser "reiniciado" posteriormente em novas condições.
>
> Pois ai que você se engana. Basta aceitar EOF como um elemento de cada token
> e usá-lo para
> parar o processo de scanning. O flex mantem o estado interno quando uma ação
> execute return.
>
> É trivial, eu já fiz isso, a descrição do lexer fica mais complicada porém
> nada impossível.
>
> Os dois únicos problemas de trabalhar dessa forma é que você deverá gerar um
> EOF sintético para
> reduzir a produção para o símbolo inicial - se precisar.

Acho que com isto é possível representar um lexer que resolve o meu
problema.
Cada campo presente na estrutura-mensagem final seria representado
(tipicamente) por um "token complexo", composto por mais de um byte,
cuja regra é capaz de identificar um "token parcial".
Esta regra deve ser capaz de identificar subsequentes "tokens
parciais" que compõe logicamente o mesmo token quando concatenados.
A ação associada à regra acumula o "token parcial" na estrutura de
dados.

Percebi que o lex é capaz de produzir um analisador reentrante,
necessário no meu contexto geral, e que ele é capaz de usar como
entrada um buffer de dados pré-existente ao invés de um FILE*.

Vou tentar produzir uma versão do meu programa baseada em lex pra
fazer uma comparação útil quando puder publicar o código-fonte.

--
P.