EBNF -> Bison / Flex



  • Also ich habe mich auf Wikipedia schlau gemacht, wie man eine Grammatik in EBNF entwickeln kann:
    http://de.wikipedia.org/wiki/EBNF

    Nun habe ich mir die Bison++ und Flex++ von
    http://www.kohsuke.org/flex++bison++/
    herunter geladen.

    Da sich leider nichteinmal die Beispiele aus der Dokumenation ausführen liesen, wollte ich fragen, ob mir jemand mal ein Beispiel dazu geben kann:

    Ausdruck = Zahl
             | Ausdruck "+" Ausdruck
             | Ausdruck "-" Ausdruck
             | Ausdruck "*" Ausdruck
             | Ausdruck "/" Ausdruck
             | "(" Ausdruck ")" ;
    
    Zahl     = Ziffer { Ziffer } ;
    
    Ziffer   = "0" | "1" | "2" | "3" | "4"
             | "5" | "6" | "7" | "8" | "9" ;
    

    Das ist die EBNF Definition. Ich hoffe, sie ist in soweit korrekt.
    Z.B. soll die Eingabe "7+(3*5)" damit geparst werden können.

    mfg olli
    P.S. scheiße, ist es spät 😞



  • EBNF benutzt keine Rekursion, daher muss Ausdruck ungefähr so aussehen

    Ausdruck = { [ ( ] Zahl [ Operator ] [ ) ] }
    Operator = "+" | "-" | "*" | "/" | "%"
    

    Naja, ist länger her, dass ich mich mit dem Thema befasst habe und das ist vermutlich auch nicht ganz richtig (würde ja auch (10)11 oder (10 oder 11) etc zulassen, hmm)



  • Vertex' schrieb:

    Ausdruck = Zahl
             | Ausdruck "+" Ausdruck
             | Ausdruck "-" Ausdruck
             | Ausdruck "*" Ausdruck
             | Ausdruck "/" Ausdruck
             | "(" Ausdruck ")" ;
    
    Zahl     = Ziffer { Ziffer } ;
    
    Ziffer   = "0" | "1" | "2" | "3" | "4"
             | "5" | "6" | "7" | "8" | "9" ;
    

    Die Grammatik ist so nicht ganz sauber.

    Man kann 3*5+2 auf zwei Arten ableiten, einmal richtig als Ausdruck -> Ausdruck + Ausdruck -> Ausdruck * Ausdruck + Ausdruck -> ... -> 3*5+2 (das erzeugt die richtige Klammerung).

    Aber auch als Ausdruck -> Ausdruck * Ausdruck -> Ausdruck * Ausdruck + Ausdruck -> ... -> 3*5+2, welches dann aber, wenn man sich den Baum anschaut falsch geklammert ist, nämlich als 3*(5+2).

    Deshalb unterscheidet man da zwischen Terms und Expression. Expressions sind additiv, Expressions multiplikativ. Will man in ner Expression wieder zurück zu nem Term, dann muß man das klammern. Damit ist die Eindeutigkeit der Ableitung gewährleistet.

    MfG Jester



  • kingruedi schrieb:

    EBNF benutzt keine Rekursion

    Bist Du Dir da sicher?



  • Danke!

    Ja, bin eigentlich auch der Meinung, das EBNF Rekursivität unterstützt.

    Bin gerade dabei, Flex (benutze doch kein Flex++ mehr) zu erlernen. Die Syntax von Flex sagt mir nicht gerade zu, aber naja...

    Jedenfalls wollte ich folgendes EBNF zum Start realisieren:

    Digit = "0" | "1" | "2" | "3" | "4"
          | "5" | "6" | "7" | "8" | "9" ;
    
    Number = [ "+" | "-" ] Digit { Digit } ;
    

    Also eine Zahl besteht aus optional vorangestellten "+" oder "-" gefolgt von einer oder mehreren Ziffern.

    Mein Idee das in Flex umzusetzen:

    %{
    #include <stdio.h>
    %}
    %option noyywrap
    %%
    "+"|"-"[0-9]* { printf("a number: %s\n", yytext); }
    . { printf("unrecognized character\n"); }
    %%
    int main()
    {
    	yylex();
    	printf("%s\n", "ready");
    }
    

    in.txt:

    +45

    dann folgender aufruf:

    yy.lex.exe < in.txt > out.txt

    Dann steht in der out.txt:

    a number: +
    unrecognized character
    unrecognized character
    ready

    Kann mir jemand da helfen?

    mfg olli



  • Jester schrieb:

    kingruedi schrieb:

    EBNF benutzt keine Rekursion

    Bist Du Dir da sicher?

    Ich hab das glaube ich nur falsch in Erinnerung.



  • kingruedi schrieb:

    EBNF benutzt keine Rekursion, daher muss Ausdruck ungefähr so...

    Laut Wikipedia ist Rekursion in BNF nicht, aber in EBNF enthalten. Bei mir in der
    Uni wurde Rekursion schon als Bestandteil der BNF gelehrt und in einem Buch das
    ich habe, wird dies ebenfalls getan.

    Jetzt draengt sich mir die Vermutung auf, dass das nicht so richtig festgelegt
    ist, was ich mir in der heutigen Zeit kaum vorstellen kann.

    Wie sieht das denn nun aus?

    mfg
    v R



  • kann von einem yacc file die ebnf generieren lassen mit einem tool?


Log in to reply