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 sensible au contexte.
Si vous autorisez l'arbitraire symbole de séquences sur les deux côtés de la production, de vous produire un Type-0 de la grammaire ("libre") dans la 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 l'équivalent 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 - 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 le 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: http://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 en IsPrime<N> est premier. Sinon, typen est un entier, et non pas un modèle, afin 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 l' α")
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".
