Jaki powinien być typ danych tokenów, które leksykon zwraca do analizatora składni?

Jak wspomniano w tytule, jaki typ danych leksyker powinien zwrócić / przekazać analizator składni? Czytając artykuł z analizy leksykalnej, który ma Wikipedia, stwierdził:

W informatyce analiza leksykalna to proces przekształcania sekwencji znaków (np. W programie komputerowym lub na stronie internetowej) w sekwencję tokenów ( ciągów o zidentyfikowanym „znaczeniu”).

Jednak w zupełnej sprzeczności z powyższym stwierdzeniem, gdy na inne witryny ( Przegląd kodu, jeśli jesteś ciekawy) udzielono odpowiedzi na inne pytanie, odpowiadający stwierdził, że:

Lexer zwykle odczytuje ciąg znaków i konwertuje go na strumień ... leksemów. Leksemy muszą być tylko strumieniem liczb .

i dał ten obraz:

nl_output => 256
output    => 257
<string>  => 258

W dalszej części artykułu wspomniał Flex, że już istnieje leksykon, i powiedział, że pisanie „reguł” z nim byłoby prostsze niż pisanie leksemu ręcznie. Podał mi ten przykład:

Space              [ \r\n\t]
QuotedString       "[^"]*"
%%
nl_output          {return 256;}
output             {return 257;}
{QuotedString}     {return 258;}
{Space}            {/* Ignore */}
.                  {error("Unmatched character");}
%%

Aby uzyskać więcej informacji i uzyskać więcej informacji, przeczytałem artykuł w Wikipedii na temat Flex . artykuł Flex pokazał, że można zdefiniować zestaw reguł składniowych z tokenami w następujący sposób:

digit         [0-9]
letter        [a-zA-Z]

%%
"+"                  { return PLUS;       }
"-"                  { return MINUS;      }
"*"                  { return TIMES;      }
"/"                  { return SLASH;      }
"("                  { return LPAREN;     }
")"                  { return RPAREN;     }
";"                  { return SEMICOLON;  }
","                  { return COMMA;      }
"."                  { return PERIOD;     }
":="                 { return BECOMES;    }
"="                  { return EQL;        }
"<>"                 { return NEQ;        }
"<"                  { return LSS;        }
">"                  { return GTR;        }
"<="                 { return LEQ;        }
">="                 { return GEQ;        }
"begin"              { return BEGINSYM;   }
"call"               { return CALLSYM;    }
"const"              { return CONSTSYM;   }
"do"                 { return DOSYM;      }
"end"                { return ENDSYM;     }
"if"                 { return IFSYM;      }
"odd"                { return ODDSYM;     }
"procedure"          { return PROCSYM;    }
"then"               { return THENSYM;    }
"var"                { return VARSYM;     }
"while"              { return WHILESYM;   }

Wydaje mi się, że leksykon Flex zwraca ciągi słów kluczowych \ tokenów. Ale może to być zwracanie stałych, które są równe pewnym liczbom.

Gdyby lekser miał zwrócić liczby, to jak odczytałby literały łańcuchowe? zwracanie liczby jest w porządku dla pojedynczych słów kluczowych, ale jak poradziłbyś sobie z ciągiem znaków? Czy leksykon nie musiałby konwertować ciągu na liczby binarne, a następnie parser przekształciłby liczby z powrotem na ciąg. Wydaje się o wiele bardziej logiczne (i łatwiejsze), aby leksykon zwracał ciągi, a następnie pozwalał analizatorowi konwertować dowolne literały ciągu liczbowego na liczby rzeczywiste.

A może leksykon może zwrócić oba? Próbowałem napisać prosty leksykon w c ++, który pozwala mieć tylko jeden typ zwracanych funkcji. Skłoniło mnie to do zadania pytania.

Aby zawęzić moje pytanie do akapitu: pisząc leksykę i zakładając, że może on zwrócić tylko jeden typ danych (ciągi lub liczby), co byłoby bardziej logicznym wyborem?

Ogólnie rzecz biorąc, jeśli przetwarzasz język leksykalnie i parsując, masz definicję swoich tokenów leksykalnych, np .:

NUMBER ::= [0-9]+
ID     ::= [a-Z]+, except for keywords
IF     ::= 'if'
LPAREN ::= '('
RPAREN ::= ')'
COMMA  ::= ','
LBRACE ::= '{'
RBRACE ::= '}'
SEMICOLON ::= ';'
...

i masz gramatykę dla parsera:

STATEMENT ::= IF LPAREN EXPR RPAREN STATEMENT
            | LBRACE STATEMENT BRACE
            | EXPR SEMICOLON
EXPR      ::= ID
            | NUMBER
            | ID LPAREN EXPRS RPAREN
...

Lexer pobiera strumień wejściowy i tworzy strumień tokenów. Strumień tokenów jest wykorzystywany przez analizator składni do utworzenia drzewa analizy. W niektórych przypadkach wystarczy znajomość typu tokena (np. LPAREN, RBRACE, FOR), ale w niektórych przypadkach potrzebujesz rzeczywistej wartości powiązanej z tokenem. Na przykład, gdy napotkasz token ID, będziesz chciał rzeczywistych znaków, które składają się na ID później, gdy będziesz próbował dowiedzieć się, do którego identyfikatora chcesz się odwoływać.

Zwykle masz coś mniej więcej takiego:

enum TokenType {
  NUMBER, ID, IF, LPAREN, RPAREN, ...;
}

class Token {
  TokenType type;
  String value;
}

Tak więc, gdy leksyk zwraca token, wiesz, jaki to typ (którego potrzebujesz do parsowania), oraz sekwencję znaków, z których został wygenerowany (z których później będziesz potrzebować, aby zinterpretować ciąg i literały liczbowe, identyfikatory, itp.). Może się wydawać, że zwracasz dwie wartości, ponieważ zwracasz bardzo prosty typ agregacji, ale tak naprawdę potrzebujesz obu części. W końcu chcesz inaczej traktować następujące programy:

if (2 > 0) {
  print("2 > 0");
}

if (0 > 2) {
  print("0 > 2");
}

Tworzą one tę samą sekwencję typów tokenów : JEŻELI, LPAREN, NUMER, GREATER_THAN, NUMBER, RPAREN, LBRACE, ID, LPAREN, STRING, RPAREN, SEMICOLON, RBRACE. Oznacza to, że parsują to samo. Ale kiedy faktycznie robisz coś z drzewem analizy, zwracasz uwagę, że wartość pierwszej liczby to „2” (lub „0”) i że wartość drugiej liczby to „0” (lub „2” ”) oraz że wartość ciągu wynosi„ 2> 0 ”(lub„ 0> 2 ”).

Jak wspomniano w tytule, jaki typ danych leksyker powinien zwrócić / przekazać analizator składni?

Oczywiście „Token”. Lexer wytwarza strumień tokenów, więc powinien zwrócić strumień tokenów .

Wspominał Flex, już istniejący leksykon, i powiedział, że pisanie „reguł” przy pomocy niego byłoby prostsze niż pisanie leksemu ręcznie.

Leksyki generowane maszynowo mają tę zaletę, że można je szybko wygenerować, co jest szczególnie przydatne, jeśli uważasz, że gramatyka leksykalna bardzo się zmieni. Ich wadą jest to, że często nie uzyskuje się dużej elastyczności przy wyborze opcji implementacji.

To powiedziawszy, kogo to obchodzi, czy to jest „prostsze”? Pisanie leksera zwykle nie jest najtrudniejsze!

Pisząc leksykę i zakładając, że może on zwrócić tylko jeden typ danych (ciągi lub liczby), co byłoby bardziej logicznym wyborem?

Ani. Lexer zazwyczaj ma „następną” operację, która zwraca token, więc powinien zwrócić token . Token nie jest łańcuchem ani liczbą. To jest token.

Ostatni lexer, który napisałem, był leksem „pełnej wierności”, co oznacza, że ​​zwrócił token śledzący położenie wszystkich białych znaków i komentarzy - które nazywamy „ciekawostkami” - w programie, a także token. W moim lekserze token został zdefiniowany jako:

• Szereg wiodących ciekawostek
• Rodzaj tokena
• Szerokość tokena w znakach
• Tablica końcowych ciekawostek

Ciekawostki zdefiniowano jako:

• Ciekawostki - białe znaki, nowa linia, komentarze i tak dalej
• Szerokość ciekawostek w znakach

Więc gdybyśmy mieli coś takiego

    foo + /* comment */
/* another comment */ bar;

że lex postaci czterech znaczników z tokenów rodzaju Identifier, Plus, Identifier, Semicoloni szerokości 3, 1, 3, 1. pierwszy identyfikator zawiera prowadzące ciekawostki składają Whitespaceo szerokości 4 i spływu ciekawostki Whitespaceo szerokości 1. Plusma wiodącą ciekawostki i końcowe ciekawostki składające się z jednej białej spacji, komentarza i nowego wiersza. Ostateczny identyfikator ma wiodące ciekawostki związane z komentarzem, spacją i tak dalej.

W tym schemacie każdy znak w pliku jest uwzględniany w danych wyjściowych leksera, co jest przydatną właściwością do takich rzeczy, jak kolorowanie składni.

Oczywiście, jeśli nie potrzebujesz ciekawostek, możesz po prostu zrobić token dwie rzeczy: rodzaj i szerokość.

Możesz zauważyć, że token i ciekawostki zawierają tylko ich szerokości, a nie ich absolutną pozycję w kodzie źródłowym. To celowe. Taki schemat ma zalety:

• Ma niewielkie rozmiary i pamięć
• Umożliwia ponowne leksykowanie po edycji; jest to przydatne, jeśli leksykon działa w środowisku IDE. Oznacza to, że jeśli wykryjesz edycję w tokenie, po prostu wykonaj kopię zapasową swojego leksykonu na kilku tokenach przed edycją i zacznij ponownie leksykację, dopóki nie zsynchronizujesz się z poprzednim strumieniem tokena. Po wpisaniu znaku zmienia się pozycja każdego tokena po tej postaci, ale zwykle zmienia się tylko jeden lub dwa tokeny, aby można było ponownie użyć całego tego stanu.
• Dokładne przesunięcia znaków każdego tokena można łatwo uzyskać przez iterację w strumieniu tokena i śledzenie bieżącego przesunięcia. Po dokładnym przesunięciu znaków można w razie potrzeby łatwo wyodrębnić tekst.

Jeśli nie obchodzi Cię żaden z tych scenariuszy, token może być reprezentowany jako rodzaj i przesunięcie, a nie rodzaj i szerokość.

Kluczową kwestią jest tutaj: programowanie to sztuka tworzenia użytecznych abstrakcji . Manipulujesz tokenami, więc zrób użyteczną abstrakcję nad tokenami, a następnie możesz sam wybrać, jakie szczegóły implementacji są u podstaw.

Ogólnie rzecz biorąc, zwracasz małą strukturę, która ma liczbę oznaczającą token (lub wartość wyliczaną dla ułatwienia użycia) i opcjonalną wartość (łańcuch, lub ewentualnie wartość ogólna / szablonowa). Innym podejściem byłoby zwrócenie typu pochodnego dla elementów, które muszą zawierać dodatkowe dane. Oba są nieco niesmaczne, ale wystarczająco dobre rozwiązania praktycznego problemu.