member of the work
 
  Home | Studium | Programming | Games | Links | About Me | eMail

Parser-Logo

Quicklinks:
[Superzeichen, Terminale und Grammatik]
[Bedeutung der Operatoren]
[Syntaxüberprüfung] [Code]

{ 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.

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

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.
   suche:
Zurück Sitemap Zu Favoriten hinzufügen
Translate
eMail   
Copyright © 1999 -2018 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. 41.4 kbytes generated in 0.004 seconds  .
 
This web site flies with a homegrown content management system. No animals were harmed while writing it.