Faire du "look-ahead" avec OcamlLex

Pour tenter de résoudre un conflit

Le problème exposé dans ce sujet a été résolu.

Salut,

Je dois parser une grammaire qui malheureusement a, en l’état, un conflit de shift reduce. Et je ne peux pas faire grand chose pour changer la grammaire en question. J’ai essayé de simplifier au maximum (et j’espère n’avoir pas trop simplifié).

En gros, j’ai des règles qui ont une forme comme:

list_inst: 
    { [] }
| inst list_inst { $1 :: $2 }

inst:
| IF exp inst { ... }
| IF exp inst ELSE inst { ... }
| IF exp inst OPEN_SPECIAL ELSE inst CLOSE_SPECIAL { ... }
| OPEN_SPECIAL inst CLOSE_SPECIAL { ... }
...

Le problème, c’est que si je suis dans un état:

IF exp inst ELSE . OPEN_SPECIAL

Le parseur ne peut pas savoir si je suis en train d’activer la troisième règle de inst ou si je suis en train d’activer la quatrième règle, depuis la règle list_inst. L’idéal dans ce cas serait de pouvoir changer la grammaire mais je n’en ai pas vraiment la liberté.

Du coup, je pensais utiliser le lexer pour aller jeter un oeil un peu en avant histoire de regarder ce que j’y trouve. Avec dans l’idée de dire "si je tombe sur ELSE, plutôt que mettre un token OPEN_SPECIAL, je met un token OPEN_SPECIAL_ELSE", ce qui règlerait le problème de la grammaire.

Du coup dans le lexer, j’ai tenté un truc super élégant à base de:

| "open_special" {
     let pos = lexbuf.Lexing.lex_curr_pos in
     look_for_else lexbuf ;
     lexbuf.Lexing.lex_curr_pos <- pos ;
     OPEN_SPECIAL
  }
and look_for_else = parse
| blank { look_for_else lexbuf }
| "else" { next_else_special := true }
| "//" { do_lex_comment lexbuf }
| _ { () }

Juste pour voir si déjà je pouvais faire mon backtracking tranquillement, sans même tenter d’insérer quoi que ce soit pour l’instant. Mais ça explose (sur une opération refill_buff). Alors avant d’investiguer plus (parce que le programme en question n’est pas un petit morceau), je voudrais déjà savoir si cette idée à la moindre chance de fonctionner ou si quelque chose d’intrinsèque à OcamlLex (dans la manière dont il gère le buffer par exemple) l’empêche complètement.

+0 -0

(Le problème arrive quand tu es dans l’état IF exp inst . OPEN_SPECIAL, sans le ELSE)

Est-ce que tu ne peux pas juste avoir une règle open_special else dans ton lexer, qui serait prioritaire sur la règle qui lexe open_special parce qu’elle matche quelque chose de plus long ? Si tu n’as que des blancs et que tes commentaires sont "jusqu’à la fin de la ligne", ça s’écrit assez bien.

Sinon, plutôt que d’essayer de faire le malin sur le buffer du lexer (ça peut sans doute marcher, ça n’est certainement pas une bonne idée), tu peux avoir un intermédiaire entre le flux de tokens qu’il génère et ton parser qui transforme simplement "OPEN_SPECIAL ELSE" en "ELSE_SPECIAL". Puisque Menhir prend en paramètre une fonction de type Lexing.lexbuf -> token, il suffit a priori d’écrire une fonction qui, pour renvoyer ce token, appelle ton lexer et l’appelle une deuxième fois lorsqu’elle tombe sur OPEN_SPECIAL. Quelque chose de ce genre (pas testé) :

let fix_lexer =
  let buffer = ref None in
  fun lexbuf ->
    match !buffer with
    | Some not_else_token -> not_else_token
    | None ->
      let token = Lexer.lexer lexbuf in
      if token = OPEN_SPECIAL
      then
        let token' = Lexer.lexer lexbuf in
        if token' = ELSE
        then ELSE_SPECIAL
        else begin
          buffer := Some token';
          OPEN_SPECIAL
        end
+0 -0

Est-ce que tu ne peux pas juste avoir une règle open_special else dans ton lexer, qui serait prioritaire sur la règle qui lexe open_special parce qu’elle matche quelque chose de plus long ? Si tu n’as que des blancs et que tes commentaires sont "jusqu’à la fin de la ligne", ça s’écrit assez bien.

Juste pour être sûr de bien comprendre, est-ce que

open_special
  // truc
  // machin
  else

serait parsable ? J’ai l’impression que c’est ce que tu dis mais je ne suis pas sûr de voir comment dans ce cas je dois écrire la ligne en question (pour le coup, je ne connais pas très bien le fonctionnement des outils de parsing). Parce que ce serait clairement le plus facile pour moi en l’état je pense.

Hum. Encore que, il faut que je regarde ce que l’on conserve dans les commentaires.

…., tu peux avoir un intermédiaire entre le flux de tokens qu’il génère et ton parser qui transforme simplement "OPEN_SPECIAL ELSE" en "ELSE_SPECIAL". Puisque Menhir prend en paramètre une fonction de type Lexing.lexbuf -> token, il suffit a priori d’écrire une fonction qui, pour renvoyer ce token, appelle ton lexer et l’appelle une deuxième fois lorsqu’elle tombe sur OPEN_SPECIAL. Quelque chose de ce genre (pas testé) :

[code]

Eusèbe

C’est ce que j’ai commencé à explorer après avoir envoyé mon post (même si pour ma part, je suis avec OcamlYacc et pas Menhir, mais j’ai vu des bouts de code qui semblent faire ce genre de chose dans le parser actuel). Il faut juste que je trouve où m’insérer dans le processus de parsing parce que sur ce point là, j’ai assez fortement simplifié, l’ensemble est plus dispersé que ce que j’ai écris plus haut. Même si ce n’est pas insurmontable, ça pourrait être pénible.

+0 -0

Est-ce que tu ne peux pas juste avoir une règle open_special else dans ton lexer, qui serait prioritaire sur la règle qui lexe open_special parce qu’elle matche quelque chose de plus long ? Si tu n’as que des blancs et que tes commentaires sont "jusqu’à la fin de la ligne", ça s’écrit assez bien.

Juste pour être sûr de bien comprendre, est-ce que

open_special
  // truc
  // machin
  else

serait parsable ? J’ai l’impression que c’est ce que tu dis mais je ne suis pas sûr de voir comment dans ce cas je dois écrire la ligne en question (pour le coup, je ne connais pas très bien le fonctionnement des outils de parsing). Parce que ce serait clairement le plus facile pour moi en l’état je pense.

Oui, parce que ces commentaires sont reconnaissables par une regex simple du genre //[^\n]*\n (tu n’as pas besoin d’une règle dédiée, qui sert en général plutôt pour parser des commentaires /* ... */ imbriqués, qui ne sont plus réguliers).

Tu peux donc juste écrire une règle comme open_special (blank|comment)* else pour trouver les ELSE_SPECIAL.

Si tu as des commentaires plus compliqués, tu peux aussi t’en sortir avec des règles dédiées, mais je ne pense pas que tu puisses faire beaucoup plus lisible qu’avec un post-traitement (autant éliminer au maximum ce qui n’est pas régulier — donc les commentaires — avant de modifier le flux).

…., tu peux avoir un intermédiaire entre le flux de tokens qu’il génère et ton parser qui transforme simplement "OPEN_SPECIAL ELSE" en "ELSE_SPECIAL". Puisque Menhir prend en paramètre une fonction de type Lexing.lexbuf -> token, il suffit a priori d’écrire une fonction qui, pour renvoyer ce token, appelle ton lexer et l’appelle une deuxième fois lorsqu’elle tombe sur OPEN_SPECIAL. Quelque chose de ce genre (pas testé) :

[code]

Eusèbe

C’est ce que j’ai commencé à explorer après avoir envoyé mon post (même si pour ma part, je suis avec OcamlYacc et pas Menhir, mais j’ai vu des bouts de code qui semblent faire ce genre de chose dans le parser actuel).

Tu dois passer à Menhir si tu en as la possibilité, mais en l’occurrence ça ne change pas grand chose.

Il faut juste que je trouve où m’insérer dans le processus de parsing parce que sur ce point là, j’ai assez fortement simplifié, l’ensemble est plus dispersé que ce que j’ai écris plus haut. Même si ce n’est pas insurmontable, ça pourrait être pénible.

Ksass`Peuk

Comment appelles-tu ton parser ? Ocamlyacc transforme tes règles principales (qui renvoient, disons, un Ast.t) en fonctions de type (Lexing.lexbuf -> token) -> lexbuf -> Ast.t. De son côté, ocamllex transforme tes règles en fonctions de type Lexing.lexbuf -> token. Appelées sur un lexbuf, elles lisent ce qu’il faut (et retirent ces caractères du lexbuf) avant de renvoyer le prochain token.

Dans une configuration simple, comme les types ont le bon goût de s’emboîter, on écrit donc quelque chose comme fun filename -> Parser.regle_principale Lexer.regle_principale (Lexing.from_channel @@ open_in filename) pour obtenir une fonction de type string (* filename *) -> Ast.t.

Ici, au lieu d’utiliser Lexer.regle_principale comme fournisseur de token, on utiliserait le wrapper fix_lexer, qui a le même comportement sauf qu’il modifie la sortie en cas de open_special else. S’il existe déjà des fonctions de ce genre dans ton code, tu peux sans doute les regrouper dans un module intermédiaire de traitement de flux. Note quand même que, selon ton code, avoir un gros amas de fonctions comme ça n’est pas forcément la meilleure façon de faire — mais on ne peut pas dire grand chose de plus sans connaître le reste.

+0 -0

Oui, parce que ces commentaires sont reconnaissables par une regex simple du genre //[^\n]*\n (tu n’as pas besoin d’une règle dédiée, qui sert en général plutôt pour parser des commentaires /* ... */ imbriqués, qui ne sont plus réguliers).

Tu peux donc juste écrire une règle comme open_special (blank|comment)* else pour trouver les ELSE_SPECIAL.

Ok, je comprends mieux.

Si tu as des commentaires plus compliqués, tu peux aussi t’en sortir avec des règles dédiées, mais je ne pense pas que tu puisses faire beaucoup plus lisible qu’avec un post-traitement (autant éliminer au maximum ce qui n’est pas régulier — donc les commentaires — avant de modifier le flux).

Il faut surtout que je regarde si on y conserve des choses. Mais ça m’éclaire déjà pas mal. Merci.

Tu dois passer à Menhir si tu en as la possibilité, mais en l’occurrence ça ne change pas grand chose.

Cette décision là n’est pas de mon ressort pour le coup.

Comment appelles-tu ton parser ?

[…]

Ici, au lieu d’utiliser Lexer.regle_principale comme fournisseur de token, on utiliserait le wrapper fix_lexer, qui a le même comportement sauf qu’il modifie la sortie en cas de open_special else. S’il existe déjà des fonctions de ce genre dans ton code, tu peux sans doute les regrouper dans un module intermédiaire de traitement de flux. Note quand même que, selon ton code, avoir un gros amas de fonctions comme ça n’est pas forcément la meilleure façon de faire — mais on ne peut pas dire grand chose de plus sans connaître le reste.

Eusèbe

Je m’étais pas posé la question, j’avoue :honte: .

Je vais déjà essayer de me brancher là dedans et faire quelques tests de performances pour voir si je ne mets pas à trop à mal le temps de parsing. Merci :) .

+0 -0

De retour après avoir mis en place une solution qui marche bien. On a finalement dû opter pour une modification du lexer, mais aussi, plus intéressant, quelques petites modifs dans le parseur.

La solution consistant à se placer entre le lexeur et le parseur n’était finalement pas trop pratique. Elle nécessitait trop de temps de calcul pour une fonctionnalité qui ne va servir que très ponctuellement. Aussi on a ajouté une règle dans le lexer pour générer un token SPECIAL_ELSE lorsque l’on recontrait les mots clés en question. Et au passage on a eu quelques petits cas particulier rigolos à gérer.

Un point plus intéressant, c’est ce qu’on a fait dans le parseur pour régler le conflit, qui apparaissait toujours avec le nouveau token :) (mais le nouveau token nous a quand même bien arranger). Pour aider le parseur, on a utilisé le mot-clé %prec pour choisir le cas le plus pertinent. En gros, à la place des règles que j’ai mis plus haut, on a maintenant quelque chose comme:

/* operator precedence */
%nonassoc   IF_NO_ELSE
%nonassoc   SPECIAL_ELSE_NO_ELSE
%nonassoc   ELSE SPECIAL_ELSE

else_part:
/* empty */ { ... }
    %prec IF_NO_ELSE /* To attach the next else to the current if */
|   ELSE inst { ... }
|   SPECIAL_ELSE inst CLOSE_SPECIAL { ... }
    %prec SPECIAL_ELSE_NO_ELSE /* To force the normal else to be attached to the current if */
|   SPECIAL_ELSE inst CLOSE_SPECIAL ELSE inst
    { error }

inst:
| IF exp inst else_part{ ... }
| OPEN_SPECIAL inst CLOSE_SPECIAL { ... }
...

Ce qui permet de régler les conflits et de détecter les cas non valides de manière relativement simple. (Le dernier cas peut, peut-être, paraître bizarre mais c’est probablement dû à un détail dans le fonctionnement de nos règles, donc si c’est le cas, il faut juste retenir le coup du %prec qui résout le premier conflit).

Merci en tout cas :)

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte