In der Informatik und Linguistik ist Syntaxanalyse, oder, mehr formell, syntaktische Analyse, der Prozess, einen Text zu analysieren, der aus einer Folge von Jetons (zum Beispiel, Wörter) gemacht ist, seine grammatische Struktur in Bezug auf eine gegebene (mehr oder weniger) formelle Grammatik zu bestimmen. Syntaxanalyse kann auch als ein Sprachbegriff zum Beispiel verwendet werden, wenn man bespricht, wie Ausdrücke in Garten-Pfad-Sätzen zerteilt werden.

Syntaxanalyse ist auch ein früherer Begriff dafür, von Sätzen von natürlichen Sprachen schematisch darzustellen, und wird noch dafür verwendet, von flektierten Sprachen, wie die Romanischen Sprachen oder das Latein schematisch darzustellen. Der Begriff Syntaxanalyse kommt aus lateinischen Durchschnitten (ōrātiōnis), Teil (der Rede) bedeutend.

Syntaxanalyse ist ein in psycholinguistics verwendeter verbreiteter Ausdruck, wenn sie Sprachverständnis beschreibt. In diesem Zusammenhang bezieht sich Syntaxanalyse auf die Weise, wie Menschen, aber nicht Computer, einen Satz analysieren oder Ausdruck (auf der Sprache oder dem Text) "in Bezug auf grammatische Bestandteile, die Wortarten identifizierend, syntaktische Beziehungen, usw." Dieser Begriff besonders üblich sind, wenn sie das besprechen, welche Sprachstichwörter Sprechern helfen, Sätze des Garten-Pfads grammatisch zu analysieren.

Parser

In der Computerwissenschaft ist ein parser einer der Bestandteile in einem Dolmetscher oder Bearbeiter, der für die richtige Syntax überprüft und eine Datenstruktur (häufig eine Art Syntaxanalyse-Baum, abstrakter Syntax-Baum oder andere hierarchische Struktur) implizit in den Eingangsjetons baut. Der parser verwendet häufig einen getrennten lexikalischen Analysator, um Jetons von der Folge von Eingangscharakteren zu schaffen. Parsers kann mit der Hand programmiert werden oder kann (halb-) (auf einigen Programmiersprachen) durch ein Werkzeug automatisch erzeugt werden.

Menschliche Sprachen

In einer maschinellen Übersetzung und Systemen der Verarbeitung der natürlichen Sprache werden menschliche Sprachen durch Computerprogramme grammatisch analysiert. Menschliche Sätze werden durch Programme nicht leicht grammatisch analysiert, weil es wesentliche Zweideutigkeit in der Struktur der menschlichen Sprache gibt, deren Gebrauch Bedeutung (oder Semantik) unter einer potenziell unbegrenzten Reihe von Möglichkeiten befördern soll, aber von denen nur einige mit dem besonderen Fall zusammenhängend sind. So beißt eine Äußerung "Mann Hund" gegen den "Hund-Bissen-Mann", ist auf einem Detail bestimmt, aber auf einer anderen Sprache könnte erscheinen, weil "Mann-Hund" mit einem Vertrauen auf dem größeren Zusammenhang beißt, um zwischen jenen zwei Möglichkeiten zu unterscheiden, wenn tatsächlich, dass Unterschied von Bedeutung gewesen ist. Es ist schwierig, formelle Regeln vorzubereiten, informelles Verhalten zu beschreiben, wenn auch es klar ist, dass einigen Regeln gefolgt wird.

Um Daten der natürlichen Sprache grammatisch zu analysieren, müssen sich Forscher zuerst über die zu verwendende Grammatik einigen. Die Wahl der Syntax wird sowohl durch linguistische als auch durch rechenbetonte Sorgen betroffen; zum Beispiel verwenden einige Syntaxanalyse-Systeme lexikalische funktionelle Grammatik, aber im Allgemeinen, wie man bekannt, für Grammatiken dieses Typs grammatisch zu analysieren, ist NP-complete. Hauptgesteuerte Ausdruck-Struktur-Grammatik ist ein anderer Sprachformalismus, der in der Syntaxanalyse-Gemeinschaft populär gewesen ist, aber andere Forschungsanstrengungen haben sich auf weniger komplizierte Formalismen wie im Penn Treebank verwendeter derjenige konzentriert. Seichte Syntaxanalyse hat zum Ziel, nur die Grenzen von Hauptbestandteilen wie nominale Wortverbindungen zu finden. Eine andere populäre Strategie, um Sprachmeinungsverschiedenheit zu vermeiden, ist Abhängigkeitsgrammatik-Syntaxanalyse.

Modernste parsers sind mindestens teilweise statistisch; d. h. sie verlassen sich auf ein Korpus von Lehrdaten, das bereits (grammatisch analysiert mit der Hand) kommentiert worden ist. Diese Annäherung erlaubt dem System, Information über die Frequenz zu sammeln, mit der verschiedene Aufbauten in spezifischen Zusammenhängen vorkommen. (Sieh Maschine erfahren.) Schließen Annäherungen, die verwendet worden sind, aufrichtigen PCFGs (probabilistic Grammatiken ohne Zusammenhänge), maximales Wärmegewicht und Nervennetze ein. Die meisten erfolgreicheren Systeme verwenden lexikalische Statistik (d. h. sie betrachten die Identität der Wörter als beteiligt, sowie ihre Wortart). Jedoch sind solche Systeme für die Überanprobe verwundbar und verlangen, dass eine Art Glanzschleifen wirksam ist.

Die Syntaxanalyse von Algorithmen für natürliche Sprache kann sich auf die Grammatik nicht verlassen, die 'nette' Eigenschaften als mit manuell bestimmten Grammatiken für Programmiersprachen hat. Wie erwähnt, früher sind einige Grammatik-Formalismen sehr schwierig, rechenbetont grammatisch zu analysieren; im Allgemeinen, selbst wenn die gewünschte Struktur nicht ohne Zusammenhänge ist, wird eine Art Annäherung ohne Zusammenhänge an die Grammatik verwendet, um einen ersten Pass durchzuführen. Algorithmen, die Grammatiken ohne Zusammenhänge häufig verwenden, verlassen sich auf eine Variante des CKY Algorithmus, gewöhnlich mit einigen heuristisch, um weg unwahrscheinliche Analysen zu beschneiden, um Zeit zu sparen. (Sieh Karte grammatisch analysieren.) Jedoch tauschen einige Systeme Geschwindigkeit gegen das Genauigkeitsverwenden, z.B, die geradlinig-maligen Versionen des Shift-Reduce-Algorithmus. Eine etwas neue Entwicklung ist Syntaxanalyse gewesen, die sich wiederaufreiht, in dem der parser eine Vielzahl von Analysen vorschlägt, und ein komplizierteres System die beste Auswahl auswählt.

Programmiersprachen

Der grösste Teil der üblichen Anwendung eines parser ist als ein Bestandteil eines Bearbeiters oder Dolmetschers. Das analysiert den Quellcode einer Computerprogrammiersprache grammatisch, um eine Form der inneren Darstellung zu schaffen. Programmiersprachen neigen dazu, in Bezug auf eine Grammatik ohne Zusammenhänge angegeben zu werden, weil schneller und effizienter parsers für sie geschrieben werden kann. Parsers werden mit der Hand geschrieben oder durch parser Generatoren erzeugt.

Grammatiken ohne Zusammenhänge werden im Ausmaß beschränkt, zu dem sie alle Voraussetzungen einer Sprache ausdrücken können. Informell besteht der Grund darin, dass das Gedächtnis solch einer Sprache beschränkt wird. Die Grammatik kann sich an die Anwesenheit einer Konstruktion über willkürlich lange Eingang nicht erinnern; das ist für eine Sprache notwendig, auf der, zum Beispiel, ein Name erklärt werden muss, bevor darin Verweise angebracht werden kann. Stärkere Grammatiken, die diese Einschränkung jedoch ausdrücken können, können effizient nicht grammatisch analysiert werden. So ist es eine allgemeine Strategie, einen entspannten parser für eine Grammatik ohne Zusammenhänge zu schaffen, die eine Obermenge der gewünschten Sprachkonstruktionen akzeptiert (d. h. es akzeptiert einige ungültige Konstruktionen); später können die unerwünschten Konstruktionen herausgefiltert werden.

Übersicht des Prozesses

Das folgende Beispiel demonstriert den allgemeinen Fall, eine Computersprache mit zwei Niveaus der Grammatik grammatisch zu analysieren: lexikalisch und syntaktisch.

Die erste Stufe ist die Scheingeneration oder lexikalische Analyse, durch die der Eingangscharakter-Strom in bedeutungsvolle durch eine Grammatik von regelmäßigen Ausdrücken definierte Symbole gespalten wird. Zum Beispiel würde ein Rechenmaschine-Programm auf einen Eingang solcher als "" schauen und ihn in die Jetons spalten, von denen jeder ein bedeutungsvolles Symbol im Zusammenhang eines arithmetischen Ausdrucks ist. Der lexer würde Regeln enthalten, ihm zu sagen, dass die Charaktere, und den Anfang eines neuen Jetons kennzeichnen, so werden sinnlose Jetons wie "" oder "" nicht erzeugt.

Die folgende Bühne analysiert grammatisch oder syntaktische Analyse, die überprüft, dass die Jetons einen zulässigen Ausdruck bilden. Das wird gewöhnlich bezüglich einer Grammatik ohne Zusammenhänge getan, die rekursiv Bestandteile definiert, die einen Ausdruck und die Ordnung zusammensetzen können, in der sie erscheinen müssen. Jedoch können nicht alle Regeln, die Programmiersprachen definieren, durch Grammatiken ohne Zusammenhänge allein, zum Beispiel Typ-Gültigkeit und richtige Behauptung von Bezeichnern ausgedrückt werden. Diese Regeln können mit Attribut-Grammatiken formell ausgedrückt werden.

Die Endphase ist semantische Syntaxanalyse oder Analyse, die die Implikationen des Ausdrucks gerade gültig gemacht ausarbeitet und die passende Handlung nimmt. Im Fall von einer Rechenmaschine oder Dolmetscher soll die Handlung den Ausdruck oder das Programm bewerten, ein Bearbeiter würde andererseits eine Art Code erzeugen. Attribut-Grammatiken können auch verwendet werden, um diese Handlungen zu definieren.

Typen von parser

Die Aufgabe des parser ist im Wesentlichen zu bestimmen, wenn und wie der Eingang aus dem Anfang-Symbol der Grammatik abgeleitet werden kann. Das kann auf im Wesentlichen zwei Weisen getan werden:

• Verfeinernde Syntaxanalyse - Verfeinernde Syntaxanalyse kann als ein Versuch angesehen werden, ganz links Abstammungen eines Eingangsstroms durch das Suchen nach Syntaxanalyse-Bäumen mit einer verfeinernden Vergrößerung der gegebenen formellen Grammatik-Regeln zu finden. Jetons werden vom linken bis Recht verbraucht. Einschließliche Wahl wird verwendet, um Zweideutigkeit durch die Erweiterung aller alternativen rechten Seiten von Grammatik-Regeln anzupassen.
• Von unten nach oben grammatisch analysierend - kann Ein parser mit dem Eingang anfangen und versuchen, ihn zum Anfang-Symbol umzuschreiben. Intuitiv versucht der parser, die grundlegendsten Elemente, dann die Elemente ausfindig zu machen, die diese und so weiter enthalten. LR parsers sind Beispiele von unten nach oben parsers. Ein anderer für diesen Typ von parser gebrauchter Begriff ist Shift-Reduce-Syntaxanalyse.

LL parsers und rekursiver Abstieg parser sind Beispiele von verfeinerndem parsers, der linke rekursive Produktion nicht anpassen kann. Obwohl es geglaubt worden ist, dass einfache Durchführungen der verfeinernden Syntaxanalyse direkt und indirekt nach-links-recursion nicht anpassen können und Exponentialkompliziertheit der Zeit und Raums verlangen können, während sie zweideutige Grammatiken ohne Zusammenhänge grammatisch analysieren, sind hoch entwickeltere Algorithmen für die verfeinernde Syntaxanalyse durch den Frost, Hafiz und Callaghan geschaffen worden, die Zweideutigkeit und verlassenen recursion in der polynomischen Zeit anpassen, und die Darstellungen der polynomischen Größe der potenziell Exponentialzahl von Syntaxanalyse-Bäumen erzeugen. Ihr Algorithmus ist im Stande, sowohl ganz links als auch niedrigstwertige Abstammungen eines Eingangs hinsichtlich eines gegebenen CFG (Grammatik ohne Zusammenhänge) zu erzeugen.

Eine wichtige Unterscheidung hinsichtlich parsers ist, ob ein parser eine leftmost Abstammung oder eine niedrigstwertige Abstammung erzeugt (sieh Grammatik ohne Zusammenhänge). LL parsers wird eine leftmost Abstammung erzeugen, und LR wird parsers eine niedrigstwertige Abstammung (obwohl gewöhnlich rückwärts) erzeugen.

Beispiele von parsers

Verfeinernder parsers

Einige der parsers, die verfeinernde Syntaxanalyse verwenden, schließen ein:

• Rekursiver Abstieg parser
• LL parser (Zum Recht nach links, Abstammung von Leftmost)
• Earley parser

Von unten nach oben parsers

Einige der parsers, die von unten nach oben Syntaxanalyse verwenden, schließen ein:

• Priorität parser
• Maschinenbediener-Priorität parser
• Einfache Priorität parser
• V. Chr. (begrenzter Zusammenhang), grammatisch analysierend
• LR parser (Zum Recht nach links, Niedrigstwertige Abstammung)
• Einfacher LR (SLR) parser
• LALR parser
• Kanonischer LR (LR (1)) parser
• GLR parser
• CYK parser

Entwicklungssoftware von Parser

Einige der weithin bekannten parser Entwicklungswerkzeuge schließen das folgende ein. Siehe auch Vergleich von parser Generatoren.

• ANTLR
• Bison
• Coco/R
• GOLD
• JavaCC
• Zitrone
• Lex
• Halb gekochter
• ParseIT
• Ragel
• SHProto (FSM parser Sprache)
• Geist Parser Fachwerk
• Syntax-Definitionsformalismus
• SYNTAX
• VisualLangLab
• XPL
• Yacc

Lookahead

Lookahead gründet die maximalen eingehenden Jetons, die ein parser verwenden kann, um zu entscheiden, welche Regel es verwenden sollte. Lookahead ist für LL, LR und LALR parsers besonders wichtig, wo es häufig durch das Anbringen des lookahead am Algorithmus-Namen in Parenthesen, wie LALR (1) ausführlich angezeigt wird.

Die meisten Programmiersprachen, das primäre Ziel von parsers, werden auf solche Art und Weise sorgfältig definiert, dass ein parser mit beschränktem lookahead, normalerweise ein, sie grammatisch analysieren kann, weil parsers mit beschränktem lookahead häufig effizienter sind. Eine wichtige Änderung zu dieser Tendenz ist 1990 gekommen, als Terence Parr ANTLR für seine Doktorarbeit, einen parser Generator für effizienten LL (k) parsers geschaffen hat, wo k jeder feste Wert ist.

Parsers haben normalerweise nur einige Handlungen nach dem Sehen jedes Jetons. Sie sind Verschiebung (fügen Sie diesen Jeton zum Stapel für die spätere Verminderung hinzu), nehmen Sie ab (Knall-Jetons vom Stapel, und bilden Sie eine syntaktische Konstruktion), Ende, Fehler (gilt keine bekannte Regel), oder Konflikt (weiß nicht, ob man sich bewegt oder abnimmt).

Lookahead hat zwei Vorteile.

• Es hilft dem parser, die richtige Handlung im Falle Konflikte zu nehmen. Zum Beispiel, wenn Behauptung im Fall von sonst Klausel grammatisch analysierend.
• Es beseitigt viele Doppelstaaten und erleichtert die Last eines Extrastapels. Eine c Sprache non-lookahead parser wird ungefähr 10,000 Staaten haben. Ein lookahead parser wird ungefähr 300 Staaten haben.

Beispiel: Syntaxanalyse des Ausdrucks 1 + 2 * 3

Der Satz von Ausdruck-Syntaxanalyse-Regeln (genannt Grammatik) ist wie folgt,

Rule1: E  E + E Ausdruck ist die Summe von zwei Ausdrücken.

Rule2: E  E * E Ausdruck ist das Produkt von zwei Ausdrücken.

Rule3: E  Zahl-Ausdruck ist eine einfache Zahl

Rule4: + hat weniger Priorität als *

Die meisten Programmiersprachen (abgesehen von einigen wie APL und Plausch) und algebraische Formeln geben höhere Priorität der Multiplikation als Hinzufügung, in welchem Fall die richtige Interpretation des Beispiels oben (1 + (2*3)) ist.

Bemerken Sie, dass Rule4 oben eine semantische Regel ist. Es ist möglich, die Grammatik umzuschreiben, um das in die Syntax zu vereinigen. Jedoch können nicht alle diese Regeln in die Syntax übersetzt werden.

Einfacher non-lookahead parser Handlungen

1. Nimmt 1 zum Ausdruck E auf dem Eingang 1 gestützter auf rule3 ab.
2. Verschiebung + auf den Stapel auf dem Eingang 1 vor rule1.
3. Reduzieren Sie Stapel-Element 2 auf den auf rule3 gestützten Ausdruck E.
4. Reduzieren Sie Stapel-Sachen E + und neuer Eingang E zu auf rule1 gestütztem E.
5. Verschiebung * auf den Stapel auf dem Eingang * vor rule2.
6. Bewegen Sie sich 3 auf den Stapel auf dem Eingang 3 vor rule3.
7. Nehmen Sie 3 zum Ausdruck E auf dem Eingang 3 gestützte auf rule3 ab.
8. Reduzieren Sie Stapel-Sachen E* und neuer Eingang E zu auf rule2 gestütztem E.

Der Syntaxanalyse-Baum und resultierende Code davon sind gemäß der Sprachsemantik nicht richtig.

Um ohne lookahead richtig grammatisch zu analysieren, gibt es drei Lösungen:

• Der Benutzer muss Ausdrücke innerhalb von Parenthesen einschließen. Das ist häufig nicht eine lebensfähige Lösung.
• Der parser muss mehr Logik haben, um denselben Weg zurückzuverfolgen und neu zu verhandeln, wann auch immer eine Regel verletzt oder nicht abgeschlossen wird. Der ähnlichen Methode wird in LL parsers gefolgt.
• Wechselweise müssen der parser oder die Grammatik Extralogik haben, um die Verminderung zu verzögern und nur abzunehmen, wenn es absolut sicher ist, die herrschen, um zuerst abzunehmen. Diese Methode wird in LR parsers verwendet. Das analysiert richtig den Ausdruck, aber mit noch vielen Staaten und vergrößerter Stapel-Tiefe grammatisch.

Handlungen von Lookahead parser

1. Bewegen Sie sich 1 auf den Stapel auf dem Eingang 1 vor rule3. Es nimmt sofort nicht ab.
2. Reduzieren Sie Stapel-Artikel 1 auf den einfachen Ausdruck auf dem Eingang + gestützt auf rule3. Der lookahead ist +, so sind wir auf dem Pfad zu E +, so können wir den Stapel auf E reduzieren.
3. Verschiebung + auf den Stapel auf dem Eingang + vor rule1.
4. Bewegen Sie sich 2 auf den Stapel auf dem Eingang 2 vor rule3.
5. Reduzieren Sie Stapel-Artikel 2 auf den Ausdruck auf dem Eingang * gestützt auf rule3. Der lookahead * erwartet nur E davor.
6. Jetzt hat Stapel E + E, und dennoch ist der Eingang *. Es hat zwei Wahlen jetzt, entweder um sich gestützt auf rule2 oder der auf rule1 gestützten Verminderung zu bewegen. Seitdem * hat mehr Priorität als + gestützt auf rule4, so bewegen Sie sich * auf den Stapel vor rule2.

Bewegen Sie sich 3 auf den Stapel auf dem Eingang 3 vor rule3.

1. Reduzieren Sie Stapel-Artikel 3 auf den Ausdruck nach dem Sehen des Endes des auf rule3 gestützten Eingangs.
2. Reduzieren Sie Stapel-Sachen E * E zu auf rule2 gestütztem E.
3. Reduzieren Sie Stapel-Sachen E + E zu auf rule1 gestütztem E.

Der erzeugte Syntaxanalyse-Baum ist richtig und einfach effizienter als non-lookahead parsers. Das ist die Strategie, die in LALR parsers gefolgt ist.

Siehe auch

• Das Zurückverfolgen
• Karte parser
• Bearbeiter-Bearbeiter
• Deterministische Syntaxanalyse
• Das Erzeugen von Schnuren
• Grammatik-Kontrolleur

LALR parser

• Lexing
• Pratt parser
• Seichte Syntaxanalyse
• Verlassene Ecke parser
• Die Syntaxanalyse der Ausdruck-Grammatik

Weiterführende Literatur

• Hausierer, Nigel P., LR Syntaxanalyse: Theorie und Praxis, Universität von Cambridge Presse, 1987. Internationale Standardbuchnummer 0 521 30413 X
• Grune, Detektiv; Jacobs, Ceriel J.H. Techniken - Ein Praktischer Führer, Vrije Universiteit Amsterdam, Amsterdam, Die Niederlande Grammatisch analysierend. Ursprünglich veröffentlicht von Ellis Horwood, Chichester, England, 1990; internationale Standardbuchnummer 0-13-651431-6

Links

• Die Zitrone LALR Parser Generator