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

21

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?

Christian Dean
źródło
Lexer zwraca to, co każesz mu zwrócić. Jeśli twój projekt wymaga numerów, zwróci numery. Oczywiście reprezentowanie literałów łańcuchowych będzie wymagało nieco więcej. Zobacz także Czy praca Lexera polega na analizie liczb i ciągów znaków? Zauważ, że literały łańcuchowe nie są ogólnie uważane za „elementy języka”.
Robert Harvey,
@RobertHarvey Czy zamieniłbyś dosłowny ciąg znaków na liczby binarne ?.
Christian Dean
Jak rozumiem, celem leksera jest wzięcie elementów języka (takich jak słowa kluczowe, operatory itp.) I przekształcenie ich w tokeny. Jako takie, cytowane ciągi nie są interesujące dla leksykonu, ponieważ nie są elementami języka. Chociaż sam nigdy nie napisałem leksera, wyobrażam sobie, że cytowany ciąg jest po prostu przekazywany bez zmian (łącznie z cytatami).
Robert Harvey
Więc, co mówisz, to, że leksykon nie czyta literałów łańcuchowych ani nie dba o to. A więc parser musi szukać tych literałów łańcuchowych? To bardzo mylące.
Christian Dean
Możesz poświęcić kilka minut na przeczytanie tego: en.wikipedia.org/wiki/Lexical_analysis
Robert Harvey

Odpowiedzi:

10

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 ”).

Joshua Taylor
źródło
Rozumiem większość twojego powiedzenia, ale jak to String valuesię wypełni? czy będzie wypełniony sznurkiem lub liczbą? A także, jak mam zdefiniować Stringtyp?
Christian Dean
1
@ Mr.Python W najprostszym przypadku to tylko ciąg znaków, który pasował do produkcji leksykalnej. Tak więc, jeśli zobaczysz foo (23, „pasek”) , dostaniesz tokeny [ID, „foo”], [LPAREN ”,„ (”], [NUMBER,„ 23 ”], [COMMA”, „ ], [STRING, „„ 23 ””], [RPAREN, ”)”] . Zachowanie tych informacji może być ważne. Lub możesz zastosować inne podejście i mieć wartość typu unii, która może być łańcuchem, liczbą, itp. I wybrać odpowiedni typ wartości na podstawie rodzaju posiadanego tokena (np. Gdy typ tokenu to NUMBER , użyj value.num, a gdy jest STRING, użyj value.str).
Joshua Taylor,
@MrPython „A także, jak zdefiniować typ ciągu?” Pisałem z mentalności Java. Jeśli pracujesz w C ++, możesz użyć typu łańcucha C ++, lub jeśli pracujesz w C, możesz użyć znaku char *. Chodzi o to, że związane z tokenem, masz odpowiednią wartość lub tekst, który możesz zinterpretować, aby uzyskać tę wartość.
Joshua Taylor,
1
@ ollydbg23 jest to opcja, a nie nieuzasadniona, ale sprawia, że ​​system jest mniej wewnętrznie spójny. Na przykład, jeśli chcesz wartość ciągu ostatniego przeanalizowanego miasta, musisz teraz jawnie sprawdzić wartość pustą, a następnie użyć odwrotnego wyszukiwania token-to-string, aby dowiedzieć się, jaki byłby ciąg. Plus, to ściślejsze sprzężenie między leksemrem a parserem; jest więcej kodów do aktualizacji, jeśli LPAREN może kiedykolwiek pasować do różnych lub wielu ciągów.
Joshua Taylor
2
@ ollydbg23 Jeden przypadek byłby prostym pseudo-minifikatorem. Jest to łatwe do zrobienia 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 kodu
Joshua Taylor
6

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.

Eric Lippert
źródło
3

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.

Telastyn
źródło
Co rozumiesz przez lekko niesmaczny ? Czy są nieefektywne sposoby uzyskiwania wartości ciągu?
Christian Dean
@ Mr.Python - doprowadzą one do wielu kontroli przed użyciem w kodzie, co jest nieefektywne, ale morale sprawia, że ​​kod jest nieco bardziej złożony / kruchy.
Telastyn
Mam podobne pytanie przy projektowaniu leksykonu w C ++, mógłbym zwrócić a Token *lub po prostu a Tokenlub taki, TokenPtrktóry jest wspólnym wskaźnikiem Tokenklasy. 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.
ollydbg23
@ ollydbg23 - każda z tych rzeczy może działać. Użyłbym struktury. W przypadku języków nie uczących się i tak będziesz używać generatora analizatora składni.
Telastyn
@Telastyn dzięki za odpowiedź. Masz na myśli, że struktura Token może być czymś takim struct Token {TokenType id; std::string lexeme; int line; int column;}, prawda? W przypadku funkcji publicznej Lexera, takiej jak PeekToken()funkcja, może zwrócić a Token *lub TokenPtr. 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
ollydbg23