python feldolgozo (parser) irasa

Szkriptek: Python, Perl, Bash, ...

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.

  • 1761 megtekintés

( vilmos.nagy | 2019. 03. 25., h – 19:53 )

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 :)

( muszike | 2019. 03. 25., h – 20:13 )

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?

( airween v | 2019. 03. 25., h – 20:37 )

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.

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.

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

( r3flow | 2019. 03. 25., h – 21:49 )

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.

( uid_15483 | 2019. 03. 25., h – 21:59 )

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… (tudom hogy neked logikai kifejezesek felismerese kell, de ezt eleg egyszeru az igenyeidnek megfeleloen modositani).

( asch v | 2019. 03. 26., k – 12:58 )

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