Ableiten des regulären Ausdrucks für C-style / ** / Kommentare

8

Ich arbeite an einem Parser für eine Sprache im C-Stil, und für diesen Parser benötige ich den regulären Ausdruck, der mit C-Stil / ** / Kommentare übereinstimmt. Jetzt habe ich diesen Ausdruck im Web gefunden:

/\*([^\*]*\*+[^\*/])*([^\*]*\*+|[^\*]*\*/

Wie Sie sehen, ist dies jedoch ein ziemlich chaotischer Ausdruck, und ich habe keine Ahnung, ob er tatsächlich genau dem entspricht, was ich möchte.

Gibt es eine andere Möglichkeit, reguläre Ausdrücke (rigoros) zu definieren, die leicht von Hand überprüft werden können, ob sie wirklich korrekt sind, und die dann in den obigen regulären Ausdruck konvertierbar ("kompilierbar") sind?

compilers parsers regular-languages Alex ten Brink
quelle
2
Beachten Sie, dass dieser Ansatz verschachtelte Kommentare verhindert. Wenn Sie ohnehin einen vollständigen Parser erstellen, sollten Sie Blockkommentare "richtig" analysieren. Es muss nicht nur klarer sein, Sie können auch strukturierte Metadaten aus Kommentaren lesen, wenn Sie möchten.
Raphael
Waren die Fragmente (!\*)beabsichtigt? Meinen Sie die häufigere Notation [^*]? Und was ist (!*|!/)?
Gilles 'SO - hör auf böse zu sein'
@ Gilles: Ich habe den Ausdruck aktualisiert. (! * |! /) soll etwas sein, das weder * noch / ist.
Alex Ten Brink
@ Raphael, in C Kommentare nicht verschachteln .
vonbrand
@vonbrand: "C-Stil" ist nicht sehr spezifisch, daher ist es ein gültiger Punkt, zu erwähnen, dass eine "natürliche Verbesserung" nicht möglich ist.
Frafl

Antworten:

6

Ich kann mir vier Möglichkeiten vorstellen:

  1. Definieren Sie einen Automaten für die Sprache, die Sie interessiert. Konvertieren Sie den regulären Ausdruck in einen Automaten (unter Verwendung von Brzozowskis Ableitungen). Überprüfen Sie, ob beide Automaten dieselbe Sprache akzeptieren (bestimmen und minimieren oder verwenden Sie ein Bisimulationsargument).

  2. Schreiben Sie viele Testfälle und wenden Sie Ihren regulären Ausdruck auf sie an.

  3. Konvertieren Sie den in Punkt 1 definierten Automaten mithilfe von Standardtechniken in einen regulären Ausdruck.

  4. Eine Kombination der oben genannten.

Dave Clarke
quelle
5

Wenn Sie sicher sein möchten, dass Sie C-Kommentare analysieren, müssen Sie Ihr Modell mit der C-Spezifikation konfrontieren. C99 §6.4.9 definiert die Syntax von Kommentaren wie folgt:

1. Außer innerhalb einer Zeichenkonstante, eines Zeichenfolgenliteral oder eines Kommentars führen die Zeichen /* einen Kommentar ein. Der Inhalt eines solchen Kommentars wird nur untersucht, um Multibyte-Zeichen zu identifizieren und die Zeichen zu finden, die */ihn beenden.

2. Außer innerhalb einer Zeichenkonstante, eines Zeichenfolgenliteral oder eines Kommentars führen die Zeichen //einen Kommentar ein, der alle Multibyte-Zeichen bis zum nächsten Zeilenumbruch enthält, jedoch nicht enthält. Der Inhalt eines solchen Kommentars wird nur untersucht, um Multibyte-Zeichen zu identifizieren und das abschließende neue Zeilenzeichen zu finden.

Dies ist englische Prosa, keine formale Definition, aber es gibt eine einigermaßen klare Interpretation in Bezug auf einen nichtdeterministischen endlichen Automaten (NFA), der einen Kommentar verbraucht:

  • Ab dem Anfangszustand tritt /gefolgt von dem *Eintritt in den mehrzeiligen Kommentarzustand und /gefolgt von dem /Eintritt in den einzeiligen Kommentarzustand ein.
  • Aus dem Status "In-Multiline-Kommentar", *gefolgt vom /Status "Post-Kommentar".
  • Aus dem Status "Einzeiliger Kommentar" wechselt eine neue Zeile in den Status "Nachkommentar".
  • Jedes andere Zeichen lässt den Status unverändert.

Beachten Sie, dass Sie, um zu wissen, ob der Anfangszustand zutrifft, etwas mehr Analysen durchführen müssen, um Zeichenfolgen- und Zeichenliterale zu erkennen.

Sobald Sie eine NFA haben, können Sie Standardtechniken verwenden, um einen regulären Ausdruck zu erstellen (ich sehe sie nicht in den Wikipedia-Artikeln, aber sie sollten in Lehrbüchern besprochen werden).

Wenn Sie bereits einen regulären Ausdruck haben und ihn testen möchten, können Sie seine generierte Sprache mit der aus der NFA abgeleiteten Sprache vergleichen, die aus der Sprachspezifikation abgeleitet wurde: Die Gleichheit der regulären Sprachen ist entscheidbar. Eine Möglichkeit, die Gleichheit zu bestimmen, besteht darin, für jeden einen minimalen deterministischen Automaten zu erstellen. Wenn die Sprachen äquivalent sind, sind die minimalen DFAs isomorph.

Gilles 'SO - hör auf böse zu sein'
quelle
Eine Suche in Google Books gibt diese Referenz für
Kleenes
0

Wenn Sie einen Parser schreiben, werden diese Dinge vom lexikalischen Analysator verarbeitet. Und dort können Sie dies durch reguläre Ausdrücke ausdrücken oder (wie die flexBeispiele, die ich gesehen habe) einfach "in die zugrunde liegende Sprache entkommen" und den Job dort beenden. Das heißt, /*wenn Sie sehen, springen Sie einfach weiter, bis Sie es finden */(ein DFA dafür ist einfach zu erstellen, und von dort aus ist ein C-Fragment einfach zu schreiben).

vonbrand
quelle