Parsing

Das Parsen dient dazu, die Struktur eines Textes hervorzuheben, normalerweise eines Satzes, der in einer natürlichen Sprache geschrieben ist. Diese Terminologie wird jedoch auch für die Analyse eines Computerprogramms verwendet. Der Parser ( Parser , auf Englisch) ist das Computerprogramm , das diese Aufgabe ausführt. Diese Operation setzt eine Formalisierung des Textes voraus, die am häufigsten als Element einer formalen Sprache angesehen wird und durch einen Satz von Syntaxregeln definiert wird, die eine formale Grammatik bilden . Die durch die Analyse aufgedeckte Struktur gibt dann genau an, wie die Syntaxregeln im Text kombiniert werden. Diese Struktur ist häufig eine Hierarchie von Phrasen , die durch einen syntaktischen Baum dargestellt werden kann, dessen Knoten dekoriert werden können (mit zusätzlichen Informationen versehen).

Das Parsen folgt normalerweise einer lexikalischen Analyse, die den Text in einen Strom (manchmal einen azyklisch gerichteten Graphen ) von Lexemen aufteilt und wiederum als Voraussetzung für eine semantische Analyse dient . Wenn Sie die syntaktische Struktur einer Äußerung kennen, können Sie die Abhängigkeitsbeziehungen (zum Beispiel zwischen Subjekt und Objekt) zwischen den verschiedenen Lexemen klären und dann eine Darstellung der Bedeutung dieser Äußerung erstellen.

In der Praxis und außer in sehr einfachen Fällen werden normalerweise Coroutinen benötigt, um die beiden zu verbinden. In FORTRAN, wo die Leerzeichen nicht signifikant waren, wären GOTO5 = 1 oder DO1I = 3 , Zuweisungen, die von der Syntax autorisiert wurden, obwohl sie pervers sind, fälschlicherweise als Syntaxfehler angesehen worden, wenn die lexikalische Analyseoperation vollständig ausgeführt worden wäre, bevor die Syntax beginnt. In der Praxis lehnten Low-End- Compiler sie ab.

Links zu formalen Sprachen

Die Methoden zur Durchführung einer syntaktischen Analyse hängen weitgehend vom Formalismus ab, der für die Syntax der Sprache verwendet wird, aber auch von der Sprache selbst. Umschreibungsgrammatiken werden jedoch häufig verwendet, um eine Sprache oder Sprache zu modellieren, von denen die beliebtesten nicht kontextbezogene Grammatiken sind .

Daher werden Programmiersprachen normalerweise durch diese Grammatiken beschrieben, und dies seit der Formalisierung von Algol in BNF . Ebenso, wenn die nicht-kontextuellen Grammatiken ungeeignet für die Beschreibung betrachtet werden natürlicher Sprachen , die Parsing - Algorithmen erfunden für die nicht kontextuellen Sprachen können manchmal auf die komplexere Formalismen im verwendeten angepasst Verarbeitung natürlicher Sprachen , wie beispielsweise die Grammatiken natürlicher Sprachen. 'Assistentenbäume (TAG) .

Die Äquivalenz zwischen den Sprachen, die von bestimmten Grammatikklassen definiert werden können, und denen, die von bestimmten Klassen von Automaten erkannt werden, ermöglicht es, Parser mithilfe von Automaten zu erstellen. Somit sind die Sprachen, die durch eine nicht kontextbezogene Grammatik definiert werden können, auch diejenigen, die durch einen Push-Down-Automaten erkennbar sind .

Nicht kontextbezogene Analyse

Bottom-up- oder Top-down-Analyse

Ein syntaktischer Analysator muss den Anwendungspfad der Syntaxregeln zurückverfolgen, die vom Axiom (Anfangselement einer algebraischen Grammatik ) zum analysierten Text führten.

Deterministische Analyse

Ein Parser als Umschreibesystem ist deterministisch, wenn in jeder Parser-Konfiguration nur eine Umschreiberegel anwendbar ist. In der Erweiterung kann es dann nur eine Folge von Regeln geben, die es ermöglichen, den Text in seiner Gesamtheit zu analysieren, und daher kann letzterer nicht syntaktisch mehrdeutig sein. Es können jedoch Techniken wie Voransicht ( Lookahead- Englisch) oder Backtracking ( Bracktracking oder Lookbehind- Englisch) verwendet werden, um zu bestimmen, welche Regel auf einen bestimmten Punkt der Analyse angewendet werden soll.

Deterministische Analysemethoden werden hauptsächlich zur Analyse von Programmiersprachen verwendet. Beispielsweise sind LR-, LL- oder LALR- Analysen (von Yacc verwendet ) alle deterministisch. Man kann jedoch keinen deterministischen Parser für eine nicht kontextbezogene Grammatik erstellen. In diesem Fall und wenn man nur eine Output-Analyse haben möchte, muss man zusätzliche Mechanismen hinzufügen, wie z. B. Disambiguierungsregeln oder Wahrscheinlichkeitsmodelle, die es ermöglichen, die „beste“ Analyse auszuwählen.

Eine top-down und deterministische Analysemethode wird als prädiktiv bezeichnet.

Nicht deterministische Analyse

Die Größe und Komplexität natürlicher Sprachen macht ihre deterministische Analyse völlig unmöglich , ohne ihre unvermeidliche Mehrdeutigkeit zu vergessen . Eine nicht deterministische Analyse ähnelt einer Auflösung in einem eingeschränkten System und lässt sich in Prolog recht einfach ausdrücken .

Die Verwendung tabellarischer Methoden zum Speichern der Zwischenberechnungen ist effizienter als ein einfaches Zurückverfolgen . Die CYK-Analyse ist ein Beispiel für eine tabellarische Analyse, bei der komplexere Methoden bevorzugt werden

Diese beiden letzten Analysemethoden werden auch für die Analyse von Programmiersprachen geschätzt, deren Syntax nicht eindeutig ist, wie z. B. C ++ .

Fehlerbehebung

Bei der syntaktischen Analyse von Programmiersprachen ist es erforderlich, die Analyse auch dann fortsetzen zu können, wenn der Quellcode Fehler enthält, um langwierige Kompilierungs- / Korrekturzyklen für den Entwickler zu vermeiden. Ebenso ist es bei der syntaktischen Analyse natürlicher Sprachen erforderlich, Aussagen analysieren zu können, auch wenn sie nicht durch die Grammatik abgedeckt sind, die unweigerlich unvollständig ist. Die Fehlerbehebung oder der Fangfehler (englische Fehlerbehebung ) sollte effektiv genug sein, um Probleme zu erkennen und "zu tun", mit einer Korrektur der Quelle oder der Fähigkeit, eine Analyse (geringfügig) im Vergleich zu einer Abweichung der Grammatik zu erstellen. Wir können vier Ansätze anführen, die in diese Richtung gehen, nämlich

Menschliche Sprachen

Traditionelle Methoden

Bei der traditionellen Analyseübung, die auch als Satzanalyse bezeichnet wird, wird ein Text in seine Bestandteile der Sprache zerlegt und gleichzeitig die Form, Funktion und syntaktische Beziehung jedes Teils erläutert. Dies kann hauptsächlich durch das Studium von Konjugationen und Deklinationen der Sprache festgestellt werden . Um einen Satz wie "der Mann beißt den Hund" zu analysieren, sollte beachtet werden, dass das Singular-Substantiv "Mann" Gegenstand des Satzes ist, das Verb "beißen", konjugiert mit "beißen", im dritten Person des gegenwärtigen Singulars, und das Singular-Substantiv "Hund" ist Gegenstand des Satzes. Um die Beziehung zwischen den Elementen des Satzes anzuzeigen, können Techniken wie Satzdiagramme verwendet werden.

Das Parsen war einst für den Grammatikunterricht in englischsprachigen Gesellschaften von wesentlicher Bedeutung und wurde allgemein als grundlegend für den Gebrauch und das Verständnis der Schriftsprache angesehen. Die allgemeine Vermittlung dieser Techniken ist jedoch nicht mehr relevant.

Psycholinguistik

Beim Studium der Psycholinguistik beinhaltet das Parsen die Zuordnung von Wörtern zu Kategorien (auch als Bildung ontologischer Perspektiven bezeichnet). Zur Analyse gehört auch die Bewertung der Bedeutung eines Satzes gemäß den Syntaxregeln, die aus Abzügen aus jedem Wort im Satz gezogen werden - dies wird als Konnotation bezeichnet . Dies geschieht normalerweise, wenn Wörter gehört oder gelesen werden. Daher konstruieren psycholinguistische Parsing-Modelle während der Satzverarbeitung eine Interpretation, die normalerweise als partielle syntaktische Struktur ausgedrückt wird. Die Erzeugung von anfänglich falschen Strukturen erfolgt bei der Interpretation syntaktischer Mehrdeutigkeitssätze.

Anmerkungen und Referenzen

Anmerkungen

Verweise

  1. „  Grammatische Begriffe: Parsing-Definition und Beispiele  “ auf ThoughtCo (abgerufen am 8. April 2019 ) .
  2. (en) "Parsing" , in Wikipedia ,8. April 2019( online lesen ).

Anhänge

Literaturverzeichnis

Zum Thema passende Artikel

Externe Links