|
LeParsing
Description du parsing d'une formule de logique modale.
parser Sommaire
Présentation du problèmeCe qu'il faut parserDans le cadre de ce projet, notre programme devra être capable de reconnaître et d'enregistrer une formule de la logique modale composée de connecteurs logiques. Cette formule vient des grammaires suivantes :
Ce choix a été fait car Ocaml ne possède pas les caractères spéciaux adéquates (comme en latex) pour une visualisation meilleure. La convention d'écriture est donnée plus bas. Le ParsingL'analyseur lexical et l'outil OcamllexL'analyseur lexical sert à transformer le flot de caractères passer en entrée, en un flot de lexèmes ou token. Le sous-langage créé par ces jetons va être utilisé dans l'analyseur syntaxique. L'outil utilisé pour la création de cette analyseur est nommé Ocamllex. Cet outil va, à partir d'un fichier dont sa création est trés simplifiée, créer de lui-même les fichiers .ml et .mli utilisés par le langage d'Ocaml. Il n'est plus alors besoin de créer de toute pièce un automate fini. Convention d'écritureLes conventions d'écriture que nous avons décidés sont ainsi :
Création du fichier lexer.mllLe fichier lexer.mll est le fichier utilisé par Ocamllex. Il est trés simple à construire :
open Parser
let Nec = "[]" let Poss = "<>" let Conj = "&&" let Disj = "||" rule token = parse
[' ' '\t'] { token lexbuf}
| litteral { LITTERAL(Lexing.lexeme lexbuf)}
| Neg { NEG }
| Nec { NEC }
| Poss { POSS }
| Conj { CONJ }
| Disj { DISJ }
| Imp { IMP }
| parouv { PAROUV }
| parfer { PARFER }
| [ '\n' ] { EOL }
| eof { raise Eof }Notre fichier est créé et la commande Ocamllex lexer.mll va créer les fichiers lexer.mli et lexer.ml que nous devrons compiler par Ocaml. Ce type de construction trés intuitif montre que quand l'analyseur trouve une chaine de caractères correpondant à l'une des reconnaissances, il va créé une suite de tokens représentant la formule parsée. L'analyseur syntaxique et l'outil OcamlyaccL'analyseur syntaxique va produire le code Ocaml correspondant à la création de la formule parsée en entrée. Il va parcourir la suite de tokens créés par l'analyseur lexical et en déduire l'enchaînement logique (la syntaxe). Le fichier Parser.mly utilisé par cet outil est aussi facile à construire que le précédent :
open Types;;
%token <string> LITTERAL %token NEG NEC POSS CONJ DISJ IMP PAROUV PARFER EOL %left CONJ DISJ IMP # diminue la priorité Devient :
Notre fichier est créé et la commande Ocamlyacc parser.mll va créer les fichiers parser.mli et parser.ml que nous devrons compiler par Ocaml. Le InputLes fichiers qui vont être parsés sont de la forme : <formule> sur une seule ligne.Les fonctions Ocaml qui utilisent les fonctions de parsing créées précédemment sont :
let input_pos file = try let fi = (open_in file) in let lexbuf = Lexing.from_channel fi in let formule = Parser_pos.main Lexer_pos.token lexbuf in (close_in fi); formule with Lexer_pos.Eof -> failwith "N'oubliez pas le retour chariot" ;; let input_nab file = try let fi = (open_in file) in let lexbuf = Lexing.from_channel fi in let formule = Parser_nab.main Lexer_nab.token lexbuf in (close_in fi); formule with Lexer_nab.Eof -> failwith "N'oubliez pas le retour chariot" ;; ConclusionLes outils Ocamllex et Ocamlyacc présents avec le langage Ocaml permettent la création rapide et intuitive de parser. Il n'est plus besoin de créer de A à Z un automate fini et de transformer une grammaire pour quelle soit LL[1]. Ces outils le font déja automatiquement. |
pour les formules avec necessité et possibilité
pour les formules avec nabla