Hans-Peter Diettrich <DrDiettrich1*aol.com> wrote:
> Ernst Baumann wrote:
>
> > Mir wurde gesagt, dass man aus Grammatiken einen Übersetzer (Compiler)
> > bauen kann.
>
> Nun ja, Grammatiken beschreiben i.d.R. nur die Syntax einer Sprache,
> nicht deren Semantik. Wenn der Übersetzer ablauffähigen Code produzieren
> soll, oder (als Interpreter) ein Resultat berechnen soll, muß ihm die
> Semantik noch extra mitgeteilt werden.
>
> > Ich überlege, ob man dies auch mit induktiven Definitionen machen
> > kann.
> > http://wwwcs.upb.de/cs/kindler/Lehre...F/Kapitel4.pdf
>
> Ohne jetzt in die Tiefe gegangen zu sein, würde ich mal vermuten, daß
> das prinzipiell möglich sein sollte. Für die Praxis dürfte dabei wichtig
> sein, wie sich Rekursionen in andere Operationen abbilden lassen. Eine
> rekursive Berechnung von (a+b) stelle ich mir jedenfalls ziemlich
> langwierig vor: O(n)

Nein. Terme wie dieser werden rekursiv ausgewertet:

"Werte (a+b) aus indem Du a und b (rekursiv) auswertest und dann die Ergebnisse
zusammenzaehlst.

z.B. ((2*4) + (6/2)):
Notation: [[ x ]] fuer "Wert/Semantik von x" wie ueblich:

[[ (2*4) + (6/2) ]] =
[[2*4]] + [[6/2]] = ...
erst [[2*4]] = [[2]] * [[4]] = (Basisfall: atomare Terme) 2 * 4 = 8
analog [[6/2]] = ... 3
also
= 8 + 3 = 11.

> IMO ist (1) zunächst nur eine (etwas unübliche) Form einer Grammatik,
> mit allen entsprechenden Konsequenzen.

Nein, wie der OP schon schrieb: induktive Definition der *Sprache*
(nicht der Grammatik). Man kann eine Sprache halt induktiv *oder* durch
eine Grammatik definieren. Beides ist natuerlich irgendwo aequivalent,
aber eben verschiedene Konzepte der Formalisierung (fuer den Praktiker
also "egal, da beides klar und eindeutig ist", aus Sicht der Informatik
als (Struktur)wissenschaft grundsaetzlich verschieden).

Wolfgang

Wolfgang May wrote:

>>rekursive Berechnung von (a+b) stelle ich mir jedenfalls ziemlich
>>langwierig vor: O(n)
>
>
> Nein. Terme wie dieser werden rekursiv ausgewertet:

Du hast das Wesentliche verpaßt :-(

> erst [[2*4]] = [[2]] * [[4]] = (Basisfall: atomare Terme) 2 * 4 = 8

Und woher kommt die Vorschrift, die aus "2 * 4" eine 8 macht? Wie sieht
sie aus?


>>IMO ist (1) zunächst nur eine (etwas unübliche) Form einer Grammatik,
>>mit allen entsprechenden Konsequenzen.
>
>
> Nein, wie der OP schon schrieb: induktive Definition der *Sprache*
> (nicht der Grammatik).

Also doch? Es *ist* eine Grammatik.

> Man kann eine Sprache halt induktiv *oder* durch
> eine Grammatik definieren.

Dann definiere bitte den Unterschied. Ich sehe keinen.

DoDi

>
>> Man kann eine Sprache halt induktiv *oder* durch
>> eine Grammatik definieren.
>
>Dann definiere bitte den Unterschied. Ich sehe keinen.
>
Schau dazu den folgenden Link an:
http://209.85.129.104/search?q=cache...lnk&cd=1&gl=de

oder gib in google ein:
"Kindler induktive Definition"
Dann kannst du die pdf-Datei downloaden.
Hier wird genau erklärt, was eine induktive Definition ist.

mfg
Ernst

Ernst Baumann wrote:

>>>Man kann eine Sprache halt induktiv *oder* durch
>>>eine Grammatik definieren.
>>
>>Dann definiere bitte den Unterschied. Ich sehe keinen.

> Hier wird genau erklärt, was eine induktive Definition ist.

Ich fragte nach einer Definition des *Unterschieds*.

DoDi

Hans-Peter Diettrich <DrDiettrich1*aol.com> wrote:
> Wolfgang May wrote:
>
> >>rekursive Berechnung von (a+b) stelle ich mir jedenfalls ziemlich
> >>langwierig vor: O(n)
> >
> >
> > Nein. Terme wie dieser werden rekursiv ausgewertet:
>
> Du hast das Wesentliche verpaßt :-(

Klarstellung: die Begriffe "Auswertung" und "Berechnung" bedeuten
ueblicherweise dasselbe, naemich das was formal als "Semantik"
(von Termen, Formeln, Ausdruecken, whatever) bezeichnet wird.

> > erst [[2*4]] = [[2]] * [[4]] = (Basisfall: atomare Terme) 2 * 4 = 8
>
> Und woher kommt die Vorschrift, die aus "2 * 4" eine 8 macht? Wie sieht
> sie aus?

Nennt sich Arithmetik.
Zum dem Teil der (Programmier)Sprache (egal ob induktiv oder als Grammatik
gegeben), der die arithmetischen Ausdruecke definiert, ist (wie alles
andere auch) zwecks Ausfuehrung/Auswertung etc eine Semantik anzugeben
(das was ich oben mit in der formal ueblichen Notation mit [[...]]
bezeichnet habe). Die Semantik der Auswertung atomarer arithmetischer
Terme wird ueblicherweise eben durch Reduktion auf die bekannten
arithmetischen Operationen (+ usw) reduziert.

> >>IMO ist (1) zunächst nur eine (etwas unübliche) Form einer Grammatik,
> >>mit allen entsprechenden Konsequenzen.
> >
> > Nein, wie der OP schon schrieb: induktive Definition der *Sprache*
> > (nicht der Grammatik).
>
> Also doch? Es *ist* eine Grammatik.

Formal gesehen ist eine Grammatik in der (theoretischen) Informatik
(und das ist das was der OP meint) eine Menge von Produktionsregeln
der Form

lhs :== rhs ,

wobei lhs (left hand side) ueblicherweise mindestens ein Nichtterminal
enthaelt (kontextfreie Grammatiken: genau ein NT); rhs ist eine beliebige
Zeichenkette aus Terminalen und Nonterminalen.

Die Menge der Ausdruecke, die in einer Grammatik G aus einem
"Anfangs-Nichtterminalsymbol" erzeugbar sind, sind die Sprache L(G).
Zu einer Sprache kann es viele Grammatiken geben, die sie erzeugen.

Um die Begriffsverwirrung noch zu vervollstaendigen: Eine Sprache
ist erstmal nur eine Menge von Zeichenketten. Noch ohne jegliche
Bedeutung/Semantik/Ausfuehrbarkeit.
Die Semantik (also "Auswertung eines Termes" oder "Ausfuehrung
eines Programmes") wird ueblicherweise induktiv ueber die Struktur
der Ausdruecke definiert ("strukturelle Induktion").

> > Man kann eine Sprache halt induktiv *oder* durch
> > eine Grammatik definieren.
>
> Dann definiere bitte den Unterschied. Ich sehe keinen.

Das glaube ich Dir aufs Wort. Ich schreibe aus der Sicht des
Informatik-Dozenten, Du siehst es mit dem gesunden Menschenverstand
des Praktikers. Aus dem Originalposting ergibt sich, dass der Poster
wohl gerade mit den Untiefen des Informatikstudiums und dem
Hineinfinden in diese Begrifflichkeiten kaempft.

Wolfgang

Wolfgang May wrote:

>>Und woher kommt die Vorschrift, die aus "2 * 4" eine 8 macht? Wie sieht
>>sie aus?
>
>
> Nennt sich Arithmetik.
> Zum dem Teil der (Programmier)Sprache (egal ob induktiv oder als Grammatik
> gegeben), der die arithmetischen Ausdruecke definiert, ist (wie alles
> andere auch) zwecks Ausfuehrung/Auswertung etc eine Semantik anzugeben
> (das was ich oben mit in der formal ueblichen Notation mit [[...]]
> bezeichnet habe). Die Semantik der Auswertung atomarer arithmetischer
> Terme wird ueblicherweise eben durch Reduktion auf die bekannten
> arithmetischen Operationen (+ usw) reduziert.

Nach meinem Verständnis soll eine induktive Definition die Arithmetik
beschreiben.


> Formal gesehen ist eine Grammatik in der (theoretischen) Informatik
> (und das ist das was der OP meint) eine Menge von Produktionsregeln
> der Form
>
> lhs :== rhs ,
>
> wobei lhs (left hand side) ueblicherweise mindestens ein Nichtterminal
> enthaelt (kontextfreie Grammatiken: genau ein NT); rhs ist eine beliebige
> Zeichenkette aus Terminalen und Nonterminalen.

Im allgemeinen Fall also eine Liste von Transformationsregeln, wie sie
auch bei induktiver Definition vorliegt.


> Um die Begriffsverwirrung noch zu vervollstaendigen: Eine Sprache
> ist erstmal nur eine Menge von Zeichenketten. Noch ohne jegliche
> Bedeutung/Semantik/Ausfuehrbarkeit.

Richtig.

> Die Semantik (also "Auswertung eines Termes" oder "Ausfuehrung
> eines Programmes") wird ueblicherweise induktiv ueber die Struktur
> der Ausdruecke definiert ("strukturelle Induktion").

Und da habe ich bei induktiver Definition gewisse Probleme. Wo soll da
z.B. der Unterschied zwischen Operatoren, Variablen und anderen
Sprachelementen definiert werden? Die Konvention, daß "+" ein Operator
mit einer bestimmten Semantik sein soll, muß doch irgendwie
festgeschrieben werden.

Ich finde es durchaus beeindruckend, daß sich Semantik induktiv
definieren läßt, doch was ist die Basis für diese Definitionen? In
welcher Relation steht die induktive Definition zur Arithmetik? Beruht
sie auf Arithmetik, gilt sie nur für arithmetische Definitionen, oder
sind arithmetische Ausdrücke nur eine frei wählbare Basis von vielen
(welchen?)?


>>>Man kann eine Sprache halt induktiv *oder* durch
>>>eine Grammatik definieren.
>>
>>Dann definiere bitte den Unterschied. Ich sehe keinen.
>
>
> Das glaube ich Dir aufs Wort. Ich schreibe aus der Sicht des
> Informatik-Dozenten, Du siehst es mit dem gesunden Menschenverstand
> des Praktikers. Aus dem Originalposting ergibt sich, dass der Poster
> wohl gerade mit den Untiefen des Informatikstudiums und dem
> Hineinfinden in diese Begrifflichkeiten kaempft.

Gut erkannt. Mein Informatik-Studium liegt nun schon etliche Jahrzehnte
zurück, aber ich erinnere mich noch gut daran, daß uns Studenten damals
irgendein Formalismus (plus Terminologie) als bahnbrechend neuartig
verkauft wurde, der sich unter Kenntnis des Stoffs aus anderen
Vorlesungen unschwer als Neuaufguss von ollen Kamellen erkennen ließ.
Der Rückzug auf die Feststellung, daß der Beschreibungsformalismus der
induktiven Definition anders aussieht als EBNF, und daß Arithmetik ein
gottgegebener Bestandteil induktiver Definitionen ist, und der Mangel an
einer Unterscheidung, ob bzw. wie weit eine induktive Definition eine
Sprache syntaktisch bzw. semantisch beschreibt, kommt mir daher verdammt
verdächtig vor, um nicht zu sagen faustisch ;-)

Aus der Sicht des Praktikers müssen die Erwartungen, die in die
induktive Definition gesetzt werden, erst noch erfüllt werden, bzw. die
Möglichkeit deren Erfüllung bewiesen werden. Bis dahin sortiere ich
diesen Ansatz ähnlich ein wie das Versprechen der Linguisten, in wenigen
Jahren die Analyse natürlicher Sprachen (Tiefenstruktur...) zu schaffen.

DoDi