Jaka jest różnica między tokenem a leksemem?

W konstrukcji kompilatora Aho Ullmana i Sethiego podano, że wejściowy ciąg znaków programu źródłowego jest podzielony na sekwencje znaków, które mają logiczne znaczenie i są znane jako tokeny, a leksemy to sekwencje tworzące token, więc co jest podstawowa różnica?

Korzystanie z „ Zasady, techniki i narzędzia kompilatorów, wydanie 2-gie ” (WorldCat) autorstwa Aho, Lam, Sethi i Ullman, AKA the Purple Dragon Book ,

Lexeme str. 111

Leksem to sekwencja znaków w programie źródłowym, która pasuje do wzorca dla tokenu i jest identyfikowana przez analizator leksykalny jako instancja tego tokenu.

Żeton str. 111

Token to para składająca się z nazwy tokena i opcjonalnej wartości atrybutu. Nazwa tokena to abstrakcyjny symbol reprezentujący rodzaj jednostki leksykalnej, np. Określone słowo kluczowe lub sekwencja znaków wejściowych oznaczająca identyfikator. Nazwy tokenów to symbole wejściowe przetwarzane przez parser.

Wzór str. 111

Wzorzec to opis formy, jaką mogą przyjąć leksemy tokena. W przypadku słowa kluczowego jako tokenu, wzorzec jest po prostu sekwencją znaków, które tworzą słowo kluczowe. W przypadku identyfikatorów i niektórych innych tokenów wzorzec jest bardziej złożoną strukturą, do której pasuje wiele ciągów.

Rysunek 3.2: Przykłady tokenów str.112

[Token]       [Informal Description]                  [Sample Lexemes]
if            characters i, f                         if
else          characters e, l, s, e                   else
comparison    < or > or <= or >= or == or !=          <=, !=
id            letter followed by letters and digits   pi, score, D2
number        any numeric constant                    3.14159, 0, 6.02e23
literal       anything but ", surrounded by "'s       "core dumped"

Aby lepiej zrozumieć tę relację do leksera i parsera, zaczniemy od parsera i cofniemy się do wejścia.

Aby ułatwić projektowanie analizatora składni, parser nie pracuje bezpośrednio z danymi wejściowymi, ale pobiera listę tokenów wygenerowaną przez lekser. Patrząc na kolumnie token rysunku 3.2 widzimy żetonów, takie jak if, else, comparison, id, numberi literal; to są nazwy żetonów. Zazwyczaj w przypadku leksera / parsera token jest strukturą, która przechowuje nie tylko nazwę tokenu, ale także znaki / symbole, które tworzą token oraz pozycję początkową i końcową ciągu znaków, które tworzą token, z pozycja początkowa i końcowa używana do zgłaszania błędów, podświetlania itp.

Teraz lekser wprowadza znaki / symbole i używając reguł leksera konwertuje wprowadzane znaki / symbole na tokeny. Teraz ludzie, którzy pracują z lexerem / parserem, mają własne słowa dla rzeczy, których często używają. To, o czym myślisz jako sekwencja znaków / symboli, które tworzą token, jest tym, co ludzie używający leksera / parsera nazywają leksemem. Kiedy więc zobaczysz leksem, pomyśl o sekwencji znaków / symboli reprezentujących token. W przykładzie porównawczym sekwencja znaków / symboli może być różnymi wzorami, takimi jak <lub >lub elselub 3.14itp.

Innym sposobem myślenia o relacji między nimi jest to, że token jest strukturą programistyczną używaną przez parser, która ma właściwość zwaną leksemem, która przechowuje znak / symbole z wejścia. Jeśli spojrzysz na większość definicji tokena w kodzie, możesz nie widzieć leksemu jako jednej z właściwości tokena. Dzieje się tak, ponieważ token będzie prawdopodobnie utrzymywał początkową i końcową pozycję znaków / symboli, które reprezentują token i leksem, sekwencję znaków / symboli można wyprowadzić z pozycji początkowej i końcowej w razie potrzeby, ponieważ dane wejściowe są statyczne.

Kiedy program źródłowy jest wprowadzany do analizatora leksykalnego, zaczyna się od rozbicia znaków na sekwencje leksemów. Leksemy są następnie wykorzystywane do konstrukcji tokenów, w których leksemy są odwzorowywane na tokeny. Zmienna o nazwie myVar zostanie odwzorowana na token zawierający < id , "num">, gdzie "num" powinno wskazywać lokalizację zmiennej w tablicy symboli.

Krótko mówiąc:

• Leksemy to słowa pochodzące ze strumienia wejściowego znaków.
• Tokeny to leksemy odwzorowane na nazwę tokenu i wartość atrybutu.

Przykład obejmuje:
x = a + b * 2
Co daje leksemy: {x, =, a, +, b, *, 2}
Z odpowiednimi tokenami: {< id , 0>, <=>, < id , 1 >, <+>, < id , 2>, <*>, < id , 3>}

a) Tokeny to symboliczne nazwy podmiotów, które składają się na tekst programu; np. jeśli dla słowa kluczowego if i id dla dowolnego identyfikatora. Stanowią one dane wyjściowe analizatora leksykalnego. 5

(b) Wzorzec to reguła określająca, kiedy sekwencja znaków z wejścia stanowi token; np. sekwencja i, f dla tokena if i dowolna sekwencja znaków alfanumerycznych zaczynająca się od litery oznaczającej identyfikator tokena.

(c) Leksem to sekwencja znaków z danych wejściowych, które pasują do wzorca (a zatem stanowią instancję tokena); na przykład if pasuje do wzorca dla if, a foo123bar pasuje do wzorca dla id.

LEKSEM - sekwencja znaków dopasowanych przez WZORZĘ tworzącą TOKEN

WZÓR - Zbiór reguł definiujących TOKEN

TOKEN - znaczący zbiór znaków w zestawie znaków języka programowania, np .: ID, stała, słowa kluczowe, operatory, interpunkcja, ciąg znaków

Leksem - leksem to sekwencja znaków w programie źródłowym, która pasuje do wzorca dla tokenu i jest identyfikowana przez analizator leksykalny jako instancja tego tokenu.

Token - token to para składająca się z nazwy tokena i opcjonalnej wartości tokena. Nazwa tokena to kategoria jednostki leksykalnej, a nazwy zwykłych to

• identyfikatory: nazwy wybrane przez programistę
• słowa kluczowe: nazwy już w języku programowania
• separatory (znane również jako znaki przestankowe): znaki interpunkcyjne i sparowane separatory
• operatory: symbole, które działają na argumentach i dają wyniki
• literały: numeryczne, logiczne, tekstowe, referencyjne

Rozważ to wyrażenie w języku programowania C:

suma = 3 + 2;

Tokenizowane i reprezentowane przez następującą tabelę:

 Lexeme        Token category
------------------------------
sum      |    Identifier
 =       |    Assignment operator
 3       |    Integer literal
 +       |    Addition operator
 2       |    Integer literal
 ;       |    End of statement

Zobaczmy działanie analizatora leksykalnego (zwanego także skanerem)

Weźmy przykładowe wyrażenie:

INPUT : cout << 3+2+3;

FORMATTING PERFORMED BY SCANNER :  {cout}|space|{<<}|space|{3}{+}{2}{+}{3}{;} 

ale nie faktyczny wynik.

SKANER PO PROSTU POWTARZA SIĘ W TEKSTIE LEKSEMU W PROGRAMIE ŹRÓDŁOWYM, AŻ WEJŚCIE ZOSTANIE WYCZERPANE

Leksem to podłańcuch danych wejściowych, który tworzy prawidłowy ciąg terminali występujący w gramatyce. Każdy leksem podąża za wzorem, który jest wyjaśniony na końcu (część, którą czytelnik może w końcu pominąć)

(Ważną zasadą jest szukanie możliwie najdłuższego prefiksu tworzącego prawidłowy ciąg terminali do momentu napotkania następnej białej spacji ... wyjaśnione poniżej)

LEKSEMY:

1. cout
2. <<

(chociaż "<" jest również poprawnym ciągiem terminala, ale powyższa reguła wybiera wzorzec dla leksemu "<<" w celu wygenerowania tokena zwróconego przez skaner)

3. 3
4. +
5. 2
6. ;

TOKENY: Tokeny są zwracane pojedynczo (przez Scanner na żądanie Parsera) za każdym razem, gdy Scanner znajdzie (prawidłowy) leksem. Skaner tworzy, jeśli jeszcze nie jest obecny, wpis w tablicy symboli (mający atrybuty: głównie kategoria tokenów i kilka innych) , gdy znajdzie leksem, w celu wygenerowania jego tokenu

„#” oznacza wpis tablicy symboli. Wskazałem na numer leksemu na powyższej liście dla ułatwienia zrozumienia, ale technicznie powinien to być rzeczywisty indeks zapisu w tablicy symboli.

Następujące tokeny są zwracane przez skaner do analizatora składni w określonej kolejności w powyższym przykładzie.

1. <identyfikator, # 1>

2. <Operator, nr 2>

3. <Dosłowne, nr 3>

4. <Operator, # 4>

5. <Dosłowne, # 5>

6. <Operator, # 4>

7. <Dosłowne, nr 3>

8. <Punctuator, # 6>

Jak widać różnicę, token jest parą, w przeciwieństwie do leksemu, który jest podłańcuchem danych wejściowych.

Pierwszym elementem pary jest klasa / kategoria tokenów

Klasy tokenów są wymienione poniżej:

I jeszcze jedno, Scanner wykrywa białe spacje, ignoruje je iw ogóle nie tworzy żadnego tokenu dla białych znaków. Nie wszystkie separatory są białymi spacjami, białe znaki to jedna z form separatorów używanych przez skanery do tego celu. Tabulatory, znaki nowej linii, spacje, znaki ucieczki na wejściu są łącznie nazywane separatorami białych znaków. Niewiele innych ograniczników to „;” ',' ':' itd., które są powszechnie rozpoznawane jako leksemy tworzące token.

Całkowita liczba zwróconych tokenów wynosi tutaj 8, jednak tylko 6 wpisów w tablicy symboli jest utworzonych dla leksemów. Łącznie jest również 8 leksemów (patrz definicja leksemu)

--- Możesz pominąć tę część

A ***pattern*** is a rule ( say, a regular expression ) that is used to check if a string-of-terminals is valid or not.

If a substring of input composed only of grammar terminals is following the rule specified by any of the listed patterns , it is validated as a lexeme and selected pattern will identify the category of lexeme, else a lexical error is reported due to either (i) not following any of the rules or (ii) input consists of a bad terminal-character not present in grammar itself.

for example :

1. No Pattern Exists : In C++ , "99Id_Var" is grammar-supported string-of-terminals but is not recognised by any of patterns hence lexical error is reported .

2. Bad Input Character : $,@,unicode characters may not be supported as a valid character in few programming languages.`

Leksem - leksem to ciąg znaków, który jest jednostką składniową najniższego poziomu w języku programowania.

Token - token jest kategorią składniową, która tworzy klasę leksemów, co oznacza, do której klasy należy leksem, czy jest to słowo kluczowe, identyfikator, czy cokolwiek innego. Jednym z głównych zadań analizatora leksykalnego jest stworzenie pary leksemów i tokenów, czyli zebranie wszystkich znaków.

Weźmy przykład: -

jeśli (y <= t)

y = y-3;

Lexeme Token

jeśli KEYWORD

(LEFT PARENTHESIS

y IDENTYFIKATOR

<= PORÓWNANIE

IDENTYFIKATOR

) PRAWA RODZICIELSTWO

y IDENTYFIKATOR

= OCENA

y IDENTYFIKATOR

_ ARYTMATYCZNY

3 INTEGER

;                                    ŚREDNIK

Relacja między leksemem a tokenem

Token: rodzaj dla (słowa kluczowe, identyfikator, znak interpunkcyjny, operatory wieloznakowe) to po prostu Token.

Wzorzec: reguła tworzenia tokena ze znaków wejściowych.

Leksem: to sekwencja znaków w PROGRAMIE ŹRÓDŁOWYM dopasowana do wzorca dla tokena. Zasadniczo jest to element tokena.

Token: Token to ciąg znaków, który można traktować jako pojedynczą jednostkę logiczną. Typowe tokeny to:
1) Identyfikatory
2) słowa kluczowe
3) operatory
4) symbole specjalne
5) stałe

Wzorzec: zestaw ciągów na wejściu, dla których ten sam token jest generowany jako dane wyjściowe. Ten zestaw ciągów jest opisywany przez regułę zwaną wzorcem skojarzonym z tokenem.
Leksem: leksem to sekwencja znaków w programie źródłowym, która jest dopasowywana przez wzorzec tokenu.

Leksem leksemami mówi się ciąg znaków alfanumerycznych) w (token.

Token Token to sekwencja znaków, które można zidentyfikować jako pojedynczą jednostkę logiczną. Zazwyczaj tokeny to słowa kluczowe, identyfikatory, stałe, ciągi znaków, symbole interpunkcyjne, operatory. liczby.

Wzorzec Zbiór ciągów opisanych przez regułę zwaną wzorcem. Wzorzec wyjaśnia, co może być tokenem, a wzorce te są definiowane za pomocą wyrażeń regularnych, które są powiązane z tokenem.

Badacze CS, podobnie jak ci z Math, lubią tworzyć „nowe” terminy. Wszystkie powyższe odpowiedzi są ładne, ale najwyraźniej nie ma tak wielkiej potrzeby rozróżniania tokenów i leksemów IMHO. Są jak dwa sposoby przedstawiania tej samej rzeczy. Leksem jest konkretny - tutaj zestaw znaków; token natomiast jest abstrakcyjny - zwykle odnosi się do typu leksemu wraz z jego wartością semantyczną, jeśli ma to sens. Tylko moje dwa centy.

Analizator leksykalny pobiera sekwencję znaków, identyfikuje leksem pasujący do wyrażenia regularnego i dalej klasyfikuje je do tokenu. W ten sposób leksem jest dopasowanym ciągiem, a nazwa tokenu jest kategorią tego leksemu.

Na przykład rozważmy poniżej wyrażenie regularne dla identyfikatora z danymi wejściowymi „int foo, bar;”

litera (litera | cyfra | _) *

Tu fooi barpasuje do wyrażenia regularnego więc są oba leksemy ale są klasyfikowane jako jeden znak IDczyli identyfikator.

Zwróć również uwagę, że następna faza, tj. Analizator składni, nie musi wiedzieć o leksemie, ale o tokenie.

Lexeme jest w zasadzie jednostką tokena i jest to w zasadzie sekwencja znaków, która pasuje do tokena i pomaga rozbić kod źródłowy na tokeny.

Na przykład: Jeśli źródłem jest x=b, to leksemy byłoby x, =, ba tokeny byłoby <id, 0>, <=>, <id, 1>.