Parsiranje Bulovske formule

[ gajo2 @ 15.12.2006. 13:46 ] @

Pozdrav,

Napravio sam mali program u Delphiju za parsiranje formule u iskaznom racunu, koji izracunava sve vrednosti formule. Npr. avb <=> bva je tautologija pa bi sve njene vrednosti bili tacni.

E sada sve ovo lepo radi, ali problem mi pravi prioritet operatora. Ne znam kako da resim da ^ ima najveci prioritet, v posle njega, a <=> da ima najmanji.

Kada npr. sve grupisem zagradama onda
(a^b) <=> (b^a)
lepo radi, medjutim
a^b <=> b^a
ce se racunati kao
a^(b <=> b)^a
sto naravno nije tacno.

Probao sam razne trikove, ispisao sve moguce kombinacije i ne ide. Nisam uopste siguran da li se iskazne formule mogu parsirati kao recimo proceduralni jezici, pa mozda je tu greska?

Inace koristio sam ovu EBNF formulu:
Ekviv ::= Impl {"<=>" Impl}
Impl ::= Disj {"=>" Disj}
Disj ::= Konj {"v" Konj}
Konj ::= Neg {"^" Neg}
Neg ::= [!] A

gde je A neki simbol.

MEDJUTIM ovo nije radio korektno, npr. za

a^(bvc)

jer za (bvc) treba da se "vrati gore" na disjunkciju.
Pa sam promenio u sledece:

Ekviv ::= Impl {"<=>" Ekviv}
Impl ::= Disj {"=>" Ekviv}
Disj ::= Konj {"v" Ekviv}
Konj ::= Neg {"^" Ekviv}
Neg ::= [!] A

Dakle uvek se vracam na pocetni iskaz, i ovako mogu da obradim svaki slucaj. Ovo lepo radi, osim onog slucaja sto sam napomenuo na pocetku, da <=> ima veci prioritet od ^
Probao sam da promenim redosled tako da Konj bude na vrhu, ali ovako je bilo pogresno i u teoriji i u praksi.

Ovo je kod za parsiranje:

Code:
const
  THE_END = #13;

var
  ch: char;
  pos: integer;
  len: integer;

function Process(str: string; values: array of TValue): boolean;
  function Equal: boolean; forward;
  function Imply: boolean; forward;
  function Disjunct: boolean; forward;
  function Conjuct: boolean; forward;
  function Negate: boolean; forward;

  procedure Scan;
  begin
    repeat
      inc(pos);
      ch := str[pos]
    until not ((ch = ' ') and (pos <= len));
  end;

  procedure Check(const checked: char);
  begin
    if ch = checked then
      Scan
    else
      raise Exception.Create(checked + ' expected but ' + ch + ' found at position ' + IntToStr(pos))
  end;

  function Equal: boolean;
  var
    res: boolean;
  begin
    {$B+}
    if ch = '(' then begin
      Scan;
      res := Imply;
      while ch = '=' do begin
        Scan;
        res := res = Equal
      end;
      Check(')')
    end else begin
      res := Imply;
      while ch = '=' do begin
        Scan;
        res := res = Equal
      end
    end;
    Result := res
    {$B-}
  end;

  function Imply: boolean;
  var
    res,pom: boolean;
  begin
    {$B+}
    if ch = '(' then begin
      Scan;
      res := Disjunct;
      while ch = '>' do begin
        Scan;
        pom := Equal;
        if res and not pom then
          res := false
        else
          res := true
      end;
      Check(')')
    end else begin
      res := Disjunct;
      while ch = '>' do begin
        Scan;
        pom := Equal;
        if res and not pom then
          res := false
        else
          res := true
      end;
    end;
    Result := res
    {$B-}
  end;

  function Disjunct: boolean;
  var
    res,pom: boolean;
  begin
    {$B+}
    if ch = '(' then begin
      Scan;
      res := Conjuct;
      while ch = '|' do begin
        Scan;
        pom := Equal;
        res := res or pom
      end;
      Check(')')
    end else begin
      res := Conjuct;
      while ch = '|' do begin
        Scan;
        pom := Equal;
        res := res or pom
      end;
    end;
    Result := res
    {$B-}
  end;

  function Conjuct: boolean;
  var
    res,pom: boolean;
  begin
    {$B+}
    if ch = '(' then begin
      Scan;
      res := Negate;
      while ch = '&' do begin
        Scan;
        pom := Equal;
        res := res and pom
      end;
      Check(')')
    end else begin
      res := Negate;
      while ch = '&' do begin
        Scan;
        pom := Equal;
        res := res and pom
      end;
    end;
    Result := res
    {$B-}
  end;

  function Negate: boolean;
  var
    res: boolean;
  begin
    {$B+}
    if ch = '!' then begin
      Scan;
      res := not Negate
    end else begin
      res := GetValue(ch, values);
      Scan;
    end;
    Result := res
    {$B-}
  end;

begin
  len := Length(str);
  pos := 1;
  ch := str[pos];
  Result := Equal;
end;

Dakle daje se str npr. a&(b|c)=(a&b)|(a&c) i jos niz vrednosti za svaki simbol. Ova funkcija se poziva 2^n puta, naravno, uvek sa drugacijim vrednostima.
{$B+} iskljucuje "lazy evaluation" kako slucajno ne bih nesto preskocio.

Ima li neko predlog sta da izmenim? Gde gresim?
Inace ceo kod, kao i kompajliranu verziju programa mozete skinuti sa Sourceforgovog sajta: http://sourceforge.net/projects/logicaleval

Pozdrav, Chaba