Parser / Grammer: 2x parenthèses dans les règles imbriquées
Malgré mes connaissances limitées sur la compilation / l'analyse, j'ai osé créer un petit analyseur de descente récursive pour les expressions de filtre OData $. L'analyseur n'a besoin que de vérifier l'exactitude de l'expression et de générer une condition correspondante dans SQL. Comme l'entrée et la sortie ont presque les mêmes jetons et la même structure, c'était assez simple et ma mise en œuvre fait 90% de ce que je veux.
Mais maintenant, je suis resté coincé avec des parenthèses, qui apparaissent dans des règles distinctes pour les expressions logiques et arithmétiques. La grammaire OData complète dans ABNF est ici , une version condensée des règles impliquées est la suivante:
boolCommonExpr = ( boolMethodCallExpr
/ notExpr
/ commonExpr [ eqExpr / neExpr / ltExpr / ... ]
/ boolParenExpr
) [ andExpr / orExpr ]
commonExpr = ( primitiveLiteral
/ firstMemberExpr ; = identifier
/ methodCallExpr
/ parenExpr
) [ addExpr / subExpr / mulExpr / divExpr / modExpr ]
boolParenExpr = "(" boolCommonExpr ")"
parenExpr = "(" commonExpr ")"
Comment cette grammaire correspond-elle à une expression simple comme (1 eq 2)? D'après ce que je peux voir, tous (sont consommés par la règle à l' parenExprintérieur commonExpr, c'est- à -dire qu'ils doivent également se fermer après commonExprpour ne pas causer d'erreur et boolParenExprne jamais être touchés. Je suppose que mon expérience / intuition sur la lecture d'une telle grammaire est tout simplement insuffisante pour l'obtenir. Un commentaire dans l'ABNF dit: "Notez que boolCommonExpr est également un commonExpr". Cela fait peut-être partie du mystère?
Évidemment, une ouverture (seule ne me dira pas où elle va se fermer: après l' commonExprexpression actuelle ou plus loin après boolCommonExpr. Mon lexer a une liste de tous les jetons à venir (l'URL est une entrée très courte). Je pensais utiliser cela pour découvrir quel type de (j'ai. Bonne idée?
Je préfère avoir des restrictions d'entrée ou un petit hack plutôt que de passer à un modèle d'analyseur généralement plus puissant. Pour une traduction d'expression simple comme celle-ci, je veux également éviter les outils du compilateur.
Edit 1: Extension après réponse par rici - La réécriture grammaticale est-elle correcte?
En fait, j'ai commencé avec l' exemple des analyseurs de descente récursifs donné sur Wikipedia . Ensuite j'ai pensé à mieux m'adapter à la grammaire officielle donnée par le standard OData pour être plus "conforme". Mais avec les conseils de rici (et le commentaire de "Internal Server Error") pour réécrire la grammaire, j'aurais tendance à revenir à la structure plus compréhensible fournie sur Wikipedia. Adapté à l'expression booléenne du filtre OData $, cela pourrait peut-être ressembler à ceci:
boolSequence= boolExpr {("and"|"or") boolExpr} .
boolExpr = ["not"] expression ("eq"|"ne"|"lt"|"gt"|"lt"|"le") expression .
expression = term {("add"|"sum") term} .
term = factor {("mul"|"div"|"mod") factor} .
factor = IDENT | methodCall | LITERAL | "(" boolSequence")" .
methodCall = METHODNAME "(" [ expression {"," expression} ] ")" .
Est-ce que ce qui précède a un sens en général pour les expressions booléennes, est-il principalement équivalent à la structure originale ci-dessus et digestible pour un analyseur de descente récursif?
@rici: Merci pour vos remarques détaillées sur la vérification de type. La nouvelle grammaire devrait résoudre vos problèmes de priorité dans les expressions arithmétiques.
Pour les trois terminaux (MAJUSCULES dans la grammaire ci-dessus), mon lexer fournit un type (chaîne, nombre, date / heure ou booléen). Les non-terminaux renvoient le type qu'ils produisent. Avec cela, j'ai très bien réussi à faire la vérification de type à la volée dans mon implémentation actuelle, y compris des messages d'erreur décents. Espérons que cela fonctionnera également pour la nouvelle grammaire.
Edit 2: Revenir à la grammaire OData originale
La différenciation entre "logique" et "arithmétique" (n'est pas triviale. Pour résoudre le problème, même N.Wirth utilise une solution de contournement douteuse pour garder la grammaire de Pascal simple. Par conséquent, en Pascal, une paire supplémentaire de () est obligatoire autour andet orexpressions. Ni intuitif ni conforme OData :-(. La meilleure lecture sur la "() difficulté" que j'ai trouvée est dans Construisons un compilateur (Partie VI) . D'autres langages semblent aller trop loin dans la grammaire pour résoudre Comme je n'ai pas d'expérience avec la construction grammaticale, j'ai arrêté de faire la mienne.
J'ai fini par implémenter la grammaire OData originale. Avant d'exécuter l'analyseur, je passe en revue tous les jetons en arrière pour déterminer lesquels (appartiennent à une expression logique / arithmétique. Pas de problème pour la longueur potentielle d'une URL.
Réponses
Personnellement, je modifierais juste la grammaire pour qu'elle n'ait qu'un seul type d'expression et donc un type de parenthèse. Je ne suis pas convaincu que la grammaire OData soit réellement correcte; il n'est certainement pas utilisable dans un analyseur LL (1) (ou descendant récursif) pour exactement la raison que vous mentionnez.
Plus précisément, si l'objectif est boolCommonExpr, il existe deux productions qui peuvent correspondre au (jeton d'anticipation:
boolCommonExpr = ( …
/ commonExpr [ eqExpr / neExpr / … ]
/ boolParenExpr
/ …
) …
commonExpr = ( …
/ parenExpr
/ …
) …
Pour la plupart, il s'agit d'une tentative malavisée de faire en sorte que la grammaire détecte une violation de type. (Si en fait c'est une violation de type.) C'est mal orienté car il est voué à l'échec s'il y a des variables booléennes, ce qu'il y a apparemment dans cet environnement. Comme il n'y a pas d'indice syntaxique quant au type d'une variable, l'analyseur n'est pas capable de décider si des expressions particulières sont bien formées ou non, il y a donc un bon argument pour ne pas essayer du tout, en particulier si cela crée des maux de tête d'analyse. Une meilleure solution consiste d'abord à analyser l'expression dans un AST d'une certaine forme, puis à effectuer une autre passe sur l'AST pour vérifier que chaque opérateur a des opérandes du type correct (et éventuellement en insérant des opérateurs de conversion explicites si cela est nécessaire).
Mis à part tout autre avantage, effectuer la vérification de type dans une passe distincte vous permet de produire de bien meilleurs messages d'erreur. Si vous faites (certaines) erreurs de syntaxe de violation de type, vous pouvez laisser l'utilisateur perplexe quant à la raison pour laquelle son expression a été rejetée; en revanche, si vous remarquez qu'une opération de comparaison est utilisée comme opérande pour multiplier (et si la sémantique de votre langage ne permet pas une conversion automatique de Vrai / Faux en 1/0), alors vous pouvez produire une erreur bien ciblée message ("les comparaisons ne peuvent pas être utilisées comme opérande d'un opérateur arithmétique", par exemple).
Une raison possible de mettre différents opérateurs (mais pas de parenthèses) dans différentes variables grammaticales est d'exprimer la priorité grammaticale. Cette considération pourrait vous encourager à réécrire la grammaire avec une priorité explicite. (Telle qu'elle est écrite, la grammaire suppose que tous les opérateurs arithmétiques ont la même priorité, ce qui conduirait vraisemblablement à 2 + 3 * aêtre analysés en tant que (2 + 3) * a, ce qui pourrait être une énorme surprise.) Alternativement, vous pouvez utiliser un sous-analyseur simple prenant en compte la priorité pour les expressions.
Si vous voulez tester votre grammaire ABNF pour le déterminisme (c.-à-d. LL (1)), vous pouvez utiliser Tunnel Grammar Studio (TGS). J'ai testé la grammaire complète, et il y a beaucoup de conflits, pas seulement cette portée. Si vous êtes en mesure d'extraire les règles pertinentes, vous pouvez utiliser la version de bureau de TGS pour visualiser les conflits (le vérificateur de version en ligne est avec un résultat textuel uniquement). Si les règles ne sont pas trop nombreuses, la démo peut vous aider à créer une grammaire LL (1) à partir de vos règles.
Si vous extrayez toutes les règles dont vous avez besoin et que vous les ajoutez à votre question, je peux l'exécuter pour vous et vous dirai s'il s'agit de LL (1). Notez que la grammaire n'est pas exactement dans la méta syntaxe ABNF, car la sensibilité à la casse est tapée avec 'pour les chaînes sensibles à la casse. L'ABNF (RFC 5234) par définition est insensible à la casse, car la RFC 7405 définit la sensibilité avec les préfixes %set %i(sensible et insensible) avant la chaîne réelle. La casse par défaut (sans préfixe) signifie toujours insensible. Cela signifie que vous devez remplacer ces '...'chaînes non valides par %s"..."avant de tester dans TGS.
TGS est un projet sur lequel je travaille.