Я пытаюсь реализовать анализатор математических выражений, который получает строку в качестве входных данных и в конечном итоге выводит условное представление на консоль. Я уже реализовал аналогичную рабочую программу на Python:
def term(self):
result = self.factor()
while self.current_token.type in (MUL, DIV):
token = self.current_token
if token.type == MUL:
self.eat(MUL)
result = result * self.factor()
elif token.type == DIV:
self.eat(DIV)
result = result / self.factor()
Но сейчас из-за моей неопытности в языке C у меня возникли некоторые проблемы.
Я приложил эскиз будущей программы, и в нем меня интересует функция parser_term
.
AST_T* parser_term(Parser_T* parser) {
AST_T* result;
while (parser->current_token->type == TOKEN_MUL
|| parser->current_token->type == TOKEN_DIV) {
if (parser->current_token->type == TOKEN_MUL) {
parser_eat(parser, TOKEN_MUL);
} else if (parser->current_token->type == TOKEN_DIV) {
parser_eat(parser, TOKEN_DIV);
}
}
return result;
}
Как мне создать новый узел бинарной операции? Возможно, это несколько глупый вопрос, но я надеюсь, что вы поможете мне разобраться.
Я также буду рад, если вы укажете мне на другие ошибки, которых может быть достаточно в моем коде.
Полный код:
#include <stdio.h>
#include <stdlib.h>
//============================ LEXICAL ANALYSIS ============================================
//---------------------------- Token -------------------------------------------------------
typedef struct TOKEN_STRUCT
{
enum
{
TOKEN_INTEGER,
TOKEN_PLUS, TOKEN_MINUS,
TOKEN_MUL, TOKEN_DIV,
TOKEN_LBRA, TOKEN_RBRA,
TOKEN_EOF
} type;
char* value;
} Token_T;
Token_T* init_token(int type, char* value)
{
Token_T* token = calloc(1, sizeof(struct TOKEN_STRUCT));
token->type = type;
token->value = value;
return token;
}
void token_debug_print(Token_T* token)
{
printf(
"Token( type: '%d', value: '%s' )\n",
token->type, token->value
);
}
//------------------------------------------------------------------------------------------
//---------------------------- Lexer -------------------------------------------------------
typedef struct LEXER_STRUCT
{
char current_char;
unsigned int position;
char* content;
} Lexer_T;
Lexer_T* init_lexer(char* content)
{
Lexer_T* lexer = calloc(1, sizeof(struct LEXER_STRUCT));
lexer->content = content;
lexer->position = 0;
lexer->current_char = lexer->content[lexer->position];
return lexer;
}
void lexer_advance(Lexer_T* lexer)
{
if (lexer->current_char != '\0')
{
lexer->position += 1;
lexer->current_char = lexer->content[lexer->position];
}
}
void lexer_skip_whitespace(Lexer_T* lexer)
{
while (lexer->current_char == ' ')
{
lexer_advance(lexer);
}
}
char* lexer_get_current_char_as_string(Lexer_T* lexer)
{
char* stringus = calloc(1, sizeof(char));
stringus[0] = lexer->current_char;
stringus[1] = '\0';
return stringus;
}
Token_T* lexer_get_digit(Lexer_T* lexer)
{
char* lexem = calloc(1, sizeof(char));
lexem[0] = '\0';
while (lexer->current_char >= '0' && lexer->current_char <= '9')
{
char* part = lexer_get_current_char_as_string(lexer);
lexem = realloc(lexem, (strlen(lexem) + strlen(part) + 1) * sizeof(char));
strcat(lexem, part);
lexer_advance(lexer);
}
return init_token(TOKEN_INTEGER, lexem);
}
Token_T* lexer_get_op(Lexer_T* lexer)
{
switch (lexer->current_char)
{
case '+':
lexer_advance(lexer);
return init_token(TOKEN_PLUS, "+");
case '-':
lexer_advance(lexer);
return init_token(TOKEN_MINUS, "-");
case '*':
lexer_advance(lexer);
return init_token(TOKEN_MUL, "*");
case '/':
lexer_advance(lexer);
return init_token(TOKEN_DIV, "/");
}
}
Token_T* lexer_get_next_token(Lexer_T* lexer)
{
while (lexer->current_char != '\0')
{
if (lexer->current_char == ' ')
lexer_skip_whitespace(lexer);
else if (lexer->current_char >= '0' && lexer->current_char <= '9')
return lexer_get_digit(lexer);
else if (lexer->current_char == '+' || lexer->current_char == '-' ||
lexer->current_char == '*' || lexer->current_char == '/')
return lexer_get_op(lexer);
else if (lexer->current_char == '(')
{
lexer_advance(lexer);
return init_token(TOKEN_LBRA, "(");
}
else if (lexer->current_char == ')')
{
lexer_advance(lexer);
return init_token(TOKEN_RBRA, ")");
}
}
return init_token(TOKEN_EOF, "\\0");
}
//-----------------------------------------------------------------------------------------
//=========================================================================================
//============================ SYNTAX ANALYSIS ============================================
//---------------------------- AST --------------------------------------------------------
typedef struct AST_STRUCT
{
enum{
AST_NUMBER,
AST_BINOP,
AST_PAREN_EXPR
} type;
char* number_value;
char* bin_operator;
struct AST_STRUCT* left;
struct AST_STRUCT* right;
struct AST_STRUCT* paren_expr;
} AST_T;
AST_T* init_AST(int type)
{
AST_T* ast = calloc(1, sizeof(struct AST_STRUCT));
ast->type = type;
return ast;
}
//-----------------------------------------------------------------------------------------
//---------------------------- Parser -----------------------------------------------------
typedef struct PARSER_STRUCT
{
Lexer_T* lexer;
Token_T* current_token;
} Parser_T;
Parser_T* init_parser(Lexer_T* lexer)
{
Parser_T* parser = calloc(1, sizeof(struct PARSER_STRUCT));
parser->lexer = lexer;
parser->current_token = lexer_get_next_token(parser->lexer);
return parser;
}
AST_T* parser_factor(Parser_T* parser);
AST_T* parser_term(Parser_T* parser);
AST_T* parser_expr(Parser_T* parser);
void parser_eat(Parser_T* parser, int type)
{
if (parser->current_token->type == type)
{
parser->current_token = lexer_get_next_token(parser->lexer);
}
else
{
printf("Unexpected token");
exit(0);
}
}
AST_T* parser_expr(Parser_T* parser)
{
}
AST_T* parser_factor(Parser_T* parser)
{
if (parser->current_token->type == TOKEN_INTEGER)
{
AST_T* node = init_AST(TOKEN_INTEGER);
node->number_value = parser->current_token->value;
parser_eat(parser, TOKEN_INTEGER);
return node;
}
}
AST_T* parser_term(Parser_T* parser)
{
AST_T* result;
while (parser->current_token->type == TOKEN_MUL || parser->current_token->type == TOKEN_DIV)
{
if (parser->current_token->type == TOKEN_MUL)
{
parser_eat(parser, TOKEN_MUL);
}
else if (parser->current_token->type == TOKEN_DIV)
{
parser_eat(parser, TOKEN_DIV);
}
}
return result;
}
//-----------------------------------------------------------------------------------------
//=========================================================================================
//============================ VISITOR ====================================================
typedef struct VISITOR_STRUCT
{
} Visitor_T;
Visitor_T* init_visitor(AST_T* ast)
{
Visitor_T* visitor = calloc(1, sizeof(struct VISITOR_STRUCT));
return visitor;
}
void visitor_visit_number(Visitor_T* visitor, AST_T* node)
{
printf("Number {\n");
printf(" %s\n", node->number_value);
printf("}\n");
}
void visitor_visit_bin_op(Visitor_T* visitor, AST_T* node)
{
printf("Binop {\n");
visitor_visit(visitor, node->left);
visitor_visit(visitor, node->right);
printf("\n}\n");
}
void visitor_visit_paren_expr(Visitor_T* visitor, AST_T* node)
{
visitor_visit(visitor, node);
}
void visitor_visit(Visitor_T* visitor, AST_T* ast)
{
if (ast->type == AST_NUMBER)
{
visitor_visit_number(visitor, ast);
}
else if (ast->type == AST_BINOP)
{
visitor_visit_bin_op(visitor, ast);
}
else if (ast->type == AST_PAREN_EXPR)
{
visitor_visit_paren_expr(visitor, ast);
}
}
//=========================================================================================
int main()
{
char* code = "77 * 12 * 9 * 2";
Lexer_T* lexer = init_lexer(code);
Parser_T* parser = init_parser(lexer);
AST_T* ast = parser_term(parser);
Visitor_T* visitor = init_visitor(ast);
visitor_visit(visitor, ast);
return 0;
}
Я пытался сначала получить значение фактора и добавить его к узлу, а затем продолжить разбор выражения, но это меня только смутило. Я ожидаю, что эта программа сможет обрабатывать подобные бинарные операции и превращать их в один AST.
Однако, возможно, чтобы ответить на вопрос... Если это парсер рекурсивного спуска, вы захотите сначала использовать операции с меньшим приоритетом (например, + и -). Таким образом, вы можете сначала разделить выражение на них. Например, 2 * 5 + 7 * 3
. Вы хотите потреблять и делиться на +
в первую очередь. Затем вы можете заняться разбором 2 * 5
и 7 * 3
по отдельности.
Я скопировал функцию Python term()
в сам вопрос. Но мне непонятно, как это делает ту же работу, которую вы хотите, чтобы функция C выполняла. Похоже, что он вычисляет значение, возможно, на основе уже построенного AST, а не строит AST.
Вам необходимо написать свой лексер с нуля? Возможно, да, но если нет, то генерация кода для лексеров — это именно то, для чего предназначены традиционная lex
программа и ее аналог GNU flex
.
Да, вы правы, это не совсем то, что нам нужно. Могу предположить, что на питоне это должно выглядеть примерно так class BinOp(AST): class Num(AST): class Parser(): def term(self): node = self.factor() while self.current_token.type in (MUL, DIV): token = self.current_token if token.type == MUL: self.eat(MUL) elif token.type == DIV: self.eat(DIV) node = BinOp(left=node, op=token, right=self.factor()) return node
Пожалуйста, прекратите публиковать многострочные фрагменты Python в комментариях. Их просто невозможно читать. Если вопрос будет прояснен или иным образом улучшен путем добавления дополнительного кода Python или редактирования того, что уже есть, используйте ссылку «Редактировать», чтобы внести такие изменения.
Также обратите внимание, что если вы хотите реализовать обычные правила арифметического старшинства, такие как, например, 1 + 2 * 3 оценивается как 7 вместо 9, вам нужно различать разные виды двоичных операций. Похоже, вы можете сделать это с помощью AST_T.bin_operator
, но я предполагаю, что будет проще разделить ваши бинарные операторы на разные виды по уровню приоритета, скажем, ADDITIVE_OP
и MULTIPLICATIVE_OP
.
извините, я все еще не могу привыкнуть к этому сайту. А что касается использования готового решения типа lex или flex, то это возможно, так как у этого проекта нет особых требований. Я не хочу использовать готовые решения, потому что я хочу понять для себя, как это работает, и не чувствовать себя таким глупым и беспомощным)
Кажется, я начал понимать, в каком направлении следует двигаться в отношении. Большое спасибо
Как вам нравится. Но обратите внимание, что способность эффективно использовать инструменты более высокого уровня, такие как Flex, делает вас лучше подготовленными, а не глупыми или беспомощными. С другой стороны, вам нужно было бы больше учиться, так что, возможно, сейчас это не то, чем нужно заниматься.
Для справки, я написал синтаксический анализатор для TSQL, который я написал для замены синтаксического анализатора, сгенерированного ANTLR. Здесь ссылка на функцию разбора выражений. Вероятно, в нем есть ошибки, так как я еще не вернулся к нему, но основная идея работает. Вы можете копировать из него все, что хотите.
Один явный вопрос здесь таков:
Как мне создать новый узел бинарной операции?
Вам нужен объект, который создается по мере необходимости, но время жизни которого не ограничивается автоматически выполнением функции, в которой он начинается. Эта комбинация требует динамического распределения. (Вы получаете это автоматически в Python все время, но в C вам нужно попросить об этом.) Например:
AST_T *result = malloc(sizeof(*result));
В соответствии с передовой практикой вы всегда должны проверять, что выделение прошло успешно, прежде чем пытаться использовать выделенный объект. Если нет, вам следует вернуться к какой-либо альтернативной операции или операции восстановления или, что чаще всего, просто потерпеть неудачу. В программе, в отличие от библиотеки, разумно потерпеть неудачу, напечатав диагностику и завершив работу. Например:
if (result == NULL) {
fputs("fatal error: memory allocation failure\n", stderr);
abort();
}
Но очень маловероятно, что аллокации в вашей программе потерпят неудачу, если только что-то еще не пойдет не так.
Предположим, что выделение прошло успешно, вы захотите соответствующим образом установить члены нового объекта. Может что-то в этом роде:
result->type = /* as appropriate */; // ...
result->number_value = NULL;
result->bin_operator = // ...
result->left = NULL; // probably something other than NULL in some cases
result->right = NULL;
result->paren_expr = NULL; // WTH?
В конечном итоге вам нужно будет либо вернуть указатель на новый узел (что, похоже, вы и ожидаете сделать), либо, возможно, назначить его члену парсера. Или оба. Это легко. Например,
return result;
Также буду рад, если вы укажете мне на другие ошибки
Боюсь, это слишком широкое требование для ТАК. Но включите предупреждения вашего компилятора и обратите на них внимание. На вашем уровне опыта вы должны исходить из того, что каждое предупреждение описывает проблему, из-за которой ваша программа будет работать неправильно.
Прежде всего, для любого компилятора, который вы используете, включите предупреждения. На gcc или clang это будет
-Wall -Wextra
, а если вы хотите сойти с ума,-Wpedantic
. Это уже укажет на несколько вещей. Работает лиparser_term
в Python, как вы ожидаете? Если да, не могли бы вы опубликовать этот код?