Poniżej moja (obecna) ulubiona demonstracja, dlaczego parsowanie C ++ jest (prawdopodobnie) zakończone przez Turinga , ponieważ pokazuje program, który jest poprawny pod względem składniowym wtedy i tylko wtedy, gdy dana liczba całkowita jest liczbą pierwszą.
Twierdzę więc, że C ++ nie jest pozbawiony kontekstu ani wrażliwy na kontekst .
Jeśli zezwalasz na dowolne sekwencje symboli po obu stronach dowolnej produkcji, tworzysz gramatykę typu 0 („nieograniczoną”) w hierarchii Chomsky'ego , która jest potężniejsza niż gramatyka kontekstowa; nieograniczone gramatyki są kompletne w Turinga. Gramatyka kontekstowa (typ 1) pozwala na umieszczenie wielu symboli kontekstu po lewej stronie produkcji, ale ten sam kontekst musi pojawić się po prawej stronie produkcji (stąd nazwa „kontekstowa”). [1] Gramatyki kontekstowe są równoważne maszynom Turinga ograniczonym liniowo .
W przykładowym programie obliczenia podstawowe mogą być wykonywane przez ograniczoną liniowo maszynę Turinga, więc nie do końca dowodzi to równoważności Turinga, ale ważną częścią jest to, że parser musi wykonać obliczenia w celu przeprowadzenia analizy składniowej. Mogłoby to być dowolne obliczenie wyrażone jako instancja szablonu i istnieją wszelkie powody, by sądzić, że tworzenie instancji C ++ jest zakończone metodą Turinga. Zobacz na przykład artykuł Todda L. Veldhuizena z 2003 roku .
Niezależnie od tego, C ++ może być analizowany przez komputer, więc z pewnością może być analizowany przez maszynę Turinga. W związku z tym nieograniczona gramatyka może to rozpoznać. W rzeczywistości pisanie takiej gramatyki byłoby niepraktyczne, dlatego standard tego nie próbuje. (Patrz poniżej.)
Problem „dwuznaczności” niektórych wyrażeń dotyczy głównie czerwonego śledzia. Po pierwsze, dwuznaczność jest cechą konkretnej gramatyki, a nie języka. Nawet jeśli można udowodnić, że język nie ma jednoznacznej gramatyki, jeśli można go rozpoznać po gramatyce bezkontekstowej, jest on pozbawiony kontekstu. Podobnie, jeśli nie może być rozpoznany przez gramatykę bezkontekstową, ale może być rozpoznany przez gramatykę kontekstową, jest wrażliwy na kontekst. Dwuznaczność nie ma znaczenia.
Ale w każdym razie, tak jak wiersz 21 (tj. auto b = foo<IsPrime<234799>>::typen<1>();) W poniższym programie, wyrażenia wcale nie są dwuznaczne; są one po prostu przetwarzane w różny sposób w zależności od kontekstu. W najprostszym wyrażeniu problemu kategoria składniowa niektórych identyfikatorów zależy od tego, jak zostały zadeklarowane (na przykład typy i funkcje), co oznacza, że język formalny musiałby rozpoznać fakt, że dwa ciągi o dowolnej długości w ten sam program jest identyczny (deklaracja i użycie). Można to modelować za pomocą gramatyki „kopiowania”, która jest gramatyką, która rozpoznaje dwie kolejne dokładne kopie tego samego słowa. Łatwo to udowodnić dzięki lemie pompującejże ten język nie jest pozbawiony kontekstu. Gramatyka kontekstowa dla tego języka jest możliwa, a odpowiedź na to pytanie zawiera gramatyka typu 0: /math/163830/context-sensitive-grammar-for-the- język kopii .
Gdyby ktoś spróbował napisać gramatykę kontekstową (lub nieograniczoną) w celu analizy C ++, całkiem możliwe, że wypełniłby wszechświat bazgrołami. Napisanie maszyny Turinga do analizy C ++ byłoby równie niemożliwym przedsięwzięciem. Nawet napisanie programu w C ++ jest trudne i, o ile wiem, żaden nie został sprawdzony. Dlatego standard nie zapewnia pełnej formalnej gramatyki i dlatego postanawia napisać niektóre zasady analizy w języku angielskim technicznym.
To, co wygląda na formalną gramatykę w standardzie C ++, nie jest pełną formalną definicją składni języka C ++. Nie jest to nawet pełna formalna definicja języka po wstępnym przetwarzaniu, którą łatwiej sformalizować. (Nie byłby to jednak język: język C ++ zdefiniowany w standardzie obejmuje preprocesor, a działanie preprocesora jest opisane algorytmicznie, ponieważ niezwykle trudno byłoby opisać go w jakimkolwiek formalizmie gramatycznym. To w tej sekcji normy, w której opisany jest rozkład leksykalny, w tym zasady, w których należy go stosować więcej niż jeden raz).
Różne gramatyki (dwie nakładające się gramatyki do analizy leksykalnej, jedna, która ma miejsce przed przetwarzaniem wstępnym, a druga, jeśli to konieczne, później, wraz z gramatyką „składniową”) są zebrane w załączniku A, z tą ważną uwagą (podkreślenie dodane):
To podsumowanie składni C ++ ma na celu pomóc w zrozumieniu. To nie jest dokładne określenie języka . W szczególności opisana tutaj gramatyka akceptuje nadzbiór prawidłowych konstrukcji C ++ . W celu odróżnienia wyrażeń od deklaracji należy zastosować reguły ujednoznacznienia (6.8, 7.1, 10.2). Ponadto należy zastosować kontrolę dostępu, niejednoznaczność i reguły typów, aby wyeliminować konstrukcyjnie poprawne, ale bezsensowne konstrukcje.
Wreszcie, oto obiecany program. Linia 21 jest poprawna pod względem składniowym wtedy i tylko wtedy, gdy N IsPrime<N>jest liczbą pierwszą. W przeciwnym razie typenjest liczbą całkowitą, a nie szablonem, dlatego typen<1>()jest analizowana jako (typen<1)>()niepoprawna pod względem składniowym, ponieważ ()nie jest wyrażeniem poprawnym pod względem składniowym.
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] Mówiąc bardziej technicznie, każda produkcja w gramatyce kontekstowej musi mieć postać:
αAβ → αγβ
gdzie Ajest nie-końcowy i α, βprawdopodobnie są pustymi sekwencjami symboli gramatycznych, i γjest niepustą sekwencją. (Symbole gramatyczne mogą być terminalami lub nie-terminalami).
Można to odczytać A → γtylko w kontekście [α, β]. W gramatyce bezkontekstowej (typ 2) αi βmusi być pusta.
Okazuje się, że można również ograniczyć gramatykę z ograniczeniem „monotonicznym”, gdzie każda produkcja musi mieć formę:
α → βgdzie |α| ≥ |β| > 0 ( |α|oznacza „długość α”)
Można udowodnić, że zestaw języków rozpoznawanych przez gramatyki monotoniczne jest dokładnie taki sam jak zestaw języków rozpoznawanych przez gramatyki kontekstowe i często zdarza się, że łatwiej jest oprzeć dowody na gramatyce monotonicznej. W związku z tym dość powszechne jest używanie słowa „kontekstowego” tak, jakby oznaczało to „monotoniczny”.