Satzanalyse

Die Aufgabe eines Übersetzers oder Compilers ist normalerweise nicht die Erzeugung oder Herleitung, sondern die Erkennung eines Satzes und seiner Struktur. Dies bedeutet, dass die Schritte der Erzeugung beim Lesen eines Satzes als Schritte der Erkennung nachvollzogen werden müssen. Dies ist im allgemeinen eine komplizierte, und in vielen Fällen sogar eine unmögliche Aufgabe. Ihre Komplexität hängt unmittelbar von der Art der Produktionen ab, die die Syntax bestimmen. Zahlreiche Erkennungs-Algorithmen für verschiedene Klassen von Sprachen unterschiedlicher struktureller Komplexität sind bekannt Ihre Effektivität hängt direkt von ihrer Mächtigkeit ab: je allgemeiner sie verwendbar sind, umso weniger Effizienz kann erwartet werden. Unser Ziel hier ist jedoch lediglich die Entwicklung einer Methodik, relativ einfach Sprachen zu erkennen, dies jedoch mit einer Effizienz, wie sie von der Praxis gefordert wird. Die Zeit, die gebraucht wird, um einen Satz zu erkennen, darf demnach höchstens proportional zu seiner Länge anwachsen. Anstatt einen möglichst allgemeinen Erkennungs-Algorithmus, genannt Parser, zu finden, gehen wir in umgekehrter Richtung vor: Wir postulieren einen einfachen Algorithmus und bestimmen danach die Klasse der Sprachen, die er verarbeiten kann.