Czym jest gramatyka niedeterministyczna?

Poniżej znajduje się przykład reguły niedeterministycznej.

Zwróć uwagę na to, że ciągi wychodzące z S posiadają wspólny prefiks $\alpha$. To właśnie sprawia, że reguła ta jest niedeterministyczna.

$S \rightarrow \alpha \beta_1 \;|\; \alpha \beta_2 \;|\; \alpha \beta_3$

Pozbywanie się niedeterminizmu z gramatyki

Zazwyczaj jeśli się spotkasz z gramatyką niedeterministyczną na zajęciach, to zapewne będziesz musiał się tego niedeterminizmu w jakiś sposób pozbyć. Czemu zależy nam na pozbyciu się go?

Jeśli chcesz zbudować parser rekurencyjnie zstępujący (recursive descent parser), czyli rodzaj parsera top-down, to Twoja gramatyka musi spełnić dwa warunki.

1. Gramatyka nie posiada lewostronnej rekurencji

2. Gramatyka jest deterministyczna

My w tym artykule omawiamy punkt 2. Więcej o gramatykach oraz parserach możesz przeczytać w naszych innych artykułach lub zobaczyć w naszym kursie na dole.

metoda

Aby przekształcić taką niedeterministyczną regułę do reguły deterministycznej, musimy wprowadzić nowy nieterminal. U nas będzie się on nazywał $S’$.

Gramatyka 1: niedeterministyczna (występuje wspólny prefiks $\alpha$)

$S \rightarrow \alpha \beta_1 \;|\; \alpha \beta_2 \;|\; \alpha \beta_3$

Gramatyka 2: deterministyczna (wspólny prefiks został zastąpniony pośrednią produkcją $S \rightarrow \alpha S'$)

$S \rightarrow \alpha S'$
$S \rightarrow \beta_1 \;|\; \beta_2 \;|\; \beta_3$

Generalnie, chodzi tutaj o to, że nie zmieniamy w żaden sposób tego, co nasza gramatyka produkuje. Jedyne co robimy, to wprowadzamy pośrednią regułę z nowym znakiem nieterminalnym, która sprawia, że w jednej linijce nie pojawiają się słowa zaczynające się od tego samego znaku lub ciągu znaków.

Gramatyka 1 jest równoważna gramatyce 2.

przykład 1

Przekształć gramatykę 1 do gramamatyki deterministycznej

Gramatyka 1

$S \rightarrow aBcD \;|\; aBcDeF \;|\; e$
$B \rightarrow b$

Skąd w ogóle wiemy, ze ta gramatyka jest niedeterministyczna? Występują tutaj w jednej linice wspólne prefiksy. Tym razem nie jest to jeden znak, lecz ciąg znaków. Zaznaczyłem ten pefiks kolorem fioletowym

$S \rightarrow \textcolor{purple}{aBcD} \;|\; \textcolor{purple}{aBcD}eF \;|\; e$
$B \rightarrow b$

Gramatyka 2 (po usunięciu niedeterminizmu)