https://www.davidvajda.de/viewtopic.php?t=79&start=1
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:
<Satz> ::= <Subjekt> <Prädikat> <Objekt>
Das
<Subjekt>
ist genauso wie
<Objekt>
durch jedes beliebige Substantiv in der richtigen Form zu ersetzen. Das selbe gilt für
<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
x*((10+y)+2)*3
Gut:
Das hat auch eine Grammatik. Die geht so:
<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
E = U/d
C = A/d
E, B, H, D
Oder auch nicht. Widerstände, Kondensatoren, Spulen müssen sitzen.
Sie sind aber nicht unbedingt Teil der technischen Informatik
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
0,1
nichts über Signale wissen
Natürlich wäre es gut Transistoren zu kennen, weil
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
E, B, C
, sondern der hat
Source, Quelle
Drain, Tor
Gate, Tor
Bulk
Das ist der FET
Und da gibt es den
MISFET
MESFET
MOSFET
JFET
IGFET
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
74xx
Und dabei steht zum Beispiel glaube
04
hinten dran, für
OR
, oder
NOR
oder
NOT
. der
01
ist wichtig. Ich glaube
7483
ist Addierer. Und so.
Nur, da brauchen sie gar keine Elektrotechnik. Sie müssen wissen, was
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:
A, B, C
Sie haben die Eingänge
A
und
B
und den Ausgang
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
AND
. Und das geht kommt bei
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
VCC
ist und was
GND
ist - nämlich
VCC
auch
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 ODER-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
an*xn+a[n-1]*x[n-1]+...a1x1+a0
Und wir kennen Gleichungen wie
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,
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
WHILE ... DO
BEGIN
END;
Dabei müssen entscheidungen getroffen werden, bei der Wiederholung, verfahren wir im nächsten Schritt so oder so.
Das
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
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:
<Satz> ::= <Subjekt> <Prädikat> <Objekt> '.'
Diese Regel müssen wir zum Text erweitern:
<Text> ::= <Satz> | <Satz> <Text>
<Satz> ::= <Subjekt> <Prädikat> <Objekt> '.'
Damit wir wissen, was ein
<Subjekt>, <Prädikat>,<Objekt>
ist. Gilt
<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
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:
<Text> ::= <Text> <Satz> | <Satz>
<Satz> ::= <Subjekt> <Prädikat> <Objekt> '.'
In dem Falle ruft
text()
immer wieder
text()
auf. Das gilt auch für mathematische Ausdrücke.
Bei der einfachsten Form, taucht die Linksrekursion nicht auf:
<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
Ausdruck, Expression, Aussage, ...
Dies bezieht sich auf die Mathematik. Die gleichung
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
(3*x+2)/(4+(x+3)*4)
Grammatisch richtig ist das nicht. Grammatisch unterscheiden wir
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
b:=(a+1)
if (b == a) ...
Eine Gleichung ist wiederum eine Verknüpfung zweier Terme über ein Gleichheitszeichen
T1 = T2
oder
T1 == T2
Eine Gleichung ist wiederum eine Aussage. Sie ist entweder
wahr
oder
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
if x == 5 then ...
begegnet, ist als
x == 5
Eine Aussagenform. Aussagen sind entweder
WAHR
oder
FALSCH
Somit lassen sich Aussagen miteinander logisch verknüpfen. Damit ist die Aussagenlogik geboren
Aussage1 UND Aussage2
Aussage1 ODER Aussage2
NICHT Aussage
Da unsere Aussagen in Wirklichkeit Gleichungen sind, steht da:
(x==5) UND (y==(6+1))
(x==5) ODER (y==(6+1))
NICHT (y==(6+1))
da eine Aussage
WAHR
oder
FALSCH
sein kann, lautet die Vorschrift
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
5 == 6
oder
5 == 5
WAHR
oder
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
/*
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
# 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
==
zeichen nehmen, auch zu
WHILE ... DO
