Przeznaczenie zestawów FIRST I FOLLOW w PARSERACH LL(1)?

W PARSERZE LL(1) parser zachowuje obszar roboczy początkowo przypisany do symbolu początku, a następnie do znacznika końca łańcucha (Zwykle oznaczonego $). Na każdym kroku wykonuje jedną z następujących czynności:

• Jeśli pierwszym symbolem obszaru roboczego jest terminal, to dopasowuje go do następnego tokena wejścia (lub zgłasza błąd, jeśli nie pasuje.)
• Jeśli pierwszy symbol obszaru roboczego jest nieterminalny, to przewiduje jaką produkcję zastąpić bezterminowe z.

Krok przewidywania to miejsce, w którym pojawiają się pierwsze i następne. Parser musi być w stanie odgadnąć, opierając się wyłącznie na bieżącym nieterminalu i następnym tokenie wejścia, której produkcji użyć. Pytanie brzmi, jak to zrobić.

Załóżmy, że bieżącym nieterminalem jest A, a następnym tokenem wejścia jest t. Jeśli znasz produkcje A, którą z nich wybierzesz? Jest jeden prosty przypadek do rozważenia: jeśli istnieje produkcja postaci a → tw, gdzie ω jest jakimś arbitralnym ciągiem, powinieneś wybrać tę produkcję, ponieważ t, na które patrzysz jako wejście, będzie pasować do t z przodu produkcji.

Istnieje również kilka złożonych przypadków do rozważenia. Załóżmy, że mamy produkcję postaci a → BW, gdzie B jest nieterminalnym, a ω jest jakimś ciągiem. W jakich okolicznościach chciałbyś odgadnąć tę produkcję? Cóż, jeśli wiesz, że następnym symbolem terminala jest t, nie chcesz zgadywać tej produkcji, chyba że wiesz że B może rozwinąć się do ciągu, który zaczyna się od terminala t (jest inny przypadek, o którym porozmawiamy za sekundę). Tutaj pojawiają się pierwsze zestawy. W gramatykach bez ε, set FIRST (X) dla niektórych nieterminalnych X jest zbiorem wszystkich terminali, które mogą potencjalnie pojawić się na początku jakiegoś ciągu pochodzącego z X. Jeśli masz produkcję postaci a → BW i widzisz nieterminalne t, domyślasz się, że używasz tej produkcji dokładnie wtedy, gdy T ∈ FIRST(B); to znaczy, B może wyprowadzać pewne wartości. łańcuch zaczynający się na t. Jeśli B nie wyprowadza niczego zaczynającego się na t, to nie ma powodu, aby go wybierać, a jeśli b wyprowadza coś zaczynającego się na t, chciałbyś dokonać tego wyboru, abyś mógł w końcu dopasować t do niego.

Rzeczy stają się nieco trudniejsze, gdy pojawiają się nowe produkcje. Załóżmy teraz, że masz postać a → BCw, gdzie B I C są nieterminalami, a ω jest ciągiem. Załóżmy również, że następnym tokenem wejścia jest t. Jeśli t & w; Najpierw (B), potem wybralibyśmy tę produkcję, jak wspomniano powyżej. Jednak co się stanie, jeśli T ∉ pierwszy(B)? Jeśli w gramatyce są produkcje ε, możemy nadal chcieć wybrać tę produkcję, jeśli B może wyprowadzić ε I T & in; FIRST (C). Dlaczego? Jeśli tak się stanie, oznacza to, że możemy być w stanie dopasować t, produkując BCW, a następnie produkując ε z B, pozostawiając Cw, z którym dopasujemy t. Jest to jeden z kontekstów, w którym możemy "przejrzeć" nieterminal. Na szczęście zajmuje się tym Pierwsze sety. Jeśli nieterminalny X może wytworzyć ε, to ε & in; FIRST(X). Dlatego możemy użyć pierwszych zestawów, aby sprawdzić, czy musimy" przejrzeć " nieterminal, sprawdzając, czy ε ∈ FIRST(X).

Do tej pory nie rozmawialiśmy o zestawach śledzenia. Gdzie one wchodzą? Cóż, Załóżmy, że przetwarzamy nieterminalne A, widzimy terminal t, ale żadna z produkcji dla A nie może faktycznie konsumować T. co wtedy zrobimy? Okazuje się, że wciąż jest sposób, żeby zjeść to T. Pamiętaj, że parsery LL(1) działają przez utrzymywanie obszaru roboczego z łańcuchem znaków. Jest możliwe, że t, na który patrzymy, nie powinno być dopasowane do obecnego nieterminalnego A w ogóle, a zamiast tego powinniśmy mieć produce ε, a następnie pozwolić, aby niektóre późniejsze nieterminalne w przestrzeni roboczej dopasowały się do t. to jest miejsce, w którym pojawiają się następne zestawy. Set FOLLOW (ang. FOLLOW) - zbiór wszystkich symboli terminali, które mogą pojawić się bezpośrednio po X w pewnej derywacji. Wybierając, którą produkcję wybrać dla A, dodajemy ostateczną regułę-jeśli symbol końcowy t znajduje się w następującym zbiorze A, wybieramy pewną produkcję, która ostatecznie wytworzy ε. W ten sposób A "zniknie" i możemy dopasować t do jakiegoś znaku, który pojawia się po a nieterminal.

To nie jest kompletne wprowadzenie do parsowania LL(1), ale mam nadzieję, że pomoże Ci zrozumieć, dlaczego potrzebujemy zestawów FIRST I FOLLOW. Aby uzyskać więcej informacji, wybierz książkę na temat parsowania (polecam Parsing Techniques: A Practical Guide by Grune and Jacobs) lub wziąć udział w kursie kompilatorów. Jako całkowicie bezwstydny plug, prowadziłem kurs kompilatorów w lecie 2012-2013 i wszystkie slajdy z wykładów są dostępne online.

Mam nadzieję, że to pomoże!