Formales System (Informatik)
In der theoretischen Informatik dienen formale Systeme zur exakten Wiedergabe der inneren Logik eines Systems. Formale Sprachen, die aus einem Alphabet von Symbolen und zughörigen Worten als Symbolketten bestehen, sind ein Hilfsmittel hierzu. Die Syntax wird durch eine zugehörige Grammatik festgelegt, über die die Gültigkeit der Worte festgestellt werden kann.
Definition der Syntax von Programmiersprachen
Ein Untersuchungsgegenstand hierzu ist die Möglichkeit einer Definition von realen Programmiersprachen über ein formales System. Als Beispiel mag hier der Aufruf von Unterprogrammen mit Parametern dienen. Die Syntax für die Unterprogrammdefinition und den Programmaufruf kann über eine formale Sprache und die zugehörige formale Grammatik definiert werden.
In der Sprache Pascal kann beispielsweise ein Unterprogramm über
PROCEDURE example(A, B: integer; VAR C: result); BEGIN .. END;definiert und später dann über
example(2*X,Y,W);aufgerufen werden.
Ein möglicher Ausschnitt der formalen Grammatik zur Syntaxdefinition in erweiterter Backus-Naur-Notation könnte dann sein:
procedure_declaration = PROCEDURE name '(' formal_parameter_list ')' block ';' block = BEGIN ... END formal_parameter_list = parameter { ';' parameter } ; parameter = [ VAR ] name ':' name ;Symbole sind hier procedure_declaration, identifier, formal_parameter_list, aber auch '(', ':', VAR usw. Eine Symbolkette auf der rechten Seite des Gleichheitszeichens wird, falls sie auftritt, durch das Symbol auf der linken Seite ersetzt. Die Symbolkette und damit das ersetzte Symbol kann wiederum Teil einer Symbolkette sein.... procedure_call = identifier '(' actual_parameter_list ')' ';' ; actual_parameter_list = expression { ',' expression } ;
Ein gegebener Programmtext ist syntaxfehlerfrei, wenn er durch die Umwandlungsregeln der formalen Grammatik auf ein einzelnes Symbol, z.B. program, reduziert werden kann.
Hätte man eine Sprache, die definiert wird durch
program = PROGRAM declarations program_block declarations = { procedure_declaration } program_block = BEGIN { procedure_call } END '.'so bestünde ein konkretes Programm nur aus Unterprogramm-Deklarationen und Aufrufen: Das reale Programm
PROGRAM PROCEDURE p1(a: integer; b: integer) BEGIN ... END; PROCDURE p2(VAR x: integer) BEGIN ... END; BEGIN p1(0,1); p2(y); END.könnte man mit obenstehendem (unvollständigen) Grammatikausschnitt reduzieren:
Schritt1:
PROGRAM PROCEDURE name(name: name; name: name) block; PROCEDURE name(VAR name: name) block; BEGIN name(expression,expression); name(expression); END.Schritt2:
PROGRAM PROCEDURE name(formal_parameter_list) block; PROCEDURE name(formal_parameter_list) block; BEGIN name(actual_parameter_list); name(actual_parameter_list); END.Schritt3:
PROGRAM procedure_declaration procedure_declaration BEGIN procedure_call procedure_call END.Schritt4:
PROGRAM declarations program_blockSchritt5:
programDas Programm ist damit syntaktisch korrekt. Es ist aber nicht die ganze Logik des Programms überprüft worden:
- Die Übereinstimmung der Namen wurde nicht überprüft (man hätte auch p3 statt p2 aufrufen können).
- Die Art der Parameterübergabe ist nicht definiert.
- Typüberprüfung findet nicht statt.
- ...