Est le C++, libre de tout contexte ou contextuelle?

J'entends souvent des réclamations que le C++ est un contexte sensible de la langue. Prenons l'exemple suivant:

a b(c);

Est-ce une définition de variable ou d'une déclaration de fonction? Cela dépend de la signification du symbole c. Si c est un variable, puis a b(c); définit une variable nommée b de type a. Il est initialisée directement avec c. Mais si c est un type, puis a b(c); déclare une fonction nommée b qui prend un c et renvoie un a.

Si vous regardez la définition du contexte langues, il va vous dire que toutes les règles de grammaire doit avoir de gauche qui consistent exactement un non-terminal symbole. Contexte de grammaires, d'autre part, de permettre à des chaînes arbitraires de terminaux et non-terminaux sur le côté gauche.

La navigation par le biais de l'Annexe A de la "Le Langage de Programmation C++", je ne pouvais pas trouver une seule règle de grammaire qui n'avait rien d'autre à part un non-terminal symbole sur son côté gauche. Cela impliquerait que le C++ est libre de tout contexte. (Bien sûr, chaque contexte du langage est également sensible au contexte, dans le sens que le contexte langues forment un sous-ensemble de l'contextuelle langues, mais ce n'est pas le point.)

Donc, est le C++, libre de tout contexte ou contextuelle?

  • Votre exemple montre clairement qu'il soit sensible au contexte.
  • Montrez-moi une seule règle de grammaire de C++ qui n'est pas constitué d'une seule non-terminal symbole sur son côté gauche, et je vais immédiatement vous croire.
  • IIUC ça dépend un peu sur l'endroit où vous dessinez la ligne pour la sensibilité au contexte. Je pense que j'ai vu de gens affirment que presque tous les typé statiquement les langages de programmation sont sensibles au contexte, non pas parce que vous ne pouvez pas construire une pratique compilateur pour eux avec CFG analyse des outils, mais parce que de telles implémentations de "tricher" par l'analyse de certains invalides des programmes et que les rejeter plus tard, lors de la vérification de type. Donc, si vous envisagez de mal tapé des programmes de ne pas être dans la langue (dans le CS sens, c'est à dire un ensemble de chaînes de caractères), l'analyseur doit accepter, plus de langues que C++ sont sensibles au contexte.
  • Ces gens sont dans l'erreur. Théorie des langages formels est une belle distinction entre les étapes, et sensible au contexte se réfère spécifiquement à l'analyse uniquement, pas de sémantique impliqués.
  • Honnêtement, je pensais que "sensible au contexte de la langue" est bien défini. Peut-être que je me trompe et il y a plusieurs définitions établies? Si c'est le cas, je serai heureux d'accepter la première réponse à m'expliquer 🙂
  • Non, vous vous trompez. Il n'y a pas de "analyse" ou "sémantique" dans le langage formel de la théorie du tout, juste de la "langue" qui est un ensemble de chaînes de caractères.
  • Pas de réponses à ce jour ont effectivement abordé votre définition de "context-free grammar". À mon avis, la réponse correcte à cette question, soit de la cites, la production dans l'annexe A qui ne correspond pas à votre définition, ou démontre que votre définition est incorrecte ou insuffisante. Stand your ground!
  • Pas tous les "définitions" sont Formelles, c'est pourquoi j'ai voté pour ré-ouvrir: les alternatives étaient en train de gagner! Dans ce genre de questions, il aide vraiment à l'accent de référence/le point particulier de guide [initial] des réponses.
  • Voir en fait D la grammaire vraiment libre de tout contexte?. En fait, je pense que tous ici devrait lire cette question et ses réponses!
  • Ne annexe A prétendre qu'il est à la fois nécessaire et suffisante définition complète du langage C++? Alors qu'est-ce que le reste de la norme document (moins la partie de la bibliothèque standard) sur?
  • Je viens de mettre la clé de citation de l'Annexe A dans ma réponse, ci-dessous. L'annexe A ne prétend pas être une définition de la langue.
  • Ressemble à aucune des réponses (y compris le mien) en fait répondre à la question! (Pour commencer, je ne vois pas comment un contexte sensible de la grammaire pourrait résoudre un de ces problèmes que les gens ont mentionné sans hacks.)
  • vous pourriez ne pas avoir vu cette citation dans ma réponse quelque part à quelqu'un d'autre: "Mathématiquement, un contexte sensible de la langue est l'équivalent d'un linéaire bornée de la machine de Turing non déterministe, également appelé un linéaire bornée automate". Je ne sais plus quoi vous vous attendez à une réponse.
  • voir mon autre commentaire ci-dessous votre réponse.
  • c'est parce que la solution réelle, il faudrait une planète vaut la peine de productions. Le fait qu'il est turing montre qu'il est possible d'écrire. Je ne pense pas que vous avez besoin de plus d'une réponse.
  • Personne n'a demandé une solution pour le C++, quel que soit le contexte sensible de la langue qui présente le même problème/solution suffirait
  • math.stackexchange.com/questions/163830/...
  • Cependant, je ne vois pas où OP demandé pour cela. Vous l'avez fait. Soins à poser une autre question?
  • Je pourrais le faire, mais j'ai envie de répondre que les revendications C++ est sensible au contexte doit être prêt à expliquer comment un contexte sensible de la grammaire serait en mesure de l'analyser.
  • FredOverflow: Ok, maintenant je vois, @rici réponse est ce que vous cherchez! Assurez-vous de suivre le lien! Il décrit comment une CSG pouvez regarder des copies de symboles, qui est ce dont nous avons besoin pour le C++.
  • Si, comme vous le dites, "très libre de tout contexte de la langue est également sensible au contexte" et les deux seules options (par la question) est "C++ libre de tout contexte ou contextuelle?" alors la réponse est clairement qu'il est moins sensible au contexte. Si, toutefois, vous voulez dire à votre question réponse "oui/non", alors peut-être :-p
  • Liés copie exacte de la question n'est pas aussi bien construit que celui-ci. En désaccord avec les proches.
  • Je pense que la question liée est bien, mais les principales réponses sont incorrectes. Ils devraient probablement être fusionnées.
  • Thunk Pourrait vous tuer l'acceptation de ma réponse. Je suis convaincu que DeamMG et coll. sont droit, mais je ne peux pas les supprimer.
  • Le problème avec ce titre c'est qu'il suppose que C++ est à moins sensible au contexte; il ne l'est pas. Je voudrais le changer s'il ne serait pas invalider tant dans les réponses.
  • Cela ne signifie pas que ce n'est pas un doublon. Cependant, je serai d'accord avec un compromis pour fermer cette question comme un doublon de celui-ci, pour ce qui va devenir "raisons historiques".
  • Voir aussi: Comment Clang gère le type / nom de la variable de l'ambiguïté de C/C++ eli.thegreenplace.net/2012/07/05/...
  • Si Une question est bonne, et la question B est mauvais, ne fermez pas la question A. Fermer l'autre comme un double, et de laisser le bon. L'autre question n'avait aucune information utile dans ses réponses. Celui-ci a de grandes choses.
  • Je me demande je ne suis pas venu à cette question... - I often hear claims that C++ is a context-sensitive language -- Oui, ensemble de tous les possible de corriger les programmes d'un langage formel est de la LCF en effet de " C " la langue est un CFL -- contrainte comme la déclaration d'abord, puis l'utiliser plus tard CSL - Vous ne pouvez pas trouver toute seule règle de CSG parce que le Compilateur est écrit en utilisant le problème est que nous ne savons pas efficaces pour l'analyse technique de l'ASC, de Sorte que nous utilisons CFG et poignées caractéristiques explicitement par programmation.
  • Ici, dans ma réponse: quelqu'un Peut-il donner un simple mais non-toy exemple d'un contexte sensible de la grammaire? j'ai essayé d'expliquer pourquoi une langue est de la CSL, même avec la même syntaxe. L'applicabilité de la syntaxe correcte de la règle de sur type est aussi un CS-fonction qui est dans votre exemple. Mais la compilation de résoudre et de choisir règle de grammaire à l'aide des informations stockées dans le symbole-table explicitement (il n'y a pas de grammaire, vous trouverez en Annexe).

InformationsquelleAutor fredoverflow | 2013-01-29
  1. 334

    Ci-dessous est ma (courant) préféré démonstration de pourquoi l'analyse C++ est (probablement) Turing-complet, car il montre un programme qui est syntaxiquement correcte si et seulement si un nombre entier est premier.

    J'ai donc affirmer que C++ est ni le contexte, ni du contexte.

    Si vous le permettez arbitraire symbole de séquences sur les deux côtés de la production, vous produisez un Type-0 de la grammaire ("libre") dans le Hiérarchie de Chomsky, qui est plus puissant que un contexte sensible de la grammaire; sans restriction grammaires sont Turing-complet. Une sensibilité au contexte (Type 1) de la grammaire permet de multiples symboles du contexte sur le côté gauche de production, mais le même contexte doit apparaître sur le côté droit de la production (d'où le nom de "sensible au contexte"). [1] le Contexte sensible de grammaires sont équivalentes à linéaire borné des machines de Turing.

    Dans le programme d'exemple, le premier calcul peut être effectué par un linéaire bornée de la machine de Turing, donc il n'a pas tout à prouver Turing équivalence, mais l'important, c'est que l'analyseur doit exécuter le calcul afin de pouvoir effectuer une analyse syntaxique. Il aurait pu être n'importe quel calcul peut s'exprimer comme une instanciation du modèle et il y a toutes les raisons de croire que le C++ instanciation du modèle est Turing-complet. Voir, par exemple, Todd L. Veldhuizen de 2003 de papier.

    Peu importe, C++ peut être analysé par un ordinateur, de sorte qu'il peut certainement être analysé par une machine de Turing. Par conséquent, un droit illimité de grammaire pourrait-il reconnaître. En fait écrire une telle grammaire serait pas pratique, c'est pourquoi la norme n'essayez pas de le faire. (Voir ci-dessous).

    Le problème avec "l'ambiguïté" de certaines expressions est surtout un hareng rouge. Pour commencer, l'ambiguïté est une fonction d'une grammaire particulière, pas une langue. Même si une langue peut être prouvé sans équivoque grammaires, si elle peut être reconnue par une grammaire libre de tout contexte, il est libre de tout contexte. De même, si elle ne peut pas être reconnu par un contexte libre de la grammaire, mais il peut être reconnu par un contexte sensible de la grammaire, il est sensible au contexte. L'ambiguïté n'est pas pertinent.

    Mais dans tous les cas, à l'instar de la ligne 21 (c'est à dire auto b = foo<IsPrime<234799>>::typen<1>();) dans le programme ci-dessous, les expressions ne sont pas ambigus, ils sont tout simplement analysée différemment selon le contexte. Dans l'expression la plus simple de la question, la catégorie syntaxique de certains identifiants dépend de la manière dont ils ont été déclarés (types et fonctions, par exemple), ce qui signifie que la langue officielle aurait à reconnaître le fait que les deux arbitraire des chaînes de longueur dans le même programme sont identiques (déclaration et utilisation). Ce peut être modélisé par la "copie" de la grammaire, qui est la grammaire qui reconnaît deux années consécutives des copies exactes d'un même mot. Il est facile de prouver avec les lemme de pompage que cette langue n'est pas libre de tout contexte. Un contexte sensible de la grammaire de cette langue est possible, et un Type-0 grammaire est fourni dans la réponse à cette question: https://math.stackexchange.com/questions/163830/context-sensitive-grammar-for-the-copy-language .

    Si l'on tentait d'écrire un contexte sensible (ou libre) de la grammaire à l'analyser en C++, il serait tout à fait peut-être remplir l'univers avec des gribouillages. L'écriture d'une machine de Turing pour analyser le C++ serait tout aussi impossible de l'entreprise. Même l'écriture d'un programme C++ est difficile, et autant que je sache, personne n'a été prouvé correct. C'est pourquoi la norme ne tente pas de fournir une grammaire formelle, et pourquoi il choisit d'écrire une partie de l'analyse de règles en anglais technique.

    Ce qui ressemble à une grammaire formelle dans la norme C++ n'est pas complète définition formelle de la syntaxe du langage C++. Il n'est même pas complète définition formelle de la langue après le prétraitement, qui pourrait être plus facile à formaliser. (Ce ne serait pas la langue, mais: le langage C++ tel que défini par la norme comprend l'préprocesseur, et le fonctionnement du préprocesseur est décrite de manière algorithmique, car il serait extrêmement difficile de décrire en toute grammaticales formalisme. C'est dans cette section de la norme lexicale de décomposition est décrite, y compris les règles, où il doit être appliqué plus d'une fois.)

    Les différentes grammaires (les deux se chevauchent les grammaires pour l'analyse lexicale, qui a lieu avant le prétraitement et l'autre, si nécessaire, par la suite, en plus de la "syntaxique" de la grammaire) sont rassemblés dans l'Annexe A, avec cette remarque importante (italiques ajoutés):

    Ce résumé de la syntaxe C++ est destiné à être une aide à la compréhension. Il n'est pas un état précis de la langue. En particulier, la grammaire décrit ici accepte un sur-ensemble de l'valide constructions C++. Les règles de désambiguïsation (6.8, 7.1, 10.2) doit être appliqué à distinguer les expressions à partir des déclarations. En outre, le contrôle d'accès, l'ambiguïté, et les règles de type doit être utilisé pour éliminer les syntaxiquement valide, mais de sens des constructions.

    Enfin, voici la promesse de programme. La ligne 21 est syntaxiquement correct si et seulement si les N dans IsPrime<N> est premier. Sinon, typen est un entier, non pas un modèle, de sorte typen<1>() est analysée comme (typen<1)>() qui est syntaxiquement incorrecte, car () n'est pas un point de vue syntaxique expression valide.

    template<bool V> struct answer { answer(int) {} bool operator()(){return V;}};
template<bool no, bool yes, int f, int p> struct IsPrimeHelper
: IsPrimeHelper<p % f == 0, f * f >= p, f + 2, p> {};
template<bool yes, int f, int p> struct IsPrimeHelper<true, yes, f, p> { using type = answer<false>; };
template<int f, int p> struct IsPrimeHelper<false, true, f, p> { using type = answer<true>; };
template<int I> using IsPrime = typename IsPrimeHelper<!(I&1), false, 3, I>::type;
template<int I>
struct X { static const int i = I; int a[i]; }; 
template<typename A> struct foo;
template<>struct foo<answer<true>>{
template<int I> using typen = X<I>;
};
template<> struct foo<answer<false>>{
static const int typen = 0;
};
int main() {
auto b = foo<IsPrime<234799>>::typen<1>(); //Syntax error if not prime
return 0;
}

    [1] Pour mettre plus techniquement, chaque production dans un contexte sensible de la grammaire doit être de la forme:

    αAβ → αγβ

    où A est un non-terminal et α, β sont éventuellement vide séquences de symboles de la grammaire, et γ est une séquence non-vide. (La grammaire des symboles peuvent être soit des terminaux ou non terminaux).

    Cela peut être lu comme A → γ seulement dans le contexte [α, β]. Dans un contexte (Type 2), de la grammaire, α et β doit être vide.

    Il s'avère que vous pouvez également limiter les grammaires avec le "monotone" restriction, où chaque production doit être de la forme:

    α → β où |α| ≥ |β| > 0  (|α| signifie "la longueur de α")

    Il est possible de prouver que l'ensemble des langages reconnus par une fonction monotone des grammaires est exactement le même que l'ensemble des langages reconnus par le contexte sensible de grammaires, et c'est souvent le cas que c'est plus facile à la base de preuves sur monotone des grammaires. Par conséquent, il est assez fréquent de voir des "sensible au contexte", utilisé comme s'il signifiait "monotone".

    • Ainsi, non seulement est-il sensible au contexte, mais il peut être subordonné à n'importe quel contexte vous pouvez vous exprimer dans les modèles, qui sont Turing-complet.
    • un contexte sensible de la langue est l'équivalent d'un linéaire bornée de la machine de Turing non déterministe, également appelé un linéaire bornée automate" (en.wikipedia.org/wiki/Context-sensitive_language) Permettez-moi de voir si je peux trouver une source primaire.
    • Comment le fait d'avoir plusieurs symboles sur le côté gauche d'une production de résoudre ce problème? Je ne pense pas que cette réponse est la réponse à la question.
    • la possibilité de mettre plusieurs symboles sur le côté gauche de production rend la grammaire de turing-complet. Depuis l'analyse de la langue est de turing calculable, un contexte sensible de la grammaire pourrait l'analyser. En fait la rédaction d'un tel CSG serait impraticable.
    • vous esquivé la question 😛 le problème actuel avec le C++, c'est que c'est CFG est ambigu. Ma question était, comment une CSG à résoudre ce problème exemple s'il vous plaît?)... Vous avez répondu en me disant que c'est Turing, qui a complètement évité de donner une solution au problème!
    • Demandez-vous comment une CSG permettrait de résoudre le problème de la grammaire en cours ambigu?
    • l'OP dit "sensible au contexte de la langue", pas sensible au contexte de la grammaire. L'ambiguïté est une fonction d'une grammaire, pas une langue. La langue est en effet sensible au contexte, mais pas à cause d'une grammaire particulière car il est ambigu.
    • Notez que mon exemple est pas ambigu. C'est une claire expression d'un programme valide. Si vous modifiez la valeur dans la ligne 21, il peut devenir mal formé. Mais dans les deux cas, il est ambigu.
    • Ouais, mais comment pourrait - tous CSG être en mesure d'analyser C++ correctement, est la question? Je peux voir la même ambiguïté des problèmes avec C++ Bec que je vois en C++ CFGs, donc je ne suis pas à voir ce qui est le C++ descriptibles par un contexte sensible de la grammaire, mais pas par une grammaire libre de tout contexte.
    • J'ai essayé de répondre. J'ai peur qu'il est maintenant un essai sur sa façon d'être un texte d'introduction sur l'analyse de la théorie. Me prouver le contraire en lisant tout cela. (Ce Bec parlez-vous?)
    • J'ai lu votre réponse, et il semble être constamment en esquivant la question. La question de l'OP posé est: Ce qui fait de C++ contextuelle? La réponse je pense qu'il (et d'autres) s'attendent à voir est: <certains de problème particulier> rend sensible au contexte, et ici est comment un problème similaire, dans un simple jouet de grammaire, pourrait être résolu par <quelques exemples de CSG>, mais il est impossible de résoudre avec un pur CFG. je n'ai pas encore vu toute réponse qui répond vraiment à la question de ce qui fait de C++ CSL (c'est à dire descriptibles par une CSG mais pas un CFG).
    • J'ai un doute: Comme vous le montrent, le résultat du modèle d'évaluation peut faire la différence entre un bien formée et mal formé programme. Modèle d'évaluation est turing-complet. Donc ne pas déterminer correctement si une chaîne est dans le langage (C++) exiger de turing-complétude? Comme vous le dites, un contexte sensible de la langue est "juste" un "linéaire bornée automate", ce qui n'est pas turing-complet autant que je sache. Ou est votre argument faisant usage de l'limites de la norme C++ met sur certaines choses, y compris le modèle d'évaluation de la profondeur?
    • Je pense que j'avais tort. J'ai changé la réponse à parler sans restriction de grammaires.
    • la copie de la langue est précisément ce genre de jouet de la langue. Attendez-vous une preuve formelle qu'il n'est pas CFG? Une telle preuve est dans chaque texte d'introduction que j'ai vu; c'est le classique de la première utilisation du lemme de pompage.
    • Ahhh oui, maintenant je vois enfin il... répondre a la lumière! +1 pour vous, c'est une formidable réponse alors.
    • Autant que je sache, le premier peut être décidé par un polynôme délimitée de la machine de Turing. Par conséquent, la langue de tous les nombres premiers devraient être sensibles au contexte.
    • Vous écrivez "je pense que le premier calcul peut être effectué par un linéaire borné machine de Turing". J'ai juste écrit que c' peut être fait.
    • Désolé, pourriez-vous rendre l'exemple plus clair? Je peux voir pourquoi le programme ne parvient pas à compiler, mais mon sentiment est qu'il échoue à la sémantique analiser, plutôt que de l'analyse - c'est à dire qu'il ont une syntaxe valide, mais non d'un programme valide néanmoins (problème similaire à la portée des variables, etc.).
    • Cette discussion devient trop long et difficile à suivre. Cependant, il contient de bonnes informations qui devraient être intégrés dans les la question ou une réponse. Merci de le faire et, si nécessaire, de poursuivre la discussion dans le chat!
    • J'ai fait ce que la discussion progresse, espérons-le, il n'est pas utile non intégré d'information. Si vous pensez que j'ai oublié quelque chose, faites le moi savoir ou de le modifier dans.
    • non, je ne pense pas que vous avez raté quelque chose. Je viens de poster mon commentaire standard pour de telles occasions 😉
    • Je tiens à ajouter à votre commentaire à propos de la norme ne cherche pas à définir un "libre de grammaire" pour le C++. Ce n'est pas seulement l'impraticabilité, mais aussi le fait qu'il ne serait toujours pas assez pour la compilation. Que la grammaire serait seulement de reconnaître un programme C++. Reconnaître si un programme est valide ou non valide en C++ est de peu d'utilité. Vous auriez également besoin de l'arbre d'analyse le "construit" dans des conditions bien définies afin de préserver toute la sémantique. Comme indiqué précédemment, aussi longtemps que vous pouvez distinguer entre valides et non valides analyser, vous n'avez pas besoin de se soucier de "l'ambiguïté" à partir d'un point de vue théorique.
    • le problème, c'est que le général systèmes de réécriture ne sont pas une très bonne façon d'écrire des analyseurs, tout comme Turing état les machines ne sont pas une très bonne manière de l'écriture d'algorithmes. Néanmoins, je ne peux pas vraiment dire que la réécriture de reconnaissance serait inutile. En l'augmentation de l'existant CFG avec un quelconque autre système formel qui pourrait porte notamment productions produira effectivement utilisable analyseur: l'CFG fournit la structure grammaticale. Malheureusement, la mise en œuvre de l'instanciation d'un modèle avec un système de réécriture serait quelque part entre un bon défi et BF.
    • J'ai essayé de ne pas utiliser le mot "inutile". Mon point est qu'une grammaire qui pourrait accepter/rejeter C++ n'est pas assez pour décrire le comportement de la sortie du programme, tout comme l'ambiguïté du contexte de la grammaire pourrait ne pas être suffisante pour la même chose (ce qui semble avoir été une source de confusion pour certaines personnes tout au long de cette page de le confondre avec sensibilité au contexte de la langue définie par la grammaire). Je suis d'accord que c'est un défi intéressant. Je serais curieux de voir comment il peut être difficile, même pour le plus simple des langues et pas du C++).
    • Cette réponse contient de nombreuses failles. Le mot "contexte" est agité autour de trop de manière informelle, ce qui est faux parce que la question est à propos de "context-free", qui est un terme. L'erreur dans le modèle n'est pas en fait une erreur de syntaxe mais une erreur sémantique. Un langage de spécification peut déclarer "fiat" qu'un programme qui porte atteinte à un sémantique contrainte n'est pas bien formé, et doivent être diagnostiqués comme si elle a un syntaxe d'erreur. Mais c'est juste une affaire de pointer vers la queue, et de l'appeler une jambe. Le fait est que la construction erronée a un parse. Exact morceau de texte analyse sous certaines conditions.
    • À suivre jusqu'à Kaz remarques: la réponse doit clairement faire la distinction entre la tâche d'analyse syntaxique en C++ avec l'objectif de les interpréter, et de simplement de reconnaître si un morceau de code est syntaxiquement valide en C++. Il devrait également faire état de ce qui constitue exactement une définition de quand un programme C++ est " syntaxiquement valide.
    • Je ne vois pas comment le modèle d'évaluation est la même que l'analyse, qui est ce que l'OP a une question sur. Je viens de lire cette réponse, "Un sous-ensemble de C++ est évaluée au moment de la compilation", qui arrive à se passer après analyse mais avant le "vrai" programme fonctionne vraiment, peut-être que c'est pourquoi ils sont en train de s'embrouiller ici.
    • J'ai fait la définition de "contexte" dans "sensible au contexte" plus précis. (I savais ce que je voulais dire :), mais je suis d'accord il n'était pas suffisamment évident.) Il n'y a pas d'erreur dans le modèle; l'erreur (dans les cas où il y en a un) est de tenter d'invoquer un modèle qui n'existe pas. En raison de la façon dont C++ analyse <, >, et >> (parfois comme des opérateurs, et parfois entre parenthèses), il est nécessaire de savoir si un symbole qui précède une < est un modèle avant qu'il soit possible de savoir ce lexeme le suit. Une fois > est connu pour être un opérateur, value > () est une erreur de syntaxe.
    • voir le précédant commentaire. Vous ne pouvez pas terminer l'analyse sans instanciation du modèle, de sorte que l'instanciation ne peut pas arriver "après les analyser".
    • si vous avez une ancienne g++)
    • Peut-être l'exemple serait plus clair si les deux branches compilé, mais produit clairement différents analyser les arbres.
    • Ma version originale de cet exemple a fait juste que, (vous pouvez l'obtenir en mettant 0 à l'intérieur de (), pour une simple), mais je pense qu'il est plus intéressant de cette façon, car il montre que vous avez besoin de l'instanciation d'un modèle même de reconnaître si une chaîne est une syntaxiquement correcte programme en C++. Si les deux branches de la compilation, alors je dois travailler plus fort, pour contester l'argument que la différence est "sémantique". Curieusement, même si je suis souvent du mal à définir "syntaxique", personne n'a jamais proposé une définition de la "sémantique" autres que les "choses" je ne pense pas syntaxique" 🙂
    • Si c'était vrai pourquoi avez-vous besoin pour utiliser le modèle de mots clés lors de l'appel d'une méthode basé sur un modèle de la classe de base? Je pensais que c'était ajoutée afin d'empêcher tout particulièrement ce que vous décrivez. Peut-être que nous sommes à la définition de l'analyse est la question-et je considère que dès que le compilateur sait que typen<> doit être d'un modèle que le fichier est "analysée'. Que vous obtenez un message d'erreur lorsqu'il n'est pas saisie d'un nombre premier, je ne le décrivent pas comme une erreur d'analyse (même si elle se produit avant la génération de code), tout comme je ne voudrais pas envisager une static_assert l'échec d'une erreur d'analyse.
    • vous avez besoin de la template mot-clé seulement lorsque l'identifiant qui nomme le modèle est une personne à charge nom. Ça ne s'applique pas dans le cas de mon programme. Si l'identifiant n'est pas une personne à charge, le nom template mot-clé est, euh, une erreur de syntaxe. (Ce qui m'a surpris, mais c'est vrai. Essayez-la.) Par la façon dont, personnellement, je ne pense pas que le fichier est analysé jusqu'à ce que le dernier caractère est analysée, mais votre définition d'œuvres: Le compilateur ne sait pas que typen est un modèle jusqu'à ce que après il instancie foo<IsPrime<234799>> (car il ne serait pas avec foo<IsPrime<234797>>).
    • petite correction. Apparemment, vous peut utiliser template même si le compilateur peut le comprendre pour lui-même. (Tant que le nom est qualifié.) Donc, en effet, j'aurais pu écrire template typen, ce qui aurait causé l'erreur de syntaxe à être remarqué un couple de jetons plus tôt, car il serait alors immédiatement une erreur après le non-premier foo<IsPrime<234797>> modèle a été instancié, au lieu d'attendre jusqu'à ce que le > est analysée comme un opérateur de comparaison et la () est pas parseable comme une expression.
    • Je vois, mais je trouve toujours la terminologie quelque peu trompeur. Appeler ça une erreur de syntaxe suggère que l'adoption d'un nombre composé de la IsPrime modèle de syntaxe erreur, lorsque seulement une langue, avocat de l'identifier comme telle. Pour être vraiment pointilleux, il semble comme un ordre supérieur type d'erreur, où le passage d'un nombre composé n'est pas supérieur-type-vérifier que typen n'est pas un genre de type qui prend des arguments de modèle.
    • le passage d'un nombre composé de la IsPrime modèle est just fine. Ce n'est pas une erreur de type; c'est une simple erreur de syntaxe. Vous ne pouvez pas utiliser () comme une expression, c'est tout. (Bien sûr, le vrai problème est que dans ce cas particulier, il n'est pas facile de prévoir que < est un opérateur; en particulier, les êtres humains se tromper parce que nous n'en réalité (et parfois à tort) l'utilisation des espaces sensibles de l'analyse. Mais le compilateur connait la syntaxe de mieux). De toute façon, je n'étais pas à parler la langue de la légalité; je parlais de grammaire formelle de la théorie.
    • Ah, je comprends maintenant. Lorsque vous passez un composite de l'erreur techniquement vient de la () n'étant pas une expression, même si le compilateur ne va pour cette interprétation basée sur typen n'étant pas un modèle, plutôt que de erroring en raison de typen n'étant pas un modèle.
    • Le IsPrime<...> exemple (avec programme) a été extrême exagéré pour un simple point... de façon plus simple (comme dans le moins alambiqué) exemple aurait été quelque chose comme: nullptr_t n = std::conditional<true, nullptr_t, int>::type{}; qui est "syntaxiquement correct" (que l'OP a formulé) si et seulement si le premier paramètre du modèle est true.
    • Je suis d'accord avec votre utilisation de "syntaxiquement correct" (qui a été ma phrase, pas OP), mais de nombreux commentateurs ne le font pas; je pense qu'ils devraient décrire votre exemple comme syntaxiquement correct, mais sémantiquement incorrect (car c'est un type d'erreur). IsPrime sortait d'une enquête de la façon dont la syntaxe, de la couleur de C++; elle faisait partie de ma prise de conscience que c'est vraiment pas pratique pour définitivement décider si < est un opérateur ou un support. (Heureusement, il y a de bonnes heuristiques et de la syntaxe-la coloration est autorisé à être mal dans les cas pathologiques.)
    • J'ai effectivement le côté avec les autres intervenants que l'erreur est une sémantique de l'un, pas un de syntaxe, mais j'avoue que c'est dur de classer un modèle de méta-erreur de programmation. Le point de mon commentaire était de montrer que votre IsPrime exemple était un peu "ésotérique" pour le simple point vous étiez en train de faire. En fin de compte, si oui ou non votre programme compilé dépendait 1) le résultat d'un modèle de méta-programmation, et 2) si oui ou non la résultante rvalue type est implicitement convertible à la lvalue type. Cela semble être une question sémantique, et non pas syntaxique, une.
    • La seule lvalue dans mon petit programme est auto donc il n'y a pas de type de conversion à tous; je pense que vous êtes l'incompréhension de la nature du programme. Le syntaxiques question est de savoir si typen<1>() est (a) une instanciation d'un modèle ou (b) une expression simple. En d'autres termes, si le < et > sont modèle des crochets ou des opérateurs de comparaison. Dans le premier cas, () est un paramètre vide de la liste; dans ce dernier cas, c'est une erreur de syntaxe. Je ne vois pas comment vous pouvez appeler cette erreur de syntaxe rien d'autre qu'une erreur de syntaxe, et qui a été le point de l'exemple.
    • Il est le type de déduction, qui est encore une sémantique non syntaxique question. J'ai pris un autre regard sur le programme, et il peut être simplifié à auto b = std::enable_if< true/false , SomeType >(); ... si oui ou non il compile dépend du C++ principe de SFINAE, qui est certainement une question sémantique. Je vois ce que vous dites à propos de l'analyse du membre de droite de l'expression comme (foo<false>::typen < 1) > () comme un "plus délicate à analyser" le scénario qui résulte en une erreur de syntaxe au () que le 2ème argument de operator>. Il est assez intéressant de faire ses propres DONC, la question pour le C++ experts de disect.
    • Je pense que vous avez besoin de regarder un peu plus :). Ce n'est pas la "plus délicate à analyser", car il s'agit clairement d'une instruction d'affectation. Notez également que si vous mettez une valeur à l'intérieur des parenthèses, dire typen<1>(42)', then it would not be a syntax error regardless of whether IsPrime " est instancié avec un premier ou pas, mais dans les deux cas, produire radicalement différent de la traite. Ce que vous êtes peut-être manque, c'est que typen pourrait être un modèle d'alias, ou il peut être un static const int; vous avez besoin de savoir qui il est afin d'analyser ce qui suit typen. Par l'analyse, je veux dire analyser. D'où la syntaxe.
    • J'ai pris un autre (final) chercher, cette fois, fait à l'aide d'un compilateur, et le programme simplifie pour ces 3 états: struct foo { typedef int type; }; struct bar { const int type = 0; }; et soit auto b = foo::type(); ou auto b = bar::type(); ... La foo cas est très bien comme il crée un par défaut int. Le bar cas devient auto b = 0(); qui est, en fait, une erreur de syntaxe dans cette forme simplifiée. Cependant, dans son modèle de formulaire, il "semble" plus comme une sémantique puisqu'elle dépend des résultats d'un modèle de méta-programme (bien qu'une banale), qui doit être évalués.
    • Le <false> cas plus précisément revient à auto b = 0<1>(); qui remonte à mon point précédent que cela pourrait être analysée comme auto b = ((0 < 1) > ()); auquel cas l'erreur de syntaxe se produit lors de la 2ème argument de operator> rend l'ensemble de l'expression non valide. La raison typen<1>(42) fonctionne, c'est que c'est le même que X<1>(42) qui implicitement construit une X int valeur 42. Si le constructeur ont été déclarées explicit, qui ne serait pas possible (une fois de plus, la sémantique).
    • La raison typen<1> fonctionne, c'est que typen est un modèle. C'est indépendant de la nature explicite du constructeur. Si typen était un non-type de modèle, puis typen<1> serait une autre erreur de syntaxe, parce qu'un nom ne peut pas être un opérande de l'opérateur <. Par ailleurs, il n'y est pas de l'optionalité à propos de l'analyse. doit être analysé soit comme basé sur un modèle du constructeur ou une expression, en fonction du "type" de la membre symbole typen; c'est pas a résolu l'ambiguïté, à la différence de la "délicate à analyser". Mais assez.
    • Oui, je sais typen est un template<int> struct X dans le <true> cas, et donc typen<1> est X<1>, et X<1>(42) implicitement construit un X<1>. Là où vous avez tort est dans le <false> cas, où typen est un const int, qui peut évidemment de l'opérande à un operator< invocation, ce qui rend possible de l'analyser comme le 1er argument à un operator< pour int arguments. Je suis d'accord avec le "assez" partie, nous semblent avoir un déconnecter ici. Par exemple, je l'ai dit typen<1>(42) et de vous lire typen<1>, etc.
    • laissez-nous continuer cette discussion dans le chat
    • "L'écriture d'une machine de Turing pour analyser le C++ serait tout aussi impossible de l'entreprise." Si une machine peut jamais exister pour analyser le C++, ce qui je suppose n'existe pas, une machine de Turing à le faire existe aussi. Juste pour dire. Revendiquant un analyseur syntaxique pour le C++ est Turing complet et en disant que c'est impossible d'écrire une machine de Turing est une contradiction.
    • Que la machine de Turing existe de la même manière que la représentation décimale de la cinquième Ackermann nombre (oeis.org/A189896) existe. Je ne crois pas qu'il est contradictoire d'affirmer qu'aucun être humain ne sera jamais écrire que nombre. Il est impossible, dans les contraintes physiques de l'univers. C'est l'impossibilité j'ai fait référence. Probablement, la machine de Turing n'est pas tout à fait aussi grand qu'une(5), mais je ne me sens pas comme je aller trop loin sur une branche d'affirmer que la tâche de l'écriture, c'est l'état de transition de la table n'est pas très plausible projet.
    • Ah bon, je l'ai interprété différemment. Appelons ça de la sémantique. Poste extraordinaire par la façon dont, certainement la meilleure analyse que j'ai jamais lu sur LE!
    • Ici est un peu plus propre C++14 version de votre (excellent) exemple: melpon.org/wandbox/permlink/8tpay0SxHvWXfDny
    • Je tiens également à souligner que le C++14 généralisée constexpr peut être utilisé pour créer un exemple similaire avec beaucoup moins mystique (pas besoin récursive de l'héritage).
    • Je ne comprends pas le but de cet exemple avec des nombres premiers. De primalité est decidable dans NSPACE(S(n)), et donc par un contexte sensible de la grammaire.

    InformationsquelleAutor rici
  2. 113

    Tout d'abord, vous l'avez fort justement observé qu'il y a pas de règles contextuelles dans la grammaire à la fin du C++ standard, de sorte que la grammaire est libre de tout contexte.

    Cependant, que la grammaire n'est pas de décrire avec précision le langage C++, car elle produit non-programmes C++ comme

    int m() { m++; }

    ou

    typedef static int int;

    Le langage C++ définit comme "l'ensemble des bien formé programmes C++" n'est pas libre de tout contexte (il est possible de montrer que le fait de simplement exigeant des variables déclarées en fait si). Étant donné que vous pouvez théoriquement écrire Turing-complet des programmes dans les modèles et faire d'un programme un mal formé en fonction de leur résultat, il n'est même pas sensible au contexte.

    Maintenant, (ignorant) de personnes (généralement pas la langue des théoriciens, mais analyseur concepteurs utilisent généralement "pas libre de tout contexte" dans certains de la signification suivante

    • ambigu
    • ne peut pas être analysée avec le Bison
    • pas LL(k), LR(k), LALR(k) ou que ce soit par l'analyseur, la langue définie par la classe, ils ont choisi

    La grammaire à l'arrière de la norme n'est pas satisfaire à ces catégories (c'est à dire qu'il est ambigu, pas LL(k)...) donc C++ grammaire "n'est pas libre de tout contexte" pour eux. Et dans un sens, ils ont raison c'est sacrément bien dur pour produire un travail analyseur C++.

    Noter que les propriétés utilisée ici ne sont que faiblement lié au contexte des langues - l'ambiguïté n'a rien à voir avec sensibilité au contexte (en fait, sensible au contexte des règles généralement aide à distinguer les productions), les deux autres sont simplement des sous-ensembles de contextes langues. Et l'analyse du contexte de libre-langues n'est pas un processus linéaire (bien que l'analyse déterministe de l'est).

    • ambiguity doesn't have anything to do with context-sensitivity C'était mon intuition aussi, je suis heureux de voir quelqu'un (une) d'accord, et (b) expliquer où je ne pouvais pas. Je crois qu'il disqualifie tous les arguments qui sont fondés sur a b(c);, et partiellement satisfaire à la question d'origine, dont le principe a été "souvent entendu" les revendications de la sensibilité au contexte en cours en raison de l'ambiguïté... surtout quand, pour la grammaire il n'y a pas d'ambiguïté, même dans le titre de MVP.
    • Ouais, c'est une autre raison pour laquelle j'ai supprimé ma réponse, après j'ai réfléchi un peu plus. Je pense qu'une grammaire est ambiguë complètement fine tant que les chaînes qu'il produit sont ceux (et que ces) à l'intérieur de la langue. C'est pourquoi je ne suis pas à voir comment d'une CSG serait de réussir à tout les problèmes qu'une CFG a échoué dans...
    • Ce serait une bonne réponse sans la phrase suivante: “ étant Donné que vous pouvez théoriquement écrire Turing-complet des programmes dans les modèles et faire d'un programme un mal formé en fonction de leur résultat, il n'est même pas sensible au contexte.” – C'est faux, sensible au Contexte est l'équivalent de Turing.
    • Pouvez-vous fournir la preuve de cela? (même si je ne suis pas le conteste)
    • Est l'article de Wikipédia n'est pas suffisant? C'est des manuels de connaissances.
    • J'aimerais une référence trop. en.wikipedia.org/wiki/Context-sensitive_language dit que sensible au contexte = Linéaire bornée automate, qui (à partir de ma compréhension limitée) n'est pas turing-complet en raison de la faible longueur de bande.
    • Donc, ne les modèles C++. La norme définit une profondeur maximale qu'un compilateur conforme à fournir (au minimum).
    • Une affirmation sans aucune référence n'est pas assez pour moi, et le pas de. Si vous êtes en citant un passage sur Wikipédia, veuillez fournir un lien et un devis.
    • Ok, je sais de cette limitation, mais ne jamais voir la personne qui fondent leur argumentation sur elle, donc en général je n'ai pas donner aux gens le bénéfice du doute 😉
    • Non, désolé. Je n'ai pas de fournir des sources pour “renvoi” de la connaissance qui peut être trivialement trouvé sur Google ou Wikipédia sans avoir à creuser pour eux.
    • Ce que dit la norme est "Il est de la mise en œuvre définie par la quantité qui spécifie la limite de la profondeur totale de récursive instanciations, ce qui peut impliquer plus d'un modèle. Le résultat d'une récursion infinie dans l'instanciation est pas défini." (14.7.1p15) - je en déduire qu'une mise en œuvre n'est pas nécessaire de comprendre chaque valides programme en c++, pas que les programmes avec une trop grande profondeur de récursion ne sont pas valides. Les seuls qui sont marqués comme non valides sont ceux avec une infinie profondeur de récursion.
    • Ah. Oui, je vois. Je pense que les versions précédentes de la norme spécifiée explicitement à un niveau supérieur (ce qui était assez faible, et la cause de beaucoup de colère, si je me souviens bien).
    • Ce n'est pas très scientifique de vous. Je suis vraiment bon à Googler et n'ai rien trouvé "trivialement". Puisque vous avez été pas en mesure ou refuse de fournir une référence lorsque l'on a demandé, je n'ai pas d'autre choix que de déclarer votre affirmation comme inadmissibles!
    • Non-sens. En fait, il est commun dans les discussions scientifiques à prendre “renvoi” de la connaissance de soi. Et j'ai même fait de vous Wikipedia. Voulez-vous vraiment me faire croire que vous avez lu l'article sur “sensible au contexte de la grammaire” et pas trouvé le paragraphe pertinent?
    • Je conteste qu'il est "renvoi". Le fait que j'ai lu que complexe article et ne pas comprendre suffisamment la pièce à ce petit fait devrait suffire à démontrer que. C'est pas comme si vous dites quelque chose comme "les ordinateurs utilisent couramment l'électricité", ou "bits peut être vrai ou faux".
    • Si ce fait est aussi largement connu je pense qu'il serait beaucoup plus facile de trouver une référence à ce que d'argumenter longuement sur si oui ou non on doit être fournie. Pour ne pas mentionner constructif.
    • Aussi loin que je peux dire, @Konrad s'est trompé quand il a dit "sensible au Contexte est l'équivalent de Turing." (au moins, il était si il était signifiant "Récursivement énumérable" par "Turing complet"), et a depuis été incapable de reconnaître cette erreur. Ici est une référence pour l'ensemble approprié de l'inclusion relation en cause ici: en.wikipedia.org/wiki/Chomsky_hierarchy
    • ou les gens utilisent le terme "libre de tout contexte linguistique" de l'autre, un CFG peut décrire une superset de l' (valide) les chaînes de caractères composée du langage (y compris les non-valides que par votre exemple). note: je ne voudrais pas étiqueter les gens travaillant avec des implémentations "ignorants", simplement parce qu'ils utilisent une mise en œuvre spécifique de CFGs au lieu d'un résumé formalité
    • Peut-on dire que le langage C++ est défini par la grammaire dans le cahier des charges, avec des restrictions? Cela peut-il être modélisé avec un minimum de grammaire, également avec des restrictions, pour illustrer la situation plus facilement?

    InformationsquelleAutor jpalecek
  3. 60

    Oui. L'expression suivante a un autre ordre des opérations selon type résolu contexte:

    Edit: Lorsque la commande de fonctionnement varie, il est incroyablement difficile d'utiliser un "régulier" du compilateur qui analyse à un non AST avant de les décorer. il (se propageant type d'information). D'autres sensibles au contexte choses mentionnées sont "plutôt facile" par rapport à cela (pas ce modèle d'évaluation est facile).

    #if FIRST_MEANING
template<bool B>
class foo
{ };
#else
static const int foo = 0;
static const int bar = 15;
#endif

    Suivie par:

    static int foobar( foo < 2 ? 1 < 1 : 0 > & bar );
    • Pourquoi peut que le problème ne se résout pas comme pour C, en se rappelant le type de définitions de la portée?
    • Une façon de faire un compilateur "propre" est de séparer les tâches en étapes indépendantes dans une chaîne, comme la création d'un arbre d'analyse à partir de l'entrée, suivie par une étape qui fait le type de l'analyse. C++ vous oblige soit à 1) fusion de ces étapes en une, ou 2) analyser le document en fonction à la fois/toutes les interprétations possibles, et permettant la résolution de type stades de la réduire à l'interprétation correcte.
    • d'accord, mais c'est le cas pour C, trop; je pense qu'une bonne réponse à cette question devrait montrer pourquoi C++ est pire que C. de La thèse de Doctorat liée ici n'est que: stackoverflow.com/a/243447/53974
    InformationsquelleAutor Sam Harwell
  4. 25

    Pour répondre à votre question, il faut distinguer deux questions différentes.

    1. La simple syntaxe de presque chaque langage de programmation est libre de tout contexte. Généralement, il est donné comme un extended Backus-Naur form ou context-free grammar rencontrent.

    2. Cependant, même si un programme est conforme avec le contexte-free grammar rencontrent défini par le langage de programmation, il n'est pas nécessairement un valide programme. Il y a beaucoup de non-libre de tout contexte poperties qu'un programme doit satisfaire afin d'être d'un programme valide. E. g., le plus simple de ces biens est la portée des variables.

    Pour conclure, si oui ou non C++ est libre de tout contexte dépend de la question que vous vous posez.

    • Il est intéressant de noter que vous avez souvent à la place de la "de simples de la syntaxe de" niveau inférieur à celui que vous attendez, afin d'obtenir une CFG pour votre langage de programmation. Prendre C, par exemple. Vous pourriez penser que la règle de grammaire pour une simple déclaration de variable en C serait VARDECL : TYPENAME IDENTIFIER, mais vous pas ont que, parce que vous ne pouvez pas distinguer les noms de type de d'autres identifiants à un CF de niveau. Un autre exemple: lors d'une FC, vous ne pouvez pas décider d'analyser a*b comme une déclaration de variable (b de type pointeur vers a) ou comme une multiplication.
    • Oui, merci de le signaler! En passant, je suis sûr qu'il est plus communément utilisé le terme technique pour simple syntaxe. Personne ne le bon terme?
    • de quoi vous parlez est une approximation de la langue donnés par certains grammaire libre de tout contexte. Bien sûr, un tel rapprochement est coontext-libre par définition. C'est le sens dans lequel la "syntaxe" est souvent utilisée lors de la discussion des langages de programmation.
    InformationsquelleAutor Dan
  5. 12

    Ouais C++ est sensible au contexte, très sensibles au contexte. Vous ne pouvez pas construire l'arbre de syntaxe par la simple analyse du fichier à l'aide d'un contexte de libre-analyseur parce que, dans certains cas, vous devez connaître le symbole de la connaissance précédente de décider (ie. construire une table des symboles lors de l'analyse).

    Premier exemple: 

    A*B;

    Est-ce une multiplication d'expression?

    OU

    Est-ce une déclaration de B variable est un pointeur de type A?

    Si A est une variable, alors c'est une expression, si A est de type, c'est une déclaration de pointeur.

    Deuxième exemple:

    A B(bar);

    Est-ce un prototype de fonction prend un argument de bar type?

    OU

    Est-ce déclarer la variable B de type A et appelle Un constructeur avec bar constante comme un initialiseur?

    Vous avez besoin de savoir encore si bar est une variable ou d'un type de table de symboles.

    Troisième exemple:

    class Foo
{
public:
void fn(){x*y;}
int x, y;
};

    C'est le cas lors de la construction de la table des symboles lors de l'analyse n'aide pas parce que la déclaration de x et y vient après la définition de la fonction. Si vous avez besoin de numériser à travers la définition de la classe de première, et de regarder les définitions de méthode dans un second passage, pour dire x*y est une expression, et non pas une déclaration de pointeur ou de quoi que ce soit.

    • A B(); est une déclaration de fonction, même dans une définition de fonction. Recherchez plus délicate à analyser...
    • "On ne peut pas construire l'arbre de syntaxe par la simple analyse du fichier" FALSE. Voir ma réponse.
    InformationsquelleAutor Calmarius
  6. 12

    Vous voudrez peut-être jeter un oeil à Le Design & Évolution de C++, par Bjarne Stroustrup. Il y décrit ses problèmes en essayant d'utiliser yacc (ou similaire) pour analyser une première version de C++, et souhaitant qu'il avait utilisé récursive descente à la place.

    • Wow... Merci. Je me demande si il fait vraiment de sens de pense à propos de l'aide de quelque chose de plus puissant qu'une CFG pour analyser toute langue artificielle.
    • Excellent livre pour comprendre le pourquoi de C++. Je recommande et Lippman, qui est à l'Intérieur de l'Objet C++ Modèle pour comprendre comment C++ fonctionne. Bien que les deux sont un peu daté, ils sont encore une bonne lecture.
    • "Méta-S" est un contexte sensible moteur d'analyse par Quinn Tyler Jackson. Je ne l'ai pas utilisé, mais il raconte une histoire impressionnante. Découvrez ses commentaires dans le comp.les compilateurs, et de voir rnaparse.com/MetaS%20defined.htm
    • votre x-ref MIA aujourd'hui - et de solides références pour le logiciel semble être insaisissable (recherche Google ne fournit pas de bonnes pistes, soit avec des 'site:rnaparse.com méta-s" ou "quinn jackson méta-s'; il y a de pièces et de morceaux, mais meta-s.com conduit à une non-information du site web, par exemple).
    • été un certain temps, juste remarqué que votre plainte. Je ne sais pas pourquoi le lien est mauvais, j'ai pensé qu'il était bon quand je l'ai écrit. Quinn l'habitude d'être très active dans la comp.les compilateurs. Google semble être feuilletée, c'est tout ce que je peux trouver: groups.google.com/group/comp.compilers/browse_thread/thread/... autant que je me souvienne, il a signé plus de droits à MetaS certaine tenue à Hawaii pour remettre sur le marché. Compte tenu de la façon tecnically bizarre c'était, à mon humble avis, c'est signer son arrêt de mort. Sonnait comme un très habile stratagème.
    • il y a un supprimée réponse au bas de laquelle vous devriez être en mesure de lire Quinn Tyler Jackson sur les Méta-S. Il (Méta-S) peuvent très bien avoir des morts.
    • Ah, oui, typique Quinn réponse. Bonne chance avec elle. Un jour, je devrais aller lire le tech rapport (je pense) il a écrit à ce sujet. Je comprends comment il (ce qui pourrait avoir) est mort; c'est assez difficile d'amener les gens à prendre les arcanes de la technologie. Témoin de ce que je fais comme un autre exemple :-{
    • En fait, il y a un récupérés réponse dans laquelle il se réfère au mystérieux nom de la société: Thothic. J'ai ajouté un lien vers le site web de la société dans les commentaires. Je n'ai aucune connaissance.

    InformationsquelleAutor
  7. 10

    C++ est analysé avec GLR de l'analyseur. Cela signifie que lors de l'analyse du code source, l'analyseur peut la rencontre de l'ambiguïté, mais il doit continuer et de décider quelle règle de grammaire à utiliser plus tard.

    look aussi,

    Pourquoi C++ ne peut pas être analysé avec un LR(1) analyseur?

    Se rappeler que le contexte grammaire ne peut pas décrire TOUS les règles d'un langage de programmation syntaxe. Par exemple, l'Attribut de la grammaire est utilisée pour vérifier la validité d'un type d'expression.

    int x;
x = 9 + 1.0;

    Vous ne peut pas décrire les aspects suivants de la règle de la grammaire libre de tout contexte :
    Le Côté Droit de la mission doivent être du même type de la Gauche.

    InformationsquelleAutor AraK
  8. 9

    J'ai le sentiment qu'il y a une certaine confusion entre la définition officielle du terme "sensible au contexte" et le secteur informel de l'utilisation de "sensible au contexte". La première a une bien définis. Ce dernier est utilisé pour dire "vous avez besoin de contexte afin d'analyser l'entrée".

    C'est aussi posée ici:
    Sensibilité au contexte vs Ambiguïté.

    Voici une grammaire libre de tout contexte:

    <a> ::= <b> | <c>
<b> ::= "x"
<c> ::= "x"

    C'est ambigu, dans le but d'analyser l'entrée "x" vous avez besoin d'un contexte (ou en direct avec l'ambiguïté, ou émettre des "Avertissement: E8271 d'Entrée est ambigu dans la ligne 115"). Mais ce n'est certainement pas un contexte sensible de la grammaire.

    • Comment le fait d'avoir plusieurs symboles sur le côté gauche d'une production de résoudre ce problème? Je ne pense pas que cette réponse est la réponse à la question.
    • Ma réponse est dans la réponse à la première phrase: "j'entends souvent des réclamations que le C++ est un contexte sensible de la langue." Si ces revendications, l'expression "sensible au contexte" de façon informelle, puis il n'y a pas de problème. Je ne pense pas que le C++ est formellement sensible au contexte.
    • Je pense que C++ est officiellement sensible au contexte, mais le problème que je rencontre est que je ne comprends pas comment un contexte sensible de la grammaire aurait plus de succès, à l'analyse C++ qu'un CFG serait.
    InformationsquelleAutor Omri Barel
  9. 6

    Pas Algol-comme le langage est libre de tout contexte, parce qu'ils ont des règles qui limitent les instructions et expressions que les identificateurs peuvent apparaître en fonction de leur type, et parce qu'il n'y a pas de limite sur le nombre de déclarations qui peuvent se produire entre la déclaration et l'utilisation.

    La solution habituelle est d'écrire un contexte de libre parser qui accepte réellement un sur-ensemble de l'valide les programmes et de mettre le contexte-les parties sensibles dans ad hoc "sémantique" code attaché à des règles.

    C++ va bien au-delà de cela, grâce à son Turing-complet système de template. Voir Un Débordement De Pile Question 794015.

    InformationsquelleAutor James Jones
  10. 5

    Vrai 🙂

    J. Stanley Warford. Les systèmes informatiques. Pages 341-346.

    InformationsquelleAutor anno
  11. 5

    Il est sensible au contexte, comme a b(c); a deux valides analyse - déclaration et variable. Quand vous dites "Si c est un type", c'est le contexte, là, et vous avez décrit exactement comment C++ est sensible. Si vous n'avez pas eu ce contexte de "qu'est-Ce que c?", vous pourriez ne pas analyser cette ambiguïté.

    Ici, le contexte est exprimé dans le choix des jetons - l'analyseur lit un identificateur de typename jeton si il le nom d'un type. C'est la résolution la plus simple, et évite une grande partie de la complexité de l'être sensible au contexte (dans ce cas).

    Edit: Il y a, bien sûr, plus de problèmes de sensibilité de contexte, j'ai simplement porté sur celui que vous avez indiqué. Les modèles sont particulièrement désagréables pour cela.

    • Aussi a<b<c>>d, droit? (Votre exemple est en fait un classique de C, où il est le que obstruction d'être libre de tout contexte.)
    • C'est plus d'un lexing problème, je pense. Mais il est certainement dans la même catégorie, oui.
    • L'interlocuteur ne demandez pas comment c'est plus contextuelle que C, uniquement pour montrer qu'il est sensible au contexte.
    • Donc.. est C++ plus sensibles au contexte que C?
    • Assez sûr qu'il y a plus d'ambiguïté, oui.
    • Je ne pense pas que vous êtes la réponse à la question (je ne pense pas que j'étais soit). Comment le fait d'avoir des bornes sur le côté gauche d'une production de résoudre ce problème?
    • La question n'est pas de demander. Il demande seulement si le C++ est sensible au contexte. Il est. C'est tout là est à lui. Je crois que vous auriez à faire les terminaux supplémentaires correspondent à la définition de type, alors vous pouvez le faire correspondre à une fonction decl, ou vous faire les terminaux supplémentaires correspondent à une définition de la variable, alors vous pouvez le faire correspondre à la variable decl. Mais vous auriez à demander à quelqu'un qui se soucie du contexte de grammaires, sauf de ne pas la production de l'un ou de piratage du fait que le contexte sensible de la partie, pas à moi.

    InformationsquelleAutor Puppy
  12. 5

    Les productions dans la norme C++ sont écrits libre de tout contexte, mais comme nous le savons tous n'ont pas vraiment définir la langue avec précision. Certains de ce que la plupart des gens considèrent comme une ambiguïté dans le langage courant pourrait (je crois) être résolu sans ambiguïté avec un contexte sensible de la grammaire.

    Pour l'exemple le plus évident, considérons la Plus Délicate à Analyser: int f(X);. Si X est une valeur, alors ceci définit f comme une variable qui sera initialisé avec X. Si X est un type, il définit f comme une fonction prenant un seul paramètre de type X.

    À la recherche à partir d'un point de vue grammatical, on pourrait l'afficher comme ceci:

    A variable_decl ::= <type> <identifier> '(' initializer ')' ';'
B function_decl ::= <type> <identifier> '(' param_decl ')' ';'
A ::= [declaration of X as value]
B ::= [declaration of X as type]

    Bien sûr, pour être tout à fait correct, nous aurions besoin d'ajouter des extra "trucs" pour tenir compte de la possibilité d'intervention des déclarations d'autres types (c, A et B doivent à la fois être vraiment "déclarations y compris la déclaration de X...", ou quelque chose de cet ordre).

    C'est encore assez différents à partir d'un type CSG bien (ou au moins ce que je me souviens d'entre eux). Cela dépend d'un symbole de la table en cours de construction -- la partie qui reconnaît spécifiquement X comme un type ou de la valeur, pas seulement un certain type de déclaration précédente, mais le bon type de déclaration pour le droit de symbole/identificateur.

    En tant que tel, je devrais faire quelques recherche pour être sûr, mais ma conjecture est que ce n'est pas vraiment qualifier de CSG, à moins que le terme est utilisé normalement.

    • L' (context-free) productions définir la plus délicate à analyser assez bien, de sorte qu'il peut être analysé par un contexte de libre-moteur d'analyse. Que les retards le problème de décider lequel de multiples interprétations sont valables qu'après l'analyse est terminée, mais qui vient de faire l'ingénierie de l'analyseur et de résolution de nom de plus facile, parce qu'ils sont modulaires plutôt que emmêlés comme dans le conventionnel C++ analyseurs. Voir AST pour plus délicate à analyser: stackoverflow.com/questions/17388771/...
    InformationsquelleAutor Jerry Coffin
  13. 5

    Le plus simple des cas de non-context-free grammar implique l'analyse des expressions impliquant des modèles.

    a<b<c>()

    Cela peut analyser comme

    template
|
a < expr > ()
|
<
/   \
b     c

    Ou 

     expr
|
<
/   \
a   template
|
b < expr > ()
|
c

    Les deux ASTs ne peut être désambiguïsés par l'examen de la déclaration de 'a' - ex AST si 'a' est un modèle, ou le dernier si ce n'.

    • Je crois que C++11 mandats de la seconde interprétation, et vous devez ajouter des parenthèses à l'opt-in à l'ancienne.
    • pas de. C++ mandats que < doit être un support s'il pouvait être (eg., il en résulte un identifiant portant le nom d'un modèle). C++11 a ajouté l'exigence que > et le premier caractère de >> être interprétées comme des crochets fermants, si cet usage est tout à fait plausible. Cela affecte l'analyse de a<b>c> où a est un modèle, mais n'a aucun effet sur a<b<c>.
    • comment est-ce plus simple que a(); (qui est soit expr.call ou expr.type.conv)?
    • Oups, je ne savais pas que c'était asymétrique.
    • Êtes-vous décrivant ambiguïté, ou de la sensibilité de contexte?
    InformationsquelleAutor Aaron
  15. 4

    Modèles C++ ont été montré pour être Turing Puissant. Bien que n'étant pas un officiel de référence, voici un lieu de chercher à cet égard:

    http://cpptruths.blogspot.com/2005/11/c-templates-are-turing-complete.html

    Je vais tenter une conjecture (vieux comme un folkoric et concis CACM de preuve indiquant que l'ALGOL dans les années 60 n'a pas pu être représentée par un CFG) et de dire que le C++ ne peut donc pas être correctement analysée que par une CFG. CFGs, en collaboration avec les divers TP mécanismes dans un arbre de passer ou au cours de la réduction des événements -- ceci est une autre histoire. Dans un sens général, en raison du Problème de l'Arrêt, il existe un programme en C++ qui ne peut être montré pour être correct/incorrect, mais est néanmoins correct/incorrect.

    {PS - Comme l'auteur de la Méta-S (mentionné par plusieurs personnes ci-dessus) - je peux assurément dire que Thothic est ni disparu, ni le logiciel est disponible gratuitement. Peut-être que j'ai rédigé cette version de ma réponse que je n'ai pas été supprimé ou ont voté jusqu'à -3.}

    InformationsquelleAutor Quinn Tyler Jackson
  16. 3

    C++ n'est pas sans contexte. J'ai appris il y a quelque temps dans les compilateurs de conférence. Une recherche rapide a donné ce lien, où la "Syntaxe ou de la sémantique" section explique pourquoi le C et le C++ ne sont pas sans contexte:

    Wikipédia Parler: Context-Free grammar

    Ce qui concerne,

    Ovanes

    InformationsquelleAutor ovanes
  17. 2

    Évidemment, si vous prenez la question verbatim, près de toutes les langues avec les identifiants sont sensibles au contexte.

    Un besoin de savoir si un identificateur est un nom de type (un nom de classe, un nom introduit par la définition de type, un typename paramètre du modèle), le nom d'un modèle ou d'un autre nom pour être en mesure de correctement certains de l'utilisation de l'identificateur. Par exemple:

    x = (name)(expression);

    est une fonte si name est un nom de type et d'un appel de fonction si name est un nom de fonction. Un autre cas est la soi-disant "plus délicate à analyser" où il n'est pas possible de différencier la définition des variables et déclaration de fonction (il y a une règle disant que c'est une déclaration de fonction).

    Que la difficulté a introduit la nécessité de typename et template ayant à charge des noms. Le reste de C++ n'est pas sensible au contexte pour autant que je sais (c'est à dire qu'il est possible d'écrire un contexte de grammaire pour elle).

    InformationsquelleAutor AProgrammer
  18. 2

    Méta-S" est un contexte sensible moteur d'analyse par Quinn Tyler Jackson. Je ne l'ai pas utilisé, mais il raconte une histoire impressionnante. Découvrez ses commentaires dans le comp.les compilateurs, et de voir rnaparse.com/MetaS%20defined.htm – Ira Baxter 25 Juil à 10:42

    Le lien correct est l'analyse enigines

    Méta-S a été la propriété d'une société défunte appelé Thothic. Je peux vous envoyer un exemplaire gratuit de la Méta-S à toute personne intéressée et je l'ai utilisé dans l'analyse de l'arn de la recherche. Veuillez noter que les pseudonoeud grammaire" inclus dans les exemples de dossiers a été écrit par un non-bioinformatique, amature programmeur et, fondamentalement, ne fonctionne pas. Mon grammaires de prendre une approche différente et fonctionnent très bien.

    • C'est en fait une trouvaille intéressante.
    InformationsquelleAutor
  19. 0

    Un gros problème ici est que les termes "context-free" et "sensible au contexte" sont un petit peu intuitive au sein de l'informatique. Pour C++, sensibilité au contexte ressemble beaucoup à l'ambiguïté, mais ce n'est pas nécessairement vrai dans le cas général.

    /C++, une instruction if est permis qu'à l'intérieur du corps d'une fonction. Qui semble la rendre sensible au contexte, à droite? Eh bien, non. Libre de tout contexte grammaires n'ont pas réellement besoin de la propriété où vous pouvez arracher quelques lignes de code et de déterminer si elle est valide. Ce n'est pas réellement ce contexte signifie. C'est vraiment juste une étiquette que vaguement implique quelque chose de gentil liées à ce que cela ressemble.

    Maintenant, si une instruction dans un corps de la fonction est analysée différemment en fonction de quelque chose de défini à l'extérieur immédiat de grammaire ancêtres (par exemple, si un identificateur décrit un type ou variable), comme dans le a * b; cas, alors il est, en effet, sensible au contexte. Il n'y a aucune ambiguïté là; il sera analysée comme une déclaration d'un pointeur si a est un type et une multiplication autrement.

    Être sensible au contexte ne signifie pas nécessairement "difficile à analyser". C est pas difficile, car l'infâme a * b; "ambiguïté" peut-être résolu avec une table de symboles contenant typedefs rencontrés précédemment. Il ne nécessite pas n'importe quel modèle d'instanciations (qui ont été prouvées pour être Turing Complet) pour résoudre ce cas, comme le C++ n'est qu'à l'occasion. Ce n'est pas vraiment possible d'écrire un programme C qui ne sont pas compilés dans une quantité limitée de temps, même si il a la même sensibilité au contexte que le C++ ne.

    Python (et d'autres espaces sensibles langues) est également dépendante du contexte, car il exige de l'état dans l'analyseur lexical pour générer de retrait et de dedent jetons, mais qui n'en est pas plus difficile à analyser que les typiques LL-1 de la grammaire. En fait, il utilise un analyseur générateur, qui est en partie pourquoi Python a peu la syntaxe des messages d'erreur. Il est également important de noter ici qu'il n'y est pas de "l'ambiguïté", comme le a * b; problème en Python, en donnant un bon exemple concret d'un contexte sensible à la langue sans "ambigu" de la grammaire (comme mentionné dans le premier paragraphe).

    InformationsquelleAutor Beefster