Der witz bei der Geschichte ist, dass sie in der Informatik, aber die Bakus-Naurr Form brauchen.
Das ist relativ simpel zu erklären.
Im Deutschunterricht, lautet die Vorschrift, für die Grammatik, eines Deutsches Satzes so:
Code: Select all
<Satz> ::= <Subjekt> <Prädikat> <Objekt>
Das
Code: Select all
<Subjekt>
ist genauso wie
Code: Select all
<Objekt>
durch jedes beliebige Substantiv in der richtigen Form zu ersetzen. Das selbe gilt für
Code: Select all
<Prädikat>
mit Verb.
Wenn sie in der Informatik die Bakus-Naur Normalform nicht hinkriegen wird es schlecht.
Programmieren können ist das eine. Das machen alle. Informatiker machen den Übersetzer
Wenn sie jetzt einen Ausdruck angucken, dann sieht der so aus
Das ist die Mathematische so in etwa Definition, das Beispiel für einen Ausdruck
Code: Select all
x*((10+y)+2)*3
Gut:
Das hat auch eine Grammatik. Die geht so:
Code: Select all
<expr> ::= <term> | <term> '+' <expr>
<term> ::= <factor> | <factor> '*' <term>
<factor ::= <num> | <id> | '('<expr>')'
So, wenn sie das hinkriegen, dann lassen sie mich aufklären. sie müssen in der Informatik 2 Dinge können
TTL, VHDL, FPGA und Prozessor wissen,
Sie müssen Programmiersprache können - Compiler
Zu (1.) sage ich was. Das mit den Transistoren ist so eine Sache. Das weiss ich auch auswendig teilweise, da sage ich ein paar Beispiele
Technisches für den Prozessor
Dinge, wie Widerstände, Kondensatoren, ... sollten klar sein. Man kann physikalische Formeln lernen, wie
Code: Select all
E = U/d
Code: Select all
C = A/d
Code: Select all
E, B, H, D
Oder auch nicht. Widerstände, Kondensatoren, Spulen müssen sitzen.
Sie sind aber nicht unbedingt Teil der technischen Informatik
Code: Select all
74xx
Gatter lassen sich ganz einfach verwenden. Ohne über den Stromkreis bescheid zu wissen. Das heisst, wenn wir die aneinander schalten, geht es ganz von alleine - wir müssen ausser
Code: Select all
0,1
nichts über Signale wissen
Natürlich wäre es gut Transistoren zu kennen, weil
Code: Select all
FPGA, CPLD, PLA, PAL, ...
kommen vor. Und wenn man den Transistor kann, wird es easy
Die Kirchhoffschen Regeln sind ganz einfach. Es gibt die erste und die zweite
Die Summe zufliessenden Ströme in einem Knotenpunkt ist gleich die Summe der abfliessenden
Die Summe aller Spannungen einer Masche sind gleich 0
Basis, Emitter, Collector - beim Transistor. Basis - Emitter - Steuerstromkreis - Collector - Arbeitsstromkreis
Dann haben sie kennlinien - wie
Arbeitspunkteinstellung
Übersteuerungsgränze
Sättigungsspannung
Kleinsignalverhalten
Stromverstärkungsgruppen
Restströme
Hochfrequenz, Grenzfrequenz
das erkläre ich mal. das weiss ich alles auswendig: Wenn sie den Transistor angucken, dann steuert der von der Basis - eingangsignal zum Emitter den Arbeitsstromkreis - Collector - Emitter. Und: Wenn sie einen Arbeitspunkt einstellen, dann legen sie einen Widerstand vom Collector - zur Basis - dass auf der Basis, wo das Eingangssignal rein kommt, immer 5 Volt sind.
So: Sättigungsspannung weiss ich nicht. Übersteuerrungsgrenze - wird das maximale Signal, also Spannung. Kleinsignalverhalten, das ist denke ich: Wie mit ganz nieder Spannungen im Eingang ist. Stromverstärkungsgruppen ist einfach - das bedeutet: Haben sie 1:2 oder 1:200 Verstärkung, am Signal. Reststrom weiss ich nicht. Grenzfrequenz - wenn sie einen Hochfrequenz Transistor haben, dann kann der mit 1 GHz unter Umständen zu recht kommen, der für die Stereoanlage taugt unter Umständen nicht.
Es gibt verschiedene Gehäusebauformen - die gehen SOT und TO, dazu gehören die Nummern 89 und 39 und 93 oder so. Irgendwas.
Jetzt kommt: Jetzt gibt es den FET
Feldeffekttransistor. Der hat nicht
Code: Select all
E, B, C
, sondern der hat
Source, Quelle
Drain, Tor
Gate, Tor
Bulk
Das ist der FET
Und da gibt es den
Code: Select all
MISFET
Code: Select all
MESFET
Code: Select all
MOSFET
Code: Select all
JFET
Code: Select all
IGFET
Code: Select all
SFET
MESFET: Metal Insulator Semiconductor
JFET: Junction FET
IG: Insulator Gate FET
SFET: Sperrschicht FET.
Dann gibt es den LASER - den Light Ampilification by Stimulated Emission of Radiation
Und der Witz bei der Geschichte ist. Das müssen sie nicht wissen.
Es gibt die TTL-Gatter. Die haben die Nummer
Code: Select all
74xx
Und dabei steht zum Beispiel glaube
Code: Select all
04
hinten dran, für
Code: Select all
OR
, oder
Code: Select all
NOR
oder
Code: Select all
NOT
. der
Code: Select all
01
ist wichtig. Ich glaube
Code: Select all
7483
ist Addierer. Und so.
Nur, da brauchen sie gar keine Elektrotechnik. Sie müssen wissen, was
Code: Select all
5 Volt
sind
Die Gatter, die kommen im IC daher. Jetzt. Die sind so gemacht, dass sie gar nichts Elektrotechnisches wissen müssen. sondern, die tun einfach indem sie sie anschliessen. Wenn sie mit einer Stricknadel klar kommen, dann kriegen sie die Maschen auf die Reihe.
Am TTL-Gatter, da sind generell ungefähr 4 Gatter. Und das bedeutet:
Code: Select all
A, B, C
Sie haben die Eingänge
Code: Select all
A
und
Code: Select all
B
und den Ausgang
Code: Select all
C
. Gut, da müssen sie wie bei der Stricknadel nicht wissen. Sie müssen wissen, zwei Signale gehen rein und eines kommt raus. Zum Beispiel als
Code: Select all
AND
. Und das geht kommt bei
Code: Select all
C
raus.
Die können sie beliebig aneinander schalten, die TTL-74xx-Gatter, da brauchen sie nur wissen, was 5V sind. Und dann müssen sie wissen,
was
Code: Select all
VCC
ist und was
Code: Select all
GND
ist - nämlich
Code: Select all
VCC
auch
Code: Select all
5V
. Dann haben sie ihre Schaltung.
Jetzt kommt der FPGA - der wird mit VHDL programmiert
VHDL bedeutet: VHSIC Hardware Description Language
und VHSIC - bedeutet: Very High Speed Integrated Circuit
Und das ist so. Angenommen, sie haben ihren FPGA - den MIPS Prozessor haben sie im Kopf. Dann bringen mit VHDL den MIPS Prozessor auf dem FPGA unter. Sie müssen sich nicht schämen, weil sie würden das mit den TTL-Gattern schon hinkriegen.
So: Zunächst zu den Bausteinen. Der FPGA kommt daher mit
PLD - Programmable Logic Device
PLA - Programmable Logic Array - da ist UND-Programmierbar
Sie müssen wissen, die PLD's sind in Disjunktiver Normalform DNF. Das heisst, lauter UND und ODER - UND-Programmierbar
Gut:
Jetzt
PAL: Programmable Array Logic: Programmierbare ODER Matrix glaube ich. Umgekehrt, auf jeden Fall, der PROM
Und: dann ist das halt ein CPLD - ein complex Programmable Logic Device - und das hat 1000 Gatter und ein FPGA 1000000 Gatter.
Und mit VHDL bringen sie die Schaltung an. Und das ist nicht schwer. Weil sie können jedes Teil in der Digitaltechnik durch durch NOT, AND OR darstellen.
Dann müssen sie VHDL können.
Das ist nicht schwer. Weil: Sie müssen wissen
Header
Entity
Architecture.
Entity legt die Signale rein und raus fest. Und Architecture die Schaltung vom Element. Nicht anders, als mit AND und OR
Gut. Und dann haben sie ihren Prozessor. Was sie jetzt können müssen ist eine Programmiersprache selber schreiben
Und eine Programmiersprache.
Ich wurde gerade auf Facebook gesperrt - für 24h, weil ich mich nicht an die Gemeinschaftsstandards halte. Warum? Weil ich das hier poste. Keine Sorge, ich bin nicht dauerhaft auf Facebook gesperrt, 24h. Und nicht richtig gesperrt, nur nichts posten, wegen dem Spam. Ich habe die Funktion zu oft genutzt. Zu schnell etwas zu posten. Oder sie haben den Zusammenhang, zwischen fpga und aussagenlogik nicht verstanden. Darauf will ich ja hinaus. Für Info brauchen sie diese zwei Dinge.
Ich wollte erklären. Was das mit Algebra zu tun hat, mit Ausdruck und Ausdrucksform und Aussage, und warum man das braucht. Wenn das so ist.
Also, ich erkläre das jetzt mal langsam.
Sie haben in der Mathematik, einerseits, die Geometrie. Und die Algebra.
Und: Zunächst, bei den Griechen, war das getrennt. Die Geometrie gehörte nicht zur Algebra.
Danke, das bisher gesagte, weiss ich auswendig. Das heisst, ich habe es auswendig gelernt. Warum sage ich das?
Die Informatik hat zwei wichtige Teile
Den Prozessor
Den Compiler
Der Prozessor, der MIPS ist schnell verstanden. Mit VHDL und FPGA lässt er sich auf eine Schaltung unterbringen. Für die Schaltung kann Elektrotechnik nicht schaden. Was ich über die Transistoren auswendig sagte, allerdings brauche ich das für den FPGA nicht. hier muss ich wissen, was CPLD ist. Schon kann ich die Schaltung auf dem FPGA unterbringen
Der zweite Teil ist der Compilerbau, für die Programmiersprachen. Hier muss ich Bakus-Naurr-Form wissen und was in der Mathematik ein Ausdruck und eine Aussage ist
Und zu Algebra gehört:
Ich sage jetzt mal so: Die Entwicklung der Mathematik dauerte lange. Ich habe hier mal eine Liste mit griechischen Mathematikern.
Ionische Periode
Thales
Pythagoras
Anaxagoras
Demokrit
Hippokrates
Theodoros
Athenische Periode
Sophisten
Platon
Aristoteles
Theaitetos
Eudoxos von Knidos
Menaichmos
Deinostratos
Autolykos von Pitane
Alexandrinische Periode
Euklides
Aristarchos
Archimedes
Erathostenes
Nikomedes
Appollonios
Sp"atzeit
Hipparchos
Menelaos
Heron von Alexandria
Ptolemäus
Diophant von Alexandrien
Pappos
Die habe ich aus https://www.wikipedia.de. Und: Die Mathematik war am Anfang noch nicht so, wie wir sie heute haben. Heute kennen wir Ausdrücke, wie
Code: Select all
an*xn+a[n-1]*x[n-1]+...a1x1+a0
Und wir kennen Gleichungen wie
Code: Select all
ax+b=0
Wir wisse, dass eine Gleichung nichts anderes ist als eine Aussage, oder eine Aussagenform. Letzteres ist eine Aussagenform, schlussendlich, nicht einfach eine Aussage - wobei wir das beim Programmieren nicht unterscheiden. Für uns bleibt lediglich zu tun,
Code: Select all
x
Die Griechen hatten noch keine derartig entwickelte Mathematik.
Sie hatte zwei Zweige.
Geometrie
Algebra
Später spielten für die Algebra, die Araber eine grosse Rolle. Dazu gehören:
Al-Chwarizmi - Frühzeit: 820 n. Chr. - Algorithmus
Al-dschabr wa'l muqabalah
Thabit ibn Qurra, al-Battani
al-Dschawhari, Abu l-Wafa.
al-Karadschi: Hochbl"ute:
Avicenna (Ibn Sina)
al-Bīrūnī; Ibn al-Haitham (Alhazen)
Omar Chayyām (um 1100)
Nasir al-Din al-Tusi
al-Kaschi (um 1400)
Das Wort Algebra und Algorithmus leitet sich aus dem Arabischen ab
Algebra bedeutet wir haben es mit Variablen, Konstanten Werten, Operatoren, Klammern und Gleichheitszeichen, Termen, Ausdrücken, Aussagen und so weiter zu tun
Algorithmus steht für das wiederholte anwenden von bestimmten Schritten. Das spielt zum Beispiel Rolle bei dem Algorithmus von Gauss zur Lösung von Matrizen. In der Fernuni Hagen. benutzt man nicht einfach den Schritt - im LGS - die Zeilen zu vertauschen. Man macht es Mathematisch noch korrekter. Man fasst ein LGS als eine Matrix auf und das Vertauschen von Zeilen, lässt sich über die Multiplikation mit Matrizen, etwa Einheitsmatrizen erreichen. Für den Mathematiker ist es wohl egal, in welcher Reihenfolge Gleichungen stehen
Doch: Schon dieses Vertauschen und das wiederholte anwenden, diese Zeilenumformungen, aber auch das Addieren von Konstanten werten zu einer Zeile, wird wiederholt angewendet. Das Gaussche Elemeninationsverfahren.
Algorithmus bezieht sich zunächst darauf, wiederholt Schritte an zu wenden. Das drückt man in der Programmierung mit der WHILE-Schleife aus
Code: Select all
WHILE ... DO
BEGIN
END;
[code]
[/list]
Dabei müssen entscheidungen getroffen werden, bei der Wiederholung, verfahren wir im nächsten Schritt so oder so.
Das
[code]
IF ... THEN
BEGIN
END
ELSE
BEGIN
END;
spielt dann eine Rolle. Der Algorithmus war ein Lösungsmittel - um zum Beispiel Gleichungen durch wiederholtes Anwenden von Schritten systematisch zu lösen.
Das Programm ist eng verwandt mit dem Algorithmus. Das Computerprogrammiert formuliert einen Algorithmus, der zunächst dazu da war, Gleichungen zu lösen.
Doch neuere Algorithmen beziehen sich wiederum auf die Auswertung, einerseits eines Arithmetischen Ausdruck, einer Gleichung, eines Terms. Oder eines Computerprogramms. Also der Algorithmus bezieht sich wieder auf ein Programm. Ein Term und eine Programmiersprache lässt sich nicht trennen. Wer Bakus-Naur-Form sagt, wird auch irgendwann
Code: Select all
WHILE ... DO
. Bzw. besonders umgekehrt.
Das zweite war die Geometrie. Beides lässt sich auf eine gemeinsame Form bringen, bis zu einem gewissen Grad, je nach wissen. Für die Griechen war das zunächst nicht bekannt, sie mussten diesen Gedanken erst entwickeln
Eine Deutsche Grammatik geht so:
Code: Select all
<Satz> ::= <Subjekt> <Prädikat> <Objekt> '.'
Diese Regel müssen wir zum Text erweitern:
Code: Select all
<Text> ::= <Satz> | <Satz> <Text>
<Satz> ::= <Subjekt> <Prädikat> <Objekt> '.'
Damit wir wissen, was ein
Code: Select all
<Subjekt>, <Prädikat>,<Objekt>
ist. Gilt
Code: Select all
<Subjekt> ::= <Substantiv in der entsprechenden Form>
<Prädikat> ::= <Verb in der entsprechenden Form>
<Objekt> ::= <Substantiv in der entsprechenden Form>
Um diesen diesen Ausdruck zu Parsen, brauchen wir zwei Funktionen in der Programmierung
Code: Select all
text () {
satz ();
if ... then text ();
}
satz () {
if (substantiv () ... )
if (prädikat () ...)
if (obeject ()...)
else error;; else error (); else error ();
}
Man sieht hier kann man eine Linksrekursion erzeugen:
Code: Select all
<Text> ::= <Text> <Satz> | <Satz>
<Satz> ::= <Subjekt> <Prädikat> <Objekt> '.'
In dem Falle ruft
Code: Select all
text()
immer wieder
Code: Select all
text()
auf. Das gilt auch für mathematische Ausdrücke.
Bei der einfachsten Form, taucht die Linksrekursion nicht auf:
Code: Select all
<expr> ::= <term> | <term> '+' <expr>
<term> ::= <factor> | <factor> '*' <term>
<factor ::= <num> | <id> | '('<expr>')'
Sollte sie das tun, brauchen wir eine erweiterte Form, mit 5 Zeilen, die ich nicht auswendig kenne
Worum es jetzt geht, ist Mathematik
Denn wir kennen aus der Programmierung, die Worte
Code: Select all
Ausdruck, Expression, Aussage, ...
Dies bezieht sich auf die Mathematik. Die gleichung
Code: Select all
x*9 = 10*y
ist in Wirklichkeit eine Aussagenform. Das möchte ich genauer machen, mit hilfe der Mathematik. Später jetzt muss ich zur Mutter.
Also, in der Mathematik müssen wir wissen, was ein Term ist. Ein Term ist etwas, wie
Code: Select all
(3*x+2)/(4+(x+3)*4)
Grammatisch richtig ist das nicht. Grammatisch unterscheiden wir
Code: Select all
Ausdruck
Term
Faktor
Trotzdem: Nun unterscheiden wir bei Termen, zum Beispie
Bruchterme
Polynome
Exponentialterme
Sie haben die gewohnte Form. In der Programmierung finden wir lauter solche Terme, einerseits bei der Zuweisung eines Wertes eines Ausdrucks an eine Variable, oder bei einer Aussage
Code: Select all
b:=(a+1)
if (b == a) ...
Eine Gleichung ist wiederum eine Verknüpfung zweier Terme über ein Gleichheitszeichen
Code: Select all
T1 = T2
oder
Code: Select all
T1 == T2
Eine Gleichung ist wiederum eine Aussage. Sie ist entweder
Code: Select all
wahr
oder
Code: Select all
falsch
Wir müssen unterscheiden, zwischen
Aussagen
Aussagenformen
Aussagen: Eine Gleichung bei der keine Variablen auftauchen
Aussagenformen: Eine Gleichung bei der Variablen auftauchen
Was uns bei
Code: Select all
if x == 5 then ...
begegnet, ist als
Code: Select all
x == 5
Eine Aussagenform. Aussagen sind entweder
Code: Select all
WAHR
oder
Code: Select all
FALSCH
Somit lassen sich Aussagen miteinander logisch verknüpfen. Damit ist die Aussagenlogik geboren
Code: Select all
Aussage1 UND Aussage2
Aussage1 ODER Aussage2
NICHT Aussage
Da unsere Aussagen in Wirklichkeit Gleichungen sind, steht da:
Code: Select all
(x==5) UND (y==(6+1))
(x==5) ODER (y==(6+1))
NICHT (y==(6+1))
da eine Aussage
Code: Select all
WAHR
oder
Code: Select all
FALSCH
sein kann, lautet die Vorschrift
Code: Select all
WAHR UND WAHR ::= WAHR
WAHR UND FALSCH ::= FALSCH
FALSCH UND WAHR ::= FALSCH
FALSCH UND FALSCH ::= FALSCH
das ist allerdings keine Boolesche Algebra. Es bezieht sich darauf ob die Aussagen
Code: Select all
5 == 6
oder
Code: Select all
5 == 5
Code: Select all
WAHR
oder
Code: Select all
FALSCH
sind
Die Boolsche Logik ersetzt das ohne Aussagen durch Werte
Ein Compiler ist schnell gemacht. Ich stelle einen von mir in Python und in JavaScript vor.
Ein mit Node ausgeführter - Backus-Naur Parser in JavaScript
Code: Select all
/*
expr ::= expr + term | term
term ::= term * factor | factor
factor ::= '(' expr ')' | const
Bzw.
expr ::= term | term '+' expr
term ::= factor | factor '*' term
factor ::= '(' expr ')' | const
const ::= '9', '8', ..., '0'
*/
/* Lexer */
let i = 0;
let s = "((4+5*(4+2))+1)*3";
function nexttoken () {
return s [i++];
}
function tokenback () {
i--;
}
function expr () {
let x;
let y = 0;
x = term ();
if (nexttoken () == '+') {
y = expr ();
}
else
tokenback ();
return x + y;
}
function term () {
let x;
let y = 1;
x = factor ();
if (nexttoken () == '*')
y = term ();
else
tokenback ();
return x * y;
}
function factor () {
let s = nexttoken ();
let x1 = parseInt (s);
let x;
if (s == '(') {
x = expr ();
if (nexttoken () != ')')
throw new Error("Missing closing bracket");
}
else if ((x1 >= 0) && (x1 <= 9))
x = x1;
else
throw new Error("Unknown or wrong character");
return x;
}
console.log (expr ());
console.log (((4+5*(4+2))+1)*3);
Sorry, dass das so lange gedauert hat, eine Variable war falsch benannt
Code: Select all
# expr ::= expr + term | term
# term ::= term * factor | factor
# factor ::= '(' expr ')' | const
# Bzw.
# expr ::= term | term '+' expr
# term ::= factor | factor '*' term
# factor ::= '(' expr ')' | const
# const ::= '9', '8', ..., '0'
i=0
s = "((4+5*(4+2))+1)*3";
def nexttoken ():
global i
j = i
if i >= len(s):
return 'e'
i = i+1
return s[j]
def tokenback ():
global i
i = i-1
def expr ():
y = 0
x = term()
s = nexttoken ()
if s == '+':
y = expr()
elif s == 'e':
return x+y
else:
tokenback()
return x+y
def term ():
y = 1
x = factor()
s = nexttoken ()
if s == '*':
y = term ()
elif s == 'e':
return x*y
else:
tokenback()
return x*y
def factor ():
s = nexttoken ()
if s.isdigit ():
y = int(s)
if s == '(':
x = expr()
if nexttoken () != ')':
exit ()
elif s == 'e':
return 0
elif (y >= 0) and (y <= 9):
x = y
else:
exit ()
return x
print(expr())
Diese Compiler habe ich selber geschrieben, entsprechend der Bakus-Naur Normalform ohne Linksrekursion - parsen sie arithmetische Terme. Zu Aussagen, kommen wir schnell - indem wir das
Code: Select all
==
zeichen nehmen, auch zu
Code: Select all
WHILE ... DO
