🚀 go-pugleaf

Dnia 14-12-2007, Pt o godzinie 01:49 +0100, Adam Karpierz pisze:

> Jako "nosnik" starczy zwykly stos /w scope pamieta sie tylko
> gdzie wrocic a szuka sie przy jednoczesnej redukcji
> typedefow od konca/.

To jest trochę inne podejście (też dobre): uproszczona analiza
kontekstowa tylko dla potrzeb rozpoznawania typedefów, której wyniki
służą tylko lekserowi. Potem się to robi od nowa z uwzględnieniem
wszystkich konstrukcji.

Bo można też wykonywać początkowe etapy dalszej analizy równolegle
z lekserem: budować wszelkie informacje o symbolach widocznych w różnych
zakresach. Do dokończenia po parsowaniu, a nie do zrobienia od początku.

> Zgadza sie.  Tyle ze niekoniecznie do pokreconej struktury tylko
> normalnie w drzewie jako node typedefa
> (node typu: typedef z subnode1: nazwa i subnode2: "rozczesanym" typem).

Zupełnie nie o to mi chodziło. Problemem nie jest parsowanie samych
definicji ze słowem kluczowym 'typedef', tylko rozróżnianie
identyfikatorów oznaczających typy od pozostałych w innych produkcjach.
Wszystkie gramatyki C, o których słyszałem, mają osobny leksem na
identyfikator zwykły i osobny na identyfikator wprowadzony przez
typedef. Bez tego gramatyka byłaby niejednoznaczna i nie wiem, czy
ujednoznacznianie byłoby praktyczne.

Jeśli mamy coś takiego:
   a(*b)(c(d));
to jeśli a był wprowadzone przez typedef, to jest to deklaracja
wskaźnika b na funkcję zwracającą a, której parametr jest typu c
(nazwa d nie ma tu znaczenia jako nazwa parametru w typie funkcji).
Jeśli jednak a nie jest wprowadzone przez typedef, to jest to aplikacja
funkcji a do wartości odczytanej spod wskaźnika b, gdzie następnie
wynik jest zaaplikowany do aplikacji c do d. To jest zupełnie inne
drzewko, tzn. może i strukturalnie wygląda podobnie, ale węzły mają
zupełnie inną interpretację.

Inne są ciągi leksemów dopuszczone w analogicznych miejscach w jednym
i w drugim przypadku. Na przykład po deklaracji może być "=", "{"
i inicjalizator tablicy bądź struktury (w C99 z dodatkowymi ficzerami
w stylu jawnych nazw pól), a jeśli po wyrażeniu jest "=", to jest to
operator przypisania, po którym jest wyrażenie, które nie może mieć
formy czegoś w klamrach.

Zatem gdyby tworzyć zunifikowane drzewko bez wiedzy o tym, które
identyfikatory zostały wprowadzone przez typedef, to tych wszystkich
wariantów nie można by rozróżniać już w trakcie parsowania, tylko trzeba
zapamiętać, że było coś w klamrach, i dopiero potem się okaże, czy to ma
być analizowane jak inicjalizator, czy jak wyrażenie.

Podobnie problematyczna jest składnia rzutowania, która zaczyna się od
zupełnie niewinnego nawiasu okrągłego. (a)(b)(c) to może być aplikacja
a do b, a wynik jeszcze zaaplikowany do c, albo rzutowanie aplikacji b
do c, na typ a, albo rzutowanie c na typ b, a potem jeszcze na typ a.
A co dopiero, jeśli w nawiasach będą kombinacje typów funkcyjnych,
tablicowych i wskaźnikowych, gdzie nie wiadomo, co jest typem, a co
wyrażeniem.

Na domiar złego przy rzutowaniu mamy typ bez identyfikatora znajdującego
się w tym miejscu, w którym zazwyczaj przy wystąpieniu typu jest jakiś
identyfikator. To znaczy deklaracja zmiennej albo typedefu może wyglądać
np. tak:
   int (*(*a)(int *b))[10];
gdzie definiowanym identyfikatorem jest a, ale przy rzutowaniu mamy
w tym miejscu dziurę:
   (int (*(*)(int *b))[10])x
co może być trudno parsować jako rozszerzone wyrażenie, gdyby zamiast
int był identyfikator, o którym nie wiemy, czy jest typedefem.

Nie wiem, jak mogłoby wyglądać zunifikowane drzewko przy gramatyce
nierozróżniającej identyfikatorów typedefów od pozostałych. Może
wcale nie przypominałoby drzewka, może na przykład nie mogłoby zrobić
wiele więcej niż zbilansowanie nawiasów różnych rodzajów i zebranie
ciągów wyrażenio-typo-deklaratoro-inicjalizatorów między nawiasami.
Ludzie wolą jednak sprzęgnąć lekser z dalszymi fazami. Parsowanie
bezkontekstowe ze zunifikowanym drzewkiem jest co prawda teoretycznie
możliwe (o ile nie mamy narzucone, które aspekty składni musimy
rozpoznać już na etapie parsowania, a które możemy zostawić na potem),
ale być może jest całkiem niepraktyczne.

Dlatego twierdzę, że else jest łatwiejsze, bo else można ujednoznacznić
samą zmianą gramatyki, w dodatku całkiem łatwą. Język z takim else
jak w C jest wciąż bezkontekstowy - jedyny kłopot jest tej natury,
że najprostsza gramatyka bezkontekstowa jest większa niż najprostsza
gramatyka z niejednoznacznością. Jest większa i zawiera irytujące
prawie-duplikaty, dlatego literatura woli używać tej drugiej gramatyki,
gdzie trzeba uważać na sposób potraktowania niejednoznaczności.

W C++ równolegle z analizą leksykalną oprócz śledzenia typedefów trzeba
sprawdzać typy, budować hierarchię klas, rozpoznawać miejsca wstawienia
niejawnych konwersji, rozwiązywać przeciążanie funkcji, dedukować
parametry szablonów z typów argumentów funkcji szablonowej, uwzględniać
Koenig lookup, liczyć sizeofy typów, wykonywać arytmetykę na stałych -
połowa kompilatora musi być napisana w taki sposób, żeby można było
wykonywać ją przyrostowo na tym, co właśnie sparsowaliśmy, nie znając
jeszcze pełnego drzewa modułu wychodzącego z parsera.

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/