Ce qu'il y a de bien avec les typhons, c'est que tout s'arrête autour, du coup on est peinard pour bosser et faire ce qu'on avait mis de côté depuis des mois...
Et ça fait des mois que j'avais envie de tester Ocamlyacc sans trop avoir de raison ni de temps pour ça. Ce week end, j'avais le temps ! Et la raison : m'attaquer au Sinica Treebank. Bon, Yacc pour parser un treebank c'est p'tet un peu disproportionné mais c'était l'occasion et puis quand on voit le résultat, on se dit qu'on a bien fait puisqu'on arrive à ce qu'on veut en moins de 100 lignes de code !. Demonstration...
(en fait je suis pas sûr que ce billet soit lisible, disons qu'il y a quelques pré-requis. Si il ne l'est pas, considérez que c'est plus un aide mémoire perso et/ou posez des questions en commentaire)
Le Sinica Treebank (STB)
http://turing.iis.sinica.edu.tw/treesearch/
Le STB est comme je l'ai dit dans le premier billet un treebank construit suivant une "Information-based Case Grammar". J'avoue n'avoir que survolé le papier qui décrit ce qu'est vraiment une ICB. Mais pour l'heure ce que j'en retiens et qui est suffisant pour mon propos ici, c'est que c'est une grammaire d'unification, "Head-Driven", et que les rôles thématiques des adjoints aux têtes sont clairement indiqués dans le Treebank. concrêtement, ça donne ça :
S(restriction:Cbbb:不僅
|experiencer:NP(
Head:Nab:遊客)
|Head:VL1:喜愛
|goal:VP(
Head:VA11:來
|location:Nep:此
|complement:VP(
Head:VB11:拍照
|complement:VI2:留念)))
en français mot à mot :
S(restriction:Cbbb:pas seulement
|experiencer:NP(
Head:Nab:touristes)
| Head:VL1:aimer
|goal:VP(
Head:VA11:venir
|location:Nep:ici
|complement:VP(
Head:VB11:prendre photo
|complement:VI2:garder un souvenir)))
L'indentation est maison, en vrai ça donne ça :
S(restriction:Cbbb:不僅|experiencer:NP(Head:Nab:遊客)|Head:VL1:喜愛|goal:VP(Head:VA11:來|location:Nep:此|complement:VP(Head:VB11:拍照|complement:VI2:留念)))
L'objectif est donc de passer d'une chaîne de caractères à une structure de donnée en arbre. Qui permettra notamment de générer ce genre de chose, beaucoup plus lisibles :
Formats des données
En observant les données si dessus, on peut dégager la grammaire suivante : (oui la grammaire du format du Treebank hein, rien à voir avec la grammaire du chinois
noeud -> rôle ':' pos ':' mot
| rôle ':' pos '(' liste_noeuds ')'
| pos '(' liste_noeuds ')'
liste_noeud -> noeud
| noeud '|' liste_noeud
"rôle", "pos" et "mot" sont des chaînes de caractères quelconques. Tellement quelconques que ça inclus des sinogrammes. Pour éviter tout risque de cafouillage dans les encodages et me faire la main au passage, j'ai donc choisi d'utiliser de l'UTF-8. Ce qui disqualifie Ocamllex pour le lexeur. En fouillant un peu, on trouve Ulex. Un lexer "unicode aware" qu'on peut facilement conjuger à ocamlyacc.
Il faut aussi définir une structure de données qui recevra les informations pendant le parsing. Au passage, on prévoit quelques fonctions d'affichage. Voici :
stb.ml
type case = Case of string
type pos = POS of string
type node = Node of case*pos*string* node list
let print_node_string n =
let rec aux_liste l = match l with
[] ->()
|f::suite -> aux f; aux_liste suite
and aux f = match f with
Node(_,_,s,fils) -> print_string s ; aux_liste fils
in aux n
let rec indent n = if n>0 then (print_string " " ; indent (n-1)) else ();;
let print_node_tree n =
let i = ref 0 in
let rec aux_liste l = match l with
[] ->()
|f::suite -> aux f; aux_liste suite
and aux f = match f with
Node(Case(c),POS(p),"",fils) -> indent !i ; print_endline (c^":"^p) ; i:= !i+1; aux_liste fils; i:= !i-1
|Node(Case(c),POS(p),s,[]) -> indent !i ; print_endline (c^":"^p^":"^s)
| _ -> print_string "error"
in aux n
let print_node_dot racine =
let n = ref 1 in
let rec aux_liste feuilles pere_id l = match l with
[] -> feuilles
|f::suite -> let feuilles'= aux feuilles pere_id f in aux_liste feuilles' pere_id suite
and aux feuilles pere_id f = match f with
Node(Case(c),POS(p),"",fils) ->
n := !n+1;
let id = "n"^(string_of_int !n) in
print_endline (id^" [label="^p^"];");
print_endline (pere_id^" -> "^id^" [label="^c^"];");
aux_liste feuilles id fils
|Node(Case(c),POS(p),s,[]) ->
n:= !n+2;
let id ="n"^(string_of_int (!n-1)) in
let id2 = "n"^(string_of_int !n) in
print_endline (id^" [label="^p^"];");
print_endline (id2^" [label="^s^"];");
print_endline (pere_id^" -> "^id^" [label="^c^"];");
print_endline (id^" -> "^id2^";");
id2::feuilles
| _ -> print_string "error";[]
in match racine with
Node(_,POS(p),_,fils)->
print_endline "digraph g {";
print_endline ("n1 [label="^p^"];");
let feuilles = aux_liste [] "n1" fils in
print_endline ("{rank=same"^(List.fold_left (fun a b -> a^";"^b) "" feuilles)^"}")
; print_endline "}"
Lexing
Contrairement à Lex&Yacc et avec eux Ocamllex et Ocamlyacc, Ulex n'a pas été codé comme un générateur de code à recompiler, mais directement comme une extension de la syntaxe d'Ocaml grâce à camlp4. Il faudra donc utiliser ce dernier pour compiler directement le lexeur.
La syntaxe de Ulex reste très proche de celle de lex et ocamlex et ne pose pas de problème en elle même. Voici le code utilisé
lexer.ml
type lexeme = SepAttributs |SepNodes | ParOuvre | ParFerme | Mot of string
(*open Parser*)
let mon_lexer = lexer ':' -> SepAttributs
| '|' -> SepNodes
|'(' -> ParOuvre
|')' -> ParFerme
| [^ ':' '(' ')' '|' ]+ ->Mot( Ulexing.utf8_lexeme lexbuf)
pour le compiler, le plus simple est d'utiliser ocamlfind :
ocamlfind ocamlc -package ulex -linkpkg -syntax camlp4o
lexer.ml
Parsing
Côté parsing pas de surprise ; à ce niveau on ne dépend plus de l'encodage des données.
Ocamlyacc fonctionne de la même façon que Yacc : on écrit notre
grammaire dans un fichier .mly et on lance ocamlyacc
fichier.mly pour obtenir un .ml qu'on peut compiler
normalement pour obtenir un parser. Dans les fait pour que ça marche, j'ai du
retouché légèrement le fichier d'interface parser.mli pour y
ajouter open Stb afin qu'il trouve des déclarations de types
manquantes.
le format du fichier .mly est très proche de ce qu'on trouve en
Yacc. Voici le mien :
parser.mly
%{
open Stb
%}
%token SepAttributs SepNodes ParOuvre ParFerme
%token <string> Mot
%start noeud
%type <node> noeud
%%
noeud : Mot SepAttributs Mot SepAttributs Mot{Node(Case($1), POS($3), $5, [] ) }
| Mot SepAttributs Mot ParOuvre liste_nodes ParFerme
{Node(Case($1),POS($3),"",$5) }
| Mot ParOuvre liste_nodes ParFerme{Node(Case(""),POS($1),"",$3) }
liste_nodes : noeud {[$1]}
| noeud SepNodes liste_nodes{ $1::$3}
%%
Assemblage des morceaux.
Maintenant, l'astuce consiste à brancher notre lexeur Ulex à la place d'un lexeur classique généré avec OCamlex. Pour appeler le parseur il faudra donc faire quelque chose comme :
let resultat = parse (fun _ -> mon_lexeur lexbuf)
(Lexing.from_string "non_utilisé")
Ce qui nous donnera... Une erreur de type !!! (bah oui, on est en caml. Passez une journée sur du code caml sans obtenir d'erreur de typage, c'est pas crédible. Fallait bien que j'en laisse au moins une.)
This expression has type Lexer.lexeme but is here used with type Parser.token
Et oui, il faut quand même que le lexeur et le parseur s'entendent sur les
données manipulées... corrigeons lexer.ml en remplaçant la
déclaration du type lexeme par un simple open Parser
et le tour est joué !
Démo
Voici donc ce que ça donne :
[pierre@Arch ocamlParse]$ ocaml -I /usr/lib/ocaml/site-lib/ulex/ ulexing.cma parser.cmo lexer.cmo stb.cmo
Objective Caml version 3.10.1
# open Parser;;
# open Lexer;;
# let lb = Ulexing.from_utf8_string "S(restriction:Cbbb:不僅|experiencer:NP(Head:Nab:遊客)|Head:VL1:喜愛|goal:VP (Head:VA11:來|location:Nep:此|complement:VP(Head:VB11:拍照|complement:VI2:留念)))";;
val lb : Ulexing.lexbuf = <abstr>
# let resultat = noeud (fun _ -> mon_lexer lb) (Lexing.from_string "bidon");;
val resultat : Stb.node =
Stb.Node (Stb.Case "", Stb.POS "S", "",
[Stb.Node (Stb.Case "restriction", Stb.POS "Cbbb",
"\228\184\141\229\131\133", []);
Stb.Node (Stb.Case "experiencer", Stb.POS "NP", "",
[Stb.Node (Stb.Case "Head", Stb.POS "Nab", "\233\129\138\229\174\162",
[])]);
Stb.Node (Stb.Case "Head", Stb.POS "VL1", "\229\150\156\230\132\155", []);
Stb.Node (Stb.Case "goal", Stb.POS "VP ", "",
[Stb.Node (Stb.Case "Head", Stb.POS "VA11", "\228\190\134", []);
Stb.Node (Stb.Case "location", Stb.POS "Nep", "\230\173\164", []);
Stb.Node (Stb.Case "complement", Stb.POS "VP", "",
[Stb.Node (Stb.Case "Head", Stb.POS "VB11",
"\230\139\141\231\133\167", []);
Stb.Node (Stb.Case "complement", Stb.POS "VI2",
"\231\149\153\229\191\181", [])])])])
# Stb.print_node_string resultat;;
不僅遊客喜愛來此拍照留念- : unit = ()
# Stb.print_node_dot resultat;;
digraph g {
n1 [label=S];
n2 [label=Cbbb];
n3 [label=不僅];
n1 -> n2 [label=restriction];
n2 -> n3;
n4 [label=NP];
n1 -> n4 [label=experiencer];
n5 [label=Nab];
n6 [label=遊客];
n4 -> n5 [label=Head];
n5 -> n6;
n7 [label=VL1];
n8 [label=喜愛];
n1 -> n7 [label=Head];
n7 -> n8;
n9 [label=VP ];
n1 -> n9 [label=goal];
n10 [label=VA11];
n11 [label=來];
n9 -> n10 [label=Head];
n10 -> n11;
n12 [label=Nep];
n13 [label=此];
n9 -> n12 [label=location];
n12 -> n13;
n14 [label=VP];
n9 -> n14 [label=complement];
n15 [label=VB11];
n16 [label=拍照];
n14 -> n15 [label=Head];
n15 -> n16;
n17 [label=VI2];
n18 [label=留念];
n14 -> n17 [label=complement];
n17 -> n18;
{rank=same;n18;n16;n13;n11;n8;n6;n3}
}
- : unit = ()
#
