Zablokowane Własny parser, potrzebuje pomysłów na AND i OR

[Pieter]

Cóż, od jakiegoś czasu pisze parser własny parser coś na styl GML, i mam problem. Udało mi się zrobić warunki pod warunkiem, że nie ma w nich warunku OR ("||") no i tu mam dla was zadanie moi drodzy. Najpierw opisze działanie systemu:

 

mamy funkcje:

if [1==1 && 2==2] { msgbox "true" } else { msgbox "false" }

jak widzicie warunki zostały spełnione i wyświetli nam "true". To samo idzie kiedy jeden bądź więcej warunków nie będzie spełnionych (zauważcie, że nie ma tam jeszcze wspomnianego OR)

 

if [2==1 && 1==2] { msgbox "true" } else { msgbox "false" }

wyświetli nam "false". No dobrze wiemy jak to wygląda ale jak to działa?

 

cóż... napisałem sobie funkcje która potrafi z stringowej kalkulacji dać wynik, np daje w stringu "2+2" i otrzymam "4". Ta sama funkcja sprawdza czy np "2<3" i daje albo "1" na true albo "0" na false. Było git do puki nie chciałem dodać wielo-warunkowości tzn AND i OR ("&&" i "||"). Wpadłem na pomysł, żeby AND zrobić na zasadzie: zliczania wszystkich kawałków tekstu w wyrażeniu "&&" i dodać do tej liczby 1, zamienić każde znaki "&&" w wyrażeniu na "+" i porównać wynik liczenia z liczbą tych znaków do których dodaliśmy jeden. Jeżeli liczba była by równa to uzyskamy "true" tzn wyrażenie zostało spełnione i vice versa. Jak to wygląda w praktyce?

 

Załóżmy że mamy jak wcześniej:

if [1==1 && 2==2] { msgbox "true" } else { msgbox "false" }

 

mój parser czyta to kolejno tak tak:

 

[1==1 && 2==2] // liczy ile znaków && jest w wyrażeniu, i dodaje do tej liczby 1. nazwijmy ją zmienna1 i przybiera ona wartość 2 (1 raz &&+1)

[1==1 + 2==2] // zamienia znaki && na +

[1 + 1] // sprawdza warunki i tworzy nowe równanie. zauważcie, że oba warunki zostały spełnione

[2] i w tym momencie sprawdza czy zmienna1 równa się wartości która jest w nawiasach. i ustawia spełnienie warunku.

 

Sprytny sposób pod warunkiem, że nie ma w tym żadnego OR na którego sposób nie mogę już wymyślić nic bo nie mam pomysłów, dlatego proszę was o jakieś pomysły, bo niestety ale OR zwróci 0 albo 1 i zastąpiwszy OR także znakiem + otrzymujemy:

 

[2==1 && 1==2 || 3==3] // zamiana na końcu jest warunek OR

[2==1 + 1==2 + 3==3] // sprawdzanie warunków i zamiana wszystkiego na + (nawet OR)

[0 + 0 + 1] // liczenie warunków

[1] // liczba końcowa.

 

i sytuacja się zmienia drastycznie kiedy np jeden warunek albo wszystkie zostaną spełnione:

 

[2==1 && 1==2 || 3==3] // zamiana

[2==1 + 1==2 + 3==3] // sprawdzanie warunków

[1 + 0 + 1] // liczenie warunków

[2] // liczba końcowa.

 

albo

 

[2==1 && 1==2 || 3==3] // zamiana

[2==1 + 1==2 + 3==3] // sprawdzanie warunków

[1 + 1 + 1] // liczenie warunków

[3] // liczba końcowa.

 

ALBO żaden warunek nie jest spełniony i powinno być false

 

[2==1 && 1==2 || 2==3] // zamiana

[2==1 + 1==2 + 2==3] // sprawdzanie warunków

[0 + 0 + 0] // liczenie warunków

[0] // liczba końcowa.

 

kolejne false (ZOBACZCIE ZE LICZBA KONCOWA JEST TAKA SAMA JAK LICZBA KONCOWA TRUE LECZ WARUNEK NIE ZOSTAJE SPEŁNIONY!):

 

[1==1 && 1==2 || 2==3] // zamiana

[1==1 + 1==2 + 2==3] // sprawdzanie warunków

[1 + 0 + 0] // liczenie warunków

[1] // liczba końcowa.

 

no a to już będzie funkcja true dla pierwszego AND.

 

[1==1 && 2==2 || 2==3] // zamiana

[1==1 + 2==2 + 2==3] // sprawdzanie warunków

[1 + 1 + 0] // liczenie warunków

[2] // liczba końcowa.

 

no i teraz, widać, że liczby false i true lubią się powtarzać, nie mam zielonego pomysłu jak to rozwiązać.

 

cóż takie działanie już daje problemy ponieważ nie da się za bardzo przewidzieć końcowego wyniku spełnionego warunku gdyż AND i OR może być więcej w wyrażeniu, albo moja wyobraźnia jest za płytka. Proszę co tęższe umysły i te słabsze o rozpatrzenie mojego problemu, dziękuje :* spróbuje pomagać jak tylko mogę i mam nadzieje, że chodź trochę zrozumieliście o co mi chodzi. Jeżeli nie to chętnie jeszcze wytłumaczę. Może ktoś inny będzie miał pomysł jak INACZEJ zrobić AND oraz OR.

[Konrad-GM]

Wg. mnie system AND i OR powinien działać mniej-więcej tak:

if( a=b && c=d || e=f )

Interpreter:

[a=b + ( c=d or e=f )] - () Blok OR

Jeśli (a=B)=1 -> Jeśli ((c=d)=0 sprawdzaj następny (e=f)=1)=1

Aby zaoszczędzić testów: jeśli (a=B)=0, przerwij lub (c=d)=1 także przerwij blok OR ( ten nawias, w którym znajduje się warunek c=d )

I dopiero sumujesz:

Dla: (a=B)=1 + ((c=d)=0 or (e=f)=1)=1

To: 1+1 = 2 - warunek spełniony, ponieważ 2 = (1xAND + 1).

Więc dla bardziej rozbudowanych warunków powinno działać podobnie:

if( a=b && c=d && e=f || g=h || i=j && k=l || m=n )

Interpreter:

[a=b + c=d + ( e=f or g=h or i=j ) + ( k=l or m=n ) ]

[ 1 + 1 + 1( np.(c=d)=1 ) + 1( np.(m=n)=1 ) ]

[ 4 ] = Warunek spełniony, ponieważ 4 = (3xAND + 1)

 

Jeśli będzie gdzieś warunek nie spełniony to:

if( a=b && c=d || e=f )

Interpreter:

[a=b + ( c=d or e=f ) ) ]

Przypuśćmy że blok OR ( (c=d)=0 or (e=f)=0 )=0

[ 1 + 0 ) ]

[ 1 ] = Warunek niespełniony, ponieważ 1 != (1xAND + 1)

[Pieter]

Całkiem fajny sposób, pomyśle nad nim. Myślę też na podzielenie tego na priorytety, np Najpierw liczę wszystko co jest po OR, jeżeli warunek zostanie spełniony wtedy jedziemy dalej, jeżeli nie sprawdzam wszystko przed OR czy zostanie spełnione i tu jak kto lubi, co myślicie o takim też rozwiązaniu? (trochę głupie jak teraz o tym myślę, chyba skorzystam z twojego rozwiązania, muszę je gruntownie przemyśleć)

[Konrad-GM]

Każdy sposób jest dobry, ważne aby działał ;p

[Pieter]

Czyli w praktyce mamy tak:

 

Funkcje która podzieli nam wyrażenie na sektory i przypisze je do tablicy.

if [1==1 && 2==2 || 3==4 || 5==5 && 0==1]

przepuszczając ją przez funkcje otrzymamy tablice:

 

tablica[0] = " 1==1 && 2==2 "
tablica[1] = " 3==4 "
tablica[2] = " 5==5 && 0==1 "

i sprawdzamy po koleji:

 

jeżeli tablica[0] = niespełnione jedziemy do następnego punktu tablicy, jeżeli spełnione to zatrzymujemy i wykonujemy to co chcemy. Jeżeli nic nie spełnionego to nie wykonujemy i już. Co o tym myślicie?

[Ranmus]

Ale żeś wykombinował. Przede wszystkim powinieneś całe wyrażenie rozbić na maksymalnie najprostsze wyrażenia. Nie możesz robić czegoś takiego jak " 1==1 && 2==2 ", bo potem nie będziesz w stanie napisać debuggera (mając 2 wyrażenia jako fizycznie jedno). Ja ogólnie bym to zrobił na zasadzie wektorów czy struktur i zaprzągł rekurencję. Mianowicie na przykładzie:

if ( 1==1 && ( 5==5 || 3 == 3 ) || ( 6 == 6 && 3 == 3 ) )

Mam globalne wyrażenie ,na które składają się trzy wyrażenia:

- wyrażenie 1==1

- wyrażenie z dwoma podwyrażeniami ( wyrażenie 5 == 5 oraz wyrażenie 3 == 3 )

- wyrażenie z dwoma podwyrażeniami ( wyrażenie 6 == 6 oraz wyrażenie 3 == 3 )

 

Do tego strukturki (C#):

enum ExpOperand {
    AND,
    OR
}

struct Expression {
    List<Expression> expressions = null;
    Expression exp = null;
    ExpOperand nextOperand = null;
}

 

I teraz parsuję tak:

1) Tworzę strukturę Expression (1)

2) (1) nextOperand = null;

3) (1) exp = null;

4) (1) expressions += 3 struktury Expression (2)(3) i (4)

5) (2) nextOperand = ExpOperand.AND;

6) (2) exp = "1==1";

7) (2) expressions = null;

8) (3) nextOperand = ExpOperand.OR;

9) (3) exp = null;

10) (3) expressions += 2 struktury Expression (5) i (6)

11) (5) nextOperand = ExpOperand.OR;

12) (5) exp = "5==5";

13) (5) expressions = null;

14) (6) nextOperand = nulll

15) (6) exp = "3==3";

16) (6) expressions = null;

17) (4) nextOperand = null;

18) (4) exp = null;

19) (4) expressions += 2 struktury (7) i (8)

20) (7) nextOperand = ExpOperand.AND;

21) (7) exp = "6==6";

22) (7) expressions = null;

23) (8) nextOperand = nulll

24) (8) exp = "3==3";

25) (8) expressions = null;

 

Mam już sparsowane wyrażenie, przemienione na struktury. Teraz tworzę sobie funkcję rekurencyjną, która za argument przyjmuje Expression i zwraca true lub false. Żeby zobrazować jak to parsować, w notatniku napisałem funkcję powiedzmy pseudo językiem:

bool ParseExpression( Expression expression )
{
    if ( expression.expressions == null )
    {
        return twojParser(exp); // true lub false
    }
    else
    {
        bool _bool = false;
        prevOperand = null;

        foreach ( Expression _expression in expression.expressions )
        {
            _bool = ParseExpression( _expression );
            if ( _bool == false )
            {
                if ( prevOperand == null && _expression.nextOperand == ExpOperand.AND )
                    return false;
                if ( prevOperand == ExpOperand.AND )
                    return false;
            }
        }  
    }
}

Zasada działania jest prosta, parsujesz wszystkie elementy, a jak element się składa z podelementów, to i je parsujesz. Oczywiście nie ręczę, że powyższa funkcja jest dobrze napisana i będzie działać - chodzi tylko o pogląd jak to ma mniej więcej wyglądać. Do tego musisz dodać optymalizację w pętli foreach żeby nie wyliczało kolejnych argumentów OR jak nie trzeba.

 

Swoją drogą powinieneś poszukać pare porządnych artykułów na temat notacji, parserów, lekserów itp. bo podchodzisz do tematu trochę od "dupy" strony. Pomijam już nawet sens pisania własnego języka, ponieważ profesjonalnych matematyków i tak nie pobijesz.

[Pieter]

szczerze mówiąc to mam gdzieś debugger ;p to mają być miniskrypty bez jakiegokolwiek debuggera do trainera do gry ;p mi zależy na jak najprostszym i szybkim rozwiązaniu, ale thx ;) głównie dlatego, że kod jest pisany w jednej linijce i ma odnosić się do możliwie łatwych rzeczy więc niestety to rozwiązanie jest dobre dla języków programowania, nie potrzebne w zwykłym skrypterze, ale dzięki za rozkminę ;* wystarczy mi mój sposób.

 

Rezultaty z mojej funkcji ;]

 

if [1==1 && 2==1 || 1==2 || 2==2 && 3==3] { msgbox "true" } else { msgbox "false" }

 

1=1 + 2=1 (1 : 2)

1=2 (0 : 1)

2=2 + 3=3 (2 : 2)

 

to co wyświetlił mi debugger :] w nawiasach: po lewej spełnione warunki, po prawej ilość do spełnienia :P

[baca]

A udostępnisz go nam? tak:nie

[Pieter]

nie (open source nie).

[baca]

Co prawda pewnie bym go nie użył(bo sam tworze do mojego programu coś podobnego i kilka podobnych już stworzyłem), ale luknąć zawsze można.