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

rüdiger

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)

Jester

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

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

rüdiger

Jester schrieb:

kingruedi schrieb:

EBNF benutzt keine Rekursion

Bist Du Dir da sicher?

Ich hab das glaube ich nur falsch in Erinnerung.

virtuell Realisticer

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?

EBNF -&gt; Bison / Flex

EBNF -> Bison / Flex