数式の評価を原始的に #21
非負整数の足し算と掛け算の入った数式を評価する。
この文法の性質上、字句スタックは最大4個、被演算子スタックは最大3個の要素を入れられればいいはず。
混同することはないので字句スタックの最初の要素である先頭記号は末尾記号で代替する。
見返さずにかなり適当に作ったのでバギーだ。最悪なのはなぜかそれなりには動いていることだ。
...snip void token_copy(Token *dst, Token *src); void token_fin(Token *token); ...snip void token_copy(Token *dst, Token *src) { dst->type = src->type; if (src->type == TOKEN_TYPE_INTEGER) { dst->value = malloc(strlen(src->value + 1)); strcpy(dst->value, src->value); } } void token_fin(Token *token) { if (token->type == TOKEN_TYPE_INTEGER) free(token->value); } ...snip void mpi_copy(Mpi *dst, Mpi *src); ...snip void mpi_copy(Mpi *dst, Mpi *src) { int i; dst->ndigit = src->ndigit; dst->digit = malloc(src->ndigit); for (i = src->ndigit; --i >= 0; ) dst->digit[i] = src->digit[i]; } ...snip #define PS_SIZE 4 #define OS_SIZE 3 typedef struct { Lexer *lexer; Token *parser_stack; size_t next_ps; size_t size_ps; Mpi *operand_stack; size_t next_os; size_t size_os; } Parser; void parser_init_with_lexer(Parser *parser, Lexer *lexer); void parser_fin(Parser *parser); int parser_parser_stack_isEmpty(Parser *parser); Token *parser_parser_stack_peek(Parser *parser); Token *parser_parser_stack_pop(Parser *parser); void parser_parser_stack_push(Parser *parser, Token *token); void parser_parser_stack_clear(Parser *parser); int parser_operand_stack_size(Parser *parser); int parser_operand_stack_isEmpty(Parser *parser); Mpi *parser_operand_stack_pop(Parser *parser); void parser_operand_stack_push(Parser *parser, Mpi *mpi); void parser_operand_stack_clear(Parser *parser); int parser_table(int type1, int type2); void parser_parse(Parser *parser); ...snip void parser_init_with_lexer(Parser *parser, Lexer *lexer) { parser->lexer = lexer; parser->parser_stack = malloc(sizeof(Token) * PS_SIZE); parser->next_ps = 0; parser->size_ps = PS_SIZE; parser->operand_stack = malloc(sizeof(Mpi) * OS_SIZE); parser->next_os = 0; parser->size_os = OS_SIZE; } void parser_fin(Parser *parser) { free(parser->parser_stack); free(parser->operand_stack); } int parser_parser_stack_isEmpty(Parser *parser) { return parser->next_ps == 0; } Token *parser_parser_stack_peek(Parser *parser) { return parser_parser_stack_isEmpty(parser) ? NULL : &parser->parser_stack[parser->next_ps - 1]; } Token *parser_parser_stack_pop(Parser *parser) { return parser_parser_stack_isEmpty(parser) ? NULL : &parser->parser_stack[--parser->next_ps]; } void parser_parser_stack_push(Parser *parser, Token *token) { token_copy(&parser->parser_stack[parser->next_ps], token); parser->next_ps++; } void parser_parser_stack_clear(Parser *parser) { while (! parser_parser_stack_isEmpty(parser)) token_fin(parser_parser_stack_pop(parser)); parser->parser_stack[0].type = TOKEN_TYPE_EOF; parser->next_ps = 1; } int parser_operand_stack_size(Parser *parser) { return parser->next_os; } int parser_operand_stack_isEmpty(Parser *parser) { return parser->next_os == 0; } Mpi *parser_operand_stack_pop(Parser *parser) { return parser_operand_stack_isEmpty(parser) ? NULL : &parser->operand_stack[--parser->next_os]; } void parser_operand_stack_push(Parser *parser, Mpi *mpi) { mpi_copy(&parser->operand_stack[parser->next_os], mpi); parser->next_os++; } void parser_operand_stack_clear(Parser *parser) { while (! parser_operand_stack_isEmpty(parser)) mpi_fin(parser_operand_stack_pop(parser)); } int parser_table(int type1, int type2) { switch (type1) { case TOKEN_TYPE_INTEGER: switch (type2) { case '+': case '*': case '\n': case TOKEN_TYPE_EOF: return 1; default: return 0; } case '+': switch (type2) { case TOKEN_TYPE_INTEGER: case '*': return -1; case '+': case '\n': case TOKEN_TYPE_EOF: return 1; default: return 0; } case '*': switch (type2) { case TOKEN_TYPE_INTEGER: return -1; case '+': case '*': case '\n': case TOKEN_TYPE_EOF: return 1; default: return 0; } case '\n': switch (type2) { case TOKEN_TYPE_INTEGER: case '+': case '*': return -1; case '\n': return 1; default: return 0; } case TOKEN_TYPE_EOF: switch (type2) { case TOKEN_TYPE_INTEGER: case '+': case '*': case '\n': return -1; default: return 0; } default: return 0; } } void parser_parse(Parser *parser) { int pre_read_token = 0; parser_parser_stack_clear(parser); for (;;) { Token *token; int t; if (! pre_read_token) { token = lexer_next_token(parser->lexer); pre_read_token = 1; } if (parser->next_ps == 1) { if (token->type == '\n' || token->type == TOKEN_TYPE_EOF) { if (! parser_operand_stack_isEmpty(parser)) { Mpi *mpi = parser_operand_stack_pop(parser); char *s = mpi_make_decimal_expr(mpi); puts(s); free(s); mpi_fin(mpi); } if (token->type == '\n') { pre_read_token = 0; continue; } else { break; } } } t = parser_table(parser_parser_stack_peek(parser)->type, token->type); if (t < 0) { parser_parser_stack_push(parser, token); pre_read_token = 0; } else if (t > 0) { for (;;) { int ok = 1; Token *r = parser_parser_stack_pop(parser); if (r->type == TOKEN_TYPE_INTEGER) { Mpi mpi; mpi_init_with_decimal_expr(&mpi, token->value); parser_operand_stack_push(parser, &mpi); mpi_fin(&mpi); } else if (r->type == '+') { if (parser_operand_stack_size(parser) >= 2) { Mpi *mpi1 = parser_operand_stack_pop(parser); Mpi *mpi2 = parser_operand_stack_pop(parser); Mpi mpi3; mpi_add(mpi1, mpi2, &mpi3); mpi_fin(mpi1); mpi_fin(mpi2); parser_operand_stack_push(parser, &mpi3); mpi_fin(&mpi3); } else ok = 0; } else if (r->type == '*') { if (parser_operand_stack_size(parser) >= 2) { Mpi *mpi1 = parser_operand_stack_pop(parser); Mpi *mpi2 = parser_operand_stack_pop(parser); Mpi mpi3; mpi_mul(mpi1, mpi2, &mpi3); mpi_fin(mpi1); mpi_fin(mpi2); parser_operand_stack_push(parser, &mpi3); mpi_fin(&mpi3); } else ok = 0; } if (! ok) { puts("error"); if (token->type != '\n' && token->type != TOKEN_TYPE_EOF) { for (;;) { token = lexer_next_token(parser->lexer); if (token->type == '\n') { pre_read_token = 0; break; } else if (token->type == TOKEN_TYPE_EOF) break; } } parser_parser_stack_clear(parser); parser_operand_stack_clear(parser); break; } t = parser_table(parser_parser_stack_peek(parser)->type, r->type); token_fin(r); if (t < 0) break; } } else { puts("error"); for (;;) { token = lexer_next_token(parser->lexer); if (token->type == '\n') { pre_read_token = 0; break; } else if (token->type == TOKEN_TYPE_EOF) break; } parser_parser_stack_clear(parser); parser_operand_stack_clear(parser); } } } int main(void) { Lexer lexer; Parser parser; lexer_init(&lexer); parser_init_with_lexer(&parser, &lexer); parser_parse(&parser); parser_fin(&parser); lexer_fin(&lexer); return 0; }