Tekst źródłowy strony Predykat (języki formalne)

Predykat – warunek o który mogą być wzbogacone produkcje [[Hierarchia Chomskiego#Języki bezkontekstowe (typu 2)|języka bezkontekstowego]]
: <math>A \to \{\pi_i\}? \alpha_i</math> – ''i''-ta predykowana produkcja.

Produkcja z semantycznym predykatem <math>\pi_i</math> jest wykonalna ({{lang|en}} viable) tylko wtedy, gdy <math>\pi_i</math> jest spełnione (true) w bieżącym stanie. Predykaty pozwalają na znaczne zwiększenie siły rozpoznawania języka, w tym, na dodaniu kontekstu do gramatyki bezkontekstowej.

Generator parserów ANTLR używa predykatów do ujednoznaczniania niejednoznacznej gramatyki.
Weźmy gramatykę niejednoznaczną i lewostronnie rekurencyjną:
: <math>E \to E\%E | E+E | id.</math>

Występuje tu dodawanie o niskim priorytecie i modulo o wyższym. Możemy przekształcić według reguł<ref name="Terence_Parr">{{cytuj |autor = Terence Parr, Sam Harwell, Kathleen Fisher |tytuł = Adaptive LL(*) Parsing: The Power of Dynamic Analysis |url = http://www.antlr.org/papers/allstar-techreport.pdf}}</ref> do postaci bez lewostronnej rekurencji:
: <math>E \to id (\%E|+E)^*.</math>

Ta gramatyka nie będąc już lewostronnie rekurencyjną pozostaje niejednoznaczna, predykaty ujednoznaczniają:
: <math>E[pr] \to \textbf{id} (\{3 \geqslant pr\}? \%E[4]| \{2 \geqslant pr\}?+E[3])^*.</math>

Wszędzie indziej odniesienia do E stają się odniesieniami do E[0].
Produkcja <math>\{3 \geqslant pr\}? \%E[4]</math> jest wykonalna kiedy priorytet operacji modulo 3, odpowiada lub przekracza parametr pr. Pierwsze wołanie E ma pr = 0 i ponieważ <math>3 \geqslant 0</math> parser rozwija „% E[4]” w E[0].
Kiedy wołamy parsowanie E[4], predykat <math>{2 \geqslant pr}?</math> nie przechodzi ponieważ priorytet operatora + jest zbyt niski: <math>2 \ngeq 4.</math> Konsekwentnie E[4] nie dopasowuje operatora + opóźniając wołanie E[0].

== Przypisy ==
{{Przypisy}}

[[Kategoria:Języki formalne]]