Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 18. 06. 2022 16:28 — Editoval Eratosthenes (18. 06. 2022 16:29)

Eratosthenes
Příspěvky: 2186
Reputace:   127 
 

Vyhodnocování aritmetických výrazů

Vlákno jsem založil jako doplnění diskuse na téma priority operátorů v sekci Zajímavé středoškolské úlohy. Protože jsem na rozpacích, kam to vlastně patří, nechal jsem to v těch zajímavých úlohách, zde jen odkaz

↑↑ Eratosthenes:


Budoucnost patří aluminiu.

Offline

 

#2 19. 06. 2022 00:48

MichalAld
Moderátor
Příspěvky: 4196
Reputace:   111 
 

Re: Vyhodnocování aritmetických výrazů

Jen bych doplnil, že když se píší překladače, nebo se vymýšlí gramatika nějakého jazyka, tak se musí krom priority operátorů definovat i tzv. asociativita, což určuje pořadí, v jakém se provádí výpočet, když mají operátory stejnou prioritu. Takže v programovacích jazycích je přesně dané, v jakém pořadí se výraz a*b*c bude vyhodnocovat. V různých jazycích je to obecně jiné, ale přesně dané.

To samé se týká i podmínek, třeba (a > b) and (c > d) and (e > f). Jazyky mohou také definovat, že výraz se dále nevyhodnocuje, pokud už je výsledek daný, takže když třeba podmínka (e > f) není splněna, tak další už se netestují. Toho lze také využívat při psaní kódu.

Třeba v C# lze legitimně psát
if ((c != null) && (c.cosi == 10))

když víme, že první závorka bude vyhodnocena dřív než ta druhá. V opačném případě by to mohlo hodit výjímku.

Offline

 

#3 19. 06. 2022 09:32

Eratosthenes
Příspěvky: 2186
Reputace:   127 
 

Re: Vyhodnocování aritmetických výrazů

↑ MichalAld:

To snad ne. Ve výrazu a*b*c je to sice jedno, ale násobení a dělení má stejnou prioritu a výraz a/b*c nelze vyhodnocovat jinak, než zleva doprava.

Pokud jde o logické podmínky, tam se (pokud vím) dá nastavit, zda se mají vyhodnocovat vždy komplet, anebo jen do jasného výsledku.


Budoucnost patří aluminiu.

Offline

 

#4 19. 06. 2022 13:14

Aleš13
Příspěvky: 208
Reputace:   
 

Re: Vyhodnocování aritmetických výrazů

Jestli si dobře pamatuju, tak třeba v Pascalu bylo přímo uvedeno, že pořadí provedení operací není definováno a že program který se spoléhá na určité pořadí provedení operací je chybný. Z hlediska konstrukce překladačů to není až tak úplně nesmyslné, třeba a/b*c může dát při určitých hodnotách operandů jiný výsledek než a*c/b (třeba denormalizace float pointu nebo naopak přetečení v průběhu výpočtu). Zrovna Pascal zná definiční obor jednotlivých proměnných a v rámci optimalizace je může přehodit. A některé překladače to i využívaly, stařičký Borland Pascal počítal výraz typu a+b+c+d odzadu, asi protože tak náhodou vyšel strom při syntaktické analýze.

ANSI C nebo Ada už to definují, ale stále zůstává na libovůli překladače pořadí vyhodnocení operandů, takže například číst ze souboru word příkazem getbyte+256*getbyte není úplně košér.

Offline

 

#5 19. 06. 2022 16:45

Eratosthenes
Příspěvky: 2186
Reputace:   127 
 

Re: Vyhodnocování aritmetických výrazů

↑ Aleš13:

S omezeným rozsahem typů by měl samozřejmě programátor počítat. Platí např.

[mathjax]\Huge e\approx \frac {(n+1)^n} {n^n} =\left( \frac {n+1} {n}\right) ^n[/mathjax]

ale zatímco pravý výraz je pro program v pohodě a n lze zvyšovat skoro do aleluja, levý zhavaruje už pro velmi malé n. A obávám se, že žádný optimalizátor programu s ním nic nenadělá.

To je ale zase trochy jiná písnička.


Budoucnost patří aluminiu.

Offline

 

#6 19. 06. 2022 20:27 — Editoval Aleš13 (19. 06. 2022 20:32)

Aleš13
Příspěvky: 208
Reputace:   
 

Re: Vyhodnocování aritmetických výrazů

Jasně, s tímhle už žádný jazyk nic nenadělá :-) Já to spíš myslel jako optimalizaci na úrovni generování kódu, když generuju kód pro a*b*c, tak v jednom pořadí násobení můžu po prvním součinu zahodit vyšší word výsledku (protože předem vím, že vyjde nulový) a v druhém ne, nebo něco v tomhle stylu.

Offline

 

#7 20. 06. 2022 16:18

MichalAld
Moderátor
Příspěvky: 4196
Reputace:   111 
 

Re: Vyhodnocování aritmetických výrazů

Myslím, že co se objevily objektové jazyky a přetěžování operátorů, tak se na tyhle věci klade větší důraz. Protože v objektových jazycích můžeme operátory používat i pro jiné než základní typy, násobit tedy nemusíme jen čísla, ale také  třídy, s tím, že překladač netuší, co to to násobení ve skutečnosti bude. Nebo můžeme mezi sebou násobit "properties" - což se sice navenek tváří jako proměnná, ale vevnitř to může něco dělat.

Myslím, že asociativita operátorů je celkem standardní pojem. To nevylučuje, že nemusí být definovaná (že může být jakákoliv), ale co jsem si všiml, tak v C-like jazycích bývá daná dost přesně. Přijde mi nesmysl, aby výraz typu

a*b/c*d*e/f/g*h se jednou počítal tak jak jsem ho napsal a podruhé třeba a*b*d*e*h/c/f/g.

Je samozřejmě nesmysl, aby se takovýhle výraz vyhodnocoval zprava, ale to parser obecně neví, a musí se mu to říct v rámci definice gramatiky jazyka.

Intuitivně bych řekl, že u LL jazyků se všechny výrazy vyhodnocují zleva. U LR jazyků (jako je céčko) je to nejspíš jedno. Jsem si téměř jistý, že v céčku se podmínky vyhodnocovaly zprava. V C# se zase naopak vyhodnocují zleva.

A samozřejmě nic nebrání podmínky psát tak, aby na tomhle nezávisely, tedy je vhodně ozávorkovat, nebo to rozdělit do více příkazů.

Ale nic z toho přece nesouvisí s obecným problémem asociativity operátorů, která určuje, v jakém pořadí se bude vyhodnocovat vícenásobný výraz.

Offline

 

#8 20. 06. 2022 16:22 — Editoval MichalAld (20. 06. 2022 17:03)

MichalAld
Moderátor
Příspěvky: 4196
Reputace:   111 
 

Re: Vyhodnocování aritmetických výrazů

Eratosthenes napsal(a):

↑ MichalAld:

To snad ne. Ve výrazu a*b*c je to sice jedno, ale násobení a dělení má stejnou prioritu a výraz a/b*c nelze vyhodnocovat jinak, než zleva doprava.

No jasně.

Jsou ale i jiné operátory, než matematické, třeba se používá >> nebo <<. A v C++ se používají jejich přetížené verze pro práci s textem, jako např:

Code:

cout << "This " << " is a " << "single C++ statement";

A tam je tak nějak jasné, že se to musí skládat od konce...naproti tomu

Code:

cin >> a >> b;

se zase musí skládat zleva.

Offline

 

#9 20. 06. 2022 16:55

MichalAld
Moderátor
Příspěvky: 4196
Reputace:   111 
 

Re: Vyhodnocování aritmetických výrazů

Já teda nechci tvrdit, že tomu nějak rozumím, jen jsem se kdysi nudil, tak jsem studoval, jak se programují překladače.

A jestli to správně chápu, tak v tom stromě, který vytváří parser, prostě neexistuje nic jako "rovnocená priorita". Vždycky je tam jen operand_1 * operand_2, a ty dva operandy se zase mohou "rozpadat" do dalších stromů.

Takže výraz typu a*b*c vždycky povede buď na strom a * (b * c) nebo (a * b) * c, tedy a * () nebo () * c, a kterou variantu si parser vybere závisí právě na asociativitě těch operátorů.

U dělení je asociativita jasná, tam ji otočit nemůžeme, u násobení si ji v principu můžeme zvolit. Nebo ji nechat stejnou jako u toho dělení. Nevím přesně, jak se to dělá.

Parser netuší nic o komutativnosti násobení, netuší že A * B = B * A, a je mu to jedno. Chci říct, že na to nesmí spoléhat a nemůže si pořadí prohazovat dle libosti. Protože když bychom operátor násobení použili pro násobení tříd představujících třeba matice, tak bychom dostali nesmyslné výsledky (násobení matic není obecně komutativní).

Offline

 

#10 20. 06. 2022 17:42

Aleš13
Příspěvky: 208
Reputace:   
 

Re: Vyhodnocování aritmetických výrazů

Po parseru dostane strom do parády optimalizátor a ten může například zaměňovat větve stromu. Samozřejmě jen když ví, že operace je komutativní, ale s tím není problém, protože přetížené operátory se stejně překládají jinak než vestavěné operace. Na téhle úrovni dokonce mohou vyhledávat opakující se podvýrazy a vyčíslovat je jen jednou (myslím, že zrovna GCC s -Os to dělá).

Offline

 

#11 20. 06. 2022 18:06

Eratosthenes
Příspěvky: 2186
Reputace:   127 
 

Re: Vyhodnocování aritmetických výrazů

↑ MichalAld:  ↑ Aleš13:

Vidím, že jsem rozpoutal debatu, která už je, přiznávám otevřeně, mimo moje obzory. Mně se kdysi hodilo nějaké takové řešítko do několika mých programů a když jsem viděl, jak z těch tradičních infixových zápisů lezou ty stromy, poněkud jsem se vyděsil. Pak jsem objevil prefix a postfix, což mi bylo sympatické. Nepootřebuju nic přetěžovat, pracuju pouze s reálnámi čísly, proměnnými a funkcemi a k tomu mi postfix stačí.

Ale téma nebudu ještě uzavírat, takže pokud si chcete ještě podiskutovat, máte volné pole :-)


Budoucnost patří aluminiu.

Offline

 

#12 20. 06. 2022 20:54 — Editoval MichalAld (20. 06. 2022 21:00)

MichalAld
Moderátor
Příspěvky: 4196
Reputace:   111 
 

Re: Vyhodnocování aritmetických výrazů

↑ Aleš13:

Já nic z toho nerozporuji. Optimalizátor může dělat obecně cokoliv, když to povede ke stejnému výsledku. Ale ten správný výsledek je určen definicí toho jazyka. A ta zahrnuje i asociativitu operátorů.

Konkrétně třeba v céčku je gramatika kolem násobení popsána takto (ANSCI C grammar (YACC)):

Code:

multiplicative_expression
    : cast_expression
    | multiplicative_expression '*' cast_expression
    | multiplicative_expression '/' cast_expression
    | multiplicative_expression '%' cast_expression
    ;

cast_expression je výraz s vyšší prioritou než má násobení, takže třeba proměnná.


Takže výraz typu A*B/C*D%E bude rozložen následovně - aby splnil tohle gramatické pravidlo, musí výraz končit proměnnou.

Tedy první krok bude () % E,
další (() * D) % E
další ((() / C) * D) % E
další (((() * B) / C) * D) % E
další ((((A) * B) / C) * D) % E

Takhle to parser rozloží do svého stromu. Parser vlastně neví, že hvězdička je nějaké násobení. Je mu to jedno. Pro něj je to jen symbol.

Offline

 

#13 20. 06. 2022 21:00

Aleš13
Příspěvky: 208
Reputace:   
 

Re: Vyhodnocování aritmetických výrazů

Jasně, to já jen, když už jsem se tu zakecal, nadhodil pár věcí které nebývají úplně zřejmé, ale přesto jsou legální. Jednou jsem se na to nachytal a pak těžce hledal chybu, tak si to kvůli tomu dobře pamatuju :-)

Offline

 

#14 21. 06. 2022 10:29

Stýv
Vrchní cenzor
Příspěvky: 5637
Reputace:   214 
Web
 

Re: Vyhodnocování aritmetických výrazů

MichalAld napsal(a):

Code:

cout << "This " << " is a " << "single C++ statement";

A tam je tak nějak jasné, že se to musí skládat od konce...

No vidis, a me je pritom jasne, ze se to musi skladat zleva. Co je podle tebe vyraz

Code:

" is a " << "single C++ statement"

?

Offline

 

#15 21. 06. 2022 15:02

MichalAld
Moderátor
Příspěvky: 4196
Reputace:   111 
 

Re: Vyhodnocování aritmetických výrazů

No jo, už to tak vypadá.

Pravda je, že já tohle nikdy nepužíval, jen jsem si na to vzpoměl... takže to asi není úplně nejlepší případ.


Tak ať nepíšu blbosti, tak jsem koukal, jak to je třeba v javě, a ony jsou skoro všechny operátory left-associative. Ale nějaké jsem našel i ty right-associative. Zpravidla jsou to unární operátory, ale také jsou to ty operátory typu +=, *=,...

Orders of operation


Takže a *= b *= c by se mělo vyhodnocovat zprava. Jako kdybychom to napsali na dva řádky:

Code:

b *= c;  // b = b * c
a *= b;  // a = a * b

Offline

 

#16 21. 06. 2022 19:10

MichalAld
Moderátor
Příspěvky: 4196
Reputace:   111 
 

Re: Vyhodnocování aritmetických výrazů

Zase si začínám pohrávat s myšlenkou, že si napíši nějaký vlastní interpret matematických výrazů. Né že by to k něčemu bylo (podobných věcí existují minimálně stovky) ale jen tak, abych si to zkusil.

Na matematický výraz myslím ani není potřeba parser, stačí na to zásobník pomocí kterého se to převede na prefixovou (či postfixovou) notaci. Ale já bych si stejně raději napsal parser.

Offline

 

#17 21. 06. 2022 21:00

Aleš13
Příspěvky: 208
Reputace:   
 

Re: Vyhodnocování aritmetických výrazů

Doporučuji, psaní parserů je výborná relaxace :-) Samozřejmě poctivé psaní ab initio, žádný Yacc a podobně :-)

Offline

 

#18 22. 06. 2022 09:38

MichalAld
Moderátor
Příspěvky: 4196
Reputace:   111 
 

Re: Vyhodnocování aritmetických výrazů

A to já jsem myslel, že bych použil Bison, pro začátek...

Ale na matematické výrazy to jde i bez toho, jen rekurzivním voláním vhodných funkcí (které odpovídají té gramatice. Tím asi začnu, to by mělo být jednoduché.

Offline

 

#19 22. 06. 2022 11:19 — Editoval Aleš13 (22. 06. 2022 11:32)

Aleš13
Příspěvky: 208
Reputace:   
 

Re: Vyhodnocování aritmetických výrazů

Je to tak. Mně to přijde, že všechny ty generátory parserů byly vymyšlené v době, kdy se šetřilo každým gigabytem :-) protože napsat rekurzivní parser je jednodušší než se učit s tím generátorem. Stačí implementovat funkce getsymbol() a ungetsymbol() (návrat o krok zpět mi přijde přirozenější než se trápit s lookahead algoritmem) a jde to samo, nejen na výrazy, ale než se vzpamatuješ, máš rozebraný celý jazyk.

Offline

 

#20 22. 06. 2022 14:49

MichalAld
Moderátor
Příspěvky: 4196
Reputace:   111 
 

Re: Vyhodnocování aritmetických výrazů

Ale tohle jde jen na LL jazyky, né ?  Na LR se to už nedá použít. Nebo ano ?

Offline

 

#21 22. 06. 2022 20:49

Aleš13
Příspěvky: 208
Reputace:   
 

Re: Vyhodnocování aritmetických výrazů

Nevím :-) Do LR parseru jsem se nikdy nepustil, na ruční práci je to moc složité a zatím všechno šlo řešit LL parserem s backtrackingem (ten není u LR potřeba). Vlastně ani nevím, který jazyk je LR a nedá se vyjádřit LL.

Offline

 

#22 22. 06. 2022 23:16

MichalAld
Moderátor
Příspěvky: 4196
Reputace:   111 
 

Re: Vyhodnocování aritmetických výrazů

Céčko by mělo být LR

Offline

 

#23 23. 06. 2022 13:16

Aleš13
Příspěvky: 208
Reputace:   
 

Re: Vyhodnocování aritmetických výrazů

Zběžně jsem na to koukal (parser na c-like jazyk jsem nikdy nepsal, tak jen takhle odhaduju) a připadá mi, že ten přístup s rekurzivním analyzátorem by na to měl fungovat:
https://cs.wmich.edu/~gupta/teaching/cs … 20form.htm
Aspoň jsem tam nenašel protipříklad, ale ten se stejně vždycky najde až když to člověk začne doopravy psát :-)

Offline

 

#24 23. 06. 2022 19:03 — Editoval MichalAld (23. 06. 2022 19:04)

MichalAld
Moderátor
Příspěvky: 4196
Reputace:   111 
 

Re: Vyhodnocování aritmetických výrazů

Já o tom mnoho nevím, měl jsem za to, že je "všeobecně známá věc" že céčka mají LR gramatiku, a ta že se nedá parsovat LL parserem (takže ani rekurzivním parserem).

Vzpomínám si, že i na ty aritmetické výrazy se tam musel dělat nějaký hack, aby to hned na začátku neskončilo nekonečnou rekurzí.

Já jsem nikdy moc nepochopil, co přesně je na tom céčku LR, protože mnoho věcí je podobných třeba pascalu, který je LL.

Jestli to chápu, tak u LL (třeba LL1) nepotřebujeme měnit nic zpětně. Stačí nám pohled na 1 krok dopředu a víme, co bude následovat. U LR to tak není, tam to "pochopíme" až zpětně, které pravidlo gramatiky to splňuje.

Proto můžeme na LL gramatiku použít rekurzivní parser, protože v daném kroku víme, kterou funkci máme zavolat. U LR to nevíme...

Ale co přesně v té céčkové gramatice tomu vadí, to já nevím. Ale hádám, že to nebude nějaká drobnost, protože by se to upravilo.

Offline

 

#25 23. 06. 2022 22:46

Aleš13
Příspěvky: 208
Reputace:   
 

Re: Vyhodnocování aritmetických výrazů

Asi neupravilo, pravověrní céčkaři (to jsou ti, co se do krve hádají, že pole je pointer) považují svůj jazyk za dokonalý, tudíž jakákoliv úprava může být jen k horšímu :-) Spíš se udělá ten hack do parseru, imho to nebude nic obtížného, jinak bych se o tom určitě už někde dočetl. Jinak s tím LL a LR je to přesně tak, proto se LR vyhýbám, není moc intuitivní a programování pak není dostatečně zábavné :D

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson