My favorites | Sign in
Project Home Downloads Wiki Issues Source
READ-ONLY: This project has been archived. For more information see this post.
Search
for
LeParsing  
Description du parsing d'une formule de logique modale.
parser
Updated Jun 15, 2009 by stephen....@gmail.com

Sommaire

  • Présentation du problème
    1. Ce qu'il faut parser
  • Le Parsing
    1. L'analyseur lexical et l'outil Ocamllex
    2. L'analyseur syntaxique et l'outil Ocamlyacc
  • Le Input
  • Conclusion

Présentation du problème

Ce qu'il faut parser

Dans 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 :

  • pour les formules avec necessité et possibilité
  • pour les formules avec nabla
Par convention notre programme, dont le parser est écrit en Ocaml, lira les lignes d'un fichier dont la forme peut se présenter ainsi :
  • (!a && b) || (<>c)
  • Nabla{(!a && []b) || (<>c), <>a || !b, c}

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 Parsing

L'analyseur lexical et l'outil Ocamllex

L'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'écriture

Les conventions d'écriture que nous avons décidés sont ainsi :

  • Littéral : chaine de caractères avec des lettres minuscules et des chiffres.
  • Necessité : []
  • Possibilité : <>
  • Négation : !
  • Conjonction : $$
  • Disjonction : ||
  • Implication : =>
  • Nabla : Nabla{ , , }
  • Parenthèses : ( et )

Création du fichier lexer.mll

Le fichier lexer.mll est le fichier utilisé par Ocamllex. Il est trés simple à construire :

  • Nous ouvrons d'abord le parser qui va utilisé les tokens créés, c'est dans le fichier du parser que les tokens sont définis :
open Parser
  • Nous créons ensuite la reconnaissance des caractères du flot :
  •                 let Nec = "[]"
    		let Poss = "<>"
    		let Conj = "&&"
    		let Disj = "||" 
  • Puis nous créons les tokens correspondant :
  • 		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 Ocamlyacc

L'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 :

  • Nous ouvrons le fichier contenant le type utilisé pour représenter les formules modales :
open Types;;
  • Nous définissons les différents tokens ainsi que leur priorité dans le calcul :
  • 		%token <string> LITTERAL
    		%token NEG NEC POSS CONJ DISJ IMP PAROUV PARFER EOL
    		%left CONJ DISJ IMP 									# diminue la priorité
  • Puis nous créons les règles qui construisent la grammaire, ainsi tout ce fait de manière intuitive et analogique :
Devient :
	main: formule EOL                    { $1 };
	formule: LITTERAL                    { Lit($1) }
        |PAROUV formule PARFER       { $2 }
		|formule CONJ formule        { Conj($1, $3) }
		|formule DISJ formule        { Disj($1, $3) }
		|formule IMP formule         { Imp($1, $3) }
		|NEG formule %prec UNEG      { Neg($2) }
		|NEC formule %prec UNEC      { Nec($2) }
		|POSS formule %prec UPOSS    { Poss($2) };

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 Input

Les 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 :
  • Formules avec necessité et possibilité
  • 	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"
    	;;
  • Formules avec Nabla
  • 	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"
    	;;

Conclusion

Les 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.

Powered by Google Project Hosting