Допустим мы в ini файл пишем вот это:
repeat (8)
{
click(10,10)
pause(100s)
click(10,10)
repeat(2)
{
pause(10)
}
}
что то вроде кода самого обычного кликера, по типу UOpilot.
Как обрабатывать и анализировать циклы, вложенные циклы?
Ответ
Окей, ну что же, вам нужен интерпретатор. Давайте-ка разомнёмся и этот самый интерпретатор напишем.
Для начала, нужно составить формальную грамматику вашего языка. Исходя из того, что вы привели в качестве примера программы, можно предположить следующую грамматику:
program ::= statement* EOF
compound-statement ::= '{' statement* '}'
statement ::= repeat-statement | function-call | compound-statement
repeat-statement ::= "repeat" "(" number-constant ")" compound-statement
function-call ::= ident "(" arglist ")"
arglist ::= EMPTY | arg ["," arg]*
arg ::= number-constant | duration-constant
Мы видим, что грамматика простая, а значит, её легко распарсить либо вручную, либо через стандартную связку lex/yacc (flex/bison). Парсить через lex/yacc намного проще, и технической работы намного меньше, но давайте напишем парсер вручную, это будет полезнее.
Итак, поскольку наша грамматика LL(1) (леворекурсивная, а для определения типа следующего правила достаточно подсмотреть на 1 токен вперёд), напишем простейший парсер рекурсивного спуска (recursive descent parser).
Я попробую написать парсер достаточно простой идейно, чтобы его было легко понять, но с другой стороны достаточно общий, чтобы его можно было легко расширить.
Первая часть любого уважающего себя парсера — токенизатор. Мы хотим разделить входную строку на осмысленные токены, чтобы не возиться с отдельными символами.
Для начала, какие у нас есть токены? Это
ключевые слова
repeat
пунктуация
круглые скобки
фигурные скобки
запятая
идентификаторы (имена функций)
константы
числа (наподобие 10)
продолжительность (наподобие 100s)
Это даёт такой enum
enum token_type
{
// keywords
tt_repeat,
tt_ident,
tt_number,
tt_duration,
// punctuation
tt_lparen,
tt_rparen,
tt_lbrace,
tt_rbrace,
tt_comma,
// end of file
tt_eof,
// parse error
tt_error
};
и тип данных для токена:
struct token
{
token_type type;
string string_value;
long num_value;
};
Сам токенизатор будет предоставлять функциональность «подсмотреть» на один токен вперёд, и будет запоминать текущую позицию токена в тексте для удобства отладки:
class tokenizer
{
const string text; // весь текст
int curridx; // текущая позиция в тексте
int endidx; // длина текста
int currline, currcol; // текущая строка/номер символа в строке
// (нужны лишь для отладки)
token lookahead; // следующий токен
void set_lookahead(); // перейти к следующему токену
// и запомнить его в lookahead
public:
tokenizer(string text) :
text(text), curridx(0), endidx(text.length()), currline(1), currcol(1)
{
lookahead.num_value = 0;
lookahead.string_value = "";
set_lookahead();
}
token peek_next() { return lookahead; }
void move_ahead() { set_lookahead(); }
};
Основная логика токенизатора находится, понятно, в функции set_lookahead. Эту функцию обычно строят на регулярках, наподобие того, как это делает lex. Но мы напишем её вручную.
void tokenizer::set_lookahead()
{
// начнём с пропуска незначащих пробелов
while (curridx < endidx && isspace(text[curridx]))
{
// не забываем следить за нашей позицией в файле
if (text[curridx] == '
')
{
currcol = 1;
currline++;
}
else
{
currcol++;
}
// переходим к следующему символу
curridx++;
}
// тут мы точно знаем, где начинается наш следующий токен
lookahead.lineno = currline;
lookahead.colno = currcol;
if (curridx == endidx) // конец файла
{
lookahead.type = tt_eof;
return;
}
char c = text[curridx];
// с пунктуацией всё просто
if (c == '(' || c == ')' || c == '{' || c == '}' || c == ',')
{
lookahead.type = (c == '(') ? tt_lparen :
(c == ')') ? tt_rparen :
(c == '{') ? tt_lbrace :
(c == '}') ? tt_rbrace :
tt_comma;
curridx++;
currcol++;
return;
}
// если токен начинается с буквы, это ключевое слово или идентификатор
if (isalpha(c))
{
// отделим-ка его сначала в переменную
string result;
while (curridx < endidx && isalpha(text[curridx]))
{
result += text[curridx];
curridx++;
currcol++;
}
// проверим ключевые слова
if (result == "repeat")
{
lookahead.type = tt_repeat;
return;
}
// у нас только одно, больше проверять нечего
// если не ключевое слово, значит, идентификатор
lookahead.type = tt_ident;
lookahead.string_value = result;
return;
}
// константы
if (isdigit(c)) // numeric
{
// отделим её от потока текста
string result;
// может содержать и буквы в нашей грамматике
while (curridx < endidx && isalnum(text[curridx]))
{
result += text[curridx];
curridx++;
currcol++;
}
auto c_str = result.c_str();
char* last_char;
// есть ли способ попроще узнать, является ли строка числом без "хвоста"?
long converted = strtol(c_str, &last_char, 10);
// разобрали все цифры? тогда это число
if (*last_char == 0)
{
lookahead.type = tt_number;
lookahead.num_value = converted;
return;
}
// в конце s? тогда это продолжительность
if (*last_char == 's' && *(last_char + 1) == 0)
{
lookahead.type = tt_duration;
lookahead.num_value = converted;
return;
}
}
// ничего не нашли? окей, запомним, что это ошибка
lookahead.type = tt_error;
}
Продолжаем. Поскольку наш язык простой, мы не будем различать syntax tree и parse tree (то есть, синтаксическое дерево и дерево разбора), и вместо честной реализации visitor'а в syntax tree просто положим виртуальную функцию execute. (Да, я ленюсь.)
Определим классы для syntax tree. Они прямо соответствуют грамматике. (Поскольку это определения, нужно бы везде сослаться на namespace std, но я не буду утяжелять код.)
struct statement
{
virtual void execute() = 0;
virtual ~statement() { }
};
struct function_call : public statement
{
shared_ptr
virtual void execute()
{
p_function->function(p_args->args);
}
};
struct compound_statement : public statement
{
vector
struct repeat_statement : public statement
{
unique_ptr
struct program : public compound_statement
{
};
Отдельно, нам нужны структуры данных для вызовов функций. Пускай аргументы будут типизированными, время union'ов прошло.
struct arg
{
virtual ~arg() { }
};
struct number_constant : arg
{
int value;
};
struct duration_constant : arg
{
std::chrono::seconds value;
};
struct arglist
{
vector
Можно, конечно, было бы не усложнять себе жизнь, и просто объявить имена функций ключевыми словами, но это не позволит легко добавлять новые функции.
struct installed_function
{
std::function
Перейдём к собственно парсеру. Он достаточно прямолинеен. Единственная хитрость — функции типа try_ пытаются найти в текущей точке потока синтаксическую конструкцию, определяя её по первому токену (вспомним, что наша грамматика LL(1)), и возвращают nullptr, если первый токен не подходит:
class parser
{
arg* try_parse_arg();
arglist* try_parse_arglist_until_rparen();
function_call* try_parse_function_call();
repeat_statement* try_parse_repeat_statement();
statement* try_parse_statement();
compound_statement* try_parse_compound_statement();
public:
program* parse();
tokenizer tokenizer;
installed_functions& functions;
public:
parser(string input, installed_functions& functions) :
tokenizer(input), functions(functions)
{
}
};
Реализация функций прямо соответствует грамматике. Мы сообщаем об ошибках при помощи исключений, поэтому нам придётся пользоваться «умными» указателями, чтобы не было утечек памяти.
// program ::= statement* EOF
program* parser::parse()
{
unique_ptr
// проверяем, что больше в файле ничего нет
token t = tokenizer.peek_next();
if (t.type != tt_eof)
throw parse_exception("extra characters after program end", t);
return p.release();
}
// compound-statement ::= '{' statement* '}'
compound_statement* parser::try_parse_compound_statement()
{
// ищем левую фигурную скобку
token t = tokenizer.peek_next();
if (t.type != tt_lbrace)
return nullptr;
tokenizer.move_ahead();
unique_ptr
// здесь должна быть закрывающая фигурная скобка
t = tokenizer.peek_next();
if (t.type != tt_rbrace)
throw parse_exception("expected closing brace after compound statement", t);
tokenizer.move_ahead();
return p.release();
}
// statement ::= repeat-statement | function-call | compound-statement
statement* parser::try_parse_statement()
{
statement* result = nullptr;
// пропробуем найти repeat statement
result = try_parse_repeat_statement();
if (result) // нашли? вот и хорошо
return result;
// не нашли? пробуем найти function call
result = try_parse_function_call();
if (result) // нашли вызов функции? прекрасно, задание выполнено
return result;
// не нашли? может, тут compound statement?
result = try_parse_compound_statement();
// нашли-не нашли, не интересно, вернём nullptr в крайнем случае.
return result;
}
// repeat-statement ::= "repeat" "(" number-constant ")" compound-statement
repeat_statement* parser::try_parse_repeat_statement()
{
// проверяем, есть ли в начале repeat
token t = tokenizer.peek_next();
if (t.type != tt_repeat)
return nullptr;
tokenizer.move_ahead();
// теперь обязательно скобка
t = tokenizer.peek_next();
if (t.type != tt_lparen)
throw parse_exception("opening parenthesis expected", t);
tokenizer.move_ahead();
// теперь количество повторений
t = tokenizer.peek_next();
if (t.type != tt_number)
throw parse_exception("number expected", t);
tokenizer.move_ahead();
// запомним его в переменую
long num = t.num_value;
// тут должна быть закрывающая скобка
t = tokenizer.peek_next();
if (t.type != tt_rparen)
throw parse_exception("closing parenthesis expected", t);
tokenizer.move_ahead();
// а за этим всем compound statement
// ну, это мы умеем
unique_ptr
// всё нашли? конструируем ответ
repeat_statement* rs = new repeat_statement();
rs->num_repeat = num;
rs->p_statement = move(s);
return rs;
}
// function-call ::= ident "(" arglist ")"
function_call* parser::try_parse_function_call()
{
// ищем идентификатор
token ft = tokenizer.peek_next();
if (ft.type != tt_ident)
return nullptr;
tokenizer.move_ahead();
// и запомниаем имя функции
string name = ft.string_value;
// проверим сначала общий синтаксис, а потом будем выяснять,
// есть ли такая функция
token t = tokenizer.peek_next();
if (t.type != tt_lparen)
throw parse_exception("left parenthesis expected for function call", t);
tokenizer.move_ahead();
unique_ptr
t = tokenizer.peek_next();
if (t.type != tt_rparen)
throw parse_exception("right parenthesis expected after function arg list", t);
tokenizer.move_ahead();
// обычно проверка семантики (является ли идентификатор функцией) -
// задача семантического анализа, то есть, последующих этапов компиляции
// но поскольку мы пишем игрушечный парсер, мы сделаем это прямо здесь
auto pfunc = functions.get(name);
if (!pfunc)
throw parse_exception("unknown function", ft);
// проверим заодно и количество аргументов
if (pfunc->argnum != args->args.size())
throw parse_exception("argument count for function doesn't match", ft);
// в принципе, ничего, кроме лени, не мешает нам проверить тут и *типы* аргументов
// а так придётся проверять типы аргументов во время выполнения
// и бросать runtime_exception
function_call* fc = new function_call();
fc->p_function = pfunc;
fc->p_args = move(args);
return fc;
}
// arg ::= number-constant | duration-constant
arg* parser::try_parse_arg()
{
arg* result = nullptr;
token t = tokenizer.peek_next();
if (t.type == tt_number)
{
auto r = new number_constant();
r->value = t.num_value;
result = r;
}
else if (t.type == tt_duration)
{
auto r = new duration_constant();
r->value = chrono::seconds(t.num_value);
result = r;
}
if (result != nullptr)
tokenizer.move_ahead();
return result;
}
// arglist ::= EMPTY | arg ["," arg]*
arglist* parser::try_parse_arglist_until_rparen()
{
unique_ptr
while (true)
{
arg* p = try_parse_arg();
if (!p)
throw parse_exception("expected argument", tokenizer.peek_next());
result->args.emplace_back(p);
t = tokenizer.peek_next();
if (t.type == tt_rparen)
return result.release();
if (t.type != tt_comma)
throw parse_exception("comma expected between arguments", t);
tokenizer.move_ahead();
}
}
Отлично, мы прошли бóльшую часть пути. Осталось лишь реализовать механизм добавления функций.
class installed_functions
{
unordered_map
public:
void install_function(
function
shared_ptr
Определим сами функции:
void f_pause(const vector
void f_click(const vector
И можно тестировать:
string text = "repeat (8)
"
"{
"
"click(10,10)
"
"pause(100s)
"
"click(10,10)
"
"repeat(2)
"
" {
"
" pause(10)
"
" }
"
"}";
int main(int argc, char* argv[])
{
installed_functions functions;
functions.install_function(f_pause, 1, "pause");
functions.install_function(f_click, 2, "click");
parser p(text, functions);
unique_ptr
return 0;
}
Получаем вывод:
executing:
click: (10, 10)
pause: 100 seconds
click: (10, 10)
runtime exception: argument type mismatch in function pause
Ах, да, мы же неправильно указали тип аргумента для pause! Меняем pause(10) на pause(10s), всё работает как часы.
Обновление: Чуть более продвинутая версия того же парсера доступна на гитхабе
Комментариев нет:
Отправить комментарий