python feldolgozo (parser) irasa

 ( tr1719 | 2019. március 25., hétfő - 20:32 )

Udv!

Egy olyan kodot szeretnek irni, ami kepes az alapjelek feldolgozasara:


()
and
or
not
boolean (true / false)

. Egyelore otleteket varok, hogy ki hogyan allna hozza? Mi a legcelszerubb? A nyelv strukturaja igazabol valaszthato, en hatarozhatom meg, es a bekeres formaja is. Akar az is lehetseges, hogy mindig kirakom, hogy milyen jelek lehetnek a kovetkezo tokenek, es abbol valaszt a felhasznalo (ez mondjuk talan nem a legegyszerubb / felhasznalobaratabb, viszont nagyobb esellyel eredmenyez ertelmezheto szintaxist) .

Biztos van, aki irt mar hasonlot. Mit lehet hasznalni? Milyen eszkoztar van ehhez?

Minden velemeny erdekel.

Koszi.

Hozzászólás megjelenítési lehetőségek

A választott hozzászólás megjelenítési mód a „Beállítás” gombbal rögzíthető.

ha kézzel kéne csinálni, akkor tuti megpróbálnám elkerülni a zárójelezést, így első tippre prefix/postfix jelölve az operandusokat.
ha ez nem megoldás, akkor antlr, vagy hasonló, már kész eszköz után néznék.

hacsak nem a hobbiból lexer írása a feladat :)

+1 Sot ma mar nem sok ertelme van meglevo nyelvre ilyet irni.

Az iparban inkabb domain specifikus nyelvekre van igeny. Peldaul MPS-el jol lehet ilyet letrehozni:
https://youtu.be/xXmYE9HrooM
En mbeddr-t hasznaltam (C99), ami ezen alapul es minden azonnal AST formaban van, parserrel nem kell foglalkozni, lehet csak a nyelvre koncentralni.

Ha megis teljesen sajat parsert akarsz irni, akkor egyszerubb nyelvvel ajanlott kezdeni: peldaul Forth
Lasd: https://skilldrick.github.io/easyforth/
Vagy keress barmilyen nyelvet eloszor egyszeru BNF-el vagy csinalj egy postfix szamologepet..

Szerk:
Bocsanat felreertettem, azt hittem python parsert akarsz irni es az alapjelekkel kezded :)

Python parsert? Ah, nincs ra egy fel eletem. Na jo, nyilvan gyorsabban menne, de minek?

Ha nem akarsz kész nyelvi elemző irányba menni, akkor valami fa gráfod van, amelyet bejársz.
Nem túl bonyolult a nyelv, tényleg előre tudhatod, milyen 1-2-3 token jöhet szóba. És annak megfelelően építed a fát. Vagy használsz kész gráf libraryt (https://github.com/yorkchu1995/graphx/), vagy implementálhatod magad is (https://www.python.org/doc/essays/graphs/).

P.S. not not not true értelmes?

Nem szeretnek ennyire bonyolult utasitasokat, de sajnos annak kell lennie. Ki tudja ki mit fog irni bele.

Lehet en ertek felre valamit, de nem pont erre "szabvanyositottak" az ast tree-t? Kar kitalalni valami ujat szerintem.

-
First impressions of the new Cloud Native programming language Ballerina

Bocs, de én nem értem pontosan a feladatot.

Csak egy scannert kell írnod, ami egy inputban felismeri a tokeneket, és szól, ha olyan szimbólum van, ami nem megengedett?

Vagy tartozik hozzá nyelvtan is?

Neked magát a scannert kell megírnod (ill ha van nyelvtan, akkor egy LR/LALR szintaktikai elemzőt is)? Vagy használhatsz valami toolt?

Mi köze a Pythonnak ehhez? Abban kell írnod, vagy ez majd Python forráskódot fog elemezni?

Pythonban írtak egy egész jó LALR elemzőt, a ply-t.

Van egy nagyobb python applikacio, es a kornyezet miatt mas nyelv nem is johet szoba, tehat a nyelv adott.

Valamilyen modon be kell kerni utasitasokat, amit kiertekelve mindossze egy True / False ertek johet ki. Pl. egy ilyen utasitas lehet:


if as.value == True: False: True

Na, ez eleg kacifantos lett, de a lenyege:

Ha az as.value erteke True, akkor a kifejezes erteke False, kulonben True .

Ez nyilvan egy peldasor volt, a kialakitas leginkabb rajtam mulik.

Szemleletesebb lenne talan ez a pelda:


if $value1 == True or ($value1 == True and not $value3 == False): False: True

. Ebben tulajdonkeppen benne van minden.

Ez azért kicsit több, mint amit legelőször megfogalmaztál :D.

Ez nem tokenizálás, ehhez már kell nyelvtan is, és szintaktikai elemző. Viszont ha vannak változóid is (és azoknak nincs explicit jelőlése, mint ebben a példában a "$"), akkor az kicsit combosabb lesz.

Mivel en alakitom ki a szintaxist, lesz explicit jelolese.

Igazabol csak az 5 alapmuvelet (amit emlitettem: (), or, and, not, boolean) fontos.

Ötletek:

Ugye, Pythonban ezt így írhatjuk, hogy:
False if as.value==True else True

Az eval()-nak megadot sztringet a Python értelmezője kiértékeli. Bármit megadhatunk így, ezért veszélyes is. Esetleg, ha előzőleg szűrnénk a sztring tartalmára.

--
eutlantis

Az evalra en is gondoltam, de tul egyszeru megoldas lenne, bar ki tudja?

Ha annyi a cél, amit fentebb írtál, akkor szerintem is egyszerűbb egy már meglévő dolgot felhasználni, akár az eval-t is. Viszont persze ez veszélyes is lehet, hiszen ha valaki tudja, hogyan olvas be és dolgoz fel a programod, akkor könnyen kihasználhatja.
Nem ismerem a python-t, de nem lehet, hogy az eval "izolálva" fusson le a főprogramtól? Azaz a változókhoz ne férjen hozzá, külső programot ne indíthasson, stb.

Másik kérdés: honnan ered a változó, hogyan éred el külső programból?
Ha erre is van valami megoldás, egy egyszerű m4 is jó lehet:

$ echo 'ifelse(egyik,másik,igaz,hamis) ifelse(egyik,egyik,igaz,hamis)' | m4
hamis igaz

Természetesen megadható a bemenetben ilyen formában: egyik,másik,igaz,hamis, és egy egyszerű sed-del (vagy valami python-szövegátalakítóval) bekeretezni ifelse()-zel. Esetleg a bemenetet érdemes lehet itt is szűrni, hiszen külső program futtatása m4-ből is lehetséges (syscmd, esyscmd).

Szerkesztés: nem megoldható, hogy valami konfigurációs fájlt használj? Biztos van pythonhoz is sok parser, és az így "beolvasott" adatot dolgoznád fel - így talán kisebb a veszély, mint eval esetén.

Konfiguracios fajl? Szerintem itt nem jatszik. Egy adatbazis tablaban minden egyes sorhoz lenne egy ilyen rule, szoval ez adatbazisban kell, hogy tarolva legyen.

Adatbázisról eddig még nem volt szó :)

Valoban, de nem gondoltam, hogy relevans. Marmint, a felhasznalok adjak meg a szabalyokat, es azokat kell feldolgozni. Innentol kezdve - szerintem - mindegy, hogy miben van tarolva.

Adatbázisban tudsz tárolni strukturált adatot, akkor parser sem kell. Ez egyszerűbb ha egy object storeod van (pl. DynamoDB, Mongo DB), de megoldható akár egy relációs adatbázissal is.

Az eval biztonságos használatához találtam ezt:
https://www.geeksforgeeks.org/eval-in-python/

--
eutlantis

Ha postfix, stack alapú nyelvet specifikálsz (így nem kell fát építeni, mert nincs zárójel, precedencia), akkor ennyi a program:

pelda1 = True
pelda2 = False

code = "pelda1 pelda2 and true and not"

def str2bool(s):
if s == "false": return False
if s == "true": return True
if s in globals():
return globals()[s]
raise Exception("Unknown token '" + s + "'")

def op_and(stk):
stk.append(stk.pop() and stk.pop())

def op_or(stk):
stk.append(stk.pop() or stk.pop())

def op_not(stk):
stk.append(not stk.pop())

op_list = {
"and": op_and,
"or": op_or,
"not": op_not
}

stack = []

for token in code.split():
if token in op_list:
op_list[token](stack)
else:
stack.append(str2bool(token))

print(stack.pop())

Persze ebben nincs se biztonsági (egész globals-ot eléri), se egyéb hibaellenőrzés :)
De elég egyszerű belerakni..

Szerk:
Persze tabokat levágta, a code itt van: http://tpcg.io/lZNJm0

Ez így elég jónak tűnik, csak az a gond, hogy ott van a zárójel is.

Postfix nyelvnel nem kell.

--
When you tear out a man's tongue, you are not proving him a liar, you're only telling the world that you fear what he might say. -George R.R. Martin

Pontosan. De ha nagyon kell infix zarojelezes, akkor kb csak masfelszer ennyi kod egy infix -> postfix konverzio.

Itt van olyan, ahol nem gond a zárójel:
https://github.com/OLIMEX/WPC/tree/master/ISSUE-16
--
eutlantis

Nagyon jonak tunik ez a ply.

Recursive descent parser. A példa ugyan C de ez gondolom nem probléma. Ha csak egyszerű és vagy egyedi kifejezéseket akarsz feldolgozni akkor ennél több nem kell.

Ez neked lehet overkill, de en valoszinu egy parser generatort hasznalnek, konkretan ANTLR-t. Egyszeru nyelvtannal meg tudod hatarozni milyen szintaxist fogadsz el, es nem kell kezzel parsert irnod.

Tud generalni python parsert is megadott nyelvtan alapjan, es sok elerheto pelda nyelvtan van githubon.
ANTLR: https://github.com/antlr/antlr4/blob/master/doc/python-target.md
Artimatikai kifejezest felismero nyelvtan: https://github.com/antlr/grammars-v4/blob/master/arithmetic/arithmetic.g4 (tudom hogy neked logikai kifejezesek felismerese kell, de ezt eleg egyszeru az igenyeidnek megfeleloen modositani).

A legegyszerűbb ha keresel egy kész libet ami pont azt tudja ami neked kell. :)
Pl. https://pypi.org/project/boolean.py/ vagy https://github.com/hgomersall/python-boolean

Ha a feladat nem ennyire egyszerű hogy lenne rá kész megoldás akkor meg valamilyen parsert/parser generátort érdemes használni amiket már fent említettek páran.

Sub

Ha a userek nem ellenségesek (értsd a saját rendszerüket konfigolják ezekkel a kifejezésekkel, tehát egyébként is tudnának kárt okozni), akkor én is úgy csinálnám meg, hogy Python-ban értelmes kifejezéseket kérnék be, és eval-lal, vagy template-tel generálni és dinamikusan betöltött Python kóddal értékelném ki. Ez a legegyszerűbb, és könnyen lehet később bővíteni is.

Ha a kiértékelőt tudod sandboxolni, akkor akár biztonságos is lehet. Például JavaScript-hez szoktak lenni interpretált futtatókörnyezetek mindenféle nyelvekhez, egy olyannal is meg lehet csinálni.

A korrekt megoldás pedig egy Domain Specifikus nyelv (DSL) létrehozása, ami viszont több munka, a többiek elég jól leírták a lehetőségeket.

Javában mindháromra láttam működő példát, tehát annyi biztos, hogy mindhárom út járható.

Ja, és ha a userek geek-ek, akkor posztfix, vagy prefix jelölésű aritmetikát (Polish Notation vagy Reverse Polish Notation) is lehet csinálni, amit nagyon könnyen egyetlen stackkel fel lehet dolgozni. Ezt is írták mások is: https://en.wikipedia.org/wiki/Polish_notation

A Lex (Flex) / Yacc (Bison) páros univerzális, tehát erre a célra is alkalmas, bár ágyúval verébre.

http://dinosaur.compilertools.net/

p.s.: Most látom: https://hup.hu/node/163579#comment-2332811 , ez egyszerűbb.