NN=Szewc, V=schował, NA=pastę, PP=do butów
Algorytm A* posługuje się heurystyką przy wyborze ścieżki. W przypadku analizy składniowej heurystyka będzie służyła do przybliżania prawdopodobnego wyniku analizy „reszty”
Poniższa ilustracja pokazuje dwie alternatywy dla analizy składniowej użytego przykładu. Dotychczasowa ścieżka jest już fragmentem poprawnie zanalizowanym (w sensie Viterbiego, kolor zielony). Wartość g(x) dla aktualnie rozważanego węzła x (kolor żółty) obliczamy zatem z prawdopodobieństw w dotychczasowym fragmencie oraz prawdopodobieństwa aktualnego węzła x, mnożąc wartość przez -1, tak aby algorytm wybierający najniższe wartości odnalazł najwyższe prawdopodobieństwo.
Heurystyka Heurystyka używana przez algorytm A* oparta jest na (zwykle nie wszystkich) pozostałych węzłach (kolor czerwony) – musi pozwalać na oszacowanie prawdopodobieństwa wyniku pozostałej części procesu analizy składniowej, przy ustalonym już, uprzednio przeanalizowanym fragmencie.