La grammaire de D est-elle vraiment sans contexte ?

Question

J'ai posté cette question dans le groupe de discussion D il y a quelques mois, mais pour une raison quelconque, la réponse ne m'a jamais vraiment convaincu, alors j'ai pensé que je la poserais ici.

---

La grammaire de D est apparemment sans contexte .

La grammaire du C++, cependant, ne l'est pas (même sans les macros). ( Veuillez lire attentivement ce qui suit ! )

Maintenant accordé, Je ne sais rien. (officiellement) sur les compilateurs, les lexers et les parsers. Tout ce que je sais vient de ce que j'ai appris sur le web.
Et voici ce que (je crois) j'ai compris concernant le contexte, dans un jargon pas trop technique :

La grammaire d'une langue est sans contexte si et seulement si vous pouvez toujours comprendre la signification (mais pas nécessairement le comportement exact) d'un élément donné de son code sans avoir besoin de "regarder" ailleurs.

Ou encore, dans moins la rigueur :

La grammaire ne peut pas être sans contexte si j'ai besoin Je ne peux pas dire le type d'une expression juste en la regardant.

Ainsi, par exemple, le C++ échoue au test de l'absence de contexte parce que l'élément signification de confusing<sizeof(x)>::q < 3 > (2) dépend de la valeur de q .

Jusqu'à présent, tout va bien.

Maintenant, ma question est la suivante : peut-on dire la même chose de D ?

Dans D, les hashtables peuvent être créés par le biais d'un Value[Key] déclaration, par exemple

int[string] peoplesAges;   // Maps names to ages

Les tableaux statiques peuvent être définis avec une syntaxe similaire :

int[3] ages;   // Array of 3 elements

Et des modèles peuvent être utilisés pour les rendre confus :

template Test1(T...)
{
    alias int[T[0]] Test;
}

template Test2(U...)
{
    alias int[U] Test2;  // LGTM
}

Test1!(5) foo;
Test1!(int) bar;
Test2!(int) baz;  // Guess what? It's invalid code.

Cela signifie que je ne peut pas dire la signification de T[0] o U juste en le regardant (c'est-à-dire qu'il peut s'agir d'un nombre, d'un type de données ou d'un tuple de Dieu sait quoi). Je ne peux même pas dire si l'expression est grammaticalement valide (puisque int[U] ne l'est certainement pas -- vous ne pouvez pas avoir une table de hachage avec des tuples comme clés ou valeurs).

Tout arbre d'analyse que je tente de faire pour Test serait échouer n'a pas de sens (puisqu'il doit savoir si le nœud contient un type de données, un littéral ou un identificateur), à moins qu'il ne s'agisse d'un type de données. retards le résultat jusqu'à ce que la valeur de T est connue (ce qui la rend dépendante du contexte).

Dans ces conditions, est-ce que D est réellement sans contexte, ou est-ce que je comprends mal le concept ?

Pourquoi/pourquoi pas ?

---

Mise à jour :

J'ai juste pensé que je devais commenter : C'est vraiment intéressant de voir les réponses, puisque :

• Certaines réponses affirment que le C++ et le D ne peut pas être sans contexte
• Certaines réponses affirment que C++ et D sont les deux sans contexte
• Certaines réponses soutiennent que C++ est sensible au contexte alors que D ne l'est pas.
• Personne n'a encore prétendu que C++ est sans contexte alors que D est sensible au contexte :-)

Je ne peux pas dire si j'apprends ou si je m'embrouille encore plus, mais dans tous les cas, je suis content d'avoir posé cette question... merci à tous d'avoir pris le temps de répondre !

Answer 1

Le fait d'être sans contexte est d'abord une propriété des grammaires génératives. Cela signifie que ce qu'un non-terminal peut générer ne dépendra pas du contexte dans lequel le non-terminal apparaît (dans une grammaire générative non libre de contexte, la notion même de "chaîne générée par un non-terminal donné" est en général difficile à définir). Cela n'empêche pas la même chaîne de symboles d'être générée par deux non-terminaux (donc pour les mêmes chaînes de symboles d'apparaître dans deux contextes différents avec une signification différente) et n'a rien à voir avec la vérification de type.

Il est courant d'étendre la définition de la liberté de contexte des grammaires au langage en déclarant qu'un langage est sans contexte s'il existe au moins une grammaire sans contexte pour le décrire.

En pratique, aucun langage de programmation n'est sans contexte parce que des choses comme "une variable doit être déclarée avant d'être utilisée" ne peuvent pas être vérifiées par une grammaire sans contexte (elles peuvent être vérifiées par d'autres types de grammaires). Ce n'est pas mauvais, en pratique les règles à vérifier sont divisées en deux : celles que vous voulez vérifier avec la grammaire et celles que vous vérifiez dans une passe sémantique (et cette division permet également un meilleur rapport d'erreur et de récupération, donc vous voulez parfois accepter plus dans la grammaire que ce qui serait possible afin de donner à vos utilisateurs de meilleurs diagnostics).

Ce que les gens veulent dire en affirmant que le C++ n'est pas sans contexte, c'est que cette division n'est pas possible de manière pratique (avec le logiciel pratique y compris comme critères "suit presque la description officielle du langage" et "mon outil de génération d'analyseur syntaxique supporte ce type de division" ; permettre à la grammaire d'être ambiguë et à l'ambiguïté d'être résolue par la vérification sémantique est un moyen relativement facile de faire la coupure pour C++ et de suivre assez fidèlement la norme C++, mais c'est peu pratique quand on s'appuie sur des outils qui ne permettent pas les grammaires ambiguës, quand on a de tels outils, c'est pratique).

Je ne connais pas suffisamment D pour savoir s'il existe ou non une coupe commode des règles du langage dans une grammaire sans contexte avec contrôles sémantiques, mais ce que vous montrez est loin de prouver qu'il n'y en a pas.

Answer 2

La propriété d'être sans contexte est un concept très formel ; vous pouvez en trouver une définition aquí . Notez qu'il s'applique à grammaires On dit d'un langage qu'il est sans contexte s'il existe au moins une grammaire sans contexte qui le reconnaît. Notez qu'il peut exister d'autres grammaires, éventuellement non libres de contexte, qui reconnaissent le même langage.

En gros, cela signifie que la définition d'un élément du langage ne peut pas changer en fonction des éléments qui l'entourent. Par éléments de langage, j'entends des concepts tels que expressions y identifiants et non des instances spécifiques de ces concepts à l'intérieur des programmes, comme a + b o count .

Essayons de construire un exemple concret. Considérons cette simple instruction COBOL :

   01 my-field PICTURE 9.9 VALUE 9.9.

Ici, je définis un champ, c'est-à-dire une variable, qui est dimensionné pour contenir un chiffre intégral, le point décimal, et un chiffre décimal, avec la valeur initiale 9,9 . Une grammaire très incomplète pour cela pourrait être :

field-declaration ::= level-number identifier 'PICTURE' expression 'VALUE' expression '.'
expression ::= digit+ ( '.' digit+ )

Malheureusement, les expressions valides qui peuvent suivre PICTURE ne sont pas les mêmes expressions valides qui peuvent suivre VALUE . Je pourrais réécrire la deuxième production dans ma grammaire comme suit :

'PICTURE' expression ::= digit+ ( '.' digit+ ) | 'A'+ | 'X'+
'VALUE' expression ::= digit+ ( '.' digit+ )

Cela rendrait ma grammaire sensible au contexte, car expression serait une chose différente selon qu'il a été trouvé après 'PICTURE' ou après 'VALUE' . Toutefois, comme on l'a fait remarquer, cela ne dit rien sur le langage sous-jacent. Une meilleure alternative serait :

field-declaration ::= level-number identifier 'PICTURE' format 'VALUE' expression '.'
format ::= digit+ ( '.' digit+ ) | 'A'+ | 'X'+
expression ::= digit+ ( '.' digit+ )

qui est sans contexte.

Comme vous pouvez le constater, cela est très différent de votre compréhension. Considérez :

a = b + c;

Il y a très peu de choses que vous pouvez dire sur cette affirmation sans regarder les déclarations de a, b et c, dans n'importe lequel des langages pour lesquels cette affirmation est valide, cependant cela n'implique pas en soi qu'un de ces langages n'est pas libre de contexte. Ce qui vous trouble probablement, c'est le fait que la liberté de contexte est différente de l'ambiguïté. Voici une version simplifiée de votre exemple C++ :

a < b > (c)

Il s'agit d'une ambiguïté dans la mesure où, en l'observant uniquement, vous ne pouvez pas dire s'il s'agit d'un appel de modèle de fonction ou d'une expression booléenne. L'exemple précédent, en revanche, n'est pas ambigu ; du point de vue des grammaires, il ne peut être interprété que de la manière suivante :

identifier assignment identifier binary-operator identifier semi-colon

Dans certains cas, vous pouvez résoudre les ambiguïtés en introduisant la sensibilité au contexte au niveau de la grammaire. Je ne pense pas que ce soit le cas avec l'exemple ambigu ci-dessus : dans ce cas, vous ne pouvez pas éliminer l'ambiguïté sans savoir si a est un template ou non. Notez que lorsqu'une telle information n'est pas disponible, par exemple lorsqu'elle dépend d'une spécialisation spécifique de template, le langage fournit des moyens de résoudre les ambiguïtés : c'est pourquoi vous devez parfois utiliser typename pour se référer à certains types dans les modèles ou pour utiliser des template lorsque vous appelez des modèles de fonctions membres.

Answer 3

Il y a déjà beaucoup de bonnes réponses, mais comme vous n'êtes pas informé sur les grammaires, les analyseurs syntaxiques et les compilateurs, etc., laissez-moi vous le démontrer par un exemple.

Tout d'abord, le concept de grammaire est assez intuitif. Imaginez un ensemble de règles :

S -> a T
T -> b G t
T -> Y d
b G -> a Y b
Y -> c
Y -> lambda (nothing)

Et imaginez que vous commencez avec S . Les lettres majuscules sont des non-terminaux et les lettres minuscules des terminaux. Cela signifie que si vous obtenez une phrase composée de tous les terminaux, vous pouvez dire que la grammaire a généré cette phrase comme un "mot" dans la langue. Imaginez de telles substitutions avec la grammaire ci-dessus (La phrase entre *phrase* est celle qui est remplacée) :

*S* -> a *T* -> a *b G* t -> a a *Y* b t -> a a b t

Donc, je pourrais créer aabt avec cette grammaire.

Ok, retour à la ligne principale.

Supposons un langage simple. Vous avez des nombres, deux types (int et string) et des variables. Vous pouvez faire des multiplications sur des entiers et des additions sur des chaînes de caractères mais pas l'inverse.

La première chose dont vous avez besoin, c'est un lexer. C'est-à-dire généralement une grammaire régulière (ou égale à celle-ci, une DFA, ou égale à une expression régulière) qui correspond aux tokens du programme. Il est courant de les exprimer en expressions régulières. Dans notre exemple :

(J'invente ces syntaxes)

number: [1-9][0-9]*    // One digit from 1 to 9, followed by any number
                       // of digits from 0-9
variable: [a-zA-Z_][a-zA-Z_0-9]*  // You get the idea. First a-z or A-Z or _
                                  // then as many a-z or A-Z or _ or 0-9
                                  // this is similar to C
int: 'i' 'n' 't'
string: 's' 't' 'r' 'i' 'n' 'g'
equal: '='
plus: '+'
multiply: '*'

whitespace: (' ' or '\n' or '\t' or '\r')*   // to ignore this type of token

Donc, maintenant vous avez une grammaire régulière, qui tokenise votre entrée, mais elle ne comprend rien de la structure.

Alors vous avez besoin d'un analyseur syntaxique. L'analyseur syntaxique, c'est généralement une grammaire sans contexte. Une grammaire sans contexte signifie que, dans la grammaire, il n'y a que des non-terminaux simples sur le côté gauche des règles de grammaire. Dans l'exemple du début de cette réponse, la règle

b G -> a Y b

rend la grammaire contextuelle sensible parce que sur la gauche, vous avez b G et pas seulement G . Qu'est-ce que cela signifie ?

Eh bien, lorsque vous écrivez une grammaire, chacun des non terminaux a une signification. Écrivons une grammaire sans contexte pour notre exemple (| signifie ou. Comme si on écrivait plusieurs règles sur la même ligne) :

program -> statement program | lambda
statement -> declaration | executable
declaration -> int variable | string variable
executable -> variable equal expression
expression -> integer_type | string_type
integer_type -> variable multiply variable |
                variable multiply number |
                number multiply variable |
                number multiply number
string_type -> variable plus variable

Maintenant cette grammaire peut accepter ce code :

x = 1*y
int x
string y
z = x+y

Grammaticalement, ce code est correct. Donc, revenons à ce que signifie "sans contexte". Comme vous pouvez le voir dans l'exemple ci-dessus, lorsque vous développez executable vous générez une déclaration de la forme variable = operand operator operand sans tenir compte de la partie du code dans laquelle vous vous trouvez. Que ce soit au tout début ou au milieu, que les variables soient définies ou non, ou que les types correspondent, vous ne savez pas et vous vous en moquez.

Ensuite, il faut faire de la sémantique. C'est là que les grammaires sensibles au contexte entrent en jeu. Tout d'abord, laissez-moi vous dire qu'en réalité, personne n'écrit une grammaire sensible au contexte (parce que l'analyser est trop difficile), mais plutôt des bouts de code que l'analyseur syntaxique appelle lorsqu'il analyse l'entrée (appelés routines d'action, bien que ce ne soit pas la seule façon). Formellement, cependant, vous pouvez définir tout ce dont vous avez besoin. Par exemple, pour être sûr de définir une variable avant de l'utiliser, au lieu de ceci

executable -> variable equal expression

vous devez avoir quelque chose comme :

declaration some_code executable -> declaration some_code variable equal expression

plus complexe cependant, pour s'assurer que le variable dans la déclaration correspond à celle qui est calculée.

Bref, je voulais juste vous donner l'idée. Donc, toutes ces choses sont sensibles au contexte :

• Vérification du type
• Nombre d'arguments pour la fonction
• valeur par défaut de la fonction
• si member existe dans obj en code : obj.member
• Presque tout ce qui n'est pas comme : disparu ; o }

J'espère que vous avez une idée des différences (si ce n'est pas le cas, je serai ravi de vous expliquer).

Donc en résumé :

• Le lexer utilise une grammaire régulière pour tokeniser l'entrée.
• L'analyseur utilise une grammaire sans contexte pour s'assurer que le programme a une structure correcte.
• L'analyseur sémantique utilise une grammaire contextuelle pour effectuer la vérification des types, la correspondance des paramètres, etc.

Mais ce n'est pas forcément toujours le cas. Cela montre simplement que chaque niveau doit devenir plus puissant pour pouvoir faire plus de choses. Cependant, chacun des niveaux de compilateur mentionnés pourrait en fait être plus puissant.

Par exemple, un langage dont je ne me souviens plus, utilisait la souscription de tableau et l'appel de fonction à la fois avec des parenthèses et donc il fallait que l'analyseur syntaxique aille chercher le type (choses liées au contexte) de la variable et détermine quelle règle (appel de fonction ou substitution de tableau) prendre.

Si vous concevez un langage dont le lexer comporte des expressions régulières qui se chevauchent, vous devrez également consulter le contexte pour déterminer le type de jeton correspondant.

Pour en venir à votre question ! Avec l'exemple que vous avez mentionné, il est clair que la grammaire c++ n'est pas sans contexte. Le langage D, je n'en ai absolument aucune idée, mais vous devriez être capable de raisonner à ce sujet maintenant. Pensez-y de cette façon : Dans une grammaire sans contexte, un non-terminal peut s'étendre sans prendre en considération quoi que ce soit, MAIS la structure du langage. Comme vous l'avez dit, il s'étend, sans "regarder" ailleurs.

Un exemple familier serait celui des langues naturelles. Par exemple, en anglais, on dit :

sentence -> subject verb object clause
clause -> .... | lambda

Bien, sentence y clause sont des non terminaux ici. Avec cette grammaire, vous pouvez créer ces phrases :

I go there because I want to

ou

I jump you that I is air

Comme vous pouvez le voir, le second a la structure correcte, mais n'a pas de sens. Tant qu'une grammaire sans contexte est concernée, le sens n'a pas d'importance. Il s'étend simplement verb à un verbe quelconque sans "regarder" le reste de la phrase.

Donc si vous pensez que D doit à un moment donné vérifier comment quelque chose a été défini ailleurs, juste pour dire que le programme est structurellement correcte, alors sa grammaire n'est pas sans contexte. Si vous isolez n'importe quelle partie du code et qu'il peut toujours dire qu'il est structurellement correct, alors il est sans contexte.

Answer 4

La grammaire ne peut pas être sans contexte si j'ai besoin Je ne peux pas dire le type de une expression juste en la regardant.

Non, c'est carrément faux. La grammaire ne peut pas être sans contexte si vous ne pouvez pas dire si elle es une expression juste en la regardant et en observant l'état actuel de l'analyseur (suis-je dans une fonction, dans un espace de nom, etc.).

Le type d'une expression, cependant, est une signification sémantique, pas syntaxique, et l'analyseur syntaxique et la grammaire ne donnent pas un centime sur les types ou la validité sémantique ou si oui ou non vous pouvez avoir des tuples comme valeurs ou clés dans les hashmaps, ou si vous avez défini cet identifiant avant de l'utiliser.

La grammaire ne se soucie pas de ce que cela signifie, ou si cela a un sens. Elle ne se soucie que de ce qu'elle es .

Answer 5

Pour répondre à la question de savoir si un langage de programmation est libre de contexte, il faut d'abord décider où tracer la ligne entre la syntaxe et la sémantique. À titre d'exemple extrême, il est illégal en C pour un programme d'utiliser la valeur de certains types d'entiers après leur avoir permis de déborder. Il est clair que cela ne peut pas être vérifié au moment de la compilation, et encore moins au moment de l'analyse :

void Fn() {
  int i = INT_MAX;
  FnThatMightNotReturn();  // halting problem?
  i++;
  if(Test(i)) printf("Weeee!\n");
}

Comme exemple moins extrême que d'autres ont souligné, les règles de décélération avant utilisation ne peuvent pas être appliquées dans une syntaxe sans contexte, donc si vous souhaitez garder votre passage syntaxique sans contexte, alors cela doit être reporté au passage suivant.

Pour une définition pratique, je commencerais par la question suivante : Pouvez-vous déterminer correctement et sans ambiguïté l'arbre d'analyse de tous les programmes corrects en utilisant une grammaire libre de contexte et, pour tous les programmes incorrects (que le langage exige de rejeter), soit les rejeter comme syntaxiquement invalides, soit produire un arbre d'analyse que les passes ultérieures peuvent identifier comme invalide et rejeter ?

Étant donné que la spécification la plus correcte pour la syntaxe D est un analyseur syntaxique (IIRC un analyseur syntaxique LL), je soupçonne fortement qu'elle est en fait sans contexte selon la définition que j'ai suggérée.

---

Note : ce qui précède ne dit rien sur la grammaire que la documentation du langage ou un analyseur syntaxique donné utilise, seulement si une grammaire libre de contexte existe. De plus, la seule documentation complète sur le langage D est le code source du compilateur DMD.