Predykat (języki formalne)

Predykat – warunek o który mogą być wzbogacone produkcje języka bezkontekstowego

$A\to \{\pi _{i}\}?\alpha _{i}$ – i-ta predykowana produkcja.

Produkcja z semantycznym predykatem $\pi _{i}$ jest wykonalna ((ang.) viable) tylko wtedy, gdy $\pi _{i}$ 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ą:

$E\to E\%E|E+E|id.$

Występuje tu dodawanie o niskim priorytecie i modulo o wyższym. Możemy przekształcić według reguł do postaci bez lewostronnej rekurencji:

$E\to id(\%E|+E)^{*}.$

Ta gramatyka nie będąc już lewostronnie rekurencyjną pozostaje niejednoznaczna, predykaty ujednoznaczniają:

$E[pr]\to {\textbf {id}}(\{3\geqslant pr\}?\%E[4]|\{2\geqslant pr\}?+E[3])^{*}.$

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