Buffl

1_2 Algorithmen - Formulierung

JB
by Julian B.

Backus-Naur-Form

Am Beispiel “17 + 27 * (Alpha + 14)”:

  • Definierung von Regeln

    • Mit Regelanwendung sind die mathematischen Rechenregeln gemeint (Klammer vor Punkt vor Strich)

    • Man kann sich folgendes Vorstellen, die Symbole links von “::=” können Symbol, die rechts von “::=” sind, zusammenfassen. Heißt, man kann die Symbole auf der rechten Seite durch das auf der linken ersetzen.

    • Folgt man der Logik, sind die äquivalenten Symbole zu <Faktor> die Grundsymbole, durch die man gegebene Terme Stück für Stück verkleinern/zusammenfassen kann

  • Anwendung der Regeln am oben genannten Beispiel:

Schaut man sich die Regeln an, sieht man unter <Faktor>, dass dieser eine <ganze Zahl> ein <Bezeichner> (bzw. Variable) oder eine geklammerte (<Formel>) sein kann. Diese 3 Voraussetzungen werden dem Beispiel Stück für Stück zugeordnet. Die Zahlen sind also <ganze Zahl> und “Alpha” ist ein <Bezeichner>.

Nun lassen sich diese Grundbedingung “zusammenfassen” bzw. auf- oder ableiten. Da ein <Faktor> eine <ganze Zahl> oder auch ein <Bezeichner> sein kann, wird <Faktor> nun an die Stelle der Grundbedingungen gesetzt, wodurch die nun 3x <Faktor> in dem Beispiel-Term steht.

Ein <Term> wiederum kann auch ein <Faktor> sein, weshalb die <Faktor>-Symbole nun durch <Term>-Symbole ersetzt werden. Theoretisch, könnte man nun weitermachen und alles auf <Formel>-Symbole ab- oder aufleiten, aber dann würde die Additionszeichen etc. immer noch dastehen. Deshalb leitet man erstmal nur zwei der <Term>-Symbole auf bzw. ab.

Nun wird erstmal in der Klamm weitergemacht, in man nun das Symbol <ganze Zahl> bis zum Term auf-/ableitet. In der Klammer steht nun <Formel>+<Term> was wiederum in der Regel unter <Formel> definiert ist. Heißt, man kann den Inhalt nun durch das <Formel>-Symbol ersetzen.

Schauen wir wieder in die Regeln unter <Faktor>, ist zu sehen, dass (<Formel>) das gleiche wie <Faktor> ist - entsprechend wird die Klammer durch <Faktor> ersetzt.

Unter <Term> ist definiert, dass dieses das Äquivalent zu <Term> * <Faktor> ist, also ersetzen wird die Mulitplikation durch das Symbol <Term> (Oder schreiben dieselbe Zeile nur ohne Mal und <Faktor>-Symbol).

Nun steht nur noch <Formel> + <Term> als Term, dieses ist nach Regeldefinition dasselbe, wie <Formel>, also ersetzen wir den Term, durch das Symbol (Bzw. Schreiben den Term ohne Plus und <Term> auf)



Author

Julian B.

Information

Last changed