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 (Szablon:Lang 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\mathrm{\%}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(\mathrm{\%}E|+E{)}^{*}.$

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

$E[pr]\to \mathbf{\text{id}}(\{3⩾pr\}?\mathrm{\%}E[4]|\{2⩾pr\}?+E[3]{)}^{*}.$

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