На лабе задали написать синтаксический анализатор языка С:
Написать синтаксический анализатор, обнаруживающий наибольшее число ошибок, для
приведённой ниже грамматики (данная грамматика является упрощённым вариантом грамматики
языка С):
< program >: < type > ’main’ ‘(‘ ‘)’ ‘{‘ < statement > ‘}’
< type >: ‘int’
| ‘bool’
| ‘void’
:
| < declaration > ‘;’
| ‘{‘ < statement > ‘}’
| < for > < statement >
| < if > < statement >
| < return >
< declaration >: < type > < identifier > < assign >
< identifier >: < character >< id_end >
< character >: ‘a’ | ‘b’ | ‘c’ | ‘d’ | ‘e’ | ‘f’ | ‘g’ | ‘h’ | ‘i' | ‘j’ | ‘k’ |
‘l’ | ‘m’ | ‘n’ | ‘o’ | ‘p’ | ‘q’ | ‘r’ | ‘s’ | ‘t’ | ‘u’ | ‘v’ | ‘w’ | ‘x’ | ‘y’ |
‘z’ | ‘A’ | ‘B’ | ‘C’ | ‘D’ | ‘E’ | ‘F’ | ‘G’ | ‘H’ | ‘I’ | ‘J’ | ‘K’ | ‘L’ | ‘M’ |
‘N’ | ‘O’ | ‘P’ | ‘Q’ | ‘R’ | ‘S’ | ‘T’ | ‘U’ | ‘V’ | ‘W’ | ‘X’ | ‘Y’ | ‘Z’ | ‘_’
:
|
:
| ‘=’
:
|
:
: ‘0’ | ‘1’ | ‘2’ | ‘3’ | ‘4’ | ‘5’ | ‘6’ | ‘7’ | ‘8’ | ‘9’
:
|
: ‘for’ ‘(‘ ‘;’ ‘;’ ‘)’
:
|
: ‘<’ | ‘>’ | ‘==’ | ‘!=’
: ‘if’ ‘(‘ ‘)’
: ‘return’ ‘;’
Первые 4-е строки вроде понял(это описание мейна). А что идет дальше? Какие варианты
кода может реализовать данный шаблон? Может у кого уже есть какие-то наработки на языке
С++? В сети ничего не нашел(т.к. не знаю что конкретно мне нужно, тупо как-то проанализировать
код?). В любом случае пример кода не помешал бы.
Ответы
Ответ 1
@Alerr, исходники yacc или bison Вам сейчас совершенно не помогут. А вот Вирта почитайте.
Еще можете поискать исходники "калькуляторов". Они довольно распространены и обычно
там для трансляции выражения, например, в обратную польскую нотацию применяют как раз
алгоритм рекурсивного спуска (он тут тоже подойдет).
Думаю, рекурсивный разбор как раз будет в следующей лабе.
В принципе ничего сложного (здесь Вам уже сказали об этом) тут нет. Для начала напишите
лексический анализатор. Это функция, которая читает ввод и возвращает лексему - структуру,
в которой описано что мы прочли идентификатор, ключевое слово, число, знак операции,
скобку и т.п.
При этом часть грамматики у Вас уйдет в этот лексический анализатор и грамматика
упростится.
Далее, просто пишете набор функций в соответствии с грамматикой. Ну, пожалуй надо
придумать, как сообщать об ошибках, принять решение, заканчивать разбор при первой
же ошибке или пробовать "восстановиться" и разбирать дальше (это сложнее) и т.п.
Я начну какой-то сильно псевдокод, думаю станет понятней
int programm () {
int rc;
lexem_t lx = get_lexem();
if (lx.type == KEYWORD &&
(lx.subtype == INT || lx.subtype == VOID || lx.subtype == BOOL)) {
lx = get_lexem();
if (lx.type == IDENT && strcmp(lx.value, "main") == 0) {
// очевидно, в нормальном Си тут нужно вызывать разбор списка параметров
// но в нашей грамматике должна идти пара '(' ')'
if ((rc = parentheses()) == OK) {
lx = get_lexem();
if (lx.type == SPEC && lx.char_value == '{')
if ((rc = statement()) == OK) { // уффф! почти добрались до конца
lx = get_lexem();
if (lx.type == SPEC && lx.char_value == '}')
return OK; // Ура!!!
rc = error_message(lx, ...); // ждали '}', а прочли ???
}
return rc;
}
rc = error_message(lx, ...); // ждали '{', а прочли ???
}
return rc;
// далее в том же духе обработка ошибок, просто в этом "редакторе" мало строк
помещается, набирать с indent трудно
...
} // конец if (lx.type == KEYWORD ...
return error_message(lx, ....); // ждали int | void | bool, а прочли ???
}
Надеюсь, в общих чертах понятно.
Еще одно, Вам почти наверняка понадобится функция аналогичная ungetc(c), но для лексемы.
Не забудьте учесть, продумывая структуры данных.
Ответ 2
Здесь простая грамматика языка, которую вполне можно реализовать без использования
lex и yacc. Для лексического анализа нужен лексический анализатор, который по набору
символов будет определять, какая именно лексема встретилась. Синтаксический анализатор,
опираясь на поток лексем, может проверять синтаксис.
Лексический анализ
В данном конкретном случае достаточно рассматривать один символ из входного потока,
для того, чтобы понять, о какой лексеме идёт речь. Такой алгоритм называется анализом
с предпросмотром на 1 символ.
Обычно лексический анализатор пропускает все разделители (пробелы и символы новой
строки), которые встречает во входном потоке, и не возвращает их в виде лексем.
Для начала определим, какие лексемы перечислены в грамматике. Это ключевые слова:
main, int, bool, void, for, if, return
разделители и операторы
{} () ; = < > == !=
а также идентификаторы и числа. Для упрощения кода мы добавим также лексему, которая
будет соответствовать концу файла. Кроме того, если мы не можем распознать лексему,
мы также должны вернуть специальный код. Итого:
#define MAIN 1
#define INT 2
#define BOOL 3
#define VOID 4
#define FOR 5
#define IF 6
#define RETURN 7
#define LBRACE 101 /* { */
#define RBRACE 102 /* } */
#define LPAREN 103 /* ( */
#define RPAREN 104 /* ) */
#define SEMICOLON 105 /* ; */
#define ASSIGN 106 /* = */
#define LT 107 /* < */
#define GT 108 /* > */
#define EQUAL 109 /* == */
#define NOT_EQUAL 110 /* != */
#define IDENTIFIER 201
#define NUMBER 202
#define END 301 /* конец файла */
#define ERROR 302 /* ошибка */
Что такое лексический анализатор? В простейшем случае это одна функция, которая получает
на вход поток символов, читает оттуда лексему и возвращает её. Для лексем IDENTIFIER
и NUMBER нам потребуются также прочитанные символы, поэтому мы должны передавать адрес
буфера для сохранения символов из входящего потока.
Для того, чтобы прочитать несколько лексем, нужно вызвать функцию несколько раз.
То есть сигнатура функции должна быть такой:
int get_lexem(FILE* stream, char* buffer);
Как её реализовать? Рассмотрим входной поток из символов "a=534", для упрощения пусть
она будет без пробелов. Прочитав из потока символ '=' мы не можем остановиться, потому
что в потоке может находиться лексема "==". Значит, мы читаем следующий символ, им
оказывается '5' и теперь мы точно значем, что прочитали лексему ASSIGN а не EQUAL.
Однако, символ '5' уже прочитан из потока, и при следующем вызове мы прочитаем оттуда
уже '3' и '4'. Нам совершенно точно нужно сохранять между вызовами get_lexem последний
прочитанный символ.
Это можно делать разными способами, мы будем возвращать символ обратно в поток, вызывая
стандартную функцию C ungetc. Такая ситуация будет возникать не каждый раз, а только
тогда, когда лексема содержит больше одного символа.
int get_lexem(FILE* stream, char* buffer, size_t buffer_length)
{
int ch = getc(stream);
size_t i;
/* пропускаем все пробелы, табуляции и символы новой строки */
while(isspace(ch))
ch = getc(stream);
/* конец файла */
if(ch == EOF)
return END;
/* простые односимвольные лексемы */
if(ch == '{')
return LBRACE;
if(ch == '}')
return RBRACE;
if(ch == '(')
return LPAREN;
if(ch == ')')
return RPAREN;
if(ch == ';')
return SEMICOLON;
if(ch == '<')
return LT;
if(ch == '>')
return GT;
/* сложный случаай 1: = или == */
if(ch == '=') {
ch = getc(stream);
if(ch == '=')
return EQUAL;
ungetc(ch, stream);
return ASSIGN;
}
/* сложный случай 2: != */
if(ch == '!') {
ch = getc(stream);
if(ch == '=')
return NON_EQUAL;
/* по грамматике сразу после ! обязан идти символ = */
/* если это не так, в лексеме ошибка */
return ERROR;
}
/* сложный случай 3: идентификатор или ключевое слово */
if(isalpha(ch) || ch == '_') {
i = 0;
do {
buffer[i++] = ch;
} while((ch = getc(stream)) != EOF && (isalpha(ch) || isdigit(ch) || ch == '_'));
if(ch != EOF)
ungetc(ch, stream);
buffer[i] = '\0';
if(strcmp("main", buffer) == 0)
return MAIN;
if(strcmp("int", buffer) == 0)
return INT;
if(strcmp("bool", buffer) == 0)
return BOOL;
if(strcmp("void", buffer) == 0)
return VOID;
if(strcmp("for", buffer) == 0)
return FOR;
if(strcmp("if", buffer) == 0)
return IF;
if(strcmp("return", buffer) == 0)
return RETURN;
return IDENTIFIER;
}
/* сложный случай 4: число */
if(isdigit(ch)) {
i = 0;
do {
buffer[i++] = ch;
} while((ch = getc(stream)) != EOF && isdigit(ch));
if(ch != EOF)
ungetc(ch, stream);
buffer[i] = '\0';
return IDENTIFIER;
}
}
Обратие внимание, как собираются символы лексем IDENTIFIER и NUMBER. Логика тут сложная,
но каждый отдельный момент мы уже обсуждали. Если в потоке, например, находятся символы
"_abc123=", то функция прочитает их все, включая '=', при этом символы "_abc123" попадут
в буфер, а '=' мы вернём назад в поток. Конец файла возвращать в поток не нужно.
Поскольку ключевые слова невозможно отличить от идентификаторов по правилам грамматики,
а можно только по словарю, мы опеределяем их там же, где и идентификаторы.
В приведённом коде есть две проблемы. Первая из них связана с тем, что возможно переполнение
буфера. Скажем, мы сделаем размер буфера равным 1000 символов, а безумный программист
придумает идентификатор длиной 1002 символа. Код и так получился довольно большим,
поэтому я не стал писать обработку этой ошибки.
Вторая проблема быстродействия, поскольку при чтении каждого идентификатора мы прогоняем
его по списку ключевых слов самым медленным способом. В реальных компилятора здесь
используют хеш-таблицы.
Синтаксический анализ
Простейший ручной способ синтаксического анализа — алгоритм рекурсивного спуска,
который позволяет разбирать грамматики LL(1). Ваша грамматика как раз такая, что упрощает
нам задачу.
Правила кодируются очень простым способом. Например, что такое программа?
program :: = type "main" "(" ")" "{" statement "}"
Вот как это кодируется в C:
char buffer[1024];
int program(FILE* stream)
{
int statement_result;
int lexem = get_lexem(stream, buffer);
if(lexem != INT || lexem != BOOL && lexem != VOID)
return UNRECOGNIZED_MAIN_TYPE;
lexem = get_lexem(stream, buffer);
if(lexem != MAIN)
return EXPECTED_MAIN;
lexem = get_lexem(stream, buffer);
if(lexem != LPAREN)
return EXPECTED_LPAREN;
lexem = get_lexem(stream, buffer);
if(lexem != RPAREN)
return EXPECTED_RPAREN;
lexem = get_lexem(stream, buffer);
if(lexem != LBRACE)
return EXPECTED_LBRACE;
statement_result = statement(stream);
if(statement_result != OK)
return statement_result;
lexem = get_lexem(stream, buffer);
if(lexem != RBRACE)
return EXPECTED_RBRACE;
return OK;
}
Многословно, но в принципе понятно. Константы OK, UNRECOGNIZED_MAIN_TYPE, EXPECTED_MAIN
необходимо определить самостоятельно. Они описывают ошибки, которые грамматика может
распознать. UNRECOGNIZED_MAIN_TYPE означает, что анализатор ожидает один из трёх типов,
но получил что-то другое. Константа OK означает, что ошибок нет.
Конструкция
lexem = get_lexem(stream, buffer);
if(lexem != RBRACE)
return EXPECTED_RBRACE;
встречается очень часто. Её можно назвать "требовать наличия лексемы во входном потоке".
Для неё удобно завести отдельные функции:
bool require_lexem1(FILE* stream, int expected1)
{
int lexem = get_lexem(stream);
return lexem == expected1;
}
bool require_lexem2(FILE* stream, int expected1, int expected2)
{
int lexem = get_lexem(stream);
return lexem == expected1 || lexem == expected2;
}
bool require_lexem3(FILE* stream, int expected1, int expected2, int expected3)
{
int lexem = get_lexem(stream);
return lexem == expected1 || lexem == expected2 || lexem == expected3;
}
Теперь функцию program можно сделать проще и короче:
int program(FILE* stream)
{
int statement_result;
if(!require_lexem3(stream, INT, BOOL, VOID))
return UNRECOGNIZED_MAIN_TYPE;
if(!require_lexem1(stream, MAIN))
return EXPECTED_MAIN;
if(!require_lexem1(stream, LPAREN))
return EXPECTED_LPAREN;
if(!require_lexem1(stream, RPAREN))
return EXPECTED_RPAREN;
if(!require_lexem1(stream, LBRACE))
return EXPECTED_LBRACE;
statement_result = statement(stream);
if(statement_result != OK)
return statement_result;
if(!require_lexem1(stream, RBRACE))
return EXPECTED_RBRACE;
return OK;
}
Функция statement сложнее и интереснее. Она на основании следующей лексемы принимает
решение о том, какое из альтернативных правил применить.
int statement(FILE* stream)
{
int statement_result;
int lexem = get_lexem(stream);
if(lexem == INT || lexem == BOOL || lexem == VOID)
return declaration(stream);
if(lexem == LBRACE) {
statement_result = statement(stream);
if(statement_result != OK)
return statement_result;
if(!require_lexem1(stream, RBRACE))
return EXPECTED_RBRACE;
return OK;
}
if(lexem == FOR)
return for_rule(stream);
if(lexem == IF)
return if_rule(stream);
if(lexem == RETURN)
return return_rule(stream);
return UNRECOGNIZED_STATEMENT;
}
Эта функция рекурсивна, поэтому позволяет распознавать сложные конструкции вида
{ { { int i = 300; } } }. Для примера реализуем также функцию declaration:
int declaration(FILE* stream)
{
if(!require_lexem1(stream, IDENTIFIER))
return EXPECTED_IDENTIFIER;
if(!require_lexem1(stream, ASSIGN))
return EXPECTED_ASSIGN;
if(!require_lexem2(stream, IDENTIFIER, NUMBER))
return EXPECTED_IDENTIFIER_OR_NUMBER;
if(!require_lexem1(stream, SEMICOLON))
return EXPECTED_SEMICOLON;
return OK;
}
Стараемся придерживаться принципа: для каждого правила в грамматике писать отдельную
функцию, так удобнее проводить соответствия. В приведённом коде я отошёл от этого принципа,
чтобы сделать код чуть короче, в частности, правила assign и assign_end попали внутрь
declaration.
В результате алгоритм спускается от верхнего общего правила к нижним (от program
к declaration через statement), при этом некоторые функции могут вызывать друг друга
рекурсивно.
Именно поэтому алгоритм называется рекурсивным спуском.
Реализовав все правила, мы получим полноценный анализатор программ, который сможет
сообщать нам об ошибках.
Напишем предпоследнюю функцию, которая превратит коды ошибок в текстовые сообщения:
const char* get_message(int code)
{
switch(code) {
case OK:
return "Ok";
case UNRECOGNIZED_MAIN_TYPE:
return "Unrecognized main type";
. . .
}
return "Unrecognized code";
}
Главная функция программы оказывается очень простой:
void main()
{
int code = program(stdin);
const char* message = get_message(code);
printf("%s\n", message);
}
Заключение
Мы реализовали лексический анализатор (get_lexem), набор вспомогательных функций
для проверки наличия лексем (require_lexem1, require_lexem2, require_lexem3) и набор
функций для каждого правила грамматики (program, statement, declaration и множество
других, которые вам предстоит написать самостоятельно). Функция get_message позволила
нам выводить понятный текст вместо непонятных кодов. У нас получилось два набора констант:
коды лексем (LPAREN, IDENTIFIER и т.д.) и коды ошибок (OK, EXPECTED_ASSIGN и т.д.)
Вся программа целиком способна проверить код другой программы и вывести OK, если
она соответствует грамматике. В противном случае она выводит сообщение об ошибке.
