• Als Spam markieren
• Beitrag melden

• 
  Diese Gruppe Alles

• Archiv
• RSS-Feeds

• Kontakt
• Hilfe
• Impressum
• Datenschutz

Alternative zu Grammatiken im Compilerbau?

Hallo allerseits,
Mir wurde gesagt, dass man aus Grammatiken einen Übersetzer (Compiler)
bauen kann.
Ich überlege, ob man dies auch mit induktiven Definitionen machen
kann.
http://wwwcs.upb.de/cs/kindler/Lehre/WS04/Semantik/PDF/Kapitel4.pdf

1)
Beispiel:
Ich will mathematische Terme wie ((a+b)*a)
durch eine induktive Definition darstellen.
Dazu braucht man sogenannte Regeln.
z1 und z2 sollen Zeichenketten über dem Alphabet X={a,b,+,-} sein
Ich nehme der Einfachheit halber hier mal nur zwei Variablen a und b
und die zwei Rechenzeichen + und -

{}
---
a


{}
---
b


{z1, z2}
--------
(z1 + z2)

{z1, z2}
--------
(z1 - z2)

{z1, z2}
--------
(z1 * z2)

{z1, z2}
--------
(z1 / z2)


D0 := {a ; b}
D1 := {(a+b) ; (a-b); (a+a); (b+b); (a-a); (b-b)}
D2 =: {a ; b; (a+b) ; (a-b); (a+a); (b+b); (a-a); (b-b),
(a+(a+a), ...}
...

I(R) = D0 u D1 u D2 u ...

Mit I(R) wird also die Menge aller Terme formalisiert (genaueres ist
dem obigen Link zu entnehmen im Kapitel "induktive Definitionen")


2)
Die Syntax einer Programmiersprache (mit Anweisung, Verzweigung,
Schleifen) kann man meines Wissens durch eine Grammatik beschreiben.
Dies müsste auch mit einer induktiven Definition möglich sein.
I(R) ist dann die Menge der syntaktisch korrekten Zeichenketten dieser
Programmiersprache


Frage:
Ist die induktive Definition (die diese Syntax beschreibt) auch
entscheidbar, d.h:
gibt es ein Verfahren, mit dem von einer Zeichenkette z entscheiden
kann, ob sie syntaktisch korrekt ist oder nicht (d.h. ist z Element
von I(R) oder nicht).

Wenn dies nicht möglich ist, bitte ich um ein einfaches Gegenbeispiel.
Wo gibt es Probleme mit der Entscheidbarkeit?

mfg
Ernst

Antworten