Predykat – warunek o który mogą być wzbogacone produkcje języka bezkontekstowego – i-ta predykowana produkcja.
Produkcja z semantycznym predykatem jest wykonalna ( viable) tylko wtedy, gdy 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ą:
Występuje tu dodawanie o niskim priorytecie i modulo o wyższym. Możemy przekształcić według reguł do postaci bez lewostronnej rekurencji:
Ta gramatyka nie będąc już lewostronnie rekurencyjną pozostaje niejednoznaczna, predykaty ujednoznaczniają:
Wszędzie indziej odniesienia do E stają się odniesieniami do E. Produkcja jest wykonalna kiedy priorytet operacji modulo 3, odpowiada lub przekracza parametr pr. Pierwsze wołanie E ma pr = 0 i ponieważ parser rozwija „% E” w E. Kiedy wołamy parsowanie E, predykat nie przechodzi ponieważ priorytet operatora + jest zbyt niski: Konsekwentnie E nie dopasowuje operatora + opóźniając wołanie E.
Przypisy
Kategoria:Języki formalne