Quicklinks:
[Superzeichen, Terminale und Grammatik]
[Bedeutung der Operatoren]
[Syntaxüberprüfung]
[Code]
Superzeichen
{ DoExp (Axiom), DoLog, DoOr, DoXor,
DoAnd, DoPrimary, =, >, |, +, &, !, (, ) }
Terminale
{ a,b,c,d,e,f,g,h,i,j,k,l,0,1 }
Grammatik
DoExp |
=> |
DoLog | DoExp = DoLog |
DoLog |
=> |
DoOr | DoLog > DoOr |
DoOr |
=> |
DoXor | (DoOr | DoXor) |
DoXor |
=> |
DoAnd | DoXor + DoAnd |
DoAnd |
=> |
DoPrimary | DoAnd & DoPrimary |
DoPrimary |
=> |
Terminal | !DoPrimary |
Bedeutung der booleschen Operatoren
Da die im Schriftverkehr benutzten Zeichen nur schwer für mich zu
implementieren waren, benutze ich eine an C++ angelehnte Symbolik. Falls
dennoch Unklarheiten bestehen sollten, will ich hier für Klärung
sorgen:
= |
Äquivalenz, gleich |
> |
Implikation, wenn-dann |
| |
Disjunktion, oder |
+ |
Antivalenz, exklusiv-oder, entweder-oder |
& |
Konjunktion, und |
! |
Negation, nicht |
Letzterer ist der einzige unäre Operator und muss vor dem zu negierenden
Ausdruck stehen.
Syntaxüberprüfung
Die Syntaxüberprüfung arbeitet die Eingabe zeichenweise von links nach rechts durch und baut im wesentlichen auf den folgenden 5 Regeln auf:
- Leerzeichen werden entfernt,Groß-/Kleinschreibung ist egal
- Terminale sind in jedem Kontext erlaubt
- nach einem ! muß ein Terminal oder ein zweites ! folgen
- nach einem &, |, +, >, = muß ein Terminal oder ein ! folgen
- zu jeder schliessende Klammer muß eine öffnende vorangegangen sein
Code
Die Umsetzung im Quellcode erfolgt geradlinig nach der Top-Down-Methode.
Beispielhaft greife ich jetzt DoEqu heraus und gehe etwas ins Detail:
bool CParser::DoEqu(bool get)
{
// rekursiv absteigen
bool left = DoLog(get);
// gesamte Aussage durchsuchen und auswerten
for (;;)
// Aequivalenz gefunden ?
if (token==_EQU)
// ja, rekursiv absteigen und Aussage berechnen
left=(DoLog(true)==left);
else
// nein, also fertig
return left;
} |
Zuerst wird der linksseitige Wert der Aussage mit DoLog ermittelt. Dieser kann sich als zusammengesetzter Ausdruck übergeordneter Priorität, z.B. a|b, repräsentieren, kann aber auch ein einfaches Terminal darstellen. Sobald dieser Wert feststeht, durchläuft die Routine den noch verbleibenden Rest der Aussage, um den rechten Teil der Äquivalenzaussage zu ermitteln. Dabei kann es sich um Verkettungen dieser handeln, diese müssen dann wieder rekursiv ihre Teilterme bestimmen.
Sobald ein gültiger rechter Ausdruck erkannt wurde, muss dieser logisch mit der linksseitigen Aussage verknüpft werden. Falls keine rechtsseitigen Terme mehr auftauchen, bricht die Routine ab und liefert die Gesamtaussage der logisch äquivalent verknüpften Teilterme zurück.
Sollte der gesamte Term keine Äquivalenzausdrücke enthalten, so wird die Schleife nur ein einziges Mal durchlaufen, wobei keinerlei logischen Operationen stattfinden, sondern die linksseitig ermittelte Aussage zurückgegeben wird.
Diese Vorgehensweise zieht sich durch durch durch alle Funktionsauswertungen. Nur DoAnd macht eine Ausnahme, da ich statt a&b auch die kürzere Schreibweise ab zulasse. Dort erfolgt zusätzlich die Überprüfung, ob der rechtsseitige Ausdruck ein Terminal ist, dies ist ein sicheres Indiz für die Verwendung der Kurzschreibweise.
Hier folgt nun der komplette Quellcode des Parsers, er umfaßt ca. 500 Zeilen, wovon ein ziemlich großer Teil auf das Konto von Anmerkungen und Kommentaren geht:
Definitionen: Parser.h
// Parser.h: Schnittstelle für die Klasse CParser.
//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_PARSER_H__C38C8AEC_9836_11D3_BEA0_000021CC8458__INCLUDED_)
#define AFX_PARSER_H__C38C8AEC_9836_11D3_BEA0_000021CC8458__INCLUDED_
#if _MSC_VER >= 1000
#pragma once
#endif // _MSC_VER >= 1000
class CParser
{
public:
CString PassedFormat;
// true, wenn ein Fehler aufgetreten ist
int nMinVars;
// true fuer die benutzten Variablen an den jeweiligen Stellen
// ihres ASCII-Codes (stets Kleinbuchstaben !)
bool Vars[128];
// enthaelt alle benutzten Variablen als lueckenlose Zeichenkette
CString ActiveVars;
// Maximalzahl benutzter Variablen
enum { MaxVars = 12 };
// Definition aller zulaessigen Zeichen
enum Token { _AND='&', _OR='|', _XOR='+', _NOT='!', _EQU='=', _LOG='>',
_LB='(', _RB=')', _TRUE='1', _FALSE='0', _END=0,
_A='a', _B='b', _C='c', _D='d',
_E='e', _F='f', _G='g', _H='h',
_I='i', _J='j', _K='k', _L='l',
};
// Statuscodes nach der Formatierung
enum ErrorCodes { _OK, _NOTOKEN, _UNKNOWNTOKEN, _NOVARS, _VAREXPECTED,
_BRACKETEXPECTED, _BRACKETNOTALLOWED };
// bereitet Ausdruck auf die Auswertung vor, entfernt Leerzeichen
int Format(CString &Expression);
// berechnet Gesamtaussage des Ausdrucks fuer eine spezifische Variablenbelegung
bool Evaluate();
private:
// aktuell zu bearbeitendes Zeichen
Token token;
// durchlaeuft die Zeichen in der Aussage
int exprcount;
// Aussage
CString expression;
// ordnet "token" das naechste zu bearbeitende Zeichen zu
void GetToken();
// bearbeite Aequivalenzen
bool DoEqu(bool get);
// Implikationen
bool DoLog(bool get);
// Disjunktionen
bool DoOr(bool get);
// Antivalenzen
bool DoXor(bool get);
// Konjunktionen
bool DoAnd(bool get);
// Elementarbausteine bzw. geklammerte Ausdruecke
bool DoPrimary(bool get);
};
#endif // !defined(AFX_PARSER_H__C38C8AEC_9836_11D3_BEA0_000021CC8458__INCLUDED_) |
Implementation: Parser.cpp
////////////////////////////////////////////////////////////////
// Parser.cpp: Implementierung der Klasse CParser, ANSI-C++
//
// Autor: Stephan Brumme, stbrumme@gmx.de, www.stephan-brumme.de
//
// (C) 1999,2000 Alle Rechte vorhalten
// Die Distribution ist nur zu Demonstrations- und Lehrzwecken in
// unveraenderter Form mit Angabe des Autoren erlaubt.
// Jegliche kommerzielle Verbreitung/Verwendung ist ohne
// Einwilligung des Autoren verboten.
//
// History: Nov-Dez 1999 Erstellung
// 18.12.1999 Dokumentation
// 03.01.2000 deutlich verbesserte Syntaxpruefung
// 14.01.2000 schnellere Auswertung und Code-Verkuerzung
// TODO: Umwandlung in Postfix-Ausdruck
//
// - stellt einen Parser fuer Boolesche Ausdruecke dar
// - implementiert 12 Variablen (A-L) und die Funktionen
// Negation, Konjunktion, Antivalenz, Disjunktion, Implikation,
// Aequivalenz (diese Reihenfolge beginnend mit hoechster Prioritaet)
// - Verschachtelung mit Klammern moeglich
// - rein theoretisch sind auch mehr Variablen moeglich, doch entstehen
// bei der jetzigen Grenze schon 4096 Moeglichkeiten, das wird langsam
// zeit- und speicherkritisch fuer Windows (NICHT FUER DIESEN CODE HIER!)
//
// Zusatzinfos: - LieMachineParser.html (auch unter www.stephan-brumme.de)
// - Sedgewick: Algorithmen, 2. Auflage
// - Stroustrup: Die C++Programmiersprache, 3. Auflage
// - Wendt: Vorlesung SST am HPI der Uni Potsdam, 1.FS
//
////////////////////////////////////////////////////////
//
// Referenz-Vorgehensweise:
//
// Format(Aussage)
// Vars[_A],Vars[_B],...,Vars[_L] je nach Benutzung
// mit booleschen Werten fuellen
// Evaluate()
//
/////////////////////////////////////////////////////////
//
// public-Variablen/Konstanten:
//
// Anzahl benutzter Variablen
// int nMinVars;
//
// true fuer die benutzten Variablen an den jeweiligen Stellen
// ihres ASCII-Codes (stets Kleinbuchstaben !)
// bool Vars[128];
//
// enthaelt alle benutzten Variablen als lueckenlose Zeichenkette
// CString ActiveVars;
//
// Maximalzahl benutzter Variablen
// enum { MaxVars = 12 };
//
// Definition aller zulaessigen Zeichen
// enum Token { ... };
////////////////////////////////////////////////////////////
// public-Funktionen:
// bereitet Ausdruck auf die Auswertung vor, entfernt Leerzeichen
// Statuscode beachten !
// int Format(CString &Expression);
//
// berechnet Gesamtaussage des Ausdrucks fuer eine spezifische Variablenbelegung
// bool Evaluate();
/////////////////////////////////////////////////////////////////////
// der ganze von VC automatisch generierte Kram
#include "stdafx.h"
#include "Parser.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
//////////////////////////////////////////////////////////
// public Format:
// bereitet Aussage fuer die Auswertung vor
// wandelt Aussage in Kleinbuchstaben um, entfernt Leerzeichen
// weist ungueltige Zeichen zurueck, kein Grammatik-Check
//
// IN: &CString - Aussage
// OUT: int - Statuscode, bei _OK ist alles i.O.
///////////////////////////////////////////////////////////
int CParser::Format(CString &Expression)
{
// Variable erwarten
bool bForceVar = true;
// Schachtelungstiefe durch Klammerung mitzaehlen
int nBracketCount = 0;
// neue Zeichenkette aus Expression aufbauen
PassedFormat = "";
// es sollte schon was drinstehen ...
if (Expression.GetLength()==0)
return _NOTOKEN;
// in Kleinbuchstaben umwandeln
Expression.MakeLower();
// alle Zeichen durchlaufen
for (int i=0; i<Expression.GetLength(); i++)
// Token ueberpruefen
switch(Expression[i])
{
// Leerzeichen ignorieren
case ' ': continue;
// zulaessige Token
// zuerst Variablen / Konstanten
case _FALSE:; case _TRUE:;
case _A:; case _B:; case _C:; case _D:;
case _E:; case _F:; case _G:; case _H:;
case _I:; case _J:; case _K:; case _L:
// es darf jedes Token folgen
bForceVar = false;
// ok bis hierher
PassedFormat+=Expression[i];
break;
// unärer Opator der Negation
case _NOT:;
// Variable muss folgen
bForceVar = true;
// ok bis hierher
PassedFormat+=Expression[i];
break;
// binäre Operatoren
case _AND:; case _OR:; case _XOR:; case _LOG:; case _EQU:;
// Variable erwartet ? wenn ja, dann Fehler
if (bForceVar)
return _VAREXPECTED;
// Variable muss folgen
bForceVar = true;
// ok bis hierher
PassedFormat+=Expression[i];
break;
// oeffnende linke Klammer
case _LB:;
// Verschachtelung mitzaehlen
nBracketCount++;
// Variable muss folgen
bForceVar = true;
// ok bis hierher
PassedFormat+=Expression[i];
break;
// schliessende rechte Klammer
case _RB:;
// muss erlaubt sein, es darf weder Variable erwartet werden,
// noch duerfen mehr rechte als linke Klammern auftauchen
if (bForceVar||(nBracketCount==0))
return _BRACKETNOTALLOWED;
// "zurueckschachteln" (Copyright auf dieses Wort beantragt)
nBracketCount--;
// ok bis hierher
PassedFormat+=Expression[i];
break;
// ungueltiges Token
default: return _UNKNOWNTOKEN;
}
// alle Klammern ordentlich aufgeloest ?
if (nBracketCount!=0)
return _BRACKETEXPECTED;
// es darf keine Variable mehr erwartet werden
if (bForceVar)
return _VAREXPECTED;
// Anzahl Variablen zaehlen
nMinVars=0;
// vorkommende Variablen mit ihrem Namen festhalten
ActiveVars = "";
// moegliche Namen begrenzen
CString AllVars = "abcdefghijkl";
// auf alle moeglichen Variablen ueberpruefen
for (i=0; i<MaxVars; i++)
// taucht sie in der Aussage auf ?
if (PassedFormat.Find(AllVars[i])!=-1)
{
// ja, also vermerken
nMinVars++;
ActiveVars+=AllVars[i];
}
// konstante Ausdruecke sind nicht erlaubt
if (nMinVars==0)
return _NOVARS;
// die formatierte Aussage an Aufrufer zurueckgeben
Expression = PassedFormat;
// Formatierung abgeschlossen, fuer die anschliessende Auswertung vormerken
expression = PassedFormat;
// Ende fuer die Auswertung markieren
expression+= _END;
// fehlerfrei bearbeitet
return _OK;
}
////////////////////////////////////////////////////////////
// public Evaluate:
//
// wertet Aussage aus, vorher muessen alle verwendeten Variablen
// in "vars" initialisiert werden (Index jeweils der Token _A,_B,...)
//
// IN: nix
// OUT: bool - false bei Fehlern
////////////////////////////////////////////////////////////////
bool CParser::Evaluate()
{
// Laufzeiger auf gerade zu bearbeitendes Token
exprcount = 0;
// erstes Token holen
GetToken();
// Aussage auswerten
return DoEqu(false);
}
//////////////////////////////////////////////////////////////
// private DoEqu:
//
// alle Aequivalenzen aufloesen
//
// IN: bool - true, falls neues Token zu holen
// OUT: bool - Gesamtaussage des Ausdrucks
//////////////////////////////////////////////////////////////
bool CParser::DoEqu(bool get)
{
// rekursiv absteigen
bool left = DoLog(get);
// gesamte Aussage durchsuchen und auswerten
for (;;)
// Aequivalenz gefunden ?
if (token==_EQU)
// ja, rekursiv absteigen und Aussage berechnen
left=(DoLog(true)==left);
else
// nein, also fertig
return left;
}
//////////////////////////////////////////////////////////////
// private DoLog:
//
// alle Implikationen aufloesen
//
// IN: bool - true, falls neues Token zu holen
// OUT: bool - Gesamtaussage des Ausdrucks
//////////////////////////////////////////////////////////////
bool CParser::DoLog(bool get)
{
// rekursiv absteigen
bool left = DoOr(get);
// gesamte Aussage durchsuchen und auswerten
for (;;)
// Implikation gefunden ?
if (token==_LOG)
// ja, rekursiv absteigen und Aussage berechnen
left=(!left)|DoOr(true);
else
// nein, also fertig
return left;
}
//////////////////////////////////////////////////////////////
// private DoOr:
//
// alle Konjunktionen aufloesen
//
// IN: bool - true, falls neues Token zu holen
// OUT: bool - Gesamtaussage des Ausdrucks
//////////////////////////////////////////////////////////////
bool CParser::DoOr(bool get)
{
// rekursiv absteigen
bool left = DoXor(get);
// gesamte Aussage durchsuchen und auswerten
for (;;)
// Disjunktion gefunden ?
if (token==_OR)
// ja, rekursiv absteigen und Aussage berechnen
left|=DoXor(true);
else
// nein, also fertig
return left;
}
//////////////////////////////////////////////////////////////
// private DoXor:
//
// alle Antivalenzen aufloesen
//
// IN: bool - true, falls neues Token zu holen
// OUT: bool - Gesamtaussage des Ausdrucks
//////////////////////////////////////////////////////////////
bool CParser::DoXor(bool get)
{
// rekursiv absteigen
bool left = DoAnd(get);
// gesamte Aussage durchsuchen und auswerten
for (;;)
// Antivalenz gefunden ?
if (token==_XOR)
// ja, rekursiv absteigen und Aussage berechnen
left^=DoAnd(true);
else
// nein, also fertig
return left;
}
//////////////////////////////////////////////////////////////
// private DoAnd:
//
// alle Konjunktionen aufloesen
//
// IN: bool - true, falls neues Token zu holen
// OUT: bool - Gesamtaussage des Ausdrucks
//////////////////////////////////////////////////////////////
bool CParser::DoAnd(bool get)
{
// rekursiv absteigen
bool left = DoPrimary(get);
// gesamte Aussage durchsuchen und auswerten
for (;;)
{
// Konjunktion gefunden ?
switch (token)
{
// ja, explizit markiert, rekursiv absteigen und Aussage berechnen
case _AND:
left&=DoPrimary(true); break;
// ja, impliziert durch Kurzschreibweise (a&b=ab)
case _A:; case _B:; case _C:; case _D:;
case _E:; case _F:; case _G:; case _H:;
case _I:; case _J:; case _K:; case _L:;
case _LB:; case _NOT:
// rekursiv absteigen und Aussage berechnen
left&=DoPrimary(false); break;
default:
// fertich glaubich
return left;
}
}
}
//////////////////////////////////////////////////////////////
// private DoPrimary:
//
// elementares Token aufloesen bzw. Klammern bearbeiten
//
// IN: bool - true, falls neues Token zu holen
// OUT: bool - Gesamtaussage des Ausdrucks
//////////////////////////////////////////////////////////////
bool CParser::DoPrimary(bool get)
{
// ggf. neues Token auslesen
if (get)
GetToken();
// Ergebnis-Zwischenspeicher
bool temp;
// Token auswerten
switch (token)
{
// Variableninhalt zurueckgeben
case _A:; case _B:; case _C:; case _D:;
case _E:; case _F:; case _G:; case _H:;
case _I:; case _J:; case _K:; case _L:;
temp = Vars[token];
// naechtes Token auslesen
GetToken();
return temp;
// unaere Negation
case _NOT:
// inverse Aussage des naechsten Tokens zurueckgeben
return !DoPrimary(true);
// Konstante "TRUE"=1
case _TRUE:
// naechtes Token auslesen
GetToken();
// "TRUE" zurueckgeben
return true;
// Konstante "FALSE"=0
case _FALSE:
// naechtes Token auslesen
GetToken();
// "FALSE" zurueckgeben
return false;
// oeffnende Klammer
case _LB:
// die Klammer auswerten
temp = DoEqu(true);
// naechtes Token auslesen
GetToken();
// Klammerinhalt zurueckgeben
return temp;
// Dummy-Funktion, damit der Compiler nicht meckert
default: return false;
}
}
///////////////////////////////////////////////////////////////
// private GetToken
//
// liest ein einzelnes Zeichen aus "expression" aus
//
// IN: nix, aber indirekt wird "expression" ind "exprcount" benutzt
// OUT: nix, aber "token" wird veraendert
////////////////////////////////////////////////////////////////
void CParser::GetToken()
{
// Zeichen lesen, Index weiterbewegen
token = Token(expression[exprcount++]);
}
// That's all folks. |
|
|
Zurück
|
Sitemap
|
Zu Favoriten hinzufügen
|
|
eMail
|
Copyright ©
1999 -2024
Stephan Brumme
all brand names and product names included in this site are trademarks,
registered trademarks or trade names of their respective holders.
refer legal issues / impressum for further details or just
contact me.
last update: Wednesday, January 3rd, 2001, 8:42pm. 40.9 kbytes generated in 0.002 seconds .
This web site flies with a homegrown content management system. No animals were harmed while writing it.
|
|
|
|