Predykat (języki formalne)
Predykat – warunek o który mogą być wzbogacone produkcje języka bezkontekstowego
- – i-ta predykowana produkcja.
Produkcja z semantycznym predykatem jest wykonalna ((ang.) 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ł[1] 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[0]. 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[4]” w E[0]. Kiedy wołamy parsowanie E[4], predykat nie przechodzi ponieważ priorytet operatora + jest zbyt niski: Konsekwentnie E[4] nie dopasowuje operatora + opóźniając wołanie E[0].
Przypisy[edytuj | edytuj kod]
- ↑ Terence Parr , Sam Harwell , Kathleen Fisher , Adaptive LL(*) Parsing: The Power of Dynamic Analysis [online] .