[ Inhalt ] [ Index ]

Next: Bottom-up-Analyse Up: Syntaktische Analyse Previous: BNF und EBNF

Top-down-Analyse

Bei der Topdown-Analyse wird ausgehend von der Wurzel des Ableitungsbaums eine Ableitungsfolge gesucht. Wenn man bei diesem Verfahren ohne Backtracking auskommen will, ist intuitiv klar, daß man in jedem Ableitungsschritt eindeutig entscheiden können muß, welche Produktion als nächste angewendet werden soll. Um diese Auswahl zu erleichtern, betrachtet man nicht nur das aktuelle Eingabesymbol, sondern man schaut (maximal k Symbole) voraus.

LL(k)-Grammatiken

Definition:
Eine kontexfreie Grammatik G = (V,T,P,S) heißt LL(k)-Grammatik , wenn ein Ableitungsschritt eindeutig durch k Symbole der Eingabe (lookahead ) bestimmt ist.

Die folgende Grammatik ist LL(1):

Beginnt ein Wort mit a wird die erste, sonst die zweite Alternative für S gewählt. Soll B abgeleitet werden, kann man auch immer am ersten Zeichen entscheiden, welche Produktion angewendet werden muß.

Das funktioniert bei der folgenden Grammatik nicht:

Wenn man einen Satz ableiten will, der mit ccc beginnt, kann man mit dem ersten c nicht entscheiden, ob oder angewendet werden soll.

Es gelten die folgenden Sätze:

Satz:
LL(k)-Grammatiken sind eindeutig.

Satz:
Es gibt kontextfreie Grammatiken, die für kein k LL(k) sind.

Satz:
Es gibt kontextfreie Grammatiken, die zwar LL(k) aber nicht LL(k-1) sind.

Satz:
Es ist entscheidbar, ob eine Grammatik für ein festes k LL(k) ist.

Satz:
Es ist nicht entscheidbar, ob für eine Grammatik ein k existiert, so daß die Grammatik LL(k) ist.

Rekursiver Abstieg

Wenn wir den regulären Ausdruck: (a+b)(a+b+c+d)* betrachten, kann man sehr einfach eine Funktion angeben, die ein Wort dieser Sprache akzeptiert:

int Parse()
{
 if ((sy == `a`) || (sy == 'b')) Nextsy();
 else return ERROR;
 while ((sy >= 'a') && (sy <= 'd')) Nextsy();
 if (sy != EOF)
  return ERROR;
 return ACCEPT;
}

Eine kontextfreie Sprache, deren Grammatik die LL(1)-Eigenschaft hat, kann man nun ganz ähnlich analysieren. Dazu ein

Beispiel:

int S()
{
 A();
 if (sy == EOF) return ACCEPT;
 else return ERROR;
}

void A()
{
 if (sy == 'a')
 {
  Nextsy(); B(); A(); 
 }
 else if (sy == 'b') Nextsy();
      else Error();
}

void B()
{
 if (sy == 'a') Nextsy();
 else if (sy == 'b')
      {
       Nextsy(); A(); B();
      }
      else Error();
}

Wir haben in diesem Beispiel für jede Variable der Grammatik, die in EBNF-Format vorliegen muß, eine Funktion geschrieben, die die Satzformen, die aus den zugehörigen rechten Seiten abgeleitet werden können, analysiert. Wenn terminale Symbole auftreten, werden diese mit den aktuellen Eingabesymbolen verglichen und überlesen. Variablen auf der rechten Seite der Produktion führen zu einem (möglicherweise rekursiven) Aufruf einer Analysefunktion.

Rekursiver Abstieg für arithmetische Ausdrücke

Produktionen von OBERON-0 für arithmetische Ausdrücke

Factor           = ident Selector | integer | 
                   ``(`` Expression ``)'' | ``~`` Factor.
Term             = Factor {(``*'' | ``DIV'' | 
                            ``MOD'' | ``&'') Factor}.
SimpleExpression = [``+'' | ``-''] Term 
                   {(``+'' | ``-'' | ``OR'') Term}.
Expression       = SimpleExpression
                   [(``='' | ``#'' | ``<'' | 
                     ``<='' | ``>'' | ``>='') 
                    SimpleExpression].

Analysefunktionen

void Expression(){
 int lsy;

 SimpleExpression();
 if ((nextsymbol >= eqsy) && (nextsymbol <= gesy))
 {
  lsy = nextsymbol;
  Insymbol();
  SimpleExpression();
 }
}

void SimpleExpression(){
 int lop;
 int sign = addop;

 if ((nextsymbol == addop) || (nextsymbol == subop)) 
 {sign = nextsymbol; Insymbol();}
 Term();
 while ((nextsymbol >= addop) && (nextsymbol <= subop))
 {
  lop = nextsymbol;
  Insymbol();
  Term();
 }
}

void Term(){
 int lop;
 
 Factor();
 while ((nextsymbol >= multop) || (nextsymbol <= andop))
 {
  lop = nextsymbol;
  Insymbol();
  Factor();
 }
}

void Factor(){
 if (nextsymbol == lpar)
 {Insymbol();
  Expression();
  if (nextsymbol == rpar)
  {Insymbol();}
  else Error(") expected");
 }
 else if (nextsymbol == integer)
 {Insymbol();}
 else if (nextsymbol == ident)
      {Insymbol(); Selector()}
      else if (nextsymbol == notsy)
           {Insymbol(); Factor();
           }
           else Error("Error in Factor\n"); 
}

int main(){
 Insymbol();
 while (nextsymbol)
 {
  Expression();
 };
 return 0;
}

Linksrekursionen

Eine Grammatik, die Produktionen der Form enthält, führt beim rekursiven Abstieg zu Problemen.

Beispiel:

Die naive Umsetzung führt zu folgendem Code:

void E()
{
 E();
 Insymbol(); // + Überlesen
 T();
}

Da dauert es nicht lange, bis der Laufzeitkeller überläuft!

Diese Linksrekursion kann man aber leicht beseitigen:

Das geht auch allgemein:

wird ersetzt durch:

Im Beispiel ist und A = E. Damit ergibt sich:

und

Die Linksrekursion ist beseitigt, falls sich nicht zu ableiten läßt. Die Sprache bleibt unverändert.

Linksfaktorisierung

Bei einer Produktion der Form

ist die Auswahl der richtigen Produktion erst nach Abarbeitung von möglich. Auch dieses Problem kann man lösen:

FIRST und FOLLOW

In diesem Abschnitt geht es um die Frage: wie entscheidet man, ob eine Grammatik LL(1) ist oder nicht.

Damit eine Grammatik diese Eigenschaft hat, muß ja sichergestellt sein, daß man mit einem Symbol Lookahead entscheiden kann, welche von zwei alternativen Produktionen gewählt werden soll. Falls die beiden Alternativen lauten, dann dürfen doch zunächst einmal die Zeichenketten, die aus bzw. abgeleitet werden können, nicht mit den gleichen terminalen Symbolen anfangen.

Die Funktion FIRST( ) berechnet nun gerade die Terminals, mit denen aus abgeleitete Satzformen beginnen.

Falls man Produktionen der Art hat, kann ein weiteres Problem auftreten. Wenn man aus das leere Wort ableiten kann, hängt die Entscheidung, welche Produktion gewählt werden soll, davon ab, ob FIRST( ) und die Menge der terminalen Symbole, die auf A folgen können, disjunkt sind. In diesem Fall kann man eindeutig entscheiden, ob zu abgeleitet, oder aber gewählt wurde. Die Symbole, die in Satzformen auf A folgen können, werden mit FOLLOW(A) berechnet.

FIRST und FOLLOW: Formale Definition

Um festzustellen, ob eine kontextfreie Grammatik G = (V,T,P,S) die LL(1)-Eigenschaft besitzt, definieren wir zwei Mengen:

Definition:
Sei . Dann ist
FIRST( )

FIRST enthält also die terminalen Symbole, mit denen Ableitungen aus beginnen können.

Definition:
Sei . Dann ist
FOLLOW(A)

FOLLOW beinhaltet also die terminalen Symbole, die in Satzformen
direkt auf A folgen können.

Satz:
Eine Grammatik ist genau dann LL(1), wenn für je zwei Produktionen gilt:
1. FIRST( ) FIRST( ) =
2. FIRST( ) FIRST( ) FOLLOW(A)

Konstruktion von FIRST

FIRST(X) , d.h.
ist X ein Terminal, dann ist X in FIRST(X)
und
FIRST(X) = FIRST(X) , d.h.
wenn die rechte Seite einer Regel für X mit einem Terminal a beginnt, so muß a in FIRST(X) enthalten sein.
und FIRST(X) = FIRST(X) , d.h
wenn das leere Wort aus X abgeleitet werden kann, ist in FIRST(X).
FIRST(X) = FIRST(X) FIRST( )
Wenn FIRST(X) = FIRST(X)
Dies ist der etwas schwierigere Fall. Die Regel bedeutet einfach, wenn eine Produktion existiert, und aus ist ableitbar, so muß man FIRST( ) zu FIRST(X) hinzufügen. Falls nun aber auch auf führt, so muß FIRST( ) zu FIRST(X) hinzugefügt werden (jeweils ohne ). Nur wenn alle auf führen, muß zu FIRST(X) getan werden.

FIRST( ) berechnet man nun so:

Alle nicht- -Symbole aus FIRST( ) gehören zu FIRST( ).

Ist FIRST( ), dann gehören auch die nicht- -Symbole aus FIRST( ) zu FIRST( ).

Ist FIRST( ), dann gehören auch die nicht- -Symbole aus FIRST( ) zu FIRST( )

u.s.w.

Ist FIRST( ) , dann gehört auch zu FIRST( ).

Konstruktion von FOLLOW

Um für FOLLOW(A) zu berechnen, wende man die folgenden drei Regeln an, bis sich keine Änderung mehr ergibt:

$, ein spezielles Endsymbol ist in FOLLOW(S)
FOLLOW(B) enthält außer alles aus FIRST( ).
oder
und FIRST( ) enthält ,
dann ist alles aus FOLLOW(A) in FOLLOW(B).

Parsingtabellen

Mit FIRST und FOLLOW läßt sich auch ein tabellengesteuerter Parser für eine Grammatik G = (V,T,P,S) konstruieren. Das wird man zwar in der Regel nicht manuell machen - aber man kann an diesem Algorithmus recht gut sehen, wie ein Parsergenerator prinzipiell funktioniert. Beim rekursiven Abstieg wird letztlich genau das gleiche Verfahren angewendet - nur nimmt einem das Laufzeitsystem die explizite Verwaltung des Parserstacks ab.

Zunächst wird eine Matrix M konstruiert, die den Parser steuert. M hat die folgende Form:

für jedes existiert eine Zeile
für jedes existiert eine Spalte
M[v,t] wird mit initialisiert
für alle Regeln
2. wenn
  für alle
alle undefinierten Einträge werden auf error gesetzt.

Wenn es jetzt keine Mehrfacheinträge gibt, kann man für jede Kombination von Symbolen aus entscheiden, welche Produktion angewendet werden soll, und es gilt der

Satz:

Eine Grammatik ist LL(1), wenn die zugehörige Parsingtabelle keine Mehrfacheinträge enthält.

Beispiel:

Wir betrachten wieder die übliche Grammatik für arithmetische Ausdrücke:

FOLLOW brauchen wir nicht zu berechnen, da keine -Produktionen existieren.

Dann hat M die Form:

M id + * ( ) $

E

T

F id (E)

Offenbar ist diese Grammatik nicht LL(1).

Mit dem Verfahren von Seite können wir die Grammatik aber leicht umformen und erhalten:

Wir berechnen FIRST und FOLLOW:

FIRST FOLLOW

E id, ( $, )

E' +, $, )

T id, ( +, $, )

T' *, +, $, )

F id, ( *, +, $, )

Somit erhalten wir für die Parsingtabelle M:

M id + * ( ) $

E TE' TE'

E' +TE'

T FT' FT'

T' *FT'

F id (E)

Der Parsingalgorithmus:

G = (V,T,P,S) und Parsingtabelle

, terminiert mit $

TopOfStack = S

actsy = 0; 
while (actsy < strlen(s))
{
 if (``TOS aus V'')
 {
  if (M[TOS, s[actsy]] != ERROR)
  {``POP(); PUSH(M[TOS,s[actsy]]);}
  else EXIT;
 }
 else // TOS aus T
 {
  if (TOS == s[actsy++]) POP();
  else EXIT;
 }
 if (``stack leer'' && (actsy == strlen(s)))
  ACCEPT;
 else EXIT;
}

Fehlerbehandlung

So wie wir die Syntaxanalyse bisher betrachtet haben, bricht der Parser seine Arbeit beim ersten Syntaxfehler ab. Das ist natürlich in der Praxis kein angemessenes Vorgehen. Vielmehr sollen ja möglichst viele Fehler aufgedeckt und sinnvolle Fehlermeldungen generiert werden.

Dies ist aber häufig gar nicht so einfach, denn um nach einem Fehler weitermachen zu können, müssen gewisse Annahmen über den Programmtext getroffen werden, damit Teile eingefügt oder überlesen werden können.

Für den Compiler besteht zwischen einem fehlenden Semikolon und einem fehlenden arithmetischen Operator kein prinzipieller Unterschied. Ein menschlicher Programmierer wird aber wesentlich seltener ein Pluszeichen als ein Semikolon vergessen.

Ein erfahrener Programmierer wird auch ganz andere Fehler machen als ein Anfänger bei seinen ersten C++-Gehversuchen. Daher ist es kaum möglich, allgemeingültige Regeln für die Fehlerbehandlung aufzustellen. Wir werden aber einige nützliche Heuristiken kennenlernen.

Qualitätskriterien für die Fehlerbehandlung (Wirth )

Möglichst viele Fehler in einem Durchlauf erkennen
Analyse fehlerfreier Texte nicht bremsen
Parser nicht unverhältnismäßig aufblähen

Offenbar spielt die konkrete Syntax hier eine große Rolle. Je einfacher die Sprachstruktur, desto besser die Möglichkeiten der Fehlerbehandlung.

Man kann prinzipiell zwei Fehlerkategorien unterscheiden:

1. Fehlende Symbole: a := b * (x + y;
Stellt der Parser die fehlende Klammer fest, wird eine Meldung erzeugt und weiter analysiert. Unangenehm ist aber der Fall, daß das Fehlen von Symbolen zu spät bemerkt wird. Dann kann man oft nicht mehr entscheiden, ob ein Symbol fehlt, oder ob ein Symbol zuviel vorhanden ist:
a := z * b * (x + y));

2. Falsche Symbole: a = b statt a := b
Bei Verwendung eines falschen Symbols wird das falsche Symbol überlesen und weitergemacht. Eventuell muß man aber Folgesymbole bis zu einer Synchronisationsstelle überlesen.

Im zweiten Fall kann die konkrete Syntax der Sprache helfen. So fangen in OBERON Deklarationen stets mit CONST, TYPE, VAR oder
PROCEDURE an, Anweisungen mit IF, WHILE oder einem Identifikator. Bei Syntaxfehlern kann man daher bis zu diesen Symbolen ''vorspulen'' und die Analyse an der Synchronisationsstelle fortsetzen.

Wir geben daher jeder Analysefunktion zwei Parameter mit: der erste beschreibt die Menge der gültigen Anfangssymbole eines Konstrukts. So erhält die Funktion Statement die Symbole ident, whilesy, ifsy. Diese Symbole entsprechen FIRST(Statement).

Der zweite Parameter beschreibt die Symbole, die zur Synchronisation dienen sollen und deshalb keinesfalls überlesen werden dürfen. Dies sind die Symbole, die in Satzformen unmittelbar hinter dem aktuellen Nonterminal auftreten können: die FOLLOW-Menge.

In einer Programmiersprache wie Pascal lassen sich diese Mengen direkt abbilden. Wir betrachten einen Ausschnitt aus einem PASCAL-Compiler

typebeginsys := [add,sub,intconst,realconst,
                 charconst,ident,stringsy, 
                 lparent,arrow,packedsy,
                 arraysy,recordsy,setsy,filesy];
statbeginsys := [beginsy,gotosy,ifsy,whilesy,
                 repeatsy,loopsy,
                 forsy,withsy,casesy];
blockbeginsys:= [labelsy,constsy,typesy,varsy,
                 valuesy,initprocsy,
                 funcsy,procsy];
factorbegsys := [intconst,realconst,stringconst,
                 charconst,ident,
                 lparent,lbrack,notsy,nilsy];

In OBERON-0 erhalten wir

typebeginsys := [ident, arraysy, recordsy];
statbeginsys := [beginsy, ifsy, whilesy, ident];
blockbeginsys:= [constsy, typesy, varsy, proceduresy];
factorbegsys := [integer, ident, lparent, notsy];

In C++ muß man etwas mehr Arbeit aufwenden, um die Mengen zu emulieren. Eine Möglichkeit ist eine geschickte Anordnung der Symbole, so daß man Bereiche testen kann:

if ((sy >= ifsy) && (sy <= whilesy))

Eleganter ist die Verwendung einer Containerklasse für Symbole, die dann auch die üblichen Mengenoperationen zur Verfügung stellt. Eine Testfunktion könnte dann etwa so aussehen:

void test(setofsys *s1, setofsys *s2, errorrange errnr)

/*tests if sy in s1, gives errormessage if no
  and skips until sy in s1+s2 */

{
 if (!s1->isMember(sy))
 {
  error(errnr);
  s1* = s1* + s2*;
  while(!s1->isMember(sy) || cin.eof()) insymbol;
 }  
}

Zum Abschluß ein Ausschnitt aus der Analysefunktion für Statement aus einem Pascal-Compiler:

            forsy:
    BEGIN
     insymbol;
     IF sy = ident
     THEN insymbol
     ELSE
     test([],fsys + [becomes,tosy,downtosy,dosy],5);
     IF sy = becomes
     THEN
      BEGIN
       insymbol;
       expression(fsys + [tosy,downtosy,dosy])
      END
     ELSE test([],fsys + [tosy,downtosy,dosy],58);
     IF (sy = tosy) OR (sy = downtosy)
     THEN
      BEGIN
       insymbol;
       expression(fsys + [dosy])
      END
     ELSE test([],fsys + [dosy],59);
     testsy(dosy,54);
     statement(fsys,statendsys)
    END;

Die Qualität der Fehlerbehandlung läßt sich weiter verbessern, wenn man die Analysefunktionen etwas flexibler hält, als von der Syntax vorgegeben.

So müssen in OBERON-0 z.B. die Deklarationen in einer festen Reihenfolge (CONST, TYPE, VAR, PROCEDURE) erfolgen:

if (sy == constsy) ...
if (sy == typesy) ...
if (sy == varsy) ...
while (sy == proceduresy) ...

Programme mit Deklarationen lassen sich besser analysieren, wenn man die folgende Konstruktion benutzt:

while ((sy >= constsy) && (sy <= proceduresy))
{
 if (sy == constsy) ...
 if (sy == typesy) ...
 if (sy == varsy) ...
 while (sy == proceduresy) ...
 if ((sy >= constsy) && (sy <= proceduresy))
  error(``Falsche Deklarationsreihenfolge'');
}

Auf diese Weise werden die Deklarationen trotz falscher Reihung vollständig geparst.

Next: Bottom-up-Analyse Up: Syntaktische Analyse Previous: BNF und EBNF

Prof. Dr. Reinhard Völler

	FIRST	FOLLOW
E	id, (	$, )
E'	+,	$, )
T	id, (	+, $, )
T'	*,	+, $, )
F	id, (	*, +, $, )