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;
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