Ist C ++ kontextfrei oder kontextsensitiv?

Ich höre oft Behauptungen, dass C ++ eine kontextsensitive Sprache ist. Nehmen Sie das folgende Beispiel:

a b(c);

Ist dies eine Variablendefinition oder eine Funktionsdeklaration? Das hängt von der Bedeutung des Symbols ab c. Wenn ces sich um eine Variable handelt , wird a b(c);eine Variable mit dem Namen btype definiert a. Es wird direkt mit initialisiert c. Wenn ces sich jedoch um einen Typ handelt , a b(c);wird eine Funktion mit dem Namen deklariert, die a bannimmt cund a zurückgibt a.

Wenn Sie die Definition kontextfreier Sprachen nachschlagen, erfahren Sie im Grunde, dass alle Grammatikregeln linke Seiten haben müssen, die aus genau einem nicht-terminalen Symbol bestehen. Kontextsensitive Grammatiken hingegen erlauben beliebige Zeichenfolgen von terminalen und nicht terminalen Symbolen auf der linken Seite.

Beim Durchsuchen von Anhang A von "The C ++ Programming Language" konnte ich keine einzige Grammatikregel finden, die auf der linken Seite etwas anderes als ein einziges nicht-terminales Symbol enthielt. Das würde bedeuten, dass C ++ kontextfrei ist. (Natürlich ist jede kontextfreie Sprache auch in dem Sinne kontextsensitiv, dass die kontextfreien Sprachen eine Teilmenge der kontextsensitiven Sprachen bilden, aber das ist nicht der Punkt.)

Ist C ++ also kontextfrei oder kontextsensitiv?

Unten ist meine (aktuelle) Lieblingsdemonstration, warum das Parsen von C ++ (wahrscheinlich) Turing-vollständig ist , da es ein Programm zeigt, das genau dann syntaktisch korrekt ist, wenn eine bestimmte Ganzzahl eine Primzahl ist.

Ich behaupte also, dass C ++ weder kontextfrei noch kontextsensitiv ist .

Wenn Sie beliebige Symbolsequenzen auf beiden Seiten einer Produktion zulassen, erstellen Sie eine Typ-0-Grammatik ("uneingeschränkt") in der Chomsky-Hierarchie , die leistungsfähiger ist als eine kontextsensitive Grammatik. Uneingeschränkte Grammatiken sind Turing-vollständig. Eine kontextsensitive Grammatik (Typ 1) erlaubt mehrere Kontextsymbole auf der linken Seite einer Produktion, aber der gleiche Kontext muss auf der rechten Seite der Produktion erscheinen (daher der Name "kontextsensitiv"). [1] Kontextsensitive Grammatiken entsprechen linear begrenzten Turing-Maschinen .

In dem Beispielprogramm könnte die Hauptberechnung von einer linear begrenzten Turing-Maschine durchgeführt werden, so dass die Turing-Äquivalenz nicht ganz bewiesen wird, aber der wichtige Teil ist, dass der Parser die Berechnung durchführen muss, um eine syntaktische Analyse durchzuführen. Es könnte jede Berechnung gewesen sein, die als Vorlageninstanziierung ausgedrückt werden kann, und es gibt allen Grund zu der Annahme, dass die C ++ - Vorlageninstanziierung vollständig ist. Siehe zum Beispiel Todd L. Veldhuizens Artikel von 2003 .

Unabhängig davon kann C ++ von einem Computer analysiert werden, sodass es sicherlich von einer Turing-Maschine analysiert werden kann. Folglich könnte eine uneingeschränkte Grammatik dies erkennen. Das Schreiben einer solchen Grammatik wäre tatsächlich unpraktisch, weshalb der Standard dies nicht versucht. (Siehe unten.)

Das Problem mit der "Mehrdeutigkeit" bestimmter Ausdrücke ist meist ein roter Hering. Ambiguität ist zunächst ein Merkmal einer bestimmten Grammatik, keine Sprache. Selbst wenn nachgewiesen werden kann, dass eine Sprache keine eindeutigen Grammatiken aufweist, ist sie kontextfrei, wenn sie von einer kontextfreien Grammatik erkannt werden kann. Wenn es von einer kontextfreien Grammatik nicht erkannt werden kann, aber von einer kontextsensitiven Grammatik erkannt werden kann, ist es ebenfalls kontextsensitiv. Mehrdeutigkeit ist nicht relevant.

In jedem Fall sind auto b = foo<IsPrime<234799>>::typen<1>();die Ausdrücke jedoch , wie in Zeile 21 (dh ) im folgenden Programm, überhaupt nicht mehrdeutig. Sie werden je nach Kontext einfach unterschiedlich analysiert. Im einfachsten Ausdruck des Problems hängt die syntaktische Kategorie bestimmter Bezeichner davon ab, wie sie deklariert wurden (z. B. Typen und Funktionen). Dies bedeutet, dass die formale Sprache die Tatsache erkennen müsste, dass zwei Zeichenfolgen beliebiger Länge enthalten sind Das gleiche Programm ist identisch (Deklaration und Verwendung). Dies kann durch die "Kopier" -Grammatik modelliert werden, bei der es sich um die Grammatik handelt, die zwei aufeinanderfolgende exakte Kopien desselben Wortes erkennt. Mit dem Pump-Lemma ist es leicht zu beweisendass diese Sprache nicht kontextfrei ist. Eine kontextsensitive Grammatik für diese Sprache ist möglich, und eine Grammatik vom Typ 0 ist in der Antwort auf diese Frage enthalten: /math/163830/context-sensitive-grammar-for-the- Kopiersprache .

Wenn man versuchen würde, eine kontextsensitive (oder uneingeschränkte) Grammatik zu schreiben, um C ++ zu analysieren, würde dies möglicherweise das Universum mit Skizzen füllen. Das Schreiben einer Turing-Maschine zum Parsen von C ++ wäre ein ebenso unmögliches Unterfangen. Selbst das Schreiben eines C ++ - Programms ist schwierig, und meines Wissens hat sich keines als richtig erwiesen. Aus diesem Grund versucht der Standard nicht, eine vollständige formale Grammatik bereitzustellen, und beschließt, einige der Parsing-Regeln in technischem Englisch zu schreiben.

Was im C ++ - Standard wie eine formale Grammatik aussieht, ist nicht die vollständige formale Definition der Syntax der C ++ - Sprache. Es ist nicht einmal die vollständige formale Definition der Sprache nach der Vorverarbeitung, die möglicherweise einfacher zu formalisieren ist. (Dies wäre jedoch nicht die Sprache: Die im Standard definierte C ++ - Sprache enthält den Präprozessor, und die Funktionsweise des Präprozessors wird algorithmisch beschrieben, da es in jedem grammatikalischen Formalismus äußerst schwierig wäre, sie zu beschreiben. Sie befindet sich in diesem Abschnitt des Standards, in dem die lexikalische Zerlegung beschrieben wird, einschließlich der Regeln, in denen sie mehrmals angewendet werden muss.)

Die verschiedenen Grammatiken (zwei überlappende Grammatiken für die lexikalische Analyse, eine vor der Vorverarbeitung und die andere, falls erforderlich, danach sowie die "syntaktische" Grammatik) sind in Anhang A mit diesem wichtigen Hinweis (Hervorhebung hinzugefügt) zusammengefasst:

Diese Zusammenfassung der C ++ - Syntax soll das Verständnis erleichtern. Es ist keine genaue Aussage der Sprache . Insbesondere akzeptiert die hier beschriebene Grammatik eine Obermenge gültiger C ++ - Konstrukte . Disambiguierungsregeln (6.8, 7.1, 10.2) müssen angewendet werden, um Ausdrücke von Deklarationen zu unterscheiden. Darüber hinaus müssen Zugriffssteuerungs-, Mehrdeutigkeits- und Typregeln verwendet werden, um syntaktisch gültige, aber bedeutungslose Konstrukte auszusondern.

Zum Schluss hier das versprochene Programm. Zeile 21 ist genau dann syntaktisch korrekt, wenn das N in IsPrime<N>eine Primzahl ist. Andernfalls typenhandelt es sich um eine Ganzzahl und nicht um eine Vorlage. typen<1>()Daher wird sie als (typen<1)>()syntaktisch falsch analysiert, da ()es sich nicht um einen syntaktisch gültigen Ausdruck handelt.

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] Technisch gesehen muss jede Produktion in einer kontextsensitiven Grammatik die folgende Form haben:

αAβ → αγβ

wobei Aein Nicht-Terminal und α, βsind möglicherweise leere Sequenzen von Symbolen der Grammatik, und γist eine nicht-leere Sequenz. (Grammatiksymbole können entweder Terminals oder Nicht-Terminals sein).

Dies kann A → γnur im Kontext gelesen werden [α, β]. In einer kontextfreien (Typ 2) Grammatik αund βmuss leer sein.

Es stellt sich heraus, dass Sie Grammatiken auch mit der "monotonen" Einschränkung einschränken können, wobei jede Produktion die Form haben muss:

α → βwo |α| ≥ |β| > 0  ( |α|bedeutet "die Länge von α")

Es ist möglich zu beweisen, dass der Satz von Sprachen, die von monotonen Grammatiken erkannt werden, genau der gleiche ist wie der Satz von Sprachen, die von kontextsensitiven Grammatiken erkannt werden, und es ist häufig einfacher, Beweise auf monotonen Grammatiken zu basieren. Folglich ist es ziemlich üblich, dass "kontextsensitiv" verwendet wird, als ob es "monoton" bedeutet.

Zuerst beobachtete man mit Recht gibt es keine kontextsensitiven Regeln in der Grammatik am Ende des C ++ Standard, so dass Grammatik ist kontextfrei.

Diese Grammatik beschreibt die C ++ - Sprache jedoch nicht genau, da sie Nicht-C ++ - Programme wie z

int m() { m++; }

oder

typedef static int int;

Die C ++ - Sprache, die als "die Menge wohlgeformter C ++ - Programme" definiert ist, ist nicht kontextfrei (es ist möglich zu zeigen, dass nur anspruchsvolle zu deklarierende Variablen dies ermöglichen). Da Sie theoretisch Turing-vollständige Programme in Vorlagen schreiben und ein Programm aufgrund seines Ergebnisses schlecht gestalten können, ist es nicht einmal kontextsensitiv.

Nun verwenden (unwissende) Personen (normalerweise keine Sprachtheoretiker, sondern Parser-Designer) in einigen der folgenden Bedeutungen normalerweise "nicht kontextfrei"

• mehrdeutig
• kann nicht mit Bison analysiert werden
• nicht LL (k), LR (k), LALR (k) oder eine von ihnen gewählte parserdefinierte Sprachklasse

Die Grammatik am Ende des Standards erfüllt diese Kategorien nicht (dh sie ist mehrdeutig, nicht LL (k) ...), daher ist die C ++ - Grammatik für sie "nicht kontextfrei". Und in gewissem Sinne haben sie Recht, es ist verdammt schwer, einen funktionierenden C ++ - Parser zu erstellen.

Beachten Sie, dass die hier verwendeten Eigenschaften nur schwach mit kontextfreien Sprachen verbunden sind - Mehrdeutigkeit hat nichts mit Kontextsensitivität zu tun (tatsächlich helfen kontextsensitive Regeln normalerweise bei der Disambiguierung von Produktionen), die anderen beiden sind lediglich Teilmengen des Kontexts -freie Sprachen. Und das Parsen kontextfreier Sprachen ist kein linearer Prozess (obwohl das Parsen deterministischer Sprachen ist).

Ja. Der folgende Ausdruck hat je nach typaufgelöstem Kontext eine unterschiedliche Reihenfolge der Operationen :

Bearbeiten: Wenn die tatsächliche Reihenfolge der Operationen variiert, ist es unglaublich schwierig, einen "normalen" Compiler zu verwenden, der vor dem Dekorieren einen nicht dekorierten AST analysiert (Weitergabe von Typinformationen). Andere kontextsensitive Dinge, die erwähnt werden, sind im Vergleich dazu "ziemlich einfach" (nicht, dass die Vorlagenbewertung überhaupt einfach ist).

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

Gefolgt von:

static int foobar( foo < 2 ? 1 < 1 : 0 > & bar );

Um Ihre Frage zu beantworten, müssen Sie zwei verschiedene Fragen unterscheiden.

1. Die bloße Syntax fast jeder Programmiersprache ist kontextfrei. Typischerweise wird es als erweiterte Backus-Naur-Form oder kontextfreie Grammatik angegeben.

2. Selbst wenn ein Programm dem durch die Programmiersprache definierten kontextfreien Grammatik entspricht, ist es nicht unbedingt ein gültiges Programm. Es gibt viele nicht kontextfreie Poperties, die ein Programm erfüllen muss, um ein gültiges Programm zu sein. Die einfachste solche Eigenschaft ist beispielsweise der Umfang der Variablen.

Ob C ++ kontextfrei ist oder nicht, hängt von der Frage ab, die Sie stellen.

Vielleicht möchten Sie einen Blick auf The Design & Evolution of C ++ von Bjarne Stroustrup werfen . Darin beschreibt er seine Probleme beim Versuch, eine frühe Version von C ++ mit yacc (oder ähnlichem) zu analysieren, und wünschte, er hätte stattdessen rekursiven Abstieg verwendet.

Ja, C ++ ist kontextsensitiv, sehr kontextsensitiv. Sie können den Syntaxbaum nicht erstellen, indem Sie die Datei einfach mit einem kontextfreien Parser analysieren, da Sie in einigen Fällen das Symbol aus dem Vorwissen kennen müssen, um entscheiden zu können (dh beim Parsen eine Symboltabelle erstellen).

Erstes Beispiel:

A*B;

Ist das ein Multiplikationsausdruck?

ODER

Ist dies eine Deklaration der BVariablen als Zeiger vom Typ A?

Wenn A eine Variable ist, ist es ein Ausdruck, wenn A ein Typ ist, ist es eine Zeigerdeklaration.

Zweites Beispiel:

A B(bar);

Ist dies ein Funktionsprototyp, der ein Argument vom barTyp annimmt?

ODER

Ist diese Deklarationsvariable Bvom Typ Aund ruft den Konstruktor von A mit barKonstante als Initialisierer auf?

Sie müssen erneut wissen, ob bares sich um eine Variable oder einen Typ aus der Symboltabelle handelt.

Drittes Beispiel:

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

Dies ist der Fall, wenn das Erstellen einer Symboltabelle während des Parsens nicht hilft, da die Deklaration von x und y nach der Funktionsdefinition erfolgt. Sie müssen also zuerst die Klassendefinition durchsuchen und die Methodendefinitionen in einem zweiten Durchgang betrachten, um festzustellen, dass x * y ein Ausdruck und keine Zeigerdeklaration oder was auch immer ist.

C ++ wird mit dem GLR-Parser analysiert. Das bedeutet, dass der Parser beim Parsen des Quellcodes möglicherweise auf Mehrdeutigkeiten stößt, jedoch fortfahren und entscheiden sollte, welche Grammatikregel später verwendet werden soll .

schau auch,

Warum kann C ++ nicht mit einem LR (1) -Parser analysiert werden?

Denken Sie daran , dass kontextfreie Grammatik nicht kann beschreiben ALLE die Regeln einer Programmiersprache Syntax. Beispielsweise wird die Attributgrammatik verwendet, um die Gültigkeit eines Ausdruckstyps zu überprüfen.

int x;
x = 9 + 1.0;

Sie können die folgende Regel mit kontextfreier Grammatik nicht beschreiben: Die rechte Seite der Zuweisung sollte vom gleichen Typ sein wie die linke Seite.

Ich habe das Gefühl, dass es eine gewisse Verwirrung zwischen der formalen Definition von "kontextsensitiv" und der informellen Verwendung von "kontextsensitiv" gibt. Ersteres hat eine klar definierte Bedeutung. Letzteres wird verwendet, um zu sagen "Sie benötigen Kontext, um die Eingabe zu analysieren".

Dies wird auch hier gefragt: Kontextsensitivität vs. Mehrdeutigkeit .

Hier ist eine kontextfreie Grammatik:

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

Es ist mehrdeutig. Um die Eingabe "x" zu analysieren, benötigen Sie einen Kontext (oder leben mit der Mehrdeutigkeit oder geben "Warnung: E8271 - Eingabe ist in Zeile 115 mehrdeutig" aus). Aber es ist sicherlich keine kontextsensitive Grammatik.

Keine Algol-ähnliche Sprache ist kontextfrei, da sie Regeln enthält, die Ausdrücke und Anweisungen einschränken, in denen Bezeichner je nach Typ angezeigt werden können, und weil die Anzahl der Anweisungen zwischen Deklaration und Verwendung unbegrenzt ist.

Die übliche Lösung besteht darin, einen kontextfreien Parser zu schreiben, der tatsächlich eine Obermenge gültiger Programme akzeptiert, und die kontextsensitiven Teile in Ad-hoc- "semantischen" Code einzufügen, der an Regeln angehängt ist.

C ++ geht dank seines Turing-vollständigen Vorlagensystems weit darüber hinaus. Siehe Stapelüberlauffrage 794015 .

Wahr :)

J. Stanley Warford. Computersysteme . Seiten 341-346.

Manchmal ist es schlimmer: Was meinen die Leute, wenn sie sagen, C ++ habe "unentscheidbare Grammatik"?

Es ist kontextsensitiv, ebenso a b(c);wie zwei gültige Analyseerklärungen und Variablen. Wenn Sie "If cis a type" sagen , ist dies genau dort der Kontext, und Sie haben genau beschrieben, wie empfindlich C ++ darauf reagiert. Wenn Sie nicht den Kontext von "Was istc ?" Sie konnten dies nicht eindeutig analysieren.

Hier wird der Kontext in der Auswahl der Token ausgedrückt. Der Parser liest einen Bezeichner als Typennamen-Token, wenn er einen Typ benennt. Dies ist die einfachste Lösung und vermeidet einen Großteil der Komplexität der Kontextsensitivität (in diesem Fall).

Bearbeiten: Es gibt natürlich mehr Probleme mit der Kontextsensitivität. Ich habe mich lediglich auf das konzentriert, das Sie gezeigt haben. Vorlagen sind dafür besonders unangenehm.

Die Produktionen im C ++ - Standard sind kontextfrei geschrieben, aber wie wir alle wissen, definieren wir die Sprache nicht wirklich genau. Einige der Probleme, die die meisten Menschen in der aktuellen Sprache als Mehrdeutigkeit ansehen, könnten (glaube ich) mit einer kontextsensitiven Grammatik eindeutig gelöst werden.

Betrachten wir für das offensichtlichste Beispiel die ärgerlichste Analyse : int f(X);. Wenn Xes sich um einen Wert handelt, wird dies fals Variable definiert , mit der initialisiert wird X. Wenn Xes sich um einen Typ handelt, wird er fals Funktion definiert, die einen einzelnen Parameter vom Typ verwendet X.

Wenn wir das aus grammatikalischer Sicht betrachten, könnten wir es so sehen:

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]

Um ganz richtig zu sein, müssten wir natürlich einige zusätzliche "Dinge" hinzufügen, um die Möglichkeit intervenierender Deklarationen anderer Typen zu berücksichtigen (dh A und B sollten beide wirklich "Deklarationen einschließlich der Deklaration von X als ..." sein. oder etwas in dieser Reihenfolge).

Dies unterscheidet sich jedoch immer noch von einem typischen CSG (oder zumindest, woran ich mich erinnere). Dies hängt davon ab, dass eine Symboltabelle erstellt wird - der Teil, der speziell erkannt wirdX als Typ oder Wert , nicht nur eine Art von Anweisung, die davor steht, sondern die richtige Art von Anweisung für das richtige Symbol / die richtige Kennung.

Als solches müsste ich etwas tun, um sicherzugehen, aber meine unmittelbare Vermutung ist, dass dies nicht wirklich als CSG qualifiziert ist, zumindest da der Begriff normalerweise verwendet wird.

Der einfachste Fall einer nicht kontextfreien Grammatik besteht darin, Ausdrücke mit Vorlagen zu analysieren.

a<b<c>()

Dies kann als beides analysiert werden

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

Oder

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

Die beiden ASTs können nur durch Prüfung der Deklaration von 'a' eindeutig gemacht werden - der erstere AST, wenn 'a' eine Vorlage ist, oder der letztere, wenn nicht.

Es hat sich gezeigt, dass C ++ - Vorlagen Turing Powerful sind. Obwohl dies keine formale Referenz ist, sollten Sie diesbezüglich einen Blick darauf werfen:

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

Ich werde eine Vermutung wagen (so alt wie ein folkorischer und prägnanter CACM-Beweis, der zeigt, dass ALGOL in den 60er Jahren nicht durch eine CFG dargestellt werden konnte) und sagen, dass C ++ daher nur von einer CFG nicht korrekt analysiert werden kann. CFGs in Verbindung mit verschiedenen TP-Mechanismen in einem Baumpass oder bei Reduktionsereignissen - das ist eine andere Geschichte. Im Allgemeinen gibt es aufgrund des Halteproblems ein C ++ - Programm, das nicht als richtig / falsch angezeigt werden kann, aber dennoch richtig / falsch ist.

{PS- Als Autor von Meta-S (von mehreren Personen oben erwähnt) kann ich mit Sicherheit sagen, dass Thothic weder verstorben ist noch die Software kostenlos verfügbar ist. Vielleicht habe ich diese Version meiner Antwort so formuliert, dass ich nicht gelöscht oder auf -3 herabgestimmt werde.}

C ++ ist nicht kontextfrei. Ich habe es vor einiger Zeit in einem Compiler-Vortrag gelernt. Eine schnelle Suche ergab diesen Link, in dem im Abschnitt "Syntax oder Semantik" erklärt wird, warum C und C ++ nicht kontextfrei sind:

Wikipedia Talk: Kontextfreie Grammatik

Grüße,
Ovanes

Wenn Sie die Frage wörtlich stellen, sind natürlich fast alle Sprachen mit Bezeichnern kontextsensitiv.

Man muss wissen, ob ein Bezeichner ein Typname (ein Klassenname, ein durch typedef eingeführter Name, ein Typennamen-Vorlagenparameter), ein Vorlagenname oder ein anderer Name ist, um einen Teil der Verwendung des Bezeichners korrekt ausführen zu können. Zum Beispiel:

x = (name)(expression);

ist eine Umwandlung, wenn namees sich um einen Typnamen handelt, und ein Funktionsaufruf, wenn namees sich um einen Funktionsnamen handelt. Ein anderer Fall ist die sogenannte "ärgerlichste Analyse", bei der es nicht möglich ist, Variablendefinition und Funktionsdeklaration zu unterscheiden (es gibt eine Regel, die besagt, dass es sich um eine Funktionsdeklaration handelt).

Diese Schwierigkeit hat die Notwendigkeit von typenameund templatemit abhängigen Namen eingeführt. Der Rest von C ++ ist meines Wissens nicht kontextsensitiv (dh es ist möglich, eine kontextfreie Grammatik dafür zu schreiben).

Meta-S "ist eine kontextsensitive Parsing-Engine von Quinn Tyler Jackson. Ich habe sie nicht verwendet, aber er erzählt eine beeindruckende Geschichte. Lesen Sie seine Kommentare in comp.compilers und sehen Sie sich rnaparse.com/MetaS%20defined.htm an - Ira Baxter 25. Juli um 10:42 Uhr

Der richtige Link ist das Parsen von Ringen

Meta-S war Eigentum einer nicht mehr existierenden Firma namens Thothic. Ich kann jedem Interessierten eine kostenlose Kopie des Meta-S senden und habe sie in der Rna-Parsing-Forschung verwendet. Bitte beachten Sie, dass die in den Beispielordnern enthaltene "Pseudoknoten-Grammatik" von einem nicht-bioinformatischen, ausgereiften Programmierer geschrieben wurde und im Grunde nicht funktioniert. Meine Grammatiken verfolgen einen anderen Ansatz und funktionieren recht gut.

Ein großes Problem dabei ist, dass die Begriffe "kontextfrei" und "kontextsensitiv" in der Informatik etwas unintuitiv sind. Für C ++ ähnelt die Kontextsensitivität stark der Mehrdeutigkeit, dies ist jedoch im allgemeinen Fall nicht unbedingt der Fall.

In C / ++ ist eine if-Anweisung nur innerhalb eines Funktionskörpers zulässig. Das scheint es kontextsensitiv zu machen, oder? Nun, nein. Kontextfreie Grammatiken benötigen nicht die Eigenschaft, mit der Sie eine Codezeile herausreißen und feststellen können, ob sie gültig ist. Das ist eigentlich nicht kontextfrei. Es ist wirklich nur ein Label, das vage etwas impliziert, das damit zusammenhängt, wie es sich anhört.

Wenn nun eine Anweisung innerhalb eines Funktionskörpers unterschiedlich analysiert wird, abhängig von etwas, das außerhalb der unmittelbaren grammatikalischen Vorfahren definiert ist (z. B. ob ein Bezeichner einen Typ oder eine Variable beschreibt), wie im a * b;Fall, dann ist sie tatsächlich kontextsensitiv. Hier gibt es keine tatsächliche Mehrdeutigkeit; Es wird als Deklaration eines Zeigers analysiert, wenn aes sich um einen Typ handelt, andernfalls um eine Multiplikation.

Kontextsensitiv zu sein bedeutet nicht unbedingt "schwer zu analysieren". C ist eigentlich nicht so schwer, weil die berüchtigte a * b;"Mehrdeutigkeit" mit einer Symboltabelle gelöst werden kann, die typedefs enthält, die zuvor angetroffen wurden. Es sind keine willkürlichen Vorlageninstanziierungen erforderlich (die sich als Turing Complete erwiesen haben), um diesen Fall zu lösen, wie dies C ++ gelegentlich tut. Es ist tatsächlich nicht möglich, ein C-Programm zu schreiben, das nicht in endlicher Zeit kompiliert werden kann, obwohl es dieselbe Kontextsensitivität wie C ++ aufweist.

Python (und andere Whitespace-sensitive Sprachen) ist ebenfalls kontextabhängig, da der Status im Lexer erforderlich ist, um Einrückungs- und Dedent-Token zu generieren. Dies macht das Parsen jedoch nicht schwieriger als eine typische LL-1-Grammatik. Es wird tatsächlich ein Parser-Generator verwendet, was ein Teil dessen ist, warum Python solche nicht informativen Syntaxfehlermeldungen hat. Es ist auch wichtig anzumerken, dass es keine "Mehrdeutigkeit" wie das a * b;Problem in Python gibt, was ein gutes konkretes Beispiel für eine kontextsensitive Sprache ohne "mehrdeutige" Grammatik darstellt (wie im ersten Absatz erwähnt).

Diese Antwort besagt, dass C ++ nicht kontextfrei ist. Es gibt eine Implikation (nicht vom Antwortenden), dass es nicht analysiert werden kann, und die Antwort bietet ein schwieriges Codebeispiel, das ein ungültiges C ++ - Programm erzeugt, wenn eine bestimmte Konstante keine ist Primzahl.

Wie andere beobachtet haben, unterscheidet sich die Frage, ob die Sprache kontextsensitiv / frei ist, von derselben Frage zu einer bestimmten Grammatik.

Um die Frage nach der Parsierbarkeit zum Stillstand zu bringen, biete ich empirische Beweise dafür, dass es kontextfreie Grammatiken für C ++ gibt, mit denen ein AST für eine kontextfreie Analyse des Quelltextes erstellt werden kann, indem er tatsächlich mit einer vorhandenen GLR analysiert wird -parser-basiertes Tool, das von einer expliziten Grammatik gesteuert wird.

Ja, es gelingt, "zu viel zu akzeptieren"; Nicht alles, was es akzeptiert, ist ein gültiges C ++ - Programm, weshalb zusätzliche Prüfungen (Typprüfungen) durchgeführt werden. Und ja, die Typprüfung kann auf Berechenbarkeitsprobleme stoßen. In der Praxis haben Tools dieses Problem nicht. Wenn Leute solche Programme schreiben würden, würde keiner von ihnen kompilieren. (Ich denke, der Standard begrenzt tatsächlich den Rechenaufwand, den Sie für das Entfalten einer Vorlage ausführen können. Die Berechnung ist also tatsächlich endlich, aber wahrscheinlich ziemlich umfangreich.)

Wenn Sie damit meinen, festzustellen, ob das Quellprogramm Mitglied der Gruppe der gültigen C ++ - Quellprogramme ist , stimme ich zu, dass das Problem viel schwieriger ist. Aber es ist nicht das Parsen , das das Problem ist.

Das Tool behebt dieses Problem, indem es die Analyse von der Typprüfung des analysierten Programms isoliert. (Wenn in Abwesenheit von Kontext mehrere Interpretationen vorhanden sind, wird ein Mehrdeutigkeitsknoten im Analysebaum mit mehreren möglichen Analysen aufgezeichnet. Die Typprüfung entscheidet, welche korrekt ist, und beseitigt die ungültigen Teilbäume.) Im folgenden Beispiel sehen Sie einen (teilweisen) Analysebaum. Der gesamte Baum ist zu groß, um in eine SO-Antwort zu passen. Beachten Sie, dass Sie einen Analysebaum erhalten, unabhängig davon, ob der Wert 234797 oder 234799 verwendet wird.

Das Ausführen des Namens- / Typ-Resolvers des Tools über den AST mit dem ursprünglichen Wert 234799 ist erfolgreich. Mit dem Wert 234797 schlägt der Namensauflöser (wie erwartet) mit der Fehlermeldung "typen is not type" fehl. und daher ist diese Version kein gültiges C ++ - Programm.

967 tree nodes in tree.
15 ambiguity nodes in tree.
(translation_unit@Cpp~GCC5=2#6b11a20^0 Line 1 Column 1 File C:/temp/prime_with_templates.cpp
 (declaration_seq@Cpp~GCC5=1021#6b06640^1#6b11a20:1 {10} Line 1 Column 1 File C:/temp/prime_with_templates.cpp
  (pp_declaration_seq@Cpp~GCC5=1022#6b049a0^1#6b06640:1 Line 1 Column 1 File C:/temp/prime_with_templates.cpp
   (declaration@Cpp~GCC5=1036#6b04980^1#6b049a0:1 Line 1 Column 1 File C:/temp/prime_with_templates.cpp
   |(template_declaration@Cpp~GCC5=2079#6b04960^1#6b04980:1 Line 1 Column 1 File C:/temp/prime_with_templates.cpp
   | (template_parameter_list@Cpp~GCC5=2082#6afbde0^1#6b04960:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp
   |  (template_parameter@Cpp~GCC5=2085#6afbd80^1#6afbde0:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp
   |   (parameter_declaration@Cpp~GCC5=1611#6afbd40^1#6afbd80:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp
   |   |(basic_decl_specifier_seq@Cpp~GCC5=1070#6afb880^1#6afbd40:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp
   |   | (decl_specifier@Cpp~GCC5=1073#6afb840^1#6afb880:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp
   |   |  (trailing_type_specifier@Cpp~GCC5=1118#6afb7e0^1#6afb840:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp
   |   |   (simple_type_specifier@Cpp~GCC5=1138#6afb7a0^1#6afb7e0:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp)simple_type_specifier
   |   |  )trailing_type_specifier#6afb7e0
   |   | )decl_specifier#6afb840
   |   |)basic_decl_specifier_seq#6afb880
   |   |(ptr_declarator@Cpp~GCC5=1417#6afbc40^1#6afbd40:2 Line 1 Column 15 File C:/temp/prime_with_templates.cpp
   |   | (noptr_declarator@Cpp~GCC5=1421#6afbba0^1#6afbc40:1 Line 1 Column 15 File C:/temp/prime_with_templates.cpp
   |   |  (declarator_id@Cpp~GCC5=1487#6afbb80^1#6afbba0:1 Line 1 Column 15 File C:/temp/prime_with_templates.cpp
   |   |   (id_expression@Cpp~GCC5=317#6afbaa0^1#6afbb80:1 Line 1 Column 15 File C:/temp/prime_with_templates.cpp
   |   |   |(unqualified_id@Cpp~GCC5=319#6afb9c0^1#6afbaa0:1 Line 1 Column 15 File C:/temp/prime_with_templates.cpp
   |   |   | (IDENTIFIER@Cpp~GCC5=3368#6afb780^1#6afb9c0:1[`V'] Line 1 Column 15 File C:/temp/prime_with_templates.cpp)IDENTIFIER
   |   |   |)unqualified_id#6afb9c0
   |   |   )id_expression#6afbaa0
   |   |  )declarator_id#6afbb80
   |   | )noptr_declarator#6afbba0
   |   |)ptr_declarator#6afbc40
   |   )parameter_declaration#6afbd40
   |  )template_parameter#6afbd80
   | )template_parameter_list#6afbde0
   | (declaration@Cpp~GCC5=1033#6b04940^1#6b04960:2 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
   |  (block_declaration@Cpp~GCC5=1050#6b04920^1#6b04940:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
   |   (simple_declaration@Cpp~GCC5=1060#6b04900^1#6b04920:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
   |   |(basic_decl_specifier_seq@Cpp~GCC5=1070#6b048e0^1#6b04900:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
   |   | (decl_specifier@Cpp~GCC5=1073#6b048c0^1#6b048e0:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
   |   |  (type_specifier@Cpp~GCC5=1110#6b048a0^1#6b048c0:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
   |   |   (class_specifier@Cpp~GCC5=1761#6b04880^1#6b048a0:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
   |   |   |(class_head@Cpp~GCC5=1763#6afb980^1#6b04880:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
   |   |   | (class_key@Cpp~GCC5=1791#6afbca0^1#6afb980:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp)class_key
   |   |   | (IDENTIFIER@Cpp~GCC5=3368#6afbcc0^1#6afb980:2[`answer'] Line 1 Column 25 File C:/temp/prime_with_templates.cpp)IDENTIFIER
   |   |   | (optional_base_clause@Cpp~GCC5=1872#6afba60^1#6afb980:3 Line 1 Column 32 File C:/temp/prime_with_templates.cpp)optional_base_clause
   |   |   |)class_head#6afb980
   |   |   |(member_specification@Cpp~GCC5=1794#6b042e0^1#6b04880:2 {2} Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   | (member_declaration_or_access_specifier@Cpp~GCC5=1806#6b04060^1#6b042e0:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |  (member_declaration@Cpp~GCC5=1822#6b04040^1#6b04060:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |   (function_definition@Cpp~GCC5=1632#6b04020^1#6b04040:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |   |(function_head@Cpp~GCC5=1673#6afbec0^1#6b04020:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |   | (ptr_declarator@Cpp~GCC5=1417#6afbfe0^1#6afbec0:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |   |  (noptr_declarator@Cpp~GCC5=1422#6afbf80^1#6afbfe0:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |   |   (noptr_declarator@Cpp~GCC5=1421#6afbf60^1#6afbf80:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |(declarator_id@Cpp~GCC5=1487#6afbea0^1#6afbf60:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |   |   | (id_expression@Cpp~GCC5=317#6afbb40^1#6afbea0:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |  (unqualified_id@Cpp~GCC5=319#6afbc80^1#6afbb40:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   (IDENTIFIER@Cpp~GCC5=3368#6afbc20^1#6afbc80:1[`answer'] Line 1 Column 34 File C:/temp/prime_with_templates.cpp)IDENTIFIER
   |   |   |   |   |  )unqualified_id#6afbc80
   |   |   |   |   | )id_expression#6afbb40
   |   |   |   |   |)declarator_id#6afbea0
   |   |   |   |   )noptr_declarator#6afbf60
   |   |   |   |   (parameter_declaration_clause@Cpp~GCC5=1559#6afbd00^1#6afbf80:2 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |(pp_parameter_declaration_list@Cpp~GCC5=1570#6afb940^1#6afbd00:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
   |   |   |   |   | (pp_parameter_declaration_seq@Cpp~GCC5=1574#6afb800^1#6afb940:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |  (parameter_declaration@Cpp~GCC5=1610#6afb9a0^1#6afb800:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   (basic_decl_specifier_seq@Cpp~GCC5=1070#6afbf40^1#6afb9a0:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   |(decl_specifier@Cpp~GCC5=1073#6afbfa0^1#6afbf40:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   | (trailing_type_specifier@Cpp~GCC5=1118#6afbfc0^1#6afbfa0:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   |  (simple_type_specifier@Cpp~GCC5=1140#6afb860^1#6afbfc0:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp)simple_type_specifier
   |   |   |   |   |   | )trailing_type_specifier#6afbfc0
   |   |   |   |   |   |)decl_specifier#6afbfa0
   |   |   |   |   |   )basic_decl_specifier_seq#6afbf40
   |   |   |   |   |  )parameter_declaration#6afb9a0
   |   |   |   |   | )pp_parameter_declaration_seq#6afb800
   |   |   |   |   |)pp_parameter_declaration_list#6afb940
   |   |   |   |   )parameter_declaration_clause#6afbd00
   |   |   |   |   (function_qualifiers@Cpp~GCC5=1438#6afbce0^1#6afbf80:3 Line 1 Column 46 File C:/temp/prime_with_templates.cpp)function_qualifiers
   |   |   |   |  )noptr_declarator#6afbf80
   |   |   |   | )ptr_declarator#6afbfe0
   |   |   |   |)function_head#6afbec0
   |   |   |   |(function_body@Cpp~GCC5=1680#6b04000^1#6b04020:2 Line 1 Column 46 File C:/temp/prime_with_templates.cpp
   |   |   |   | (compound_statement@Cpp~GCC5=888#6afbee0^1#6b04000:1 Line 1 Column 46 File C:/temp/prime_with_templates.cpp)compound_statement
   |   |   |   |)function_body#6b04000
   |   |   |   )function_definition#6b04020
   |   |   |  )member_declaration#6b04040
   |   |   | )member_declaration_or_access_specifier#6b04060
   |   |   | (member_declaration_or_access_specifier@Cpp~GCC5=1806#6b042c0^1#6b042e0:2 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
   |   |   |  (member_declaration@Cpp~GCC5=1822#6b04820^1#6b042c0:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
   |   |   |   (function_definition@Cpp~GCC5=1632#6b04280^1#6b04820:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
   |   |   |   |(function_head@Cpp~GCC5=1674#6b04220^1#6b04280:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
   |   |   |   | (basic_decl_specifier_seq@Cpp~GCC5=1070#6b040e0^1#6b04220:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
   |   |   |   |  (decl_specifier@Cpp~GCC5=1073#6b040c0^1#6b040e0:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
   |   |   |   |   (trailing_type_specifier@Cpp~GCC5=1118#6b040a0^1#6b040c0:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |(simple_type_specifier@Cpp~GCC5=1138#6b04080^1#6b040a0:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp)simple_type_specifier
   |   |   |   |   )trailing_type_specifier#6b040a0
   |   |   |   |  )decl_specifier#6b040c0
   |   |   |   | )basic_decl_specifier_seq#6b040e0
   |   |   |   | (ptr_declarator@Cpp~GCC5=1417#6b04200^1#6b04220:2 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
   |   |   |   |  (noptr_declarator@Cpp~GCC5=1422#6b041e0^1#6b04200:1 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
   |   |   |   |   (noptr_declarator@Cpp~GCC5=1421#6b041a0^1#6b041e0:1 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |(declarator_id@Cpp~GCC5=1487#6b04180^1#6b041a0:1 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
   |   |   |   |   | (id_expression@Cpp~GCC5=317#6b04160^1#6b04180:1 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |  (unqualified_id@Cpp~GCC5=320#6b04140^1#6b04160:1 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   (operator_function_id@Cpp~GCC5=2027#6b04120^1#6b04140:1 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   |(operator@Cpp~GCC5=2070#6b04100^1#6b04120:1 Line 1 Column 62 File C:/temp/prime_with_templates.cpp)operator
   |   |   |   |   |   )operator_function_id#6b04120
   |   |   |   |   |  )unqualified_id#6b04140
   |   |   |   |   | )id_expression#6b04160
   |   |   |   |   |)declarator_id#6b04180
   |   |   |   |   )noptr_declarator#6b041a0
   |   |   |   |   (parameter_declaration_clause@Cpp~GCC5=1558#6afba40^1#6b041e0:2 Line 1 Column 65 File C:/temp/prime_with_templates.cpp)parameter_declaration_clause
   |   |   |   |   (function_qualifiers@Cpp~GCC5=1438#6b041c0^1#6b041e0:3 Line 1 Column 66 File C:/temp/prime_with_templates.cpp)function_qualifiers
   |   |   |   |  )noptr_declarator#6b041e0
   |   |   |   | )ptr_declarator#6b04200
   |   |   |   |)function_head#6b04220
   |   |   |   |(function_body@Cpp~GCC5=1680#6b04300^1#6b04280:2 Line 1 Column 66 File C:/temp/prime_with_templates.cpp
   |   |   |   | (compound_statement@Cpp~GCC5=889#6b04760^1#6b04300:1 Line 1 Column 66 File C:/temp/prime_with_templates.cpp
   |   |   |   |  (pp_statement_seq@Cpp~GCC5=894#6b04780^1#6b04760:1 Line 1 Column 67 File C:/temp/prime_with_templates.cpp
   |   |   |   |   (statement@Cpp~GCC5=857#6b04440^1#6b04780:1 Line 1 Column 67 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |(jump_statement@Cpp~GCC5=1011#6afba80^1#6b04440:1 Line 1 Column 67 File C:/temp/prime_with_templates.cpp
   |   |   |   |   | (pm_expression@Cpp~GCC5=551#6b04380^1#6afba80:1 Line 1 Column 74 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |  (cast_expression@Cpp~GCC5=543#6b04360^1#6b04380:1 Line 1 Column 74 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   (unary_expression@Cpp~GCC5=465#6b04340^1#6b04360:1 Line 1 Column 74 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   |(primary_expression@Cpp~GCC5=307#6b04320^1#6b04340:1 Line 1 Column 74 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   | (id_expression@Cpp~GCC5=317#6b042a0^1#6b04320:1 Line 1 Column 74 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   |  (unqualified_id@Cpp~GCC5=319#6b04260^1#6b042a0:1 Line 1 Column 74 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   |   (IDENTIFIER@Cpp~GCC5=3368#6b04240^1#6b04260:1[`V'] Line 1 Column 74 File C:/temp/prime_with_templates.cpp)IDENTIFIER
   |   |   |   |   |   |  )unqualified_id#6b04260
   |   |   |   |   |   | )id_expression#6b042a0
   |   |   |   |   |   |)primary_expression#6b04320
   |   |   |   |   |   )unary_expression#6b04340
   |   |   |   |   |  )cast_expression#6b04360
   |   |   |   |   | )pm_expression#6b04380
   |   |   |   |   |)jump_statement#6afba80
   |   |   |   |   )statement#6b04440
   |   |   |   |  )pp_statement_seq#6b04780
   |   |   |   | )compound_statement#6b04760
   |   |   |   |)function_body#6b04300
   |   |   |   )function_definition#6b04280
   |   |   |  )member_declaration#6b04820
   |   |   | )member_declaration_or_access_specifier#6b042c0
   |   |   |)member_specification#6b042e0
   |   |   )class_specifier#6b04880
   |   |  )type_specifier#6b048a0
   |   | )decl_specifier#6b048c0
   |   |)basic_decl_specifier_seq#6b048e0
   |   )simple_declaration#6b04900
   |  )block_declaration#6b04920
   | )declaration#6b04940
   |)template_declaration#6b04960
   )declaration#6b04980
  )pp_declaration_seq#6b049a0
  (pp_declaration_seq@Cpp~GCC5=1022#6b06620^1#6b06640:2 Line 3 Column 1 File C:/temp/prime_with_templates.cpp
   (declaration@Cpp~GCC5=1036#6b06600^1#6b06620:1 Line 3 Column 1 File C:/temp/prime_with_templates.cpp
   |(template_declaration@Cpp~GCC5=2079#6b065e0^1#6b06600:1 Line 3 Column 1 File C:/temp/prime_with_templates.cpp
   | (template_parameter_list@Cpp~GCC5=2083#6b05460^1#6b065e0:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
   |  (template_parameter_list@Cpp~GCC5=2083#6b05140^1#6b05460:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
   |   (template_parameter_list@Cpp~GCC5=2083#6b04ee0^1#6b05140:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
   |   |(template_parameter_list@Cpp~GCC5=2082#6b04cc0^1#6b04ee0:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
   |   | (template_parameter@Cpp~GCC5=2085#6b04ca0^1#6b04cc0:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
   |   |  (parameter_declaration@Cpp~GCC5=1611#6b04c80^1#6b04ca0:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
   |   |   (basic_decl_specifier_seq@Cpp~GCC5=1070#6b04a40^1#6b04c80:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
   |   |   |(decl_specifier@Cpp~GCC5=1073#6b04a20^1#6b04a40:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
   |   |   | (trailing_type_specifier@Cpp~GCC5=1118#6b04a00^1#6b04a20:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
   |   |   |  (simple_type_specifier@Cpp~GCC5=1138#6b049e0^1#6b04a00:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp)simple_type_specifier
   |   |   | )trailing_type_specifier#6b04a00
   |   |   |)decl_specifier#6b04a20
   |   |   )basic_decl_specifier_seq#6b04a40
   |   |   (ptr_declarator@Cpp~GCC5=1417#6b04c40^1#6b04c80:2 Line 3 Column 15 File C:/temp/prime_with_templates.cpp
   |   |   |(noptr_declarator@Cpp~GCC5=1421#6b04be0^1#6b04c40:1 Line 3 Column 15 File C:/temp/prime_with_templates.cpp
   |   |   | (declarator_id@Cpp~GCC5=1487#6b04bc0^1#6b04be0:1 Line 3 Column 15 File C:/temp/prime_with_templates.cpp
   |   |   |  (id_expression@Cpp~GCC5=317#6b04b60^1#6b04bc0:1 Line 3 Column 15 File C:/temp/prime_with_templates.cpp
   |   |   |   (unqualified_id@Cpp~GCC5=319#6b04ac0^1#6b04b60:1 Line 3 Column 15 File C:/temp/prime_with_templates.cpp
   |   |   |   |(IDENTIFIER@Cpp~GCC5=3368#6b049c0^1#6b04ac0:1[`no'] Line 3 Column 15 File C:/temp/prime_with_templates.cpp)IDENTIFIER
   |   |   |   )unqualified_id#6b04ac0
   |   |   |  )id_expression#6b04b60
   |   |   | )declarator_id#6b04bc0
   |   |   |)noptr_declarator#6b04be0
   |   |   )ptr_declarator#6b04c40
   |   |  )parameter_declaration#6b04c80
   |   | )template_parameter#6b04ca0
   |   |)template_parameter_list#6b04cc0
   |   |(template_parameter@Cpp~GCC5=2085#6b04ec0^1#6b04ee0:2 Line 3 Column 19 File C:/temp/prime_with_templates.cpp
   |   | (parameter_declaration@Cpp~GCC5=1611#6b04ea0^1#6b04ec0:1 Line 3 Column 19 File C:/temp/prime_with_templates.cpp
   |   |  (basic_decl_specifier_seq@Cpp~GCC5=1070#6b04b40^1#6b04ea0:1 Line 3 Column 19 File C:/temp/prime_with_templates.cpp
   |   |   (decl_specifier@Cpp~GCC5=1073#6b04ba0^1#6b04b40:1 Line 3 Column 19 File C:/temp/prime_with_templates.cpp
   |   |   |(trailing_type_specifier@Cpp~GCC5=1118#6b04c60^1#6b04ba0:1 Line 3 Column 19 File C:/temp/prime_with_templates.cpp
   |   |   | (simple_type_specifier@Cpp~GCC5=1138#6b04580^1#6b04c60:1 Line 3 Column 19 File C:/temp/prime_with_templates.cpp)simple_type_specifier
   |   |   |)trailing_type_specifier#6b04c60
   |   |   )decl_specifier#6b04ba0
   |   |  )basic_decl_specifier_seq#6b04b40
   |   |  (ptr_declarator@Cpp~GCC5=1417#6b04e60^1#6b04ea0:2 Line 3 Column 24 File C:/temp/prime_with_templates.cpp
   |   |   (noptr_declarator@Cpp~GCC5=1421#6b04e40^1#6b04e60:1 Line 3 Column 24 File C:/temp/prime_with_templates.cpp
   |   |   |(declarator_id@Cpp~GCC5=1487#6b04de0^1#6b04e40:1 Line 3 Column 24 File C:/temp/prime_with_templates.cpp
   |   |   | (id_expression@Cpp~GCC5=317#6b04d80^1#6b04de0:1 Line 3 Column 24 File C:/temp/prime_with_templates.cpp
   |   |   |  (unqualified_id@Cpp~GCC5=319#6b04ce0^1#6b04d80:1 Line 3 Column 24 File C:/temp/prime_with_templates.cpp
   |   |   |   (IDENTIFIER@Cpp~GCC5=3368#6b04560^1#6b04ce0:1[`yes'] Line 3 Column 24 File C:/temp/prime_with_templates.cpp)IDENTIFIER
   |   |   |  )unqualified_id#6b04ce0
   |   |   | )id_expression#6b04d80
   |   |   |)declarator_id#6b04de0
   |   |   )noptr_declarator#6b04e40
   |   |  )ptr_declarator#6b04e60
   |   | )parameter_declaration#6b04ea0
   |   |)template_parameter#6b04ec0
   |   )template_parameter_list#6b04ee0
   |   (template_parameter@Cpp~GCC5=2085#6b05120^1#6b05140:2 Line 3 Column 29 File C:/temp/prime_with_templates.cpp
   |   |(parameter_declaration@Cpp~GCC5=1611#6b05100^1#6b05120:1 Line 3 Column 29 File C:/temp/prime_with_templates.cpp
   |   | (basic_decl_specifier_seq@Cpp~GCC5=1070#6b04d20^1#6b05100:1 Line 3 Column 29 File C:/temp/prime_with_templates.cpp
   |   |  (decl_specifier@Cpp~GCC5=1073#6b04dc0^1#6b04d20:1 Line 3 Column 29 File C:/temp/prime_with_templates.cpp
   |   |   (trailing_type_specifier@Cpp~GCC5=1118#6b04e80^1#6b04dc0:1 Line 3 Column 29 File C:/temp/prime_with_templates.cpp
   |   |   |(simple_type_specifier@Cpp~GCC5=1140#6b046e0^1#6b04e80:1 Line 3 Column 29 File C:/temp/prime_with_templates.cpp)simple_type_specifier
   |   |   )trailing_type_specifier#6b04e80
   |   |  )decl_specifier#6b04dc0
   |   | )basic_decl_specifier_seq#6b04d20
   |   | (ptr_declarator@Cpp~GCC5=1417#6b05080^1#6b05100:2 Line 3 Column 33 File C:/temp/prime_with_templates.cpp
   |   |  (noptr_declarator@Cpp~GCC5=1421#6b05020^1#6b05080:1 Line 3 Column 33 File C:/temp/prime_with_templates.cpp
   |   |   (declarator_id@Cpp~GCC5=1487#6b05000^1#6b05020:1 Line 3 Column 33 File C:/temp/prime_with_templates.cpp
   |   |   |(id_expression@Cpp~GCC5=317#6b04fa0^1#6b05000:1 Line 3 Column 33 File C:/temp/prime_with_templates.cpp
   |   |   | (unqualified_id@Cpp~GCC5=319#6b04f00^1#6b04fa0:1 Line 3 Column 33 File C:/temp/prime_with_templates.cpp
   |   |   |  (IDENTIFIER@Cpp~GCC5=3368#6b046c0^1#6b04f00:1[`f'] Line 3 Column 33 File C:/temp/prime_with_templates.cpp)IDENTIFIER
   |   |   | )unqualified_id#6b04f00
   |   |   |)id_expression#6b04fa0
   |   |   )declarator_id#6b05000
   |   |  )noptr_declarator#6b05020
   |   | )ptr_declarator#6b05080
   |   |)parameter_declaration#6b05100
   |   )template_parameter#6b05120
   |  )template_parameter_list#6b05140
   |  (template_parameter@Cpp~GCC5=2085#6b05440^1#6b05460:2 Line 3 Column 36 File C:/temp/prime_with_templates.cpp
   |   (parameter_declaration@Cpp~GCC5=1611#6b05420^1#6b05440:1 Line 3 Column 36 File C:/temp/prime_with_templates.cpp
   |   |(basic_decl_specifier_seq@Cpp~GCC5=1070#6b05160^1#6b05420:1 Line 3 Column 36 File C:/temp/prime_with_templates.cpp
   |   | (decl_specifier@Cpp~GCC5=1073#6b04fe0^1#6b05160:1 Line 3 Column 36 File C:/temp/prime_with_templates.cpp
   |   |  (trailing_type_specifier@Cpp~GCC5=1118#6b050e0^1#6b04fe0:1 Line 3 Column 36 File C:/temp/prime_with_templates.cpp
   |   |   (simple_type_specifier@Cpp~GCC5=1140#6b050c0^1#6b050e0:1 Line 3 Column 36 File C:/temp/prime_with_templates.cpp)simple_type_specifier
   |   |  )trailing_type_specifier#6b050e0
   |   | )decl_specifier#6b04fe0
   |   |)basic_decl_specifier_seq#6b05160
   |   |(ptr_declarator@Cpp~GCC5=1417#6b053e0^1#6b05420:2 Line 3 Column 40 File C:/temp/prime_with_templates.cpp
   |   | (noptr_declarator@Cpp~GCC5=1421#6b053c0^1#6b053e0:1 Line 3 Column 40 File C:/temp/prime_with_templates.cpp
   |   |  (declarator_id@Cpp~GCC5=1487#6b05360^1#6b053c0:1 Line 3 Column 40 File C:/temp/prime_with_templates.cpp
   |   |   (id_expression@Cpp~GCC5=317#6b05280^1#6b05360:1 Line 3 Column 40 File C:/temp/prime_with_templates.cpp
   |   |   |(unqualified_id@Cpp~GCC5=319#6b051a0^1#6b05280:1 Line 3 Column 40 File C:/temp/prime_with_templates.cpp
   |   |   | (IDENTIFIER@Cpp~GCC5=3368#6b046a0^1#6b051a0:1[`p'] Line 3 Column 40 File C:/temp/prime_with_templates.cpp)IDENTIFIER
   |   |   |)unqualified_id#6b051a0
   |   |   )id_expression#6b05280
   |   |  )declarator_id#6b05360
   |   | )noptr_declarator#6b053c0
   |   |)ptr_declarator#6b053e0
   |   )parameter_declaration#6b05420
   |  )template_parameter#6b05440
   | )template_parameter_list#6b05460