🚀 go-pugleaf

W dniu piątek, 21 kwietnia 2017 23:51:30 UTC+2 użytkownik (fir) napisał:


> ten przyklad wyglada dosyc ladnie, ale ciagle lispa powiedzialbym jak patrze na kod rozumiem powiedzialbym 'polowicznie' (co nie jest dziwne bo sie go nie uczylem)
> 
> a przetlumaczenie na asma takiego czegos
> 
> x = (3*a+(c-2)/d+f)*g 
> 
> (gdzie to co jest litera monza uznac za rejestr, tylko jednoliterowe nazwy rejestrow, a to co jest digitem mozna uznac za inta) 
> 
> duzo by w lispie zajelo?, w c to mi zajelo o ile mgliscie pamietam dobrych kilkaset linijek (co prawda zle to napisalem) - jesli by ten lisp naprawde robil to sprawniej niz c to mozna uznac za pewna wartosc

Tzn. oczywiście zależy jak do tego podejść.
Jeżeli chcielibyśmy przeparsować stringa "(3*a+(c-2)/d+f)*g", to pewnie
byłoby z tym nieco zabawy (najwygodniej pewnie byłoby to oprzeć
o wyrażenia regularne).

Gdybyśmy założyli, że mamy listę tokenów daną w postaci
lispowej, a dodatkowo wyrażenia w nawiasach są już złożone
do pojedynczego wyrażenia, tzn, że mamy w Lispie takie coś

'((3 * a + (c - 2) / d + f) * g)

[tzn. separatory tokenów w lispie to spacje oraz nawiasy,
ale zupełnie nie ma znaczenia, czy symbole są jednoliterowe albo
liczby jednocyfrowe] to trzeba by to sobie było najpierw
zinterpretować, uwzględniając priorytety operatorów.

zakładając łączność lewostronną, tzn. że interpretujemy a + b + c
jako ((a + b) + c), oraz normalne priorytety, tzn. że / wiąże
najsilniej, po nim *, a + najsłabiej, można by to tak napisać:

(define (associate-left expression operator)
  (match expression
    ((left op right)
     (if (eq? op operator)
	 `((,left ,op ,right))
	 expression))
    
    ((left op right . more)
     (if (eq? op operator)
	 (associate-left `((,left ,op ,right) . ,more) operator)
	 `(,left ,op . ,(associate-left `(,right . ,more) operator))))))

(e.g. (associate-left '(a * b + c * d) '+) ===> (a * (b + c) * d))
(e.g. (associate-left '(a * b + c * d) '*) ===> ((a * b) + (c * d)))

(define (infix->prefix expression)
  (match expression
    ((left op right)
     `(,op ,(infix->prefix left) ,(infix->prefix right)))

    ((left op right . more)
     (infix->prefix (fold-left associate-left
			       expression
			       '(/ * - +))))

    ((expression) ;; usuwamy nadmiarowe nawiasy
     (infix->prefix expression))

    (_
     expression)))

(e.g. (infix->prefix '((3 * a + (c - 2) / d + f) * g))
   ===> (* (+ (+ (* 3 a) (/ (- c 2) d)) f) g))

ale jak mówię, generalnie dla lispiarzy zagadnienia parsowania
są umiarkowanie interesujące, i lepiej sobie zaprojektować format
pliku tak, żeby dało się go przeparsować zwykłym lispowym
readem (który od razu zwraca drzewo, tzn. pozagnieżdżaną listę)

może kogoś to mierzić, że 1-1 to nie jest działanie arytmetyczne,
tylko symbol, ale mnie takie coś daje większą swobodę ekspresji
(ale też trzeba uważać, bo np. Scheme ma w standardzie liczby
zespolone, i zapis 1+1i oznacza liczbę, a nie symbol. No ale to
takie drobne niuanse)