Apa yang seharusnya menjadi tipe data token yang dikembalikan oleh lexer ke parsernya?

Seperti yang dikatakan dalam judul, tipe data mana yang harus dikembalikan / diberikan parser lexer? Ketika membaca artikel analisis leksikal yang dimiliki Wikipedia, dinyatakan bahwa:

Dalam ilmu komputer, analisis leksikal adalah proses mengubah urutan karakter (seperti dalam program komputer atau halaman web) menjadi urutan token ( string dengan "makna" yang diidentifikasi).

Namun, dalam kontradiksi lengkap dengan pernyataan di atas, Ketika pertanyaan lain saya tanyakan di situs yang berbeda ( Peninjauan Kode jika Anda penasaran) dijawab, Orang yang menjawab menyatakan bahwa:

Lexer biasanya membaca string dan mengubahnya menjadi aliran ... lexeme. Leksem hanya perlu aliran angka .

dan dia memberikan visual ini:

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

Kemudian dalam artikel yang disebutkannya Flex, seorang lexer yang sudah ada, dan mengatakan menulis 'aturan' dengan itu akan lebih sederhana daripada menulis lexer dengan tangan. Dia kemudian memberi saya contoh ini:

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

Untuk memajukan wawasan saya dan mendapatkan informasi lebih lanjut, saya membaca artikel Wikipedia tentang Flex . artikel Flex menunjukkan bahwa Anda dapat menetapkan sekumpulan aturan sintaks, dengan token, dengan cara berikut:

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;   }

Sepertinya saya bahwa Flex lexer mengembalikan string kata kunci \ token. Tapi bisa jadi konstanta yang dikembalikan sama dengan angka-angka tertentu.

Jika lexer akan mengembalikan angka, bagaimana ia membaca string literal? mengembalikan nomor tidak masalah untuk kata kunci tunggal, tetapi bagaimana Anda akan berurusan dengan string? Bukankah lexer harus mengubah string ke angka biner dan kemudian parser akan mengubah angka kembali menjadi string. Tampaknya jauh lebih logis (dan lebih mudah) bagi lexer untuk mengembalikan string, dan kemudian membiarkan parser mengubah sembarang string angka menjadi angka aktual.

Atau mungkinkah lexer mengembalikan keduanya? Saya sudah mencoba untuk menulis lexer sederhana di c ++, yang memungkinkan Anda hanya memiliki satu tipe pengembalian untuk fungsi Anda. Dengan demikian mengarahkan saya untuk mengajukan pertanyaan saya.

Untuk menyingkat pertanyaan saya menjadi paragraf: Saat menulis lexer, dan dengan asumsi bahwa itu hanya bisa mengembalikan satu tipe data (string atau angka), yang mana yang akan menjadi pilihan yang lebih logis?

Secara umum, jika Anda sedang memproses suatu bahasa melalui lexing dan parsing, Anda sudah memiliki definisi token leksikal Anda, misalnya:

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

dan Anda memiliki tata bahasa untuk parser:

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

Lexer Anda mengambil aliran input dan menghasilkan aliran token. Aliran token dikonsumsi oleh parser untuk menghasilkan pohon parse. Dalam beberapa kasus, hanya mengetahui jenis token yang cukup (misalnya, LPAREN, RBRACE, UNTUK), namun dalam beberapa kasus, Anda akan memerlukan sebenarnya nilai yang terkait dengan token. Misalnya, ketika Anda menemukan token ID, Anda akan menginginkan karakter aktual yang membentuk ID nanti ketika Anda mencoba mencari tahu pengenal apa yang Anda coba referensi.

Jadi, Anda biasanya memiliki sesuatu yang kurang lebih seperti ini:

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

class Token {
  TokenType type;
  String value;
}

Jadi ketika lexer mengembalikan token, Anda tahu jenisnya (yang Anda perlukan untuk penguraian), dan urutan karakter yang dihasilkannya (yang akan Anda perlukan nanti untuk menafsirkan string dan literal angka, pengidentifikasi, dll.) Mungkin terasa seperti Anda mengembalikan dua nilai, karena Anda mengembalikan tipe agregat yang sangat sederhana, tetapi Anda benar-benar membutuhkan kedua bagian tersebut. Bagaimanapun, Anda ingin memperlakukan program-program berikut secara berbeda:

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

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

Ini menghasilkan urutan jenis token yang sama : IF, LPAREN, NUMBER, GREATER_THAN, NUMBER, RPAREN, LBRACE, ID, LPAREN, STRING, RPAREN, SEMICOLON, RBRACE. Itu berarti mereka menguraikan hal yang sama juga. Tetapi ketika Anda benar-benar melakukan sesuatu dengan pohon parse, Anda akan peduli bahwa nilai angka pertama adalah '2' (atau '0') dan bahwa nilai angka kedua adalah '0' (atau '2 '), dan bahwa nilai string adalah' 2> 0 '(atau' 0> 2 ').

Seperti yang dikatakan dalam judul, tipe data mana yang harus dikembalikan / diberikan parser lexer?

"Token", jelas. Lexer menghasilkan aliran token, jadi itu harus mengembalikan aliran token .

Dia menyebutkan Flex, seorang lexer yang sudah ada, dan mengatakan menulis 'aturan' dengan itu akan lebih mudah daripada menulis lexer dengan tangan.

Mesin lexer yang dihasilkan mesin memiliki keuntungan yang bisa Anda hasilkan dengan cepat, yang sangat berguna jika Anda berpikir tata bahasa leksikal Anda akan banyak berubah. Mereka memiliki kelemahan bahwa Anda sering tidak mendapatkan banyak fleksibilitas dalam pilihan implementasi Anda.

Yang mengatakan, siapa yang peduli jika itu "lebih sederhana"? Menulis lexer biasanya bukan bagian yang sulit!

Saat menulis lexer, dan dengan asumsi bahwa itu hanya bisa mengembalikan satu tipe data (string atau angka), mana yang akan menjadi pilihan yang lebih logis?

Tidak juga. Lexer biasanya memiliki operasi "berikutnya" yang mengembalikan token, jadi itu harus mengembalikan token . Token bukan string atau angka. Itu token.

Lexer terakhir yang saya tulis adalah lexer "kesetiaan penuh", yang berarti ia mengembalikan token yang melacak lokasi semua spasi putih dan komentar - yang kami sebut "trivia" - dalam program, serta token. Dalam lexer saya token didefinisikan sebagai:

• Array trivia terkemuka
• Jenis token
• Lebar token dalam karakter
• Array trivia tertinggal

Trivia didefinisikan sebagai:

• Jenis trivia - spasi putih, baris baru, komentar, dan sebagainya
• Lebar trivia dalam karakter

Jadi jika kita punya sesuatu seperti

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

yang akan lex empat token dengan jenis tanda Identifier, Plus, Identifier, Semicolon, dan lebar 3, 1, 3, 1. identifier pertama memiliki hal-hal sepele yang terdiri dari terkemuka Whitespacedengan lebar 4 dan trailing trivia Whitespacedengan lebar 1. Plustidak memiliki trivia terkemuka dan trailing trivia yang terdiri dari satu spasi putih, komentar dan baris baru. Identifier akhir memiliki trivia utama dari komentar dan spasi, dan sebagainya.

Dengan skema ini setiap karakter dalam file akan diperhitungkan dalam output dari lexer, yang merupakan properti berguna untuk hal-hal seperti pewarnaan sintaks.

Tentu saja, jika Anda tidak membutuhkan hal-hal sepele maka Anda bisa membuat token dua hal: jenis dan lebar.

Anda mungkin memperhatikan bahwa token dan trivia hanya berisi lebarnya, bukan posisi absolutnya dalam kode sumber. Itu disengaja. Skema semacam itu memiliki kelebihan:

• Ini kompak dalam memori dan format kawat
• Ini memungkinkan pengeksporan ulang pada hasil edit; ini berguna jika lexer berjalan di dalam IDE. Artinya, jika Anda mendeteksi edit dalam token, Anda cukup mencadangkan lexer Anda ke beberapa token sebelum edit dan mulai lexing lagi sampai Anda disinkronkan dengan aliran token sebelumnya. Saat Anda mengetik karakter, posisi setiap token setelah karakter itu berubah, tetapi biasanya hanya satu atau dua token yang berubah lebar, sehingga Anda dapat menggunakan kembali semua status itu.
• Offset karakter yang tepat dari setiap token dapat dengan mudah diperoleh dengan mengulangi aliran token dan melacak offset saat ini. Setelah Anda memiliki offset karakter yang tepat, maka mudah untuk mengekstrak teks saat diperlukan.

Jika Anda tidak peduli dengan salah satu skenario itu, maka token dapat direpresentasikan sebagai jenis dan offset, bukan jenis dan lebar.

Tetapi kunci yang bisa diambil di sini adalah: pemrograman adalah seni membuat abstraksi yang bermanfaat . Anda memanipulasi token, jadi buat abstraksi yang berguna atas token, dan kemudian Anda bisa memilih sendiri apa detail implementasi yang mendasari itu.

Secara umum, Anda mengembalikan struktur kecil yang memiliki angka yang menandakan token (atau nilai enum untuk kemudahan penggunaan) dan nilai opsional (string, atau mungkin nilai generik / templated). Pendekatan lain adalah mengembalikan tipe turunan untuk elemen yang perlu membawa data tambahan. Keduanya agak tidak menyenangkan, tetapi solusi yang cukup bagus untuk masalah praktis.