Parser für Grammatiken

[jochen (Gast)]

Hallo, ich bin grade dran, mir die Funktionsweise von einem Parser für 
Grammatiken zu erarbeiten jedoch finde ich keine Beschreibung, durch die 
ich es verstehe. Meine Original Folien habe ich beigefügt, in google 
kann ich auch nichts brauchbares finden.

Als Beispiel habe ich mir die Grammatik

G = ({S,A} , {a,b} {S-> a, S->aA, A-> bS},S) ausgedacht.

Verstehe ich das richtig, wenn ich einen Parser für diese Grammatik 
schreibe, schreibe ich ein Programm, dass eine Zeichenfolge einliest und 
dann ausgibt, wie diese Zeichenfolge durch die Grammatik erzeugt wird?

Wie funtkioniert sowas, das verstehe ich nicht.
Ich verstehe zwar noch den ersten Schritt in der Anleitung, dann hört es 
aber auf. Könntet ihr mir die zusammenhängende Idee in eigenen Worten 
erklären?

Danke :D

[jochen (Gast)]

hier die FOlie

[jochen (Gast)]

...oder könntet ihr mir das möglicherweise an einen Beispiel zeigen?

[Oops (Gast)]

Vielleicht könntest Du ein klein bischen erklären was an Deiner Folie Du 
nicht verstehst.
Die Folie suggeriert, das Du irgendwie mit dem Thema befasst bist,
also die Terminologie in etwa kennen solltest.

Auch werden solche Themen eher nach dem erlernen einer 
Programmiersprache aufgebracht. Ich nehme an, Du kannst programmieren?

Gruss
Oops

[jochen (Gast)]

Ja, in Java so etwas ;)
Also Rekursionen kenn ich schon, methoden und Klassen auch.  Auch wie 
eine Grammatik aufbebaut ist.
Nur ich verstehe nicht, was der Recursice Descent Parser macht.
Danke für die Nachfrage!

[Oops (Gast)]

Wenn ich mein eigenes Post so lese, dann wird vielleicht nicht klar, das 
ich nur wissen möchte was für Voraussetzungen Du hast. Will Dich auf 
keinen Fall abbügeln.

>ein Programm, dass eine Zeichenfolge einliest und
>dann ausgibt, wie diese Zeichenfolge durch die Grammatik erzeugt wird

Nicht zwangsläufig beides. Man fängt, wenn man das Konzept lernt, 
erstmal an ein Programm zu schreiben, das nur sagt ob ein Satz der 
Grammatik entspricht oder nicht.

Dann erweitert man das Programm so, das es einen Baum aus dem 
eingelesenen Satz baut, wobei die Knoten aus den Nicht-Terminalen und 
die Blätter aus den Terminalen bestehen.

In der Praxis interessiert einen aber im Ergebnis nicht wie der Baum der 
Sätze aussieht, d.h. wie diese Zeichenfolge durch die Grammatik erzeugt 
wird. Man konstruiert ihn zwar intern, aber nur als Zwischenschritt für 
eine Kompilation.


Gruss
Oops

[Oops (Gast)]

OK. Java.

"Recursive Descent" heisst auf Deutsch "rekursiver Abstieg".

Rekursion kennst Du ja schon.
Abstieg kommt hier zum Tragen, wenn die rechte Seite einer Produktion 
wiederum Nicht-Terminale enthält. Zu diesen wird dann "abgestiegen" umd 
den Teil der Grammatik zu erkennen, der durch sie beschrieben wird.
Man könnten eine Grammatik auch als Hierarchie betrachten. Z.B. liegt A 
bei der auf der "zweiten" Ebene, während S auf der ersten Ebene liegt.

Gruss
Oops

[Oops (Gast)]

Oops. So ist das nicht ganz vollständig.

Der Kernpunkt ist, das die rechte Seite wiederum ein Nicht-Terminal 
enthalten kann, das in "derselben" oder einer "höheren" Ebene liegt.
Wie in Deinem Beispiel bei A-> bS.

Gruss
Oops

[Oops (Gast)]

Etwas deutlicher wird es vielleicht wenn man die Grammatik umformuliert.

G = ({S} , {a,b} {S-> a, S->abS},S)

Man kann sie noch etwas günstiger formulieren.

G = {{S,A}, {a,b,EOF} {S->aA, A->ba|EOF},S}

indem man EOF (End of File) als Pseudo-Symbol mit aufnimmt.
Dann braucht man nämlich keinen Look-Ahead.

Gruss
Oops

[Oops (Gast)]

Oops. Schon wieder ein Fehler. Muss ins Bett. ;-)

Durch
G = {{S,A}, {a,b,EOF} {S->aA, A->ba|EOF},S}
können die Sätze nicht mehr aus endlosen "ab" mit abschliessendem "a" 
bestehen. Das sieht man auch daran, das keine Rekursion mehr in der 
Grammatik ist.

Es muss sein.
G = {{S,A}, {a,b,EOF} {S->aA, A->baS|EOF},S}

Der Vorteil dieser zweiten Formulierung nennt sich 
"Links-Eindeutigkeit".

Gruss
Oops

[yalu (Gast)]

Folgendes C-Programm liest eine Zeile von der Konsole und parst sie
nach der von dir angegebenen Grammatik. Als Ergebnis wird das geparste
Nonterminalsymbol und in Klammern die verwendete rechte Seite der
Produktionsregel angezeigt. Enthält die rechte Seite Nonterminal-
symbole, wird mit diesen ebenso verfahren.

Kann auf diese Weise die gesamte Eingabezeile (abgeschlossen durch ein
Newline '\n') verarbeitet werden, gehört die Eingabe zu der durch die
Grammatik definierten Sprache, und es wird 'ok' angezeigt, sonst
'Fehler'.

Beispiel: Für die Eingabe

  ababa

wird

  S(aA(bS(aA(bS(a)))))
  ok

ausgegeben.

#include <stdio.h>
#include <stdlib.h>

char last;

void next(void) {
  // Nächstes Zeichen der Eingabe lesen
  last = getchar();
}

void error(void) {
  printf("\nFehler\n");
  exit(0);
}

void parseA(void);

void parseS(void) {
  printf("S(");
  // Erstes Zeichen in S ist immer ein a, sonst Fehler.
  if(last != 'a')
    error();
  printf("a");
  next();
  // Entweder kommt jetzt das Ende (S->a) oder ein A (S->A)
  if(last != '\n')
    parseA();
  printf(")");
}

void parseA(void) {
  printf("A(");
  // Erstes Zeichen in A ist immer ein b, sonst Fehler.
  if(last != 'b')
    error();
  printf("b");
  next();
  // Dann folgt ein S.
  parseS();
  printf(")");
}

int main(void) {
  next();
  parseS();
  // Bisher kein Fehler? Dann ist alles ok.
  printf("\nok\n");
  return 0;
}

[yalu (Gast)]

Kleiner Fehler: Der Kommentar

  // Entweder kommt jetzt das Ende (S->a) oder ein A (S->A)

im geposteten Programm sollte natürlich heißen

  // Entweder kommt jetzt das Ende (S->a) oder ein A (S->aA)

[yalu (Gast)]

Hier ist übrigens noch ein kleines Beispiel mit etwas praktischerer
Bedeutung:

  Beitrag "Re: Weis jemand, wie man mathematische Ausdrücke in C++ aus"

Das C++Programm wertet arithmetische Ausdrücke, bestehend aus
Integerkonstanten, den Operatoren +, -, * und / sowie Klammern aus.
Es arbeitet ebenfalls nach dem Prinzip des rekursiven Abstiegs.

Die Grammatik in EBNF lautet:

  sum    = prod   { ( "+" | "-" ) prod   } ;
  prod   = factor { ( "*" | "/" ) factor } ;
  factor = "(" sum ")" | "-" factor | number ;
  number = digit { digit } ;
  digit  = "0" | "1" |"2" | "3" |"4" | "5" |"6" | "7" | "8" | "9" ;

sum ist das Startsymbol.

[jochen (Gast)]

Danke für die vielen Beiträge. Mien Problem ist die grundsätzliche 
Arbeitsweise. Wenn ich z.B. von der o.g. Grammatik die Eingabe

ababa mache,

was macht das Programm dann?
Wie bestimmt es den ABleitungsbaum, wie geht das Programm vor?
Wie genau kommt es darauf, dass die Eingabe in der Grammatik liegt, wie 
sind die Schritte von dem Programm?

Die Vorgehensweise ist mir leider nicht deutlich.

Danke...

[jochen (Gast)]

Die Grammatik war ja

G = ({S,A} , {a,b} {S-> a, S->aA, A-> bS},S)

und die EIngabe ababa.

Jetzt steht in der Folie

"Jedem Nichtterminal einer Grammatik wird eine Methode zugeordnet. Diese 
Methode prüft die rechte Seite der zum Nichtterminal gehörenden 
Porduktion"

heißt das ich habe hier zwei Methoden (S und A), die Methode S prüft a 
und ua. Die Methode A prüft bS ??? Was heißt "prüft" Was macht die 
Methode mit der Eingabe?

[jochen (Gast)]

Der Code, den wir benutzen, ist hier im ANhang. Ich erkenne gerade mal 
die Klassen für die Nicht Terminalsymblole. Aber, was passiert da ??

[c]
public class Parser {
  public char[] str; // zu parsende Zeichen
  public int pos; // aktuelle Position
  public Parser(String s) {
    str = s.toCharArray();
    pos = 0;
    // Aufruf mit Methode des Startsymbols
    if (O() && pos == str.length)
      System.out.println("Wort erkannt: " + s);
    else
      System.out.println("Wort nicht erkannt: " + s);
  }
  // O -> UO'
  public boolean O() {
    // erst U erkennnen
    if (!U()) return false;
    // dann O'
    return Os();
  }
  // O' -> '|' UO' | epsilon
  public boolean Os() {
    // epsilon, falls kein Zeichen mehr uebrig
    if (pos == str.length) return true;
    int tmp = pos;
    // erste Alternative:
    if (str[pos] == '|') { // Terminalzeichen testen
      pos ++; // Zeichen erkannt
      if (U()) { // rekursiv U erkennen
        if (Os()) { // rekursiv O' erkennen
          return true;
        }
      }
    }
    pos = tmp;// Bei Fehler zurueck zum aktuellen Zeichen:
    return true;// O' erkennen durch epsilon-Produktion:
  }
  // U -> BU'
  public boolean U() {
    // erst B erkennnen
    if (!B()) return false;
    // dann U'
    return Us();
  }
  // U' -> '&' BU' | epsilon
  public boolean Us() {
    // epsilon, falls kein Zeichen mehr uebrig
    if (pos == str.length) return true;
    int tmp = pos;
    // erste Alternative:
    if (str[pos] == '&') { // Terminalzeichen testen
      pos ++; // Zeichen erkannt
      if (B()) { // rekursiv B erkennen
        if (Us()) { // rekursiv U' erkennen
          return true;
        }
      }
    }
    pos = tmp;// Bei Fehler zurueck zum aktuellen Zeichen:
    return true;// U' erkennen durch epsilon-Produktion:
  }
  // B -> 't' | 'f'
  public boolean B() {
    // kein Zeichen mehr uebrig?
    if (pos == str.length) return false;
    if (str[pos] == 't') {
      pos ++; // Zeichen erkannt
      return true;
    }
    if (str[pos] == 'f') {
      pos ++;
      return true;
    }
    // anderes Zeichen nicht erlaubt:
    return false;
  }

  public static void main (String ... args) {
    // Mehrere Woerter mit dem Parser testen:
    String s = "t";
    new Parser(s);
    s = "t&f|t";
    new Parser(s);
    s = "t&f|";
    new Parser(s);
    s = "";
    new Parser(s);
  }
}


{/c]

[Gast (Gast)]

Ich habe auch mal einen Assembler geschrieben, mir hat dabei sehr das 
"Drachenbuch" von  Alfred V. Aho, Ravi Sethi und Jeffrey D. Ullman 
geholfen. Gibt es mittlerweile in 2. Auflage (2 Teile)...

[jochen (Gast)]

Jetzt mal eine ganz konkrete Frage zu dem Quelltext:

Bei der 1. Methode (// O -> UO') und bei der zweiten  ( // O' -> '|' UO' 
| epsilon) kommt jeweils das nicht Terminalsymbol UO' vor.
Wieso steht bei der Produktion  O -> UO' (1. Methode) eien if Abfrage 
mit !U return false bei der zweiten aber ohne das Ausrufezeichen und 
auch sonst der ganze Rest bezüglich UO' wird ganz anders abgehandelt.
Mein Ziel ist es gemäß diesem Quellcode für eine beliebeige Grammatik 
einen Parser zu programmieren ;)

// O -> UO'
  public boolean O() {
    // erst U erkennnen
    if (!U()) return false;
    // dann O'
    return Os();
  }
  // O' -> '|' UO' | epsilon
  public boolean Os() {
    // epsilon, falls kein Zeichen mehr uebrig
    if (pos == str.length) return true;
    int tmp = pos;
    // erste Alternative:
    if (str[pos] == '|') { // Terminalzeichen testen
      pos ++; // Zeichen erkannt
      if (U()) { // rekursiv U erkennen
        if (Os()) { // rekursiv O' erkennen
          return true;
        }
      }

[Unbekannter (Gast)]

> Ich verstehe zwar noch den ersten Schritt in der Anleitung, dann hört
> es aber auf. Könntet ihr mir die zusammenhängende Idee in eigenen
> Worten erklären?

Das ist ganz einfach:

Jede parse_xyz()-Funktion/Methode gibt zurück, ob sie erfolgreich war, 
oder nicht. So können sich die parse_xyz() gegenseitig rekursiv 
aufrufen. Effektiv  wird so einfach durch probiert, wie der Text geparst 
werden kann.


>  sum    = prod   { ( "+" | "-" ) prod   } ;
>  prod   = factor { ( "*" | "/" ) factor } ;
>  factor = "(" sum ")" | "-" factor | number ;
>  number = digit { digit } ;
>  digit  = "0" | "1" |"2" | "3" |"4" | "5" |"6" | "7" | "8" | "9" ;

Wird dann etwa (ganz grob):

bool parse_sum();
bool parse_literal(char);
bool parse_prod();
bool parse_factor();
...

bool parse_sum()
{
  if ( ! parse_prod() )
    return false;

  while ( (parse_literal('+') || parse_literal('-')) && parse_prod() )
    ;
}

bool parse_prod()
{
  if ( ! parse_factor() )
    return false;

  while ( (parse_literal('*') || parse_literal('/')) && parse_factor() )
    ;
}


bool parse_factor()
{
  if ( parse_literal('(') && parse_sum() && parse_literal(')') )
    return true;

  if ( parse_literal('-') && parse_factor() )
    return true;

  if ( parse_number() )
    return true;

  return false;
}

...

Das Prinzip sollte klar sein.

Natürlich müssen die parse_xyz() den Input-Stream verwalten, also bei 
ungültigen Parse-Versuchen den verbrauchten Input-Stream wieder zurück 
schreiben.

[jochen (Gast)]

Danke für deinen beitrag. Das Prinzip habe ich nun  hoffentlich 
verstanden.
Der Quellcode von meinem Beitrag um (.23 ist der Originale, so 
funktioniert er. Ich habe versucht, ihn umzuschreiben für die folgende 
Grammatik

B-> aB
B-> b

aber es funktioniert noch nicht. Was habe ich dort falsch gemacht ?

 public class Parser {
  public char[] str; // zu parsende Zeichen
  public int pos; // aktuelle Position
  public Parser(String s) {
    str = s.toCharArray();
    pos = 0;
    // Aufruf mit Methode des Startsymbols
    if (Bs() && pos == str.length)
      System.out.println("Wort erkannt: " + s);
    else
      System.out.println("Wort nicht erkannt: " + s);
  }
  // B -> aB
  
     
    public boolean Bs() {
      // epsilon, falls kein Zeichen mehr uebrig
      if (pos == str.length) return true;
      int tmp = pos;
      if (str[pos] == 'a') { // Terminalzeichen testen
        pos ++; // Zeichen erkannt
        if (B()) { // rekursiv B erkennen
           
        }
      }
      pos = tmp;// Bei Fehler zurueck zum aktuellen Zeichen:
      return true;// U' erkennen durch epsilon-Produktion:
    }
  
  
  // B -> b
  public boolean B() {
    // kein Zeichen mehr uebrig?
    if (pos == str.length) return false;
    if (str[pos] == 'b') {
      pos ++; // Zeichen erkannt
      return true;
    }
     
    // anderes Zeichen nicht erlaubt:
    return false;
  }

  public static void main (String ... args) {
    // Mehrere Woerter mit dem Parser testen:
    String s = "";
    new Parser(s);
    s = "ab";
    new Parser(s);
    s = "bb";
    new Parser(s);
    s = "b";
    new Parser(s);
  }
}

[Karl H. (kbuchegg)]

jochen wrote:
> Danke für die vielen Beiträge. Mien Problem ist die grundsätzliche
> Arbeitsweise. Wenn ich z.B. von der o.g. Grammatik die Eingabe
>
> ababa mache,
>
> was macht das Programm dann?
> Wie bestimmt es den ABleitungsbaum, wie geht das Programm vor?

Es bestimmt den Ableitungsbaum gar nicht.
Ein Parser versucht einfach, ob er die Eingabesequenz mit
der gegebenen Grammatik durchlaufen kann.

Wenn deine Grammatik fordert, dass als nächstes das terminale
Symbol 'b' kommen muss, dann sieht der Parser einfach nach
ob das in der Eingabesequenz tatsächlich so ist. Ist es so,
dann ist dieses Symbol abgehakt und das nächste kommt dran.
Wieder versucht der Parser, ausgehend von der Stelle an der
er sich in der Grammatik gerade befindet etwas zu finden,
so dass das nächste Eingabesymbol einen Match darstellt.
und so gehts weiter und weiter.
Gibt es keinen Match, dann ist die Eingabesequenz nicht in
Übereinstimmung mit der Grammatik und es gibt einen Fehler.

Das ist im Grunde schon alles. Genau so arbeitet ein Parser.

[Karl H. (kbuchegg)]

jochen wrote:

> funktioniert er. Ich habe versucht, ihn umzuschreiben für die folgende
> Grammatik
>
> B-> aB
> B-> b

Du musst diese Grammatik noch mal umschreiben. Diese hier eignet
sich nicht für einen rekursiven Abstieg.
Insbesondere kann es nicht 2 Regeln für 'B' geben. Für jedes
nicht terminale Symbol kann es nur 1 Regel geben.

B -> { a } b.

(Heist soviel wie: Ein B ist eine (möglicherweise auch 0
lange) Sequenz von a gefolgt von einem b.

Hinweis: { a } kann implementiert werden durch

    while( str[pos] == 'a' )
      // a wurde erkannt
      pos++;

Deine komplette Umsetzung dieser Regel sieht daher so aus

   ...

   while( str[pos] == 'a' )
     pos++;

   if( str[pos] == 'b' ) {
     pos++;
     return true;
   }

   return false;

Neben { }  gibt es noch [ ] und |

[ ] bedeutet: entweder 0 oder 1 mal. So wie in: Bei einer Zahl
kann es ein Vorzeichen geben:

  Signed =  [ Vorzeichen ] Zahl.

| bedeutet 'oder'. Entweder der eine Pfad ist korrekt oder der
andere. So wie in

  Vorzeichen = '+' | '-'

Mit den beiden regeln ist damit klar. Das eine Zahl, wenn überhaupt
nur 1 Vorzeichen haben kann und dieses Vorzeichen entweder '+' oder
'-' sein kann.

Vorzeichen würde man so implementieren

  if( str[pos] == '+' ) {
    pos++;
    return true;
  }

  else if( str[pos] == '-' ) {
    pos++;
    return true;
  }

  return false;

Es wird also ganz einfach geprüft, ob einer der beiden terminalen
Anfänge vorliegt. Wenn ja, dann gilt dieser Zweig als genommen
und als erkannt wenn der Rest in dieser Alternative auch erkannt
wird. (In dem konkreten Fall gibt es keinen 'Rest')

Die [] sind auch leicht zu implementieren.
Entweder der Teil in der  [ ] liegt vor oder er liegt nicht
vor. Liegt er vor, dann wird er von der Eingabe weggeparst
und gilt als erkannt. Liegt er nicht vor, dann gilt die Regel
trotzdem als erkannt und das parsing geht an dieser Eingabestelle
weiter.

Wenn eine Grammatik korrekt ist, dann ist das Generieren eines
Parsers aus dieser Grammatik eine rein mechanische Angelegenheit
die auch von einem Programm erledigt werden kann. Es muss nur
sichergestellt sein, dass der Parser anhand des nächsten Eingabe-
symbols immer erkennen kann, wie es in der Grammatik weiter geht.
Unter Umständen muss man dazu die Grammatik ein klein wenig
umstellen, damit einen die terminalen Symbole durch die
Grammatik führen.

bsp:

  S ->  T | U.
  T -> a [c] b.
  U -> a [d] e.

Das wäre nicht gültig (nicht LL(1)).
Damit der Parser bei S unterscheiden kann ob nun der T oder
der U Pfad der richtige ist, muss er sich die terminalen Start-
symbole für T und U ansehen. T beginnt mit einem a und U beginnt
mit einem a. Ist also in der Eingangssequenz ein a enthalten, dann
kann der Parser nicht entscheiden, ob nun T oder U der richtige
Pfad ist.

Lösung: Die Grammatik umstellen

  S -> a ( T | U ).
  T -> [c] b.
  U -> [d] e.

Jetzt kann sehr leicht unterschieden werden. Als erstes muss ein a
kommen. Ist es da: Super, die Sequenz kann zumindest mal richtig
sein. Ist es nicht da: Fehlermeldung 'a expected' ausgeben und
parsing einstellen.
Weiter geht es. Als nächstes kommt entweder T oder U. Probieren
wir mal T. Dazu muss das nächste Eingabesymbol ein c oder ein b
sein. Ist dem so, dann ist T der richtige Pfad. Ist dem nicht so,
dann kann es noch U sein. Dazu muss das nächste Eingabesymbol
entweder ein d oder ein e sein. Je nachdem was tatsächlich
in der Eingabe vorliegt, kann also entschieden werden ob es mit
T oder mit U weitergeht. Ist keines der möglichen Eingangssymbole
in der Eingabe vorhanden -> Fehlermeldung 'c, b, d or e expected'
ausgeben.

Das schwierigste beim Parsen ist die Generierung einer vernünftigen
Fehlermeldung. Die Umsetzung der Grammatikregeln ist ziemlich
simpel.

[jochen (Gast)]

Vielen, VIELEN Danke für diese Antoworten.
Ich werde mir das jetzt ausdrucken,  in Ruhe durchlesen und ich hoffe 
ich versteh es dann ;)
Ich melde mich dann nochmal, kann aber ein paar Stunden dauern weil das 
viel auf einmal ist.

Nochmal herzlichen Dank!!!

[Karl H. (kbuchegg)]

jochen wrote:
> Vielen, VIELEN Danke für diese Antoworten.
> Ich werde mir das jetzt ausdrucken,  in Ruhe durchlesen und ich hoffe
> ich versteh es dann ;)

Zumindest dieser Teil ist sehr viel einfacher als du denkst.

Kann mich an einen c't Artikel erinnern. Da wurde es
so dargestellt:

Angenommen man hat einen Zug. In jedem Waggon ist ein Terminalsymbol
(ein Wort) aus der zu untersuchenden Sequenz.

Weiters hat man ein Schienennetzwerk aus vielen Weichen und
Haltestellen. An jeder Haltestelle kann ein Waggon nur dann
stehen bleiben, wenn er das richtige terminale Symbol beinhaltet.
Das ist die Grammatik.

Aufgabe des Parsers ist es nun, die Weichen so zu stellen, dass
der Zug in das Schienenwirrwarr einfahren kann und an jeder
Haltestelle an der er vorbeikommt, den jeweils nächsten Waggon
stehen zu lassen (wenn das geht). Dabei darf keine Haltestelle
auf diesem Weg leer bleiben und am Ende muss die Lok alleine
aus dem Schienenwirrwarr wieder herauskommen. Gelingt dies,
dann entspricht die Eingangssequenz dieser Grammatik (und aus
der Weichenstellung kann dann auch der Zuordnungsbaum
rekonstruiert werden).
In der Praxis läuft das dann so ab, dass der Lokführer bei jeder
Weiche sich anschaut, was im nächsten Waggon steht und er dann
die Gleisanlage studiert um zu entscheiden wie er weiterfahren
muss, damit genau dieser Waggon bei der nächsten Haltestelle
abgestellt werden kann. Gibt es keinen derartigen Weg, dann
kann unterschiedlich weiter verfahren werden. Wenn die Grammatik
streng LL(1) ist, dann hat man eine Fehlersituation: Die
Eingangssequenz entspricht nicht der Grammatik.
Ist LL(1) nicht gefordert, dann kann man zb. zur letzten Weiche
zurückfahren und einen anderen Weg probieren.
Die meisten Grammatiken lässen sich aber LL(1) formulieren und
ich würde jedem empfehlen auf LL(1) zu achten.

LL(1) bedeutet ganz einfach, dass man nur mit der Kenntniss
des nächsten (einen) Eingangssymbols das Parsing vorantreiben kann
und man nie zurückgehen muß um eine bereits getroffene Entscheidung
zu revidieren.

[Karl H. (kbuchegg)]

PS:
Es ist meistens vom Verständnis her einfacher, wenn man mit
einer Grammatik anfängt unter der man sich auch etwas vorstellen
kann. Also keine abstrakten abcde Grammatiken. Warum nicht
etwas was zumindest entfernt an arithmetische Ausdrücke
erinnert:
  Nur einstellige Zahlen
  Kein Vorzeichen
  Als Operationen nur + und -

Eine einfache Grammatik könnte dann lauten

Expression :=  Zahl { Operator Zahl } .
Operator   := '+' | '-' .
Zahl       := '0' | '1' | '2' | '3' | '4' | '5' |
              '6' | '7' | '8' | '9' .

Intuitiv ist dann klar, dass
  5+7-8
ein Satz dieser Grammatik ist. Der Parser müsste also sein
OK dazu geben, während
  5++9 oder 59+ oder 6- oder +2
keine Sätze dieser Grammatik ist und der Parser hier verweigern
muss.

Bsp: Wenn du soweit bist, kannst du dich ja mal an einer
kompletten Grammatik für arithmetische Ausdrücke versuchen
(wieder: Zahlen ohne Vorzeichen)

Expression := Term { ( '+' | '-' ) Term } .
Term       := Faktor { ( '*' | '/' ) Faktor } .
Faktor     := Zahl | ( '(' Expression ')' ) .
Zahl       := Digit { Digit } .
Digit      := '0' | '1' | '2' | '3' | '4' | '5' |
              '6' | '7' | '8' | '9' .

[jochen (Gast)]

Das ist sehr lieb und freundlich von Dir !

Ich habe mir das alles gründlichst durchgelesen und auch einigermaßen 
verstanden.

Ich habe aber noch eine Frage zu deinem Quelltext

   ...

   while( str[pos] == 'a' )
     pos++;

   if( str[pos] == 'b' ) {
     pos++;
     return true;
   }

   return false;

Dieser prüft zunächst, ob eine Zeichenkette aus forlaufenden a's 
besteht.
So lange läuft die while Schleife. Tauch dann kein a mehr auf, wird 
geschaut, ob der darauffolgende Buchstabe ein b ist. Ist dies der Fall, 
wird true zurückgegeben. Verstehe ich das so richtig?
Wäre dann nicht aaaaaabhallo
auch ein Wort dieser Grammatik, laut dem parser?

[Oops (Gast)]

>Wäre dann nicht aaaaaabhallo auch ein Wort dieser Grammatik, laut dem parser?

Ja, da das Satzende nicht Teil des Parsers ist.

  ...

   while( str[pos] == 'a' )
     pos++;

   if( str[pos] == 'b' )
     pos++;

   if (pos == str.length)
      return true;

Gruss
Oops

[jochen (Gast)]

Ich hoffe, ich habe jetzt die grundlegende Idee verstanden.
Und zwar habe ich mir ein neues Beispiel ausgedacht:

A -> aCd
C -> b

Startsymbol A.

Wenn ich das Vorgehen richtig verstehe, erstelle ich eine 
"Startmethode". Diese schaut dann, ob die ersten Buchstaben ein a 
darstellen und erhöht dazu pos immer um eins. Somit kann man auch 
zählen, wie oft der Buchstabe a auftaucht.
Dann wird eine neue Methode C() aufgerufen, die schaut ob die aktuelle 
Position von pos gleich dem Buchstaben b ist.
Dann geht es bei der ersten Methode weiter, die noch schaut, ob der Rest 
der Folge ein b enthält, und zwar genau so oft wie der Buchstabe a 
anfangs vorkam.

Wäre das ok?

Ich hab dann mal angefangen das zu programmieren:

public void A(){
while str[pos] =='a'
pos ++

if (C () ==true)
 {if(wenn rest der folge b ist, so oft wie anfangs a da war)
  return true
 }

return false;

Was meint ihr?

[Oops (Gast)]

Hier bringst Du ein neues Teilthema auf.
EBNF bietet keine Sprachmittel um die Anzahl von Terminalen zu 
bestimmen.
Die einzige Ausnahme ist die tatsächliche Nennung des Terminals so 
häufig wie es auftreten soll.

Übrigens beschreibt Deine Grammatik keine beliebige Anzahl von "a"s 
sondern eben nur genau das einmalige Auftreten.
Sie erkennt nur einen Satz: abc.

Die Methode für das aber ist schon ungefähr richtig:

int acount = 0;
int bcount = 0;
public void A(){
while str[pos] =='a' {
pos ++
acount++;
}

if (C () ==true)
while str[pos] =='b' {
pos ++
bcount++;
 {if(acount == bcount)
  return true
 }

return false;

Gruss
Oops

[jochen (Gast)]

ja danke stimmt, da hab ich die Grammatik falsch interpretiert, klar das 
ist ja nur abc. Ich probier noch ein bisschen rum....danke soweit ;)

[Karl H. (kbuchegg)]

jochen wrote:
>
> A -> aCd
> C -> b
>
> Startsymbol A.
>
> Wenn ich das Vorgehen richtig verstehe, erstelle ich eine
> "Startmethode". Diese schaut dann, ob die ersten Buchstaben ein a
> darstellen und erhöht dazu pos immer um eins. Somit kann man auch
> zählen, wie oft der Buchstabe a auftaucht.
> Dann wird eine neue Methode C() aufgerufen, die schaut ob die aktuelle
> Position von pos gleich dem Buchstaben b ist.
> Dann geht es bei der ersten Methode weiter, die noch schaut, ob der Rest
> der Folge ein b enthält, und zwar genau so oft wie der Buchstabe a
> anfangs vorkam.
>
> Wäre das ok?

Äh. Nein.
Das ist nicht das was in deiner Grammatik steht.

Deine Grammatik fordert, dass ein Satz mit einem a beginnt.
Genau 1 a, nicht mehr, nicht weniger.
Auf dieses a muss etwas folgen, dass C heist.
Ein C ist es nur dann, wenn ein b kommt.
Ist das C vorhanden, dann muss noch ein d kommen. 1 d, nicht mehr
und nicht weniger.

Diese Grammatik kann also nur der Satz  abd  erfüllen.
Alle anderen Sätze sind nicht Teil der Grammatik.

> Ich hab dann mal angefangen das zu programmieren:
>
> public void A(){
> while str[pos] =='a'

Wieso while. In deiner Grammatik kommt keine Wiederholung
vor.

Deine Grammatik implementiert schon nicht das was du haben
möchtest.

[jochen (Gast)]

Ich bin übrigens begeistert, dass ihr mir so da durch helft. Danke, 
Danke !

[Karl H. (kbuchegg)]

Oops wrote:
>>Wäre dann nicht aaaaaabhallo auch ein Wort dieser Grammatik, laut dem parser?
>
> Ja, da das Satzende nicht Teil des Parsers ist.

Im Prinzip ja.
Normalerweise geht man aber davon aus, dass es einen Fehler
darstellt, wenn nach dem Parsen noch nicht verarbeitete
Symbole übrig sind.

[Oops (Gast)]

Oops: Ja, richtig Karl-Heinz, es ist abd nicht abc.

A: a{a}Cd{d}.
C: b

Wiegesagt gibt es aber in der BNF keine Mittel die Anzahl der as mit der 
Anzahl der bs durch eine Bedingung zu verknüpfen.

Gruss
Oops

[Karl H. (kbuchegg)]

Sieh dir mal diese Grammatik an:


 S ->   aSb | c .

Welche Sätze können diese Grammatik erfüllen.

 c      der ist einfach, denn das steht ja schon dort:
        ein S ist es genau dann, wenn das Symbol c daher kommt

 acb    ist auch einfach zu sehen.
        das a zwingt mich, die erste Alternative (aSb) zu nehmen
        und bei dieser Alternative muss das mittlere S dann mit
        c belegt werden, damit die Sache aufgeht.

 aacbb  auch das ist gültig ( S wird zweimal durch aSb ersetzt
        und das mittlere S kann durch das einzelne c abgedeckt
        werden

 aaacbbb  ist gültig

 aaacccbbbb    ist nicht gültig. Egal wie ich die Grammatik drehe
               und wende es gelingt mir nicht, mehrere c in der
               Mitte zu erzeugen. Daher kann umgekehrt, das auch
               nicht gültig geparst werden

 aaacbb    Das ist etwas knifflig, aber die Grammatik ist so
           aufgebaut, dass die Anzahl der a und die Anzahl der b
           immer gleich sein müssen. Daher ist das auch kein
           gültiger Satz. Um zu sehen dass #a und #b immer gleich
           sein müssen, generieren wir einfach mal ein paar Sätze.
           Wir fangen an mit S

           S               ( einsetzen der ersten Alternative )
           aSb             ( noch mal: erste Alternative für S )
           aaSbb           ( und nochmal )
           aaaSbbb         ( das kann jetzt ewig so weiter gehen.
                             Jedesmal wenn S durch die erste Altern.
                             ersetzt wird, kommt ein a und ein b dazu.
                             Erhöht sich also die Anzahl der a um 1
                             erhöht sich auch die Anzahl der b um 1

          aaaaaaSbbbbbb    diesmal ersetzen wir S mit der 2. Altern.
          aaaaaacbbbbbb

[Oops (Gast)]

Nochmal Oops:
Jetzt habe ich mich glaube ich ein bischen verrannt.
Der Code geht nämlich davon aus das auch garkeine as und garkeine bs 
zulässig sind.

Es muss also
A: {a}C{d}.
C: b

sein.

Deine Grammatik, Jochen in dem Post von 14:52 war aber:
A -> aCd
C -> b

Dann aber ist der Code mit den while-Schleifen aus diesem Post falsch.
Lag wohl daran, das Du die Anzahl mit in's Spiel gebracht hast.

Sorry

Gruss
Oops

[jochen (Gast)]

Ich danke für die Erklärungen.
Wäre mein Code in etwa eine Beschreibung der Grammatik

a -> aCd
C -> aCd | b

?

[jochen (Gast)]

A -> aCd
C -> aCd | b

[Karl H. (kbuchegg)]

Edit, letzter Post:

Eine Funktion dafür könnte so aussehen

bool S()
{
  if( str[pos] == 'a' ) {
    pos++;
    if( S() ) {
      if( str[pos] == 'b' ) {
        pos++;
        return true;
      }
      else
        return false;
    }
    else
      return false;

  else if( str[pos] == 'c' ) {
    pos++;
    return true;
  }

  else
    return false;
}

void Parse()
{
  pos = 0;
  if( S() )
    printf( "Ist ein Satz\n" );
  else
    printf( "Ist kein Satz\n" );
}

Ich hoffe man kann sehen, wie die Grammatikregel sich praktisch
von alleine in Code umwandelt.
Steht in der Grammatik ein terminales Symbol, dann wird verglichen
ob es tatsächlich vorliegt. Wenn nein -> Fehler, return false
Liegt es vor, dann nächstes Symbol und weiter gehts.
Steht in der Grammatik ein nicht terminiales Symbol, dann wird
die Funktion gleichen Namens aufgerufen, die true oder false
zurückliefert. Liefert sie false, dann wird ebenfalls mit false
ausgestiegen. Liefert sie true, dann gehts weiter.

Das | in der Grammatik übersetzt sich zu einem if - else if - else

[Karl H. (kbuchegg)]

jochen wrote:
> A -> aCd
> C -> aCd | b

Dass sieht gut aus.
Sätze müssen hier mit mindestens einem a beginnen, in der
Mitte ein b haben und gleich viele d wie a haben.

Dein Code ist im Grunde eine Implementierung, die diese
Grammatik parsen kann. Aber er setzt diese Grammatik nicht
direkt um.
Direkt unmsetzen würde bedeuten, dass in deinem Code nichts
auftaucht, was nicht auch in der Grammatik steht. In der
Grammatik steht explizit nichts davon, dass irgendwelche
Zähler übereinstimmen müssen. Diese Zähler-Übereinstimmung
ist ein Nebeneffekt, der sich aus der Grammatik ergibt.

Obwohl dein Code also die gleichen Sätze als richtig erkennt,
ist er doch keine Umsetzung dieser Grammatik.

Edit: Ich meine den Code von Oops, der allerdings auch 0 a und
0 b als korrekt erkennt.


Wenn man kein zusätzliches Wissen zu einer Grammatik benötigt
(wie zb. diese Zähler), dann nennt man sowas übrigens eine
kontextfreie Grammatik.

[Oops (Gast)]

@ Karl-Heinz
Ich beziehe das jetzt mal auf mich

>Sieh dir mal diese Grammatik an:
Dein Beispiel ist beschreibt tatsächlich eine Sprache wo die Anzahl der 
as und der bs gleich sein muss.

Meine Aussagen waren aber auch etwas anders gelagert "EBNF bietet keine 
Sprachmittel um die Anzahl von Terminalen zu bestimmen.
Die einzige Ausnahme ist die tatsächliche Nennung des Terminals so
häufig wie es auftreten soll."
und
"Wiegesagt gibt es aber in der BNF keine Mittel die Anzahl der as mit 
der
Anzahl der bs durch eine Bedingung zu verknüpfen."
wobei in letzterem Satz die Bedingung "...keine Mittel ausdrücklich die 
Anzahl..."

Da es sich hier um einen Anfänger handelt, ist die Nennung Deines 
Beispiels natürlich sinnvoll.
Allerdings geht Deine Argumentation nur in den Fällen wo die Anzahlen 
gleich sind und nicht für beliebige Verhältnisse.

Wiegesagt aber finde ich Dein Gegenbeispiel durchaus hilfreich in diesem 
Zusammenhang.

Gruss
Oops

[Oops (Gast)]

@ Karl-Heinz

>Ich meine den Code von Oops, der allerdings auch 0 a und
0 b als korrekt erkennt.

Das hatte ich schon in meinem Post von 15:48 korrigiert.

Gruss
Oops

[Karl H. (kbuchegg)]

Oops wrote:

> "Wiegesagt gibt es aber in der BNF keine Mittel die Anzahl der as mit
> der
> Anzahl der bs durch eine Bedingung zu verknüpfen."
> wobei in letzterem Satz die Bedingung "...keine Mittel ausdrücklich die
> Anzahl..."

Ja klar.
Da haben sich unsere Postings überschnitten.

> Da es sich hier um einen Anfänger handelt, ist die Nennung Deines
> Beispiels natürlich sinnvoll.
> Allerdings geht Deine Argumentation nur in den Fällen wo die Anzahlen
> gleich sind und nicht für beliebige Verhältnisse.

Logisch.
Ich kann mir auch keine real existierende Grammatik vorstellen,
bei der sowas sinnvoll eingesetzt werden könnte. Gleiche Anzahl,
ja, macht Sinn und wird bei der Klammerung in arithmetischen
Ausdrücken benutzt. Aber andere Verhältnisse ...

[Karl H. (kbuchegg)]

Oops wrote:
> @ Karl-Heinz
>
>>Ich meine den Code von Oops, der allerdings auch 0 a und
> 0 b als korrekt erkennt.
>
> Das hatte ich schon in meinem Post von 15:48 korrigiert.

Das ging jetzt alles so schnell, dass ich mit dem Raussuchen
des Codes nicht mehr nach kam.
Sorry, wollte niemandem auf die Füsse steigen.

[Oops (Gast)]

@ Karl-Heinz

>Ich kann mir auch keine real existierende Grammatik vorstellen,
>bei der sowas sinnvoll eingesetzt werden könnte. Gleiche Anzahl,
>ja, macht Sinn und wird bei der Klammerung in arithmetischen
>Ausdrücken benutzt. Aber andere Verhältnisse ...

Habe ich auch überlegt. Vielleicht wenn man irgendwelche kryptischen 
ASCII-Protokolle mit Yacc erledigt. Irgendwelche dynamischen Sequenzen 
die eine Redundanz haben. Meistens wird aber sowas schon im Lexer 
erledigt. Aber bei Programmiersprachen kann ich mir da auch nichts 
denken.

Naja. Das führt jetzt vom Thema weg. Ich lasse es also.

Gruss
Oops

[Karl H. (kbuchegg)]

Oops wrote:
>
> Naja. Das führt jetzt vom Thema weg. Ich lasse es also.

Denke ich auch, dass das jetzt zu weit geht. Wir wollen ja
keine Einführung in 'formale Sprachen' daraus machen.
Das Ziel muss sein, dass Jochen erkennt wie man eine Grammatik
liest, wie man sie aufbaut und wie man sie mehr oder weniger
halbautomatisch in Code umsetzen kann.

Wenn er das hat, werden wir ihn mal zu Compiler-Compiler
lotsen :-) Es gibt da auch welche, die tatsächlich einen
rekursiven Abstieg erzeugen.

[Oops (Gast)]

@Karl-Heinz

>Sorry, wollte niemandem auf die Füsse steigen.
Gleichfalls, sorry. Sollte nicht so empfindlich sein.

Gruss
Oops

[Oops (Gast)]

Hallo Jochen?

Bist wohl gerade fleissig beim grammatisieren und kompilieren. Fein.
Frag ruhig weiter, wenn Du soweit bist!

Gruss
Oops

[jochen (Gast)]

Hey, ja ich habe etwas rumexperimentiert und auch noch einige Beispiele 
gemacht, die mir klar sind :) Nett von euch, wie ihr mir da heut 
Nachmittag geholfen habt!

Danke, dass ich noch Fragen loswerden darf.



Wir hatten anfänglich gesagt, mache Grammatiken muss man, bevor man das 
Schema anwendet, umschreiben.

Wie würde man die folgende Regel umschreiben können, hierzu fällt mir 
leider nichts ein, wie ich das einfach "ausklammern"kann wie in dem 
Beitrag von Herrn Buchegger um 11:16.
Regel: B - > aC, C-> b | cC | dC | aC

Meine zweite Frage, ich habe das ganze mit einer ähnlichen Regel
Regel: B - > aC, C-> b | cC | dC
nochmal programmiert und wollte nachfragen, ob es grundlegend richtig 
ist:

public boolean B(){

if str[pos]=='a' {
 if ( C()==true) return true; }
return false;

}

public boolean C(){
//erster Buchstabe ist ein b, dann ok.
if (str[pos]==b) return true;

//Zweiter Fall, wenn C->cC oder C->dC
if (str[pos]=='c' || str[pos]=='d'){
pos ++;
if (C()==true) return true;
}
return false;

}

Dankeschön!

[Karl H. (kbuchegg)]

jochen wrote:

> Wie würde man die folgende Regel umschreiben können, hierzu fällt mir
> leider nichts ein, wie ich das einfach "ausklammern"kann wie in dem
> Beitrag von Herrn Buchegger um 11:16.
> Regel: B - > aC, C-> b | cC | dC | aC


Da müsste mal gehen:

  C -> b | ( ( c | d | a ) C )

(Du kannst in einer Grammatik runde Klammern wie in der
Mathematik benutzen um Dinge zu gruppieren.

Ansonsten würde ich es dabei belassen. Die terminalen Anfänge
aller Teile sind voneinander verschieden, so dass das Parsen
kein Problem darstellt.
Allenfalls könnte man über eine zusätzliche Regel noch etwas
'Klarheit' schaffen, weil es die Klammerorgie etwas reduziert.

  B -> a C
  C -> b | D
  D -> ( c | d | a ) C

>
> Meine zweite Frage, ich habe das ganze mit einer ähnlichen Regel
> Regel: B - > aC, C-> b | cC | dC
> nochmal programmiert und wollte nachfragen, ob es grundlegend richtig
> ist:
>
>

> public boolean B(){
> 
> if str[pos]=='a' {
>  if ( C()==true) return true; }
> return false;
> 
> }
> 
> public boolean C(){
> //erster Buchstabe ist ein b, dann ok.
> if (str[pos]==b) return true;
> 
> //Zweiter Fall, wenn C->cC oder C->dC
> if (str[pos]=='c' || str[pos]=='d'){
> pos ++;
> if (C()==true) return true;
> }
> return false;
> 
> }
>

sieht gut aus.

Wenn du Grammatiken erfindest, dann überleg dir immer welche
Sätze von dieser Grammatik gebildet werden können. Das ist normaler-
weise leicht möglich, indem man einfach die Umkehrung des Parsens
macht:
Geh vom Startsymbol aus

  B

und jetzt nimm einfach deine B Regel und ersetzt mal. Wenn es mehere
mögliche Ersetzungen gibt, dann nimm einfach irgendeine.

   B                               B -> aC
   aC

aC ist also 'Satz' deiner Grammatik. Nicht ganz, denn in einem
Satz können ja nur terminale Symbole vorkommen. C in aC ist
nicht terminal, also ersetze auch hier wieder. Nimm irgendeine
Alternative aus

  C-> b | cC | dC

zb. C -> b und setze ein

   B                               B -> aC
   aC                              C -> b
   ab

ab ist also Satz deiner Grammatik.
Jetzt nimm dein Programm und wirf ihm mal 'ab' vor. Da 'ab' Satz
ist, muss ihn der Parser akzeptieren.

Du kannst auch eine andere Ersetzung probieren

   C -> dC

aus  'aC' wird so 'adC' und da es immer noch ein nicht terminales
Symbol gibt, suchst du dir wieder eine Möglichkeit aus dem
Fundus an Möglichkeiten für C aus.

   B                               B -> aC
   aC                              C -> dC
   adC                             C -> cC
   adcC                            C -> b
   adcb

'adcb' ist also ebenfalls Satz der Grammatik. Was sagt dein Code
dazu?

Jetzt ist es auch mal Zeit einen Gegentest zu machen. Nach
kurzem Grammatikstudium ist klar, dass kein Satz mit d anfangen
kann. Was sagt dein Parser wenn du ihm 'd' fütterst?

Was sagt er zu 'aab'? Auch das ist kein Satz.

[Karl H. (kbuchegg)]

jochen wrote:
Ach ja, noch was

> Beitrag von Herrn Buchegger um 11:16.

Der 'Herr Buchegger', das ist mein Vater.
Ich bin ganz einfach 'Karl Heinz', oder einfach nur Heinz.

[jochen (Gast)]

Heinz, danke für den beitrag. Mein Quellcode akzeptiert ab garnicht, was 
ist falsch?

[jochen (Gast)]

Also die Ausgabe lautet

Wort nicht erkannt: ab

[Karl H. (kbuchegg)]

jochen wrote:
> Heinz, danke für den beitrag. Mein Quellcode akzeptiert ab garnicht, was
> ist falsch?

Der Standardfehler, den jeder Zig-mal macht wenn er seine
ersten rekursiven Abstiegscompiler macht.

Nach dem erkennen eines terminalen Symbols, muss natürlich
das nächste Symbol geholt werden.

> public boolean B(){
>
> if str[pos]=='a' {

    pos++;

>  if ( C()==true) return true; }
> return false;
>
> }
>
> public boolean C(){
> //erster Buchstabe ist ein b, dann ok.
> if (str[pos]==b) return true;

  if( str[pos] == 'b' ) {
    pos++;
    return true;
  }

>
> //Zweiter Fall, wenn C->cC oder C->dC
> if (str[pos]=='c' || str[pos]=='d'){
> pos ++;
> if (C()==true) return true;
> }
> return false;
>
> }

[jochen (Gast)]

OK, danke!!
Herzlichen Dank für die Unterstützung, alleine wäre das doch fast 
unmöglich gewesen zu erarbeiten.
Ich danke !

[jochen (Gast)]

hab grad nochmal getestet, ich hab jetzt weitgehend alles vertsanden, 
bin sooooo froh, dass ihr mir geholfen habt

[jochen (Gast)]

Ich versuche gerade das Beispiel

Expression :=  Zahl { Operator Zahl }

umzusetzen.

Wenn ich die Grammatik hätte, könnte ich das auch programmieren, denk 
ich.

Z -> Z O | Z
O -> O Z

dann hätte ich schon einmal die passende Form, jetzt muss für Z nur noch 
eine Zahl und für O nur noch ein Operator eingesetzt werden wie ergänze 
ich die Grammatiok von mir am geeignetsten, damit ich das habe?
Oder geht man anders vor?

[jochen (Gast)]

ach nee, die Grammatik sollte sein

Z -> 1 |2 ...|9 |1P | 2P ... | 9P

p -> +Z | -Z

[jochen (Gast)]

die Grammatik in meinem letzten Post habe ich mal in Code umgeschrieben. 
Ich kann beim Besten Willen den Fehler nicht finden. Der folgende Code 
funktioniert nicht:

Grammatik:

Z -> 1 |2 ...|9 |1P | 2P ... | 9P

P -> +Z | -Z


(Z ist im Code die Klasse B.  P ist im Code die Klasse C.

public boolean B() {

    
     if (str[pos]=='1' ||  str[pos]=='2' || str[pos]=='3' || str[pos]=='4' || str[pos]=='5'
         || str[pos]=='6' || str[pos]=='7' || str[pos]=='8' || str[pos]=='9'){
       pos++;
       return true;
       }
     
     if (str[pos]=='1' ||  str[pos]=='2' || str[pos]=='3' || str[pos]=='4' || str[pos]=='5'
         || str[pos]=='6' || str[pos]=='7' || str[pos]=='8' || str[pos]=='9'){   
       
       pos++;
         if (C()==true){
         
         return true;
         }
       
     }
     return false;
        
  }

 
    public boolean C(){
   
   
    if(str[pos]=='+' || str[pos]=='-'){
      pos++;
      if (B()==true) 
    
       return true;
       
    }
      return false;
       }

}

[jochen (Gast)]

Compilieren lässt er sich. Tippe ich aber

9+2

ein ist die Ausgabe:

"Wort nicht erkannt"

[Karl H. (kbuchegg)]

Dann wirf deinen Debugger an und steppe den Code in
Einzelschritten durch.

Sorry. Aber irgendwann musst du da mal durch und deine
Fehler selber finden.

Aber einen Hinweis gebe ich noch:
2 alternative Pfade in einer Regel können niemals denselben terminalen
Anfang haben:

Z -> 1 |2 ...|9 |1P | 2P ... | 9P


Wenn dein nächstes Eingangssymbol nun eine 1 ist, woher weist
du welche Alternative jetzt die richtige ist?

Ist es die hier

Z -> 1 |2 ...|9 |1P | 2P ... | 9P
    ***

oder ist es die hier

Z -> 1 |2 ...|9 |1P | 2P ... | 9P
                ***

Anwort: Du kannst es nicht wissen und dein Parser kann es auch
nicht wissen. Also musst du die Grammatik so umstellen, dass
dieser Fall nicht mehr auftritt.

Wie eine Grammatik zur Erkennung von arithmetischen Ausdrücken
aussehen kann, habe ich weiter oben schon mal gepostet.

[Karl H. (kbuchegg)]

jochen wrote:
> Ich versuche gerade das Beispiel
>
> Expression :=  Zahl { Operator Zahl }
>
> umzusetzen.
>
> Wenn ich die Grammatik hätte,

Hinweis:
Das ist schon die Grammatik!

Niewmand sagt, dass in Grammatiken nur einbuchstabige Dinge
vorkommen dürfen.

bool Expression()
{
  if( ! Zahl() )
    return false;

  while( Operator() ) {
    if( ! Zahl() )
      return false;
  }

  return true;
}

Du schreibst jetzt noch die Regeln für Zahl bzw. Operator
als Code und fertig.

[Jochen (Gast)]

Hallo, dankeschön, es funktioniert. Es ist jetzt wirklich die 
abschließende Frage. Aber bei einem Typ bin ich mir noch leicht 
unsicher:

S-> a, S-> aA, a-> bS  Startsymbol: S

Sähe dann die Methode für das Symbol A so ähnlich aus:

public boolean S(){
if str[pos] = = 'a'{
 pos ++;
 if A() == true) return true
 

//Soweit bisher der Teil S-> aA. Also wenn das erste ein a ist, dann wird //überprüft, wie es beim nicht Terminal A weitergeht
// ist jetzt A() ==false, dann muss die Funktion dennoch true zurücgeben, da //ja der erste Buchstabe dennoch ein a war und somit A-> a erfüllt ist.
//D.h. die Funktion S() gibt(unabhängig ob A() true oder false ist) ein true //zurüück, sofern der erste Buchstabe ein a war und geht also folgendermaßen //weiter:

return true
}
return false
}

[Jochen (Gast)]

ich hatte halt die Regel umgeschrieben, zu S -> aA | a.
Aber ich komm leider nicht weiter.
Mein Ansatz funktioniert nicht.

[Jochen (Gast)]

ich komm einfach nicht drauf. Überlege jetzt schon seit 2 einhalb 
Stunden. Weiß nicht was ich machen soll. Es wäre echt nett wenn ihr mir 
das sagt.
Danke

[Jochen (Gast)]

S-> a, S-> aA, A-> bS
war ein kl. Tippfehler drin

[Jochen (Gast)]

Es ist ja genau das, was Heinz sagt:

"2 alternative Pfade in einer Regel können niemals denselben terminalen
Anfang haben"


Nur ich weiß hier nicht wie ichd as umschreiben kann. Ich habe zwar 
schon etliche Varrianten ausprobiert, doch die sind nicht identisch mit 
meiner ursprünglichen Grammatik.
Wie gesagt ich habe alles mir mögliche versucht, ich komme einfach nicht 
drauf. Es wäre lieb, wenn ihr mir bei dieser letzten Frage noch helft.

[Jochen (Gast)]

o.k.

rausgefunden, nach langer Zeit jetzt habe ich_

B-> B ba
B -> aba

so kann ich das umschreiben.

Nur wie mach ich das in Code, wie prüfe ich 3 Sequenzen, das hatte ich 
definitiv noch nicht, wie geht das ?

[Karl H. (kbuchegg)]

Jochen wrote:
> ich komm einfach nicht drauf. Überlege jetzt schon seit 2 einhalb
> Stunden. Weiß nicht was ich machen soll. Es wäre echt nett wenn ihr mir
> das sagt.

Weil du immer noch nicht die EBNF vollständig ausnutzt.

Es gibt nicht nur |

Da gibt es auch noch {}  (geschwungene Klammern)  und  []
(eckige Klammern)

{}   bedeutet: kann 0 oder beliebig oft vorkommen
[]   bedeutet: kann 0 oder 1 mal vorkommen

S   ->  a  |  aA

ist identisch zu

S  ->  a [ A ]

in Umgangssprache: gefordert ist, dass genau 1 a kommt, welches
dann möglicherweise von 1 A gefolgt wird.

Genau das sagt deine originale Grammatik aus und genau dasselbe
sagt die modifizierte Grammatik aus.

bool S()
{
  if( buf[pos] != 'a' )
    return false;
  pos++;

  if( !A() ) {
    // A war nicht da. macht aber nichts A muss ja auch
    // nicht da sein
    ;
  }

  return true;
}

Achtung: Ich habe die Bearbeitung des terminalen Symbols
umgedreht, da sich sonst im Allgemeinen elendslange ineinander-
geschachtelte if-else Ketten ergeben.

Da du noch keine Semantik in deinen Grammatiken hast, könnte
man die Überprüfung ob A() gut gegangen ist, auch weglassen.
Spätestens wenn aber Semantik ins Spiel kommt, wird normalerweise
auch überprüft. Wichtig ist nur, dass es keinen Fehler darstellt,
wenn A nicht aufgefunden wurde. Denn das ist ja die Aussage in
der Grammatik: A kann da sein oder auch nicht.

[joch (Gast)]

Hi, als es drauf ankam, bin ich an folgendem Bsp gescheitert:

A -> aAS |c
S -> b

ich hab 2 Ideen, mir sind beide logisch, ich weiß aber nicht welche die 
richtige ist:

public static A(){
if str[pos]='a'{
 pos++;
  if (A()==true)
   { if S() ==true)
      return true
    }
}
else if str[pos] == 'c'
return true;

public static S(){
if str[pos] == 'b'
 { return true;
  pos++;
 }
return false;

--------------------
Oder ich machs so, wie ich im Beitrag


Autor: Oops (Gast)
Datum: 27.02.2008 15:23

gelernt habe:

public static A(){
acount = 0;
functionCcount = 0;

while (str[pos]=='a'){
 pos++;
acount++;
}
if (str[pos] =='b') {
 while (S()==true) {
 functionCcount++:
   if (acount == functionCcount) return true
 }
return false;
}

Welcher Weg stimmt, und warum gerade ?

[Karl H. (kbuchegg)]

joch wrote:
> Hi, als es drauf ankam, bin ich an folgendem Bsp gescheitert:
>
> A -> aAS |c
> S -> b
>
> ich hab 2 Ideen, mir sind beide logisch, ich weiß aber nicht welche die
> richtige ist:

Probiers aus, welche stimmt. Erfinde ein paar Sätze und hetze deinen
Parser auf sie.

>

> public static A(){
> if str[pos]='a'{
>  pos++;
>   if (A()==true)
>    { if S() ==true)
>       return true
>     }
> }
> else if str[pos] == 'c'
> return true;


Hmm. Irgendwie seltsam. Aus der Funktion A() kann immer nur
true returniert werden. Das kanns ja wohl nicht sein.
ZUm zweiten: Nachdem 'c' erkannt wurde, wird pos nicht erhöht.

> 
> public static S(){
> if str[pos] == 'b'
>  { return true;
>   pos++;

Wenn du zuerst retournierst und dann pos erhöhst, dann wird wohl
pos nie erhöht werden.

>  }
> return false;
>

> --------------------
> Oder ich machs so, wie ich im Beitrag
>
>
> Autor: Oops (Gast)
> Datum: 27.02.2008 15:23
>
> gelernt habe:
>
> public static A(){
> acount = 0;
> functionCcount = 0;
>

> while (str[pos]=='a'){
>  pos++;
> acount++;
> }
> if (str[pos] =='b') {
>  while (S()==true) {
>  functionCcount++:
>    if (acount == functionCcount) return true
>  }
> return false;
> }
>

>
> Welcher Weg stimmt, und warum gerade ?

Korrekt ist das Programm, welches Sätze die der Grammatik entsprechen
als true parst und welches Sätze die nicht der Grammatik entsprechen
als false parst. So einfach ist das.
Es kann durchaus sein, dass es für ein Problem 2 Lösungen gibt.
Das Problem ist z.b eine Funktion zu schreiben, welches das
Zweifache einer Zahl liefert.
Version A: int foo( int a )  { return 2 * a; }
Version B: int foo( int b )  { return b + b; }
Beide Versionen sind fundamental unterschiedlich und doch sind sie
beide korrekt.

Also musst du deinen Code testen. Besonders bei Parsern ist ein
systematisches Testen wichtig! Sowohl: Erkennt er alle Sätze die
der Grammatik entsprechen UND weist er alle Sätze ab, die nicht
der Grammatik entsprechen.
Da du in deinem ersten Code 3 ziemlich schwerwiegende Fehler hast,
hast du den Code nie ausprobiert, sonst wären dir diese Fehler
aufgefallen. -> ausgiebiger testen!

Der Unterschied zwischen den beiden Lösungen ist ganz einfach der:
In der ersten Lösung ergibt sich das Verhalten, daß immer gleich
viele 'a' wie 'b' enthalten sein müssen, implizit. Es ist quasi
ein Nebenprodukt. In der zweiten Lösung hat sich jemand zurückgelehnt
und die Grammatik analysiert und festgestellt, daß das so sein muß
und hat dieses Wissen explizit hineinkodiert.

[Ingo B. (arctis77)]

Falls du nicht zwingend auf die Implementierung per Hand und zu Fuß 
angewiesen bist, schau dir doch mal die Spirit Library aus Boost an.

[joch (Gast)]

schön, wenn im Ansatz beide Lösungen funktionieren.
Danke, dann ist es mir hoffentlich klar :)