Matematické Fórum

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

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

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é

Čí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éž :-)

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;

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.