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?
źródło
Odpowiedzi:
Ogólnie rzecz biorąc, jeśli przetwarzasz język leksykalnie i parsując, masz definicję swoich tokenów leksykalnych, np .:
i masz gramatykę dla parsera:
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:
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:
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 ”).
źródło
String value
się wypełni? czy będzie wypełniony sznurkiem lub liczbą? A także, jak mam zdefiniowaćString
typ?parse(inputStream).forEach(token -> print(token.string); print(' '))
(tzn. Po prostu wydrukuj wartości ciągów tokenów, oddzielone spacją). To dość szybko. I nawet jeśli LPAREN może pochodzić tylko z „(”, może to być ciąg ciągły w pamięci, więc włączenie odwołania do tokena może być nie droższe niż włączenie odwołania zerowego. Ogólnie wolałbym pisać kod, który nie czyni ze mnie żadnego specjalnego koduOczywiście „Token”. Lexer wytwarza strumień tokenów, więc powinien zwrócić strumień tokenów .
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!
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:
Ciekawostki zdefiniowano jako:
Więc gdybyśmy mieli coś takiego
że lex postaci czterech znaczników z tokenów rodzaju
Identifier
,Plus
,Identifier
,Semicolon
i szerokości 3, 1, 3, 1. pierwszy identyfikator zawiera prowadzące ciekawostki składająWhitespace
o szerokości 4 i spływu ciekawostkiWhitespace
o szerokości 1.Plus
ma 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:
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.
źródło
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.
źródło
Token *
lub po prostu aToken
lub taki,TokenPtr
który jest wspólnym wskaźnikiemToken
klasy. Ale widzę też, że niektóre leksery zwracają tylko TokenType i przechowują wartość ciągu lub liczby w innych zmiennych globalnych lub statycznych. Kolejne pytanie dotyczy tego, w jaki sposób możemy przechowywać informacje o lokalizacji. Czy potrzebuję struktury Token, która ma pola TokenType, String i Location? Dzięki.struct Token {TokenType id; std::string lexeme; int line; int column;}
, prawda? W przypadku funkcji publicznej Lexera, takiej jakPeekToken()
funkcja, może zwrócić aToken *
lubTokenPtr
. Myślę, że przez chwilę, jeśli funkcja zwróci TokenType, w jaki sposób Parser próbuje uzyskać inne informacje o tokenie? Tak więc wskaźnik typu danych jest preferowany do powrotu z takiej funkcji. Jakieś komentarze na temat mojego pomysłu? Dzięki