Représente la syntaxe optionnelle et la répétition avec OcamlYacc/FsYacc

Question

J'essaie de développer quelques compétences dans les grammaires de lexing/parsing. Je regarde en arrière sur un analyseur simple que j'ai écrit pour SQL, et je ne suis pas tout à fait heureux avec lui - il semble qu'il aurait dû y avoir un moyen plus facile d'écrire l'analyseur. Le SQL m'a fait trébucher parce qu'il a beaucoup de jetons et de répétition optionnels. Par exemple:

SELECT * 
FROM t1 
INNER JOIN t2 
INNER JOIN t3 
WHERE t1.ID = t2.ID and t1.ID = t3.ID 

équivaut à:

SELECT * 
FROM t1 
INNER JOIN t2 ON t1.ID = t2.ID 
INNER JOIN t3 on t1.ID = t3.ID 

Les ON et WHERE clauses sont facultatives et peuvent se produire plus d'une fois. Je me suis occupé ces derniers dans mon analyseur comme suit:

%{ 
open AST 
%} 

// ...  
%token <string> ID 
%token AND OR COMMA 
%token EQ LT LE GT GE 
%token JOIN INNER LEFT RIGHT ON 
// ... 

%% 

op: EQ { Eq } | LT { Lt } | LE { Le } | GT { Gt } | GE { Ge } 

// WHERE clause is optional  
whereClause: 
    |      { None } 
    | WHERE whereList  { Some($2) }   

whereList: 
    | ID op ID     { Cond($1, $2, $3) } 
    | ID op ID AND whereList  { And(Cond($1, $2, $3), $5) } 
    | ID op ID OR whereList  { Or(Cond($1, $2, $3), $5) } 


// Join clause is optional  
joinList: 
    |      { [] } 
    | joinClause   { [$1] } 
    | joinClause joinList { $1 :: $2 } 

joinClause: 
    | INNER JOIN ID joinOnClause { $3, Inner, $4 } 
    | LEFT JOIN ID joinOnClause  { $3, Left, $4 } 
    | RIGHT JOIN ID joinOnClause { $3, Right, $4 } 

// "On" clause is optional  
joinOnClause: 
    |      { None } 
    | ON whereList   { Some($2) } 

// ... 
%% 

En d'autres termes, je syntaxe facultative en traitées découpant en règles distinctes, et manutentionnés répétition utilisant récursion. Cela fonctionne, mais cela brise l'analyse d'un tas de petits sous-programmes, et il est très difficile de voir ce que la grammaire représente réellement.

Je pense qu'il serait beaucoup plus facile d'écrire si je pouvais spécifier la syntaxe optionnelle entre parenthèses et la répétition avec un * ou +. Cela réduirait mes règles whereClause et joinList à ce qui suit:

whereClause: 
    |      { None } 
// $1 $2, I envision $2 being return as an (ID * op * ID * cond) list 
    | WHERE [ ID op ID { (AND | OR) }]+ 
     { Some([for name1, op, name2, _ in $1 -> name1, op, name2]) } 

joinClause: 
    |      { None } 

// $1, returned as (joinType 
//      * JOIN 
//      * ID 
//      * ((ID * op * ID) list) option) list 
    | [ (INNER | LEFT | RIGHT) JOIN ID [ON whereClause] ]* 
     { let joinType, _, table, onClause = $1; 
      Some(table, joinType, onClause) } 

Je pense que ce formulaire est beaucoup plus facile à lire et exprime la grammaire, il essaie de capturer de manière plus intuitive. Malheureusement, je ne trouve rien dans la documentation Ocaml ou F # qui supporte cette notation ou quoi que ce soit de similaire. Y at-il un moyen facile de représenter les grammaires avec des jetons optionnels ou répétitifs dans OcamlYacc ou FsYacc?

Existe-t-il un moyen facile de représenter les grammaires avec des jetons optionnels ou répétitifs dans OcamlYacc ou FsYacc?

Answer 1

Lorsque vous composez tous les petits morceaux, vous devriez obtenir quelque chose comme vous voulez. Au lieu de:

(INNER | RIGHT | LEFT) 

vous suffit

inner_right_left 

et définir que, pour être l'union de ces trois mots-clés.

Vous pouvez également définir l'union dans le lexeur. dans la façon dont vous définissez les jetons, ou en utilisant camlp4, je n'ai pas fait grand-chose dans ce domaine, donc je ne peux pas vous conseiller de prendre ces routes. Et je ne pense pas qu'ils vont travailler pour vous aussi bien que d'avoir de petites pièces partout.

EDIT:

Ainsi, pour camlp4 vous pouvez regarder Camlp4 Grammar module et un tutorial et un better tutorial. Ce n'est pas exactement ce que vous voulez, remarquez, mais c'est assez proche. La documentation est assez mauvaise, comme exprimé dans le recent discussion on the ocaml groups, mais pour cette zone spécifique, je ne pense pas que vous aurez trop de problèmes. J'ai fait un peu avec et peut poser plus de questions.

Answer 2

Menhir permet de paramétrer les symboles non-terminaux par d'autres symboles et fournit la bibliothèque de raccourcis standard, comme les options et les listes, et vous pouvez créer les vôtres.Exemple:

option(X): x=X { Some x} 
     | { None } 

Il existe également une syntaxe de sucre, 'token?' est équivalent à 'option (token)', 'token +' à 'nonempty_list (token)'.

Tout cela raccourcit vraiment la définition grammaticale. En outre, il est pris en charge par ocamlbuild et peut être un remplacement de ocamlyacc. Hautement recommandé!

drôle, je l'ai utilisé pour analyser SQL trop :)