Jak rozwiązać niejednoznaczność w definicji gramatyki LR (1)?

Question

Piszę kompilator Golang w OCaml, a listy argumentów powodują mi trochę bólu głowy. W Go, można grupować kolejnych nazw parametrów tego samego typu w następujący sposób:

func f(a, b, c int) === func f(a int, b int, c int) 

można również wykaz rodzajów, bez nazwy parametrów:

func g(int, string, int) 

Oba style nie mogą być mix-and-dopasowane; albo wszystkie parametry są nazwane, albo żadne nie są.

Mój problem polega na tym, że gdy analizator składni widzi przecinek, nie wie, co robić. W pierwszym przykładzie jest a nazwa typu lub nazwa zmiennej o większej liczbie zmiennych? Przecinek ma podwójną rolę i nie jestem pewien, jak to naprawić.

Używam generatora parserów Menhir dla OCaml.

Edit: W tej chwili moja gramatyka Menhir następuje dokładnie zasady określone w http://golang.org/ref/spec#Function_types

Answer 1

Jak napisano, gramatyka go nie jest LALR(1). W rzeczywistości nie jest to LR(k) dla żadnego k. Jest to jednak jednoznaczne, więc możesz z powodzeniem przetworzyć go za pomocą parsera GLR, jeśli możesz go znaleźć (jestem prawie pewien, że istnieje kilka generatorów parowania GLR dla OCAML, ale nie wiem wystarczająco dużo o żadnym z nich polecić jeden).

Jeśli nie chcą (lub nie mogą) korzystać z GLR parser, można zrobić to samo, Russ Cox robił w gccgo kompilator, który korzysta bison. (bison może generować parsery GLR, ale Cox nie używa tej funkcji.) Jego technika nie polega na tym, że skaner rozróżnia nazwy typów od nazw innych niż typu.

Raczej po prostu akceptuje listę parametrów, których elementy są albo name_or_type lub name name_or_type (faktycznie, istnieje więcej możliwości niż te, ze względu na składnię ..., ale to nie zmienia ogólnej zasady.) To proste, jednoznaczne i LALR(1), ale jest nadmiernie akceptująca - na przykład akceptuje func foo(a, b int, c) - i nie generuje poprawnego drzewa składni abstrakcyjnej, ponieważ nie dołącza tego typu do listy zadeklarowanych parametrów.

Co oznacza, że ​​po pełnym przeanalizowaniu listy argumentów i umieszczeniu jej w AST dołączonej do deklaracji funkcji (na przykład), zostanie wykonany skan semantyczny, aby go naprawić i, jeśli to konieczne, wyprodukować komunikat o błędzie. Ten skan jest wykonywany od prawej do lewej nad listą elementów deklaracji, aby określony typ mógł być propagowany w lewo.

Warto zauważyć, że gramatyka w podręczniku referencyjnym również jest nadmiernie akceptująca, ponieważ nie wyraża ograniczenia, że ​​"albo wszystkie parametry są nazwane, albo żadne nie są". Ograniczenie to może być wyrażone w gramatyce LR (1) - pozostawiam to jako ćwiczenie dla czytelników - ale wynikowa gramatyka będzie o wiele trudniejsza do zrozumienia.

Answer 2

Nie masz niejasności. Świadczy o tym fakt, że standardowy analizator Go to LALR (1).

to nazwa typu lub nazwa zmiennej o większej liczbie zmiennych?

Więc twoja gramatyka i parser jako całość powinny być całkowicie odłączone od tablicy symboli; nie być C – Twoja gramatyka nie jest niejednoznaczna, dlatego możesz sprawdzić nazwę typu później w AST.

Oto odpowiednie zasady (od http://golang.org/ref/spec); są już poprawne.

Parameters  = "(" [ ParameterList [ "," ] ] ")" . 
ParameterList = ParameterDecl { "," ParameterDecl } . 
ParameterDecl = [ IdentifierList ] [ "..." ] Type . 
IdentifierList = identifier { "," identifier } . 

Wytłumaczę ci je:

IdentifierList = identifier { "," identifier } . 

Nawiasy klamrowe reprezentują KLEENE-zamknięcie (POSIX notacji wyrażenie regularne to gwiazdka). Zasada ta mówi, „an nazwa identyfikatora, a następnie ewentualnie dosłownym przecinkiem i identyfikator, a następnie ewentualnie dosłownym przecinkiem i identyfikator itp & hellip; ad infinitum”

ParameterDecl = [ IdentifierList ] [ "..." ] Type . 

nawiasach kwadratowych są wartości null; oznacza to, że ta część może być obecna lub nie. (W notacji regularnej POSIX jest to znak zapytania). Więc trzeba „Może IdentifierList, a następnie być może wielokropkiem, a następnie typu.

ParameterList = ParameterDecl { "," ParameterDecl } . 

Możesz mieć kilka ParameterDecl w liście, jak np func x(a, b int, c, d string).

Parameters  = "(" [ ParameterList [ "," ] ] ")" . 

Te zasady określa, że ParameterList jest opcjonalny i może być otoczony przez nawias i może zawierać opcjonalny końcowy przecinek dosłowne, przydatna, gdy piszesz coś takiego:

func x(
    a, b int, 
    c, d string, // <- note the final comma 
) 

GO gramma r jest przenośny i może być przetwarzany przez każdy parownik bottom-up z jednym znacznikiem z wyprzedzeniem.

---

Edit dotyczące „nie bądź C”: Powiedziałem to, bo C is context-sensitive i sposobu ich rozwiązywania tego problemu w wielu (wszystkich?) Kompilatorów jest przez okablowanie tablicę symboli do lexer i Lexing tokeny inaczej w zależności od tego, czy są zdefiniowane jako nazwy lub zmienne. To jest hackowanie i nie powinno się tego robić dla jednoznacznych gramatyk!