Grammatik anbringen

Eine Affix-Grammatik ist eine Art formale Grammatik, die zur Beschreibung der Syntax von Sprachen verwendet wird und von der Beschreibung natürlicher Sprachen inspiriert ist .

Tatsächlich handelt es sich um eine operative Variante der Grammatik von van Wijngaarden (2. Form).

Die Regeln einer Affix-Grammatik ähneln denen nicht-kontextueller Grammatiken , deren Begriffsnamen (oder Nicht-Terminals) parametrisiert würden. Diese als Affixe bezeichneten Parameter ermöglichen es, diese Begriffe mit Modalitäten zu versehen. Ihr Name ist von der Linguistik inspiriert, in der Modalitäten die Affixe (Präfixe, Infixe oder Suffixe) bestimmen können.

Wenn derselbe Zusatz in einer Regel mehrmals vorkommt, wird angenommen, dass sein Wert jedes Mal der gleiche ist.

Beispiel

Betrachten Sie die folgende nicht kontextbezogene Grammatik:

Satz → Prädikat Betreff "." Betreff → Name Prädikat → Verbobjekt Betreff → Name Name → Pierre | Verheiratet Name → Eltern | die Kinder Verb → mag | mögen Verb → Hilfe | Hilfe

Diese Grammatik beschreibt Sätze wie:

• Pierre liebt Kinder.
• Marie hilft Pierre.
• Kinder helfen Eltern.
• Eltern lieben Marie.

Mit mehr Substantiven , mehr Verben , mehr Konzepten, mehr Regeln können viele französische Sätze beschrieben werden, was vielversprechend aussieht.

Diese Art der Grammatik beschreibt jedoch auch viele Sätze wie:

• Eltern lieben Pierre. Pierre hilft Marie.

Während Französisch erfordert, dass Subjekt und Verb in der Anzahl übereinstimmen.

Eine angehängte Grammatik drückt es folgendermaßen aus:

Hyperregeln: Satz → Betreff + Nummer Prädikat + Nummer "." Betreff + Nummer → Name + Nummer Prädikat + Nummer → Verb + Nummer Objekt Betreff → Name + Nummer Nom + Singular → Pierre | Verheiratet Name + Plural → die Eltern | die Kinder Verb + Singular → Hilfe | Gefällt mir Verb + Plural → Hilfe | Gefällt mir Metarule: Nummer → Singular | Plural.

Indem diese Grammatik in ihrer ersten Regel die Ausrichtung der Anzahl des Subjekts und des Prädikats (tatsächlich seines einzigen Verbs) auferlegt, hinterlässt sie nur korrekte Sätze, obwohl wir das sagen können

• Jean liebt Jean.

sollte stattdessen geschrieben werden

• Jean liebt sich.

Dies könnte auch mit Hilfe von Affixen behandelt werden, abhängig von den verfügbaren Mitteln, um die Beziehungen zwischen Affixen zu definieren.

Arten von Affix-Grammatiken

Im einfachsten Fall können die Affixe nur eine endliche Anzahl von Werten annehmen, und diese Werte können nur gleich oder unterschiedlich sein. In diesem Fall machen die Affixe die nicht kontextuellen Grammatiken kompakter, ohne ihre Leistung zu erhöhen (Klasse 2 von N. Chomsky ).

Wir können auch zulassen, dass die Affixe beliebige Zeichenfolgen als Werte verwenden und ihre Verkettung zulassen , wobei die zulässigen Werte für die Affixe durch eine bestimmte nicht kontextbezogene Grammatik festgelegt werden , die als Affix-Grammatiken bezeichnet wird . Wir sprechen dann von 2-Level- Grammatiken oder vW2-Grammatiken. Diese Art von Grammatik wurde in den Berichten zur Definition der Programmiersprache Algol 68 verwendet .

Die Regeln , die Konzepte definieren , werden dann genannt Konzept Regeln oder hyperrules  : sie sind allgemeine Regeln.

Die Regeln, die die Affixe oder Regeln für Affixe definieren, spielen die Rolle von Metarulen: Sie organisieren die Affixe oder Modalitäten und skizzieren eine Theorie der beschriebenen Sprache.

Für das obige Beispiel würden wir also nehmen:

Nummer: Singular | Plural-

Das Erweitern einer Affix-Regel multipliziert die Möglichkeiten, zum Beispiel mit:

Nummer: Singular | Duell | Plural- Modus: indikativ | bedingt | Konjunktiv | Imperativ | Partizip | Infinitiv

M. Sintzoff und CHA Koster haben gezeigt, dass vW2-Grammatiken und Affix-Grammatiken die Beschreibung von Sprachen der Klasse 0 ermöglichen. Obwohl dies viele unentscheidbare Fragen aufwirft, haben Cleaveland und Uzgalis die konkrete Kraft dieser Formalismen für Programmiersprachen gezeigt Sie können die Syntax, die statische Semantik (Konsistenzprüfung) und die dynamische Semantik beschreiben.

Erweiterte Affix-Grammatiken (EAG) und endliche gitterwertige Affix-Grammatiken (AGFL) sind Varianten, mit denen der beste Kompromiss gefunden werden soll zwischen:

• die beschreibende Kraft formaler oder natürlicher Sprachen,
• die Betriebskapazität, die sich aus dem Prinzip ergibt, dass Peter Lucas jede formale Grammatik als algorithmische Notation des Analysators der beschriebenen Sprache wahrnimmt.

Programmieren mit Affix-Grammatiken

Über die Formalisierung von Sprachen oder Sprachen hinaus basiert die Anpassung von Affix-Grammatiken im Hinblick auf die grammatikalische Programmierung , die Grundlage vieler Werkzeuge, auf drei Punkten:

• Die Regeln von Konzepten (oder Hyperregeln) werden in ausführbaren Spezifikationen verarbeitet  .
• Die Affix-Regeln werden als Typdeklarationen verarbeitet, die diese ausführbaren Spezifikationen einschränken.
• Bestimmte Affix-Werte müssen durch Ablesen oder Berechnen ermittelt oder schriftlich ausgenutzt werden. Zu diesem Zweck werden Codefragmente als rechtes Element einiger Regeln angezeigt, um Lese-, Schreib- und Rechenprimitive bereitzustellen.

Darstellung von Affixen

Es entwickelte sich zunächst unter zwei Gesichtspunkten:

• Jedes Affix ist eine Zeichenfolge (aber wir riskieren, sie analysieren zu müssen).
• Bei jedem Affix ist die Darstellung in der Support-Sprache festgelegt, wobei das Risiko von Inkonsistenzen besteht (CDL2, LET).

Die Entwicklung des Feldes hat weniger problematische Darstellungen begünstigt:

• AGFL entspricht dem einfachsten Fall (endliche Anzahl von Befestigungswerten), wobei die Gitter Effizienz ermöglichen, indem verschiedene Werte "parallel" behandelt werden;
• EAG verwendet Zeichenfolgen, Ganzzahlen oder Tupel. Die Affix-Regeln sind nicht obligatorisch. Der Standardwert ist "string".
• CDL3, StarLet, LET + verwenden Bäume, Ganzzahlen oder Zeichenfolgen gemäß den Affix-Regeln.

Modage anbringen

Die Ausrichtung der Parameterpassagen schafft andere Varianten: Es kann sein:

• optional: EAG;
• angegeben und verifiziert: CDLs und LETs.

Arbeitsplätze

Die Umsetzung dieser Ideen ergab:

• die CDL-Sprache (Compiler Design Language) und ihre Nachfolger (CDL2, CDL3 ... dann der AGFL-Workshop, der ab den 1970er Jahren an der Universität Nijmegen (NL) entwickelt wurde,
• die LET-Sprache (Writing Language for Translators) und ihre Nachfolger StarLET und LET +, entwickelt ab 1976 von J. Beney et al. an der INSA Lyon .

Diese Sprachen und ihre Umgebungen wurden ursprünglich entwickelt, um die Erstellung von Compilern zu erleichtern. Sie haben zu anderen Anwendungen geführt, z. B. zur Textbearbeitung, zur automatischen Analyse von AFP-Versendungen, zur automatischen Klassifizierung von Dokumenten und in einem anderen Genre zum interaktiven Design verschiedener Anzeigen Hoc- Sprachen durch skalierbares Mock-up / Prototyping ihrer Compiler.

Hinweis

Obwohl dieser Formalismus im Prinzip in der Nähe von Attributgrammatiken , Metamorphosegrammatiken oder DCGs liegt, erleichtern die Unterscheidung zwischen notwendigem Begriff und möglichem Begriff und die Tatsache, dass die Anhänge immer typisiert und häufig moderiert werden, die Erkennung von Fehlern und Inkonsistenzen in großen Anwendungen erheblich.

Anmerkungen

1. bereits von CHA Koster besprochen in: CHA Koster & L. Meertens. Basic English, eine generative Grammatik für einen Teil des Englischen . Technischer Bericht, Euratom Seminar Machine en Talen , Univ. von Amsterdam, 1962.
2. van Wijngaarden, Mailloux, Peck, Koster, Sintzoff, Lambert, Meertens, Fisker: Überarbeiteter Bericht über die algorithmische Sprache ALGOL 68 , 1975, Acta Informatica , 5: 1-236
3. Sintzoff, M., 1967 Existenz der van Wijngaarden-Syntax für jede rekursiv aufzählbare Menge , Annals of the Scientific Society of Brussels 2, 115-118
4. Cleveland & Uzgalis "Grammatiken für Programmiersprachen", 1977 Computer Science Library, Elsevier.
5. siehe CHA Koster, 1991, Grammatiken für natürliche Sprachen anbringen in: Attributgrammatiken
6. bestätigt von Cleveland & Uzgalis, op. cit.
7. Die Anzahl wird minimiert, da sie bei Bedarf auch eine Schwachstelle bei der Konsistenzprüfung darstellen.
8. Beney J., Präsentation der STARLET / GL-Sprache , 1989 rev. 2001
9. wie ein PL1 / C-Compiler für Kontrolldaten Frankreich: Maranzana M., Martin JF, Frécon L., 1990, Un Traducteur de PL1 / Multics gegen C / VE , TSI, Band 9, Nr. 5, S. 399-42. (Quelle: 24.000 LET-Zeilen; Produkt-Compiler: 94.000 undokumentierte C-Zeilen).
10. Arbeiten für Englisch, Niederländisch, Latein, Französisch, Russisch und Arabisch
11. Colmerauer A., ​​1975, Die Grammatiken der Metamorphose , Artificial Intelligence Group, Fakultät für Naturwissenschaften von Luminy, Universität Aix-Marseille II
12. Pereira F., Warren D., 1980, Definite-Klausel-Grammatiken für die Sprachanalyse - Ein Überblick über den Formalismus und ein Vergleich mit Augmented Transition Networks . Künstliche Intelligenz Nr. 13, p.  231-278

Literaturverzeichnis

Basen

• CHA Koster, 1970, Grammatik anbringen , In: Tagungsband der IFIP-Konferenz zur Implementierung von ALGOL 68, München, Nordholland Publ. No. Cy.
• CHA Koster. 1991, Grammatiken für natürliche Sprachen anbringen . In: Attributgrammatiken, Anwendungen und Systeme, Internationale Sommerschule SAGA, Prag, Tschechoslowakei. Lecture Notes in Computer Science, Band 545. Springer-Verlag.
• CHA Koster. 1991, Grammatiken für Programmiersprachen anbringen . In: Attributgrammatiken, Sammlung oben.
• CHAKoster, J. Beney, 1991, An der Grenze zwischen Grammatik und Programmen , 3. Internationales Symposium PLILP, Passau, Deutschland,August 1991Lecture Notes in Computer Science n o  528, Springer-Verlag 1991
• M. Sutter, 2001, Informelle Einführung in die Extended Affix Grammars formalim und deren Compiler .

Metakompilierung

• J. Beney, L. Frécon, 1980, Sprache und Schreibsystem von Übersetzern , RAIRO Informatique , Band 14, n o  4, p.  379-394
• J. Beney, JFBoulicaut, Von grammatikalischen Spezifikationen bis zur Logikprogrammierung, der Starlet-Kompromiss , Bigre + Globule n 45,Oktober 1985, p.  81-86
• JFBoulicaut, J. Beney, 1988, Meta-Kompilation und Programmierung, methodische Regeln , die den Aufbau von Programmen zu unterstützen , Software Engineering und Expertensystemen n o  11, 1988, p.  36-48
• J. Beney, JFBoulicaut, 1990, STARLET: ein Affix-basierten Compiler Compiler als logische Programmiersystem entworfen , 3. Internationaler Workshop zu Compiler Compiler, CC'90, Schwerin (DDR), Lecture Notes in Computer Science n o  477, p.  71-85 , Springer-Verlag 1990
• CHA Koster, J. Beney, 1991 rev. 1993, CDL3 Lehrbuch , Interner Bericht der Katholischen Universität Nimwegen, 120 Seiten,
• J.-F. Boulicaut, J. Beney, Übersetzer, der in einem breiten Spektrum schreibt . In: P. Fritzon (Hrsg.): Proceedings of the poster session, 5. Internationale Konferenz über Compilerbau CC'94, Edinburgh, 7.-9. April 1994, p.  11-20

Zusammenstellung und Sprachgestaltung

• Maranzana M., Martin JF, Frécon L., Ein Übersetzer von PL1 / Multics nach C / VE , TSI, vol. 9, 1990, n o  5, p.  399-422
• Sidhoum H., Babout M., Frécon L., 1990, Ampère2, eine Programmiersprache für Physik , The European Journal of Physics, vol. 11, p.  163-171

Sprachen

• De Brito M., 1991, Realisierung eines morphosyntaktischen Analysators zur Erkennung der Nominalphrase: Verwendung angehängter Grammatiken , Dissertation Universität Lyon, ENSSIB.
• E. Farkas, CHA Koster, P. Köves und M. Naszodi, 1991, Auf dem Weg zu einer Affix-Grammatik für die ungarische Sprache . In: A. György (Hrsg.), Proceedings CIS'91 Konferenz über intelligente Systeme, John von Neumann Gesellschaft für Informatik, Budapest, p.  233-246 .
• CHA Koster und R. Willems. Auf dem Weg zu einer Affix-Grammatik für Türkisch . In: M. Baray und B. Ozguc (Hrsg.), Computer- und Informationswissenschaft VI, Elsevier, Amsterdam 1991, pag. 1067-1076.
• E. Oltmans. 1994 AMAZON in AGFL. Een contextvrije herschrijfgrammatica voor de structurele Komponente van het AMAZON / CASUS-System, beschreven in het AGFL-Formalismus . Masterarbeit (auf Niederländisch, 177 Seiten). Universität Nimwegen. (Zusammenfassung in Englisch; Entwicklung einer breiten niederländischen Grammatik).

Automatische Dokumentation

• Maria Paula Santalla del Rio, 2002, Eine formale Grammatik des Spanischen für die Analyse auf Phrasenebene , die auf das Abrufen von Informationen angewendet wird , Lalia, 14, Reihe Maior, Universität Santiago de Compostela, Santiago de Compostela.
• CHA Koster und CPA Tiberius, 1997, AGFL-Grammatiken zum Abrufen von Volltextinformationen . In: A. Ralli et al. (Hrsg.), Working Papers in Natural Language Processing, Ekdosis Diavlos, Athen, 1997, p.  139-154 .
• CHA Koster, J. Beney, S. Verberne und M. Vogel, 2011, Phrasenbasierte Dokumentenkategorisierung , In Current Challenges in Patent Information Retrieval, Springer, The Information Retrieval Series, Vol. 3, No. 29, Teil 4, p.  263-286 .
• CHA Koster, M. Seutter, J. Beney, 2003, Mehrfachklassifizierung von Patentanmeldungen mit Winnow, Proceedings PSI 2003, Springer LNCS Nr. 2890, 2003, p.  545-554 .
• J.Beney, CHA Koster 2003 überwacht Patentklassifikation: ein Testspiel mit dem realen Fall , Proceedings of the XXI th Congress Inforsid, p.  50-59 .
• CHA Koster, M. Seutter & J. Beney, 2001, Klassifizieren von Patentanmeldungen mit Winnow , Proceedings Benelear, p.  19-26 .

Siehe auch

• Formale Grammatik
• Van Wijngaardens Grammatiken
• Compiler Compiler
• Grammatik zugeschrieben
• (en) Bringen Sie die Grammatik über einem endlichen Gitter an
• (de) Erweiterte Affix-Grammatik
• (en) Van Wijngaarden-Grammatik
• (de) „  Einige Veröffentlichungen über Affix-Grammatiken, AGFL und das AGFL-System  “ zum AGFL-Projekt (Affix-Grammatiken über ein endliches Gitter)