Warum ist regulärer Ausdruck ((x, y) | (x, z)) nicht deterministisch, wie das Buch "Core Java" sagt? Der Autor gibt seinen Standpunkt:
Wenn der Parser x sieht, weiß er nicht, welche der beiden Alternativen er zu nehmen hat. Dieser Ausdruck kann in einer deterministischen Form als (x, (y | z))
umgeschrieben werden
Könnte mir jemand eine Erklärung geben?
Um eine deterministische Form zu haben, dürfen Sie nur maximal einen möglichen Weg an Ihrer aktuellen Position haben. Nehmen wir an, Sie haben eine Zeichenfolge " x, y ". Jetzt schaut die Regex-Engine auf das erste Zeichen, das " x ". In Ihrem Ausdruck haben Sie 2 Möglichkeiten, wie Ihre Zeichenfolge nach einem " x " an der ersten Position weitergehen kann, um Ihre Eingabe zu akzeptieren. Weiter gibt es 2 Möglichkeiten zu überprüfen. Entweder, wenn auf die Zeichenfolge ", y " oder ", z " folgt.
%Vor%Für (x, (y | z)) hast du immer nur einen Weg. Wenn sich ein " x " an Position 1 befindet, wechseln Sie zu Position 2. Gleiches gilt auch für ", ". Schließlich muss er überprüfen, ob an Position 3 ein " y " oder ein " z " vorhanden ist, um das Wort zu akzeptieren. Es gab nie 2 Wege.
%Vor%Eine endliche Zustandsmaschine wird als nichtdeterministischer endlicher Automat (NFA) bezeichnet, wenn in einem bestimmten Zustand kann es mehrere Übergänge mit demselben Symbol haben
Das bedeutet, dass Ihre Grammatik (d. h. Ihre Regex) dazu führen kann, dass zwei Ableitungsbäume für denselben Ausdruck vorhanden sind und wir nicht den Zustand kennen, den der Automat wählen wird:
%Vor%((x, y) | (x, z))
In diesem Fall weiß der Parser, wenn er x sieht, nicht, welche Gruppe er annehmen soll, d. h. x,y oder x,z (nicht deterministische Form)
(x, (y | z))
In diesem Fall kann der Parser x, lesen und kann nun y oder z (deterministische Form)
Ich denke, dass das erwähnte Problem nur dann relevant ist, wenn es um Gruppenabgleich geht.
Wenn x ([a-z][a-z]) ist und y ([0-6][0-6]) und z ([3-9][3-9]) , dann haben Sie einen regulären Ausdruck wie folgt:
Bei einer gegebenen Eingabe wie pq,45 kann diese mit einer Seite des Pipe-Symbols abgeglichen werden (d. h. es stimmt mit (([a-z][a-z]),([0-6][0-6])) und (([a-z][a-z]),([3-9][3-9])) überein).
In diesem Fall definiert der Standard, dass die linke Seite des Rohrsymbols Vorrang vor der rechten Seite hat. Der Wert für x kann dann in der Gruppennummer 3 gefunden werden (die dritte öffnende Klammer).
Wenn sich die Eingabe jetzt zu e ändert. G. pq,78 , dann hat sich die Übereinstimmung für x überhaupt nicht geändert (es ist immer noch pq ), aber jetzt stimmt die rechte Seite des Pipe-Symbols überein und Sie finden xs Wert in der Gruppennummer 6.
Dies kann vermieden werden, indem ein stabilerer regulärer Ausdruck wie (([a-z][a-z]),(([0-6][0-6])|([3-9][3-9]))) verwendet wird, in dem x immer in Gruppe 2 ist.