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

#26 24. 06. 2022 10:49 — Editoval MichalAld (24. 06. 2022 10:56)

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

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

Já o tom skoro nic nevím, mám o tom jedinou knížku, tuhle - Compiller design in C.

Tam je takový úvodní příklad (učebnicový) na parser výrazů sestávajících jen ze sčítání a násobení a závorek. S tím, že používá následující gramatiku:

Code:

1. statements -> expression ;
2.             | expression ; statements
3. expression -> expression + term
4.              | term
5. term -> term *factor
6.       | factor
7. factor -> number
8.         | ( expression )

No a s tímhle si rekurzivní parser neporadí, protože třeba pravidlo 3 by znamenalo aby funkce "expression" zavolala hned sama sebe. A tak se gramatika musí převést na jiný tvar, dost neintuitivní. No a v tom je asi ten problém, že někdy to takto převést nejde.

LR parser s tímhle problém nemá, a nemusí se to na nic převádět. Ale každopádně existují gramatiky, které na LL prostě převést nelze. To je podle mě jisté.

Ta upravená gramatika vypadá (v té knížce) nějak takto.


Code:

1. statements -> EOF
2.             | expression ; statements
3. expression -> term expression'
4. expression' -> + term expression'
5.             | ee
6. term -> factor term'
7. term' -> *factor term'
8.        | ee
9. factor -> number
10.        | ( expression )

EOF je End Of File, a ee je empty string, v tom se teď trochu ztrácím, ale právě že ten má zastavit tu nekonečnou rekurzi. Ty tomu asi budeš rozumět líp...


No a právě že ty LR  parsery tyhle modifikace gramatiky nepotřebují, může zůstat ta původní, kterou každý chápe. A taky se tam píše (a mě to tak taky připadá) že jazyky s LR gramatikami jsou takové víc intuitivní, pro nás, co je používáme. Podle mě to s těma "céčkovskýma vynálezama" jakou jsou pointery vždy a všude, moc nesouvisí. Tohle se týká spíš syntaxe samotné, než toho, co to pak reálně dělá.

Offline

 

#27 24. 06. 2022 23:13 — Editoval Aleš13 (24. 06. 2022 23:28)

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

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

Souhlas, existují LR které nelze převést na LL, i jsem na to kdysi viděl nějaký důkaz (a samozřejmě ho úplně zapomněl). Jde o to, kdy a na co je taková gramatika potřeba. Já jsem spíš praktik, takže by mě asi nenapadlo si nadefinovat takovéhle výrazy (nebo programovací jazyk) který nebude snadné analyzovat. To co uvádějí v té knížce mi přijde takové dost umělé, nedovedu si představit, že bych to mohl chtít takhle vymyslet. Pro mě byl výraz vždycky spíš něco jako

      Výraz ::= [ Unární_operátor ] Člen { Aditivní_operátor Člen }
      Unární_operátor ::= "-" | "+"
      Aditivní_operátor ::= "+" | "-"
      Člen ::= Prvek { Multiplikativní_operátor Prvek }
      Multiplikativní_operátor ::= "*" | "/"
      Prvek ::= Numerický_literál | "(" Výraz ")" 
      Numericky_literal ::=  Číslo ["." [Číslo]]
      Číslo ::= Číslice { Číslice }
      Číslice ::== "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"

(snad v tom nemám moc chyb - aspoň idea je snad jasná) Chápu, že to ode mě není úplně obecný přístup, ale s tím LR bych se dost trápil, tak pokud by to nebylo v rámci nějakého vyššího cíle naprosto nezbytné, asi bych se na to vykašlal :-)

Offline

 

#28 25. 06. 2022 00:14

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

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

Tak ono je to skoro to samé, když jsem přeložil pojmy a vyhodil tam ten "statement", je to skoro jak to tvoje. Ale úplně stejné to není, ty tam používáš ty složené závorky, já úplně přesně nevím, co znamenají. Ale zasae tam nemáš tu rekurzi (na pravé straně to samé co na levé).

Code:

výraz ::= výraz + člen  |  člen
člen ::= člen * prvek  |  prvek
prvek ::= Numericky_literal  | ( výraz )

Offline

 

#29 25. 06. 2022 12:22 — Editoval Aleš13 (25. 06. 2022 12:26)

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

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

Teď jsi mě trochu zaskočil. Když vynechám balast, tak ten můj příklad v nerekurzivní verzi (závorky [ ] znamenají část která může být vynechána, { } opakování části nula- až vícekrát) vypadá opravdu stejně, jen tam nelze vyrobit tu nekonečnou rekurzi (a nemusí se tudíž ani použít ta úprava viz výše).

Code:

Výraz ::= Člen { + Člen }
Člen ::= Prvek { * Prvek }
Prvek ::= Číslo | ( Výraz )

Podle toho se dá skutečně programovat tak jak to čtu, když ještě dodefinuju zjednodušené

Code:

Číslo ::= 0|1|2|3|4|5|6|7|8|9

tak program na výpočet výrazu může vypadat třeba takhle nějak, kdy rekurze, až na nepřímou rekurzi Prvek -> Výraz, je nahrazená cyklem. Ale mám teď trochu chaos v tom proč se to liší když je to totéž :-)

Code:

function getchar : char; // přečte znak ze vstupu
procedure ungetchar; // vrátí pozici vstupu o jeden symbol zpět

function clen : integer;
begin
  result:=prvek;
  while true do begin // nekonečný cyklus
    c:=getchar;
    if c='*' then begin
      result*=prvek;
      end
    else begin
      ungetchar; // backtracking
      break; // vyskočit z cyklu
      end;
    end;
  end;

function vyraz : integer;
begin
  result:=clen;
  while true do begin // nekonečný cyklus
    c:=getchar;
    if c='+' then begin
      result+=clen;
      end
    else begin
      ungetchar; // backtracking
      break; // vyskočit z cyklu
      end;
    end;
  end;

function prvek : integer;
begin
  c:=getchar;
  if c in ['0'..'9'] then begin
    result:=ord(c)-ord('0');
    end
  else if c='(' then begin
    result:=vyraz;
    c:=getchar;
    if c<>')' then begin
      writeln('Chyba: očekávána pravá závorka');
      halt; // konec programu
      end;
    end
  else begin
    writeln('Chyba: očekáváno číslo');
    halt; // konec programu
    end;
  end;

function main : integer;
begin
  result:=vyraz;
  if getchat<>EOF then begin // nezpracoval se celý vstup
    writeln('Chyba: neočekávaný konec výrazu');
    halt; // konec programu
    end;
  end;

Offline

 

#30 26. 06. 2022 19:09

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

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

Doufal jsem, že tenhle jazyk se už nebudu muset učit ... ale podívám se na to.
Můžu to srovnat s tím parserem z knížky.

Offline

 

#31 26. 06. 2022 21:03

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

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

To asi ani neni potreba, je to psane presne podle te BNF a funguje to :-) Spis je otazka jestli a jak by to slo timhle stylem  naprogramovat 1:1 podle te rekurzivni definice.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson