Pok-11-wyk-Slajd14
Porównanie złożoności gramatyk(1)
Sprawdźmy teraz, czy rzeczywiście gramatyka niejednoznaczna jest prostsza.
W inżynierii oprogramowania jako miarę złożoności gramatyk przyjmuje się liczbę nieterminali i liczbę produkcji (im liczby te są większe, tym złożoność jest większa). Liczba terminali nie zależy od gramatyki tylko od języka wejściowego.
W porównaniu nie weźmiemy pod uwagę produkcji S –> E, ponieważ została dodana tylko ze względów technicznych – do drukowania wyniku.
Wyniki porównania wskazują, że gramatyka niejednoznaczna rzeczywiście jest prostsza:
- w gramatyce jednoznacznej są 3 nieterminale (E , T , F ) , w niejednoznacznej – 1 (E )
- w gramatyce jednoznacznej mamy 10 produkcji, w niejednoznacznej - 8.
Jako porównanie trudności rozbudowywania obu typów gramatyk warto spróbować rozbudować przedstawioną gramatykę jednoznaczną o:
- niewiążący operator porównania ‘=‘
- prawostronnie łączny operator potęgowania '^‘
a następnie porównać efekt z przedstawionymi dalej rozwiązaniami dla gramatyki niejednoznacznej.
