Zbiory First i Follow: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
oszablonowałem.... |
po co, uproszczona definicja |
||
Linia 2:
{{dopracować|definicje powinny być jaśniejsze; potrzebne wyjaśnienie po co to etc}}
{{do weryfikacji|polska terminologia}}
'''FIRST<sub>k</sub>(''w''), FOLLOW<sub>k</sub>(''w'')''' - zbiory [[słowo|słów]] nad pewnym [[alfabet|alfabetem]], służące do analizowania [[gramatyka formalna|gramatyk]], np. podczas konstuowania [[parser|parserów]]. W uproszczeniu:
*FIRST<sub>k</sub>(''w'') - to [[prefiks|prefiksy]] długości ''k'' słów [[wyprowadzenie|wyprowadzalnych]] z ''w'' w badanej gramatyce.
*FOLLOW<sub>k</sub>(''w'') - to prefiksy długości ''k'', fragmentów słów wyprowadzalnych z danej gramatyki, znajdujące się bezpośrednio za fragmentem wyprowadzonym z ''w''.
*''w'' to ciąg symboli z gramatyki ([[symbol terminalny|terminalnych]] i [[symbol nieterminalny|nieterminalnych]]); w praktyce, zwłaszcza dla FOLLOW jest to pojedyńczy nieterminal.
Zbiory te pozwalają określić czy gramatyka posiada pewne własności (np. ułatwiające parsowanie). Podczas konstrukcji parsera za ich pomocą oblicza się jakie są możliwe konfiguracje analizatora i jakie powinny być podjęte działania w danej konfiguracji.
== Definicja ==
K-głową napisu ω będziemy nazywać pierwszych min(k, |ω|+1) symboli terminalnych napisu ω$ i oznaczać przez k:ω, bardziej formalnie k:ω = ω$ gdy |ω|<k oraz α gdy ω = αγ i |α|=k.<ref>W. Waite, G. Goos, Konstrukcja kompilatorów, Wydawnictwa Naukowo-Techniczne, Warszawa 1989</ref>
Linia 10 ⟶ 17:
Indeks k dla First i Follow pomijamy gdy ma wartość równą 1.
== Obliczanie dla ''k''=1 ==
Zbiór First możemy określić dla symbolu terminalnego, symbolu nieterminalnego oraz ciągu symboli. Jeśli x jest symbolem terminalnym wtedy First(x) = {x}. Dla symbolu nieterminalnego X używamy następującego algorytmu:
| |||