|
Fachbereich 2 Studiengang: Ing.Informatik Dozent: Döben-Henisch |
|
|
Prozessrechner - Übungsaufgabe Nr.3 - Lösungsbeispiel zum Parser |
|
|
Letzte
Änderung: 21.Mai 2004
Seite |
Die Teilaufgabe hatte gelautet: Auf welche Weise könnten sie komplexe Systeme so beschreiben, dass ein Computerprogramm diese Beschreibung lesen und berechnen könnte? Geben Sie eine abstrakte Beschreibung solch eines Computerprogramms....
Man kann diese Teilaufgabe so verstehen, dass es in der realen Welt irgndeine konkrete Anlage entweder gibt oder geben soll, deren Zuverlässigkeit R(t) für einen bestimmten Zeitraum t berechnet werden soll. Z.B. eine kleine Sortieranlage, die aus 5 Komponenten besteht: die Komponenten SORT sortiert Müll nach Nicht-Glas (D) und Glas (F). Innerhalb der Kategorie Glas F gibt es dann zwei weitere Komponenten F1 für weisse Flaschen und F2 für grüne Flaschen. Bei dem Nicht-Glas wird unterschieden zwischen Blech (D1) und Plastik (D2).
Eine mögliche Beschreibung dieser Anlage kann entweder mit einem Diagramm in Form eines Taskgraphen erfolgen oder mittels einer formalen Sprache. Im Idealfall sind beide Beschreibungsformen formal äquivalent, d.h. sie lassen sich ineinander 'verlustfrei' überführen.
Ziel ist es nun, ein Programm zu schreiben, das Beschreibungen beliebiger komplexer Systeme als Input nimmt und zu diesen als Output die Zuverlässigkeit liefert.
Programme, die Zeichenketten als Input bekommen und diese Zeichenketten bzgl. der in ihnen enthaltenen Informationen verarbeiten, sind in der Regel sogenannte Parser oder Compiler.
Man unterscheidet bei einem Compiler in der Regel drei Dimensionen: die
Ein Scanner bildet Zeichenketten auf Zeichenklassen (Kategorien) ab. Ein Parser ordnet erkannte Zeichenklassen bestimmten syntaktischen Regeln zu, durch die die ursprünglichen lexikalischen Klassen auf syntaktische Klassen reduziert werden. In Abhängigkeit von den aktivierten syntaktischen Regeln können dann nach Bedarf unterschiedliche semantische Aktionen ausgelöst werden. Dies sei an einem Beispiel demonstriert.
Nehmen wir die Sortiermaschine aus dem Diagramm. Eine mögliche Darstellung wäre laut Vorlesung (siehe: Taskgraph und formale Sprache) die folgende:
SORT-> ( (F1 -> F2) || (D1 -> D2))
Diese Zeichenkette beschreibt ein komplexes System bestehend aus einzelnen Komponenten {SORT, F1, F2, D1, D2} sowie Metazeichen {(, ), ->, ||}, die festlegen, wie diese Komponenten angeordnet sind. In diesem Beispiel koennte man also z.B. annehmen, dass es einen Scanner gibt, der erkennt, ob bestimmte Zeichen zu einer dieser Zeichenklassen gehören.
Eine Möglichkeit, Scanner zu erzeugen, ist die Benutzung eines Scannergenerators wie flex. Ein einfaches Beispielprogramm wäre das folgende:
/********************************
*
* ii-prt-ex3-flexscanner.l
*
* Scanner for complex systems
*
* Standalone Test Version
*
* author: gerd doeben-henisch
* first: may-21, 2004
* last: may-21, 2004
*
**************************************
*
* Which kinds of tokens are needed?
*
* COMPONENTS <---------> {Names of Components}
* METASIGNS <-----------> {(,),->,|| }
*
***********************************************/
%{
#include <stdio.h>
%}
LB "("
RB ")"
NEWLINE ['\n''\r']+
VARNAME [A-Z]+[a-zA-Z_0-9]*
SEQU [\-]>
PAR "||"
%%
[ \t] ;
{LB} { printf( "LB: %s\n", yytext ); }
{RB} { printf( "RB: %s\n", yytext ); }
{SEQU} {printf( "SEQUENCE: %s \n", yytext); }
{PAR} {printf( "PARALLEL: %s \n", yytext); }
{VARNAME} {printf( "VARNAME: %s \n", yytext); }
{NEWLINE} {printf( "NEWLINE: %s \n", yytext); }
%%
int main( int argc, char **argv ) {
++argv;
--argc; /* skip over program name */
if ( argc > 0 ){
yyin = fopen( argv[0], "r" ); }
else {
yyin = stdin; }
yylex();
}
Um den Scanner zu kompilieren, erzeugt man erst aus der Spezifikationsdatei ii-prt-ex3-flexscanner.l mit flex automatisch eine C-Datei mit dem namen lex.yy.c. Diese wird dann ganz normal kompiliert, allerdings hier mit der Bibliothek -lfl von flex:
gerd@kant:~/public_html/fh/II-PRT/II-PRT-EX/EX3> flex ii-prt-ex3-flexscanner.l gerd@kant:~/public_html/fh/II-PRT/II-PRT-EX/EX3> gcc -o ii-prt-ex3-flexscanner lex.yy.c -lfl
Wendet man den Scanner auf das Beispiel an, dann bekommt man folgende Ausgaben:
gerd@kant:~/public_html/fh/II-PRT/II-PRT-EX/EX3> ./ii-prt-ex3-flexscanner test.txt LB: ( VARNAME: SORT SEQUENCE: -> LB: ( LB: ( VARNAME: F1 SEQUENCE: -> VARNAME: F2 RB: ) PARALLEL: || LB: ( VARNAME: D1 SEQUENCE: -> VARNAME: D2 RB: ) RB: ) RB: ) NEWLINE:
Man sieht, dass der Scanner alle geforderten Zeichenklassen erkennt. Was er noch nicht kann, das ist den korrekten Zusammenhang der Zeichen zu erkennen. Dazu benoetigt man noch eine Grammatik, die von einem Parser geprüft werden soll. Zum Bau eines Parsers benutzt man in der Regel auch einen Parsergenerator, wie z.B. bison. Ein Beispiel wäre das folgende:
/***********************+
*
* ii-prt-ex3-bisonparse.y
*
*************************/
%{
#include <stdio.h>
#include <stdlib.h>
extern int yylex();
extern FILE* yyin;
extern void yyerror(const char *);
%}
%token NEWLINE LB RB SEQ PAR VAR
%%
system: /* empty */
| VAR NEWLINE
| LB exp SEQ exp RB NEWLINE { printf("bison: SYSTEM SEQ \n"); }
| LB exp PAR exp RB NEWLINE { printf("bison: SYSTEM PAR \n"); }
;
exp: VAR
| LB exp SEQ exp RB { printf("bison: SYSTEM SEQ \n"); }
| LB exp PAR exp RB { printf("bison: SYSTEM PAR \n"); }
;
%%
int main( int argc, char **argv ) {
FILE* yyin;
extern int yydebug;
++argv;
--argc; /* skip over program name */
if ( argc > 0 ){
yyin = fopen( argv[0], "r" ); }
else {
yyin = stdin; }
/* yydebug nur setzen, wenn benoetigt ! Zugleich '-t' benutzen */
/* yydebug=1; */
yyparse();
}
Der zugehörige Scanner mit flex muss leicht abgeändert werden:
/********************************
*
* ii-prt-ex3-flexscanner2.l
*
* Scanner for complex systems
*
* Test Version with bison
*
* author: gerd doeben-henisch
* first: may-21, 2004
* last: may-21, 2004
*
**************************************
*
* Which kinds of tokens are needed?
*
* COMPONENTS <---------> {Names of Components}
* METASIGNS <-----------> {(,),->,|| }
*
***********************************************/
%{
#include <stdio.h>
#include "ii-prt-ex3-bisonparse.tab.h"
%}
LB "("
RB ")"
NEWLINE "\n"
VARNAME [A-Z]+[a-zA-Z_0-9]*
SEQ [\-]>
PAR "||"
%%
[ \t] ;
{LB} { printf( "LB: %s\n", yytext ); return(LB); }
{RB} { printf( "RB: %s\n", yytext ); return(RB); }
{SEQ} {printf( "SEQUENCE: %s \n", yytext ); return(SEQ); }
{PAR} {printf( "PARALLEL: %s \n", yytext ); return(PAR); }
{VARNAME} {printf( "VARNAME: %s \n", yytext ); return(VAR); }
{NEWLINE} {printf( "NEWLINE: %s \n", yytext); return(NEWLINE); }
%%
void
yyerror (const char *s) /* called by yyparse on error */
{
printf ("%s\n", s);
}
Um diese Programme zu kompilieren empfiehlt sich schon der Einsatz eines Makefiles. Ein Beispiel eines einfachen Makefiles ist das folgende:
############################################################################# # Makefile for building: ii-prt-ex3-flexscanner.l+y # # Author: gerd doeben-henisch # first: may-21, 2004 # last: may-21, 2004 ############################################################################# ####### Compiler, tools and options CC = gcc CXX = g++ LEX = flex YACC = bison CFLAGS = -pipe -O2 -march=i586 -mcpu=i686 -DYYDEBUG -Wall -W -g CXXFLAGS = -pipe -O2 -march=i586 -mcpu=i686 -DYYDEBUG -Wall -W -g LEXFLAGS = YACCFLAGS= -d LIBS = -lfl ####### Output directory OBJECTS_DIR = ./ ####### Files HEADERS = C-SOURCES = lex.yy.c ii-prt-ex3-bisonparse.tab.c F-SOURCES = ii-prt-ex3-flexscanner2.l B-SOURCES = ii-prt-ex3-bisonparse.y OBJECTS = lex.yy.o ii-prt-ex3-bisonparse.tab.o TARGET = ii-prt-ex3-systemparser $(TARGET): $(OBJECTS) $(CC) $(CFLAGS) -o $(TARGET) $(OBJECTS) $(LIBS) ii-prt-ex3-bisonparse.tab.c: $(B-SOURCES) $(YACC) $(YACCFLAGS) $(B-SOURCES) lex.yy.c: $(F-SOURCES) $(LEX) $(F-SOURCES) lex.yy.o: lex.yy.c $(CC) -c lex.yy.c ii-prt-ex3-bisonparse.tab.o: ii-prt-ex3-bisonparse.tab.c $(CC) -c ii-prt-ex3-bisonparse.tab.c clean: rm $(TARGET) $(OBJECTS) $(C-SOURCES)
Die Kompilierung ist dann sehr einfach:
gerd@kant:~/public_html/fh/II-PRT/II-PRT-EX/EX3> make -f Makefile-bison flex ii-prt-ex3-flexscanner2.l gcc -c lex.yy.c bison -d ii-prt-ex3-bisonparse.y gcc -c ii-prt-ex3-bisonparse.tab.c gcc -pipe -O2 -march=i586 -mcpu=i686 -DYYDEBUG -Wall -W -g -o ii-prt-ex3-systemparser lex.yy.o ii-prt-ex3-bisonparse.tab.o -lfl
Angewendet auf die Testdatei test.txt liefert das Programm dann:
gerd@kant:~/public_html/fh/II-PRT/II-PRT-EX/EX3> ./ii-prt-ex3-systemparser < test.txt LB: ( VARNAME: SORT SEQUENCE: -> LB: ( LB: ( VARNAME: F1 SEQUENCE: -> VARNAME: F2 RB: ) bison: SYSTEM SEQ <--- Parser erkennt eine Sequenz PARALLEL: || LB: ( VARNAME: D1 SEQUENCE: -> VARNAME: D2 RB: ) bison: SYSTEM SEQ <--- Parser erkennt eine Sequenz RB: ) bison: SYSTEM PAR <--- Parser erkennt eine Parallelität RB: ) NEWLINE: bison: SYSTEM SEQ <--- Parser erkennt ein System
Damit eröffnet sich die Möglichkeit, auch beliebig andere, natürlich auch komplexere, Beschreibungen einzugeben, z.B. die Beschreibung test-sys3.txt mit folgendem Text:
( SORT -> ( (F1 -> (Kk || Bb ) ) || (D1 -> (CCC || (Xy1 -> CV ) ) ) ) )
Wir erhalten:
gerd@kant:~/public_html/fh/II-PRT/II-PRT-EX/EX3> ./ii-prt-ex3-systemparser < test-sys3.txt LB: ( VARNAME: SORT SEQUENCE: -> LB: ( LB: ( VARNAME: F1 SEQUENCE: -> LB: ( VARNAME: Kk PARALLEL: || VARNAME: Bb RB: ) bison: SYSTEM PAR RB: ) bison: SYSTEM SEQ PARALLEL: || LB: ( VARNAME: D1 SEQUENCE: -> LB: ( VARNAME: CCC PARALLEL: || LB: ( VARNAME: Xy1 SEQUENCE: -> VARNAME: CV RB: ) bison: SYSTEM SEQ RB: ) bison: SYSTEM PAR RB: ) bison: SYSTEM SEQ RB: ) bison: SYSTEM PAR RB: ) NEWLINE: bison: SYSTEM SEQ
Damit wurde das Ziel der Aufgabenstellung schon fast erreicht; beliebig komplexe Systemstrukturen werden von dem Parserprogramm erfasst. Was jetzt nocht fehlt, das ist die Eingabe von Fehlerraten lambda für jede einzelne Komponente, so dass zum Schluss die Zuverlässigkeit R(t) für das gesamte System ermittelt werden kann.
Der erste Schritt zu einer erweiterten Lösung ist wieder ein kleines Testprogramm mit einem erweiterten Scanner, der bei jedem Systemnamen jetzt auch eine Wertangabe erkennen kann, zum Beispiel:
/********************************
*
* ii-prt-ex3-flexscannerb.l
*
* Scanner for complex systems
*
* Standalone Test Version
*
* author: gerd doeben-henisch
* first: may-21, 2004
* last: may-21, 2004
*
**************************************
*
* Which kinds of tokens are needed?
*
* COMPONENTS <---------> {Names of Components}
* COMP-VALUES <---------> {Values of Components [Number]}
* METASIGNS <-----------> {(,),->,|| }
*
***********************************************/
%{
#include <stdio.h>
%}
LB "("
RB ")"
LSB "\["
RSB "\]"
NEWLINE "\n"
VARNAME [A-Z]+[a-zA-Z_0-9]*
VALUE [0-9]+"."[0-9]+
SEQ [\-]>
PAR "||"
%%
[ \t] ;
{LB} { printf( "LB: %s\n", yytext ); }
{RB} { printf( "RB: %s\n", yytext ); }
{LSB} { printf( "LSB: %s\n", yytext ); }
{RSB} { printf( "RSB: %s\n", yytext ); }
{SEQ} {printf( "SEQUENCE: %s \n", yytext); }
{PAR} {printf( "PARALLEL: %s \n", yytext); }
{VARNAME} {printf( "VARNAME: %s \n", yytext); }
{VALUE} {printf( "VALUE: %s \n", yytext); }
{NEWLINE} {printf( "NEWLINE: %s \n", yytext); }
%%
int main( int argc, char **argv ) {
++argv;
--argc; /* skip over program name */
if ( argc > 0 ){
yyin = fopen( argv[0], "r" ); }
else {
yyin = stdin; }
yylex();
}
Die Kompilierung erfolgt wie im Beispiel zuvor.
flex ii-prt-ex3-flexscannerb.l gcc -c lex.yy.c gcc -o ii-prt-ex3-flexscannerb lex.yy.o -lfl
Eine erweiterte testdatei testb.txt könnte wie folgt aussehen:
( SORT[1.0] -> ( (F1[0.123] -> F2[0.234]) || (D1[4.23] -> D2[123.456]) ) )
Man erhält dann das Ergebnis:
gerd@kant:~/public_html/fh/II-PRT/II-PRT-EX/EX3/PARSER2> ./ii-prt-ex3-flexscannerb testb.txt LB: ( VARNAME: SORT LSB: [ VALUE: 1.0 RSB: ] SEQUENCE: -> LB: ( LB: ( VARNAME: F1 LSB: [ VALUE: 0.123 RSB: ] SEQUENCE: -> VARNAME: F2 LSB: [ VALUE: 0.234 RSB: ] RB: ) PARALLEL: || LB: ( VARNAME: D1 LSB: [ VALUE: 4.23 RSB: ] SEQUENCE: -> VARNAME: D2 LSB: [ VALUE: 123.456 RSB: ] RB: ) RB: ) RB: ) NEWLINE:
Im nächsten Schritt muss man die Werte der einzelnen Komponenten dem Parser übermitteln und dieser muss diese Werte entsprechend ihrem Auftreten im System lokal berechnen.
Zu diesem Zweck erstellen wir eine neue Testdatei testb1.txt, die nun neben den Komponentennamen auch Werte für Lambda enthält:
( SORT[0.000011] -> ( (F1[0.00022] -> F2[0.00033]) || (D1[0.00044] -> D2[0.00055]) ) )
Die Werte für Lambda sind in den eckigen Klammern als Fliesskommazahlen eingetragen.
Die zugehörige flex-Scannerdatei ii-prt-ex3-flexscannerb3.l sieht wie folgt aus:
/********************************
*
* ii-prt-ex3-flexscannerb3.l
*
* Scanner for complex systems
*
* Test Version cooperating with bison
*
* author: gerd doeben-henisch
* first: may-21, 2004
* last: may-21, 2004
*
**************************************
*
* Which kinds of tokens are needed?
*
* COMPONENTS <---------> {Names of Components}
* COMP-VALUES <---------> {Values of Components [Number]}
* METASIGNS <-----------> {(,),->,|| }
*
***********************************************/
%{
#include <stdio.h>
#include <math.h>
#include "ii-prt-ex3-bisonparseb2.tab.h"
%}
YYSTYPE yylval;
LB "("
RB ")"
LSB "\["
RSB "\]"
NEWLINE "\n"
VARNAME [A-Z]+[a-zA-Z_0-9]*
VALUE [0-9]+"."[0-9]+
SEQ [\-]>
PAR "||"
%%
[ \t] ;
{LB} { printf( "LB: %s\n", yytext ); return(LB); }
{RB} { printf( "RB: %s\n", yytext ); return(RB); }
{LSB} { printf( "LSB: %s\n", yytext ); return(LSB); }
{RSB} { printf( "RSB: %s\n", yytext ); return(RSB); }
{SEQ} {printf( "SEQUENCE: %s \n", yytext); return(SEQ); }
{PAR} {printf( "PARALLEL: %s \n", yytext); return(PAR); }
{VARNAME} {printf( "VARNAME: %s \n", yytext); return(VAR); }
{VALUE} {printf( "VALUE: %s \n", yytext); sscanf(yytext,"%f",&yylval); return(VAL); }
{NEWLINE} {printf( "NEWLINE: %s \n", yytext); return(NEWLINE); }
%%
void
yyerror (const char *s) /* called by yyparse on error */
{
printf ("%s\n", s);
}
Die entscheidende Zeile für die Weitergabe der konkreten Zahlenwerte ist die Zeile
{VALUE} {printf( "VALUE: %s \n", yytext); sscanf(yytext,"%f",&yylval); return(VAL); }
D.h. wenn in der Eingabe ein Pattern VALUE erkannt wird, dann wird dieser Wert aus yytext von String nach float konvertiert und als float-Zahl an die Variable yylval übergeben. Über diese Variable steht der Wert dann in der übergeordneten Routine yyparse() im bison-Parser zur Verfügung.
Das bison-Parserprogramm sieht wie folgt aus:
/***********************+
*
* ii-prt-ex3-bisonparseb2.y
*
*************************/
%{
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
extern int yylex();
extern void yyerror(const char *);
double time;
%}
%union { float real; }
%token NEWLINE LB RB LSB RSB <real>VAL SEQ PAR VAR
%type <real>exp system
%%
system: system NEWLINE
| VAR LSB VAL RSB NEWLINE { printf("bison: SYSTEM up VAR \n"); $$=exp(-$3*time);
printf("sys var up val = %g %g\n", $$, $3);
}
| LB exp SEQ exp RB NEWLINE { printf("bison: SYSTEM up SEQ \n"); $$=$2*$4;
printf("sys seq up val = %g %g = %g \n", $2, $4, $$);
}
| LB exp PAR exp RB NEWLINE { printf("bison: SYSTEM up PAR \n"); $$=1-(1-$2)*(1-$4);
printf("sys par up val = %g %g = %g \n", $2, $4, $$ );
}
;
exp: VAR LSB VAL RSB { printf("bison: SYSTEM VAR \n"); $$=exp(-$3*time);
printf("sys var val = %g = %g \n", $$,$3 );
}
| LB exp SEQ exp RB { printf("bison: SYSTEM SEQ \n");
$$=$2*$4;
printf("sys seq val = %g %g = %g \n", $2, $4, $$);
}
| LB exp PAR exp RB { printf("bison: SYSTEM PAR \n");
$$=1-(1-$2)*(1-$4);
printf("sys par val = %g %g = %g \n", $2, $4, $$);
}
;
%%
int main( int argc, char **argv ) {
extern int yydebug;
extern double time;
++argv;
--argc; /* skip over program name */
if ( argc > 0 ){
time = (double)atof(argv[0]);
}
else {
if (time == 0){time = 1000;}
}
printf("Time Value = %lf \n",time);
/* yydebug nur setzen, wenn benoetigt ! Zugleich '-t' benutzen */
/* yydebug=1; */
/* lambda_sum = 0; */
yyparse();
}
Diese Version enthält gegenüber den bisherigen Programmen einige Besonderheiten. So muss man z.B. für diejenigen Vaiablen, deren Werte einen bestimmten Typ --in unserem Fall 'double'-- haben sollen, als solche kennzeichnen. Dies geschieht in 3 Schritten:
Der neue Datentyp muss explizit mit 'union' eingeführt werden
Jedes Token, das vom Scanner geliefert wird und das diesen neuen Datentyp liefert, muss mit dem Typ gekennzeichnet werden
Ferner müssen auch alle Variablen des bison-Parsers --die 'types'-- gekennzeichnet werden, die diesen Datentyp benutzen:
%union { float real; }
%token NEWLINE LB RB LSB RSB <real>VAL SEQ PAR VAR
%type <real>exp system
Mittels der speziellen Variablen $1, $2, ... kann man dann auf die Werte der einzelnen Regeln zugreifen. Mittels der ariablen '$$' kann man diese Werte dann dem internen Auswertungsmechanismus des Parsers bekannt machen. Wenn also an einer stelle eine Variable mit einem double-Wert über die Variable $3 erkannt wird, dann führt die Zuweisung des Wertes an $$ dazu, dass die Variable mit diesem Wert in der Auswertung verknüpft wird. Gleichzeitig wird bei dieser Gelegenheit die Umwandlung des Lambda-Wertes in den Zuverlässigkeitswert R(t) vorgenommen. Der Wert time für den Auswertungszeitraum kann bei Aufruf des Programms übergeben werden.
Dort, wo sequentielle oder parallele Muster erkannt werden, da werden dann die Werte der beteiligten Komponenten nach der jweiligen Berechnungsformel (siehe für sequentielle Anordnung und für parallele Anordnung) berechnet werden.
Der main()-Teil wurde so erweitert, dass man jetzt per Kommandozeile die Zeitdauer (mit Variable 'time') eingeben kann. Gibt man nichts ein wird die Zeitdauer defaultmaessig auf 1000 Einheiten gesetzt.
Das zugehörige Mkefile Makefile-bisonb2 sieht wie folgt aus:
############################################################################# # Makefile for building: ii-prt-ex3-flexscannerb2.l+y # # Author: gerd doeben-henisch # first: may-21, 2004 # last: may-21, 2004 ############################################################################# ####### Compiler, tools and options CC = gcc CXX = g++ LEX = flex YACC = bison CFLAGS = -pipe -O2 -march=i586 -mcpu=i686 -DYYDEBUG -Wall -W -g CXXFLAGS = -pipe -O2 -march=i586 -mcpu=i686 -DYYDEBUG -Wall -W -g LEXFLAGS = YACCFLAGS= -d LIBS = -lfl -lm ####### Output directory OBJECTS_DIR = ./ ####### Files HEADERS = C-SOURCES = lex.yy.c ii-prt-ex3-bisonparseb2.tab.c F-SOURCES = ii-prt-ex3-flexscannerb3.l B-SOURCES = ii-prt-ex3-bisonparseb2.y OBJECTS = lex.yy.o ii-prt-ex3-bisonparseb2.tab.o TARGET = ii-prt-ex3-systemparserb1 $(TARGET): $(OBJECTS) $(CC) $(CFLAGS) -o $(TARGET) $(OBJECTS) $(LIBS) ii-prt-ex3-bisonparseb2.tab.h: $(B-SOURCES) $(YACC) $(YACCFLAGS) $(B-SOURCES) ii-prt-ex3-bisonparseb2.tab.c: $(B-SOURCES) $(YACC) $(YACCFLAGS) $(B-SOURCES) lex.yy.c: $(F-SOURCES) $(LEX) $(F-SOURCES) lex.yy.o: lex.yy.c $(CC) -c lex.yy.c ii-prt-ex3-bisonparseb2.tab.o: ii-prt-ex3-bisonparseb2.tab.c $(CC) -c ii-prt-ex3-bisonparseb2.tab.c clean: rm $(TARGET) $(OBJECTS) $(C-SOURCES)
Hier zwei Beispiele der Anwendung.
Das erste Beispiel nimmt als Input die Beschreibung testb1.txt:
( SORT[0.000011] -> ( (F1[0.00022] -> F2[0.00033]) || (D1[0.00044] -> D2[0.00055]) ) )
gerd@kant:~/public_html/fh/II-PRT/II-PRT-EX/EX3/PARSER2> ./ii-prt-ex3-systemparserb1 < testb1.txt Time Value = 1000.000000 LB: ( VARNAME: SORT LSB: [ VALUE: 0.000011 RSB: ] bison: SYSTEM VAR sys var val = 0.98906 = 1.1e-05 SEQUENCE: -> LB: ( LB: ( VARNAME: F1 LSB: [ VALUE: 0.00022 RSB: ] bison: SYSTEM VAR sys var val = 0.802519 = 0.00022 SEQUENCE: -> VARNAME: F2 LSB: [ VALUE: 0.00033 RSB: ] bison: SYSTEM VAR sys var val = 0.718924 = 0.00033 RB: ) bison: SYSTEM SEQ sys seq val = 0.802519 0.718924 = 0.57695 PARALLEL: || LB: ( VARNAME: D1 LSB: [ VALUE: 0.00044 RSB: ] bison: SYSTEM VAR sys var val = 0.644036 = 0.00044 SEQUENCE: -> VARNAME: D2 LSB: [ VALUE: 0.00055 RSB: ] bison: SYSTEM VAR sys var val = 0.57695 = 0.00055 RB: ) bison: SYSTEM SEQ sys seq val = 0.644036 0.57695 = 0.371577 RB: ) bison: SYSTEM PAR sys par val = 0.57695 0.371577 = 0.734145 RB: ) NEWLINE: bison: SYSTEM up SEQ sys seq up val = 0.98906 0.734145 = 0.726114
Das zweite Beispiel benutzt als Input das Beispiel von [STOREY 1996:173ff]. Die Lambda-Werte wurden aus den Zuverlässigkeitswerten bezogen auf die Zeit von 1000 Einheiten interpoliert. Die beschreibung lautet (testb3.txt):
(
M1[0.00001]
->
(
(
(
(
M2[0.000223] || M3[0.000223]
)
||
M4[0.000223]
)
->
(
(
M5[0.000105] -> M7[0.000051]
)
||
(
M6[0.000105] -> M8[0.000051]
)
)
)
||
M9[0.000062]
)
)
Als Ausgabe ergibt sich:
gerd@kant:~/public_html/fh/II-PRT/II-PRT-EX/EX3/PARSER2> ./ii-prt-ex3-systemparserb1 1000 < testb3.txt Time Value = 1000.000000 LB: ( VARNAME: M1 LSB: [ VALUE: 0.00001 RSB: ] bison: SYSTEM VAR sys var val = 0.99005 = 1e-05 SEQUENCE: -> LB: ( LB: ( LB: ( LB: ( VARNAME: M2 LSB: [ VALUE: 0.000223 RSB: ] bison: SYSTEM VAR sys var val = 0.800115 = 0.000223 PARALLEL: || VARNAME: M3 LSB: [ VALUE: 0.000223 RSB: ] bison: SYSTEM VAR sys var val = 0.800115 = 0.000223 RB: ) bison: SYSTEM PAR sys par val = 0.800115 0.800115 = 0.960046 PARALLEL: || VARNAME: M4 LSB: [ VALUE: 0.000223 RSB: ] bison: SYSTEM VAR sys var val = 0.800115 = 0.000223 RB: ) bison: SYSTEM PAR sys par val = 0.960046 0.800115 = 0.992014 SEQUENCE: -> LB: ( LB: ( VARNAME: M5 LSB: [ VALUE: 0.000105 RSB: ] bison: SYSTEM VAR sys var val = 0.900325 = 0.000105 SEQUENCE: -> VARNAME: M7 LSB: [ VALUE: 0.000051 RSB: ] bison: SYSTEM VAR sys var val = 0.950279 = 5.1e-05 RB: ) bison: SYSTEM SEQ sys seq val = 0.900325 0.950279 = 0.855559 PARALLEL: || LB: ( VARNAME: M6 LSB: [ VALUE: 0.000105 RSB: ] bison: SYSTEM VAR sys var val = 0.900325 = 0.000105 SEQUENCE: -> VARNAME: M8 LSB: [ VALUE: 0.000051 RSB: ] bison: SYSTEM VAR sys var val = 0.950279 = 5.1e-05 RB: ) bison: SYSTEM SEQ sys seq val = 0.900325 0.950279 = 0.855559 RB: ) bison: SYSTEM PAR sys par val = 0.855559 0.855559 = 0.979137 RB: ) bison: SYSTEM SEQ sys seq val = 0.992014 0.979137 = 0.971317 PARALLEL: || VARNAME: M9 LSB: [ VALUE: 0.000062 RSB: ] bison: SYSTEM VAR sys var val = 0.939883 = 6.2e-05 RB: ) bison: SYSTEM PAR sys par val = 0.971317 0.939883 = 0.998276 RB: ) NEWLINE: bison: SYSTEM up SEQ sys seq up val = 0.99005 0.998276 = 0.988343 NEWLINE:
Hier noch die Ausgabe bei Eingabe der Werte time = 10000 und time = 10:
gerd@kant:~/public_html/fh/II-PRT/II-PRT-EX/EX3/PARSER2> ./ii-prt-ex3-systemparserb1 10000 < testb3.txt Time Value = 10000.000000 LB: ( VARNAME: M1 LSB: [ VALUE: 0.00001 RSB: ] bison: SYSTEM VAR sys var val = 0.904837 = 1e-05 SEQUENCE: -> LB: ( LB: ( LB: ( LB: ( VARNAME: M2 LSB: [ VALUE: 0.000223 RSB: ] bison: SYSTEM VAR sys var val = 0.107528 = 0.000223 PARALLEL: || VARNAME: M3 LSB: [ VALUE: 0.000223 RSB: ] bison: SYSTEM VAR sys var val = 0.107528 = 0.000223 RB: ) bison: SYSTEM PAR sys par val = 0.107528 0.107528 = 0.203495 PARALLEL: || VARNAME: M4 LSB: [ VALUE: 0.000223 RSB: ] bison: SYSTEM VAR sys var val = 0.107528 = 0.000223 RB: ) bison: SYSTEM PAR sys par val = 0.203495 0.107528 = 0.289142 SEQUENCE: -> LB: ( LB: ( VARNAME: M5 LSB: [ VALUE: 0.000105 RSB: ] bison: SYSTEM VAR sys var val = 0.349938 = 0.000105 SEQUENCE: -> VARNAME: M7 LSB: [ VALUE: 0.000051 RSB: ] bison: SYSTEM VAR sys var val = 0.600496 = 5.1e-05 RB: ) bison: SYSTEM SEQ sys seq val = 0.349938 0.600496 = 0.210136 PARALLEL: || LB: ( VARNAME: M6 LSB: [ VALUE: 0.000105 RSB: ] bison: SYSTEM VAR sys var val = 0.349938 = 0.000105 SEQUENCE: -> VARNAME: M8 LSB: [ VALUE: 0.000051 RSB: ] bison: SYSTEM VAR sys var val = 0.600496 = 5.1e-05 RB: ) bison: SYSTEM SEQ sys seq val = 0.349938 0.600496 = 0.210136 RB: ) bison: SYSTEM PAR sys par val = 0.210136 0.210136 = 0.376115 RB: ) bison: SYSTEM SEQ sys seq val = 0.289142 0.376115 = 0.10875 PARALLEL: || VARNAME: M9 LSB: [ VALUE: 0.000062 RSB: ] bison: SYSTEM VAR sys var val = 0.537944 = 6.2e-05 RB: ) bison: SYSTEM PAR sys par val = 0.10875 0.537944 = 0.588193 RB: ) NEWLINE: bison: SYSTEM up SEQ sys seq up val = 0.904837 0.588193 = 0.532219 NEWLINE:
gerd@kant:~/public_html/fh/II-PRT/II-PRT-EX/EX3/PARSER2> ./ii-prt-ex3-systemparserb1 10 < testb3.txt Time Value = 10.000000 LB: ( VARNAME: M1 LSB: [ VALUE: 0.00001 RSB: ] bison: SYSTEM VAR sys var val = 0.9999 = 1e-05 SEQUENCE: -> LB: ( LB: ( LB: ( LB: ( VARNAME: M2 LSB: [ VALUE: 0.000223 RSB: ] bison: SYSTEM VAR sys var val = 0.997772 = 0.000223 PARALLEL: || VARNAME: M3 LSB: [ VALUE: 0.000223 RSB: ] bison: SYSTEM VAR sys var val = 0.997772 = 0.000223 RB: ) bison: SYSTEM PAR sys par val = 0.997772 0.997772 = 0.999995 PARALLEL: || VARNAME: M4 LSB: [ VALUE: 0.000223 RSB: ] bison: SYSTEM VAR sys var val = 0.997772 = 0.000223 RB: ) bison: SYSTEM PAR sys par val = 0.999995 0.997772 = 1 SEQUENCE: -> LB: ( LB: ( VARNAME: M5 LSB: [ VALUE: 0.000105 RSB: ] bison: SYSTEM VAR sys var val = 0.998951 = 0.000105 SEQUENCE: -> VARNAME: M7 LSB: [ VALUE: 0.000051 RSB: ] bison: SYSTEM VAR sys var val = 0.99949 = 5.1e-05 RB: ) bison: SYSTEM SEQ sys seq val = 0.998951 0.99949 = 0.998441 PARALLEL: || LB: ( VARNAME: M6 LSB: [ VALUE: 0.000105 RSB: ] bison: SYSTEM VAR sys var val = 0.998951 = 0.000105 SEQUENCE: -> VARNAME: M8 LSB: [ VALUE: 0.000051 RSB: ] bison: SYSTEM VAR sys var val = 0.99949 = 5.1e-05 RB: ) bison: SYSTEM SEQ sys seq val = 0.998951 0.99949 = 0.998441 RB: ) bison: SYSTEM PAR sys par val = 0.998441 0.998441 = 0.999998 RB: ) bison: SYSTEM SEQ sys seq val = 1 0.999998 = 0.999998 PARALLEL: || VARNAME: M9 LSB: [ VALUE: 0.000062 RSB: ] bison: SYSTEM VAR sys var val = 0.99938 = 6.2e-05 RB: ) bison: SYSTEM PAR sys par val = 0.999998 0.99938 = 1 RB: ) NEWLINE: bison: SYSTEM up SEQ sys seq up val = 0.9999 1 = 0.9999 NEWLINE:
Die folgende Tabelle zeigt die Zuverlässigkeitswerte des Systems aus testb3.txt in Abhängigkeit von der Zeitdauer. Man kann sehen, dass der sehr gute Wert von 99.9% - 98.8% bis 1000 Einheiten sich gut hält, dann aber dramatisch abfällt.
| TIME | RELIABILITY R(t) |
| 10 | 0.9999 |
| 100 | 0.998999 |
| 1000 | 0.988343 |
| 10.000 | 0.532219 |
| 100.000 | 0.000746586 |