Потік введення символів
Це найменша частина. Ми створимо "об'єкт потоку", який надає операції для читання символів з рядка. Об'єкт потоку має 4 методи:
peek()— повертає наступне значення, але не видаляє його з потоку.next()— повертає наступне значення і видаляє його з потоку.eof()— повертаєtrue, якщо і тільки якщо в потоці більше немає значень.croak(msg)— генерує винятокnew Error(msg).
Останній метод важливий, оскільки потік може легко відстежувати поточне місцезнаходження (тобто рядок/стовпчик), що важливо для відображення у випадку повідомлення про помилку.
З відкриттям нових потреб можна додавати більше методів, але для мого посібника цих чотирьох буде достатньо.
Потік введення символів працює з символами, тому значення, що повертають next() / peek(), є символами (ну, оскільки JS не має типу char, вони є рядками, що містять один символ).
Ось повний код цього об'єкта, який я називатиму "InputStream". Він досить невеликий, і ви повинні зрозуміти його без проблем:
function InputStream(input) {
var pos = 0, line = 1, col = 0;
return {
next : next,
peek : peek,
eof : eof,
croak : croak,
};
function next() {
var ch = input.charAt(pos++);
if (ch == "\n") line++, col = 0; else col++;
return ch;
}
function peek() {
return input.charAt(pos);
}
function eof() {
return peek() == "";
}
function croak(msg) {
throw new Error(msg + " (" + line + ":" + col + ")");
}
}Зверніть увагу, що це не стандартний об'єкт (типу, який створюється за допомогою new). Просто використовуйте var stream = InputStream(string), щоб отримати об'єкт потоку.
Токенізатор
Токенізатор (також називається "лексер") працює з потоком введення символів і повертає об'єкт потоку з таким самим інтерфейсом, але значення, що повертають peek() та next(), будуть токенами. Токен - це об'єкт з двома властивостями: type (тип) і value (значення). Ось деякі приклади підтримуваних токенів:
{ type: "punc", value: "(" } // пунктуація: дужки, коми і т. д.
{ type: "num", value: 5 } // числа
{ type: "str", value: "Привіт, світе!" } // рядки
{ type: "kw", value: "lambda" } // ключові слова
{ type: "var", value: "a" } // ідентифікатори
{ type: "op", value: "!=" } // операториДля написання токенізатора нам потрібно докладніше розглянути синтаксис нашої мови. Ідея полягає в тому, щоб помітити, що в залежності від поточного символу (який повертається input.peek()), ми можемо вирішити, який тип токену читати:
Пропускаємо пробіли та коментарі, не повертаючи жодного токену.
Якщо
input.eof(), то повертаємо null.Якщо це знак “решітки” (
#), пропускаємо коментар (повторюємо після кінця рядка).Якщо це лапки (
"), то читаємо рядок.Якщо це цифра, тоді продовжуємо зчитування числа.
Якщо це літера, тоді читаємо ідентифікатор або ключове слово.
Якщо це один з символів пунктуації, повертаємо токен пунктуації.
Якщо це один з символів операторів, повертаємо токен оператора.
Якщо жоден з вищеперерахованих випадків не відповідає, видаємо помилку за допомогою
input.croak().
Отже, функція read_next це "ядро" токенізатора - яка реалізує вищезазначене:
function read_next() {
read_while(is_whitespace);
if (input.eof()) return null;
var ch = input.peek();
if (ch == "#") {
skip_comment();
return read_next();
}
if (ch == '"') return read_string();
if (is_digit(ch)) return read_number();
if (is_id_start(ch)) return read_ident();
if (is_punc(ch)) return {
type : "punc",
value : input.next()
};
if (is_op_char(ch)) return {
type : "op",
value : read_while(is_op_char)
};
input.croak("Can't handle character: " + ch);
}Це функція "диспетчера", і саме її викликатиме next(), щоб отримати наступний токен. Зауважте, вона використовує багато допоміжних функцій, спрямованих на конкретні типи токенів, такі як read_string(), read_number() і т. д. Немає сенсу ускладнювати диспетчера кодом цих функцій, навіть якщо ми ніколи не викликаємо їх десь інде.
Ще одне, на що варто звернути увагу, - це те, що ми не споживаємо весь потік вводу одним кроком. Кожного разу, коли парсер викликає наступний токен, ми читаємо один токен. У випадку помилки синтаксичного аналізу ми навіть не доходимо до кінця потоку.
read_ident() буде читати символи, доки вони дозволені як частина ідентифікатора (is_id). Ідентифікатори повинні починатися з літери, або λ або _, і можуть містити подальші такі символи, цифри або один із наступних: ?!-<>=. Тому foo-bar не буде зчитано як три токени, а як один ідентифікатор (токен "var"). Причина цього правила в тому, що я б хотів мати змогу визначати функції з назвами типу is-pair? або string>= (вибачте, це Ліспер в мені).
Крім того, функція read_ident() буде перевіряти ідентифікатор на наявність в списку відомих ключових слів і, якщо він там є, поверне токен "kw", а не "var".
Я думаю, що код вже досить зрозумілий сам по собі, тому ось повний токенізатор для нашої мови. Кілька інших невеликих зауважень нижче.
function TokenStream(input) {
var current = null;
var keywords = " if then else lambda λ true false ";
return {
next : next,
peek : peek,
eof : eof,
croak : input.croak
};
function is_keyword(x) {
return keywords.indexOf(" " + x + " ") >= 0;
}
function is_digit(ch) {
return /[0-9]/i.test(ch);
}
function is_id_start(ch) {
return /[a-zλ_]/i.test(ch);
}
function is_id(ch) {
return is_id_start(ch) || "?!-<>=0123456789".indexOf(ch) >= 0;
}
function is_op_char(ch) {
return "+-*/%=&|<>!".indexOf(ch) >= 0;
}
function is_punc(ch) {
return ",;(){}[]".indexOf(ch) >= 0;
}
function is_whitespace(ch) {
return " \t\n".indexOf(ch) >= 0;
}
function read_while(predicate) {
var str = "";
while (!input.eof() && predicate(input.peek()))
str += input.next();
return str;
}
function read_number() {
var has_dot = false;
var number = read_while(function(ch){
if (ch == ".") {
if (has_dot) return false;
has_dot = true;
return true;
}
return is_digit(ch);
});
return { type: "num", value: parseFloat(number) };
}
function read_ident() {
var id = read_while(is_id);
return {
type : is_keyword(id) ? "kw" : "var",
value : id
};
}
function read_escaped(end) {
var escaped = false, str = "";
input.next();
while (!input.eof()) {
var ch = input.next();
if (escaped) {
str += ch;
escaped = false;
} else if (ch == "\\") {
escaped = true;
} else if (ch == end) {
break;
} else {
str += ch;
}
}
return str;
}
function read_string() {
return { type: "str", value: read_escaped('"') };
}
function skip_comment() {
read_while(function(ch){ return ch != "\n" });
input.next();
}
function read_next() {
read_while(is_whitespace);
if (input.eof()) return null;
var ch = input.peek();
if (ch == "#") {
skip_comment();
return read_next();
}
if (ch == '"') return read_string();
if (is_digit(ch)) return read_number();
if (is_id_start(ch)) return read_ident();
if (is_punc(ch)) return {
type : "punc",
value : input.next()
};
if (is_op_char(ch)) return {
type : "op",
value : read_while(is_op_char)
};
input.croak("Can't handle character: " + ch);
}
function peek() {
return current || (current = read_next());
}
function next() {
var tok = current;
current = null;
return tok || read_next();
}
function eof() {
return peek() == null;
}
}Функція
next()не завжди викликаєread_next(), оскільки можливо, що вона вже була переглянута (у такому випадкуread_next()вже було викликано, і потік було переміщено вперед). Тому нам потрібна зміннаcurrent, яка відстежує поточний токен.Ми підтримуємо лише десяткові числа за звичайною нотацією (без речей типу
1E5, без шістнадцяткових, без вісімкових). Але якщо нам коли-небудь знадобиться більше, зміни вносяться тільки вread_number()і вони досить легкі для виконання.На відміну від JavaScript, єдині символи, які не можуть з'являтися без лапок у рядку, - це сам символ лапки та зворотній слеш. Вам потрібно ставити перед ними зворотний слеш. В іншому випадку рядки можуть містити переноси, табуляцію та все інше. Ми не інтерпретуємо звичайні екранування, такі як \n, \t і т. д., хоча знову ж таки, зміни були б досить тривіальні (у функції
read_string).
Тепер у нас є достатньо потужні інструменти для легкої реалізації синтаксичного аналізатора, але спочатку я рекомендую вам ознайомитися з описом AST.
