#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_BUF 512
#define MAX_ID 128

/* token 种类枚举，词法扫描输出的记号类型 */
enum {
    SYN_INT,
    SYN_FLOAT,
    SYN_IF,
    SYN_WHILE,
    SYN_PRINT,
    SYN_ID,
    SYN_NUM,
    SYN_EQ,
    SYN_PLUS,
    SYN_MINUS,
    SYN_STAR,
    SYN_SLASH,
    SYN_LPAREN,
    SYN_RPAREN,
    SYN_LBRACE,
    SYN_RBRACE,
    SYN_SEMI,
    SYN_END,
    SYN_ERR
};

/* AST 结点类型枚举，区分不同语法结构 */
typedef enum {
    NODE_PROG,
    NODE_STMTLIST,
    NODE_DECL,
    NODE_ASSIGN,
    NODE_IF,
    NODE_WHILE,
    NODE_PRINT,
    NODE_BLOCK,
    NODE_BINOP,
    NODE_ID,
    NODE_NUM,
    NODE_TYPE
} NodeType;

/* 抽象语法树结点结构体 */
typedef struct AstNode {
    NodeType type;
    char val[MAX_ID];
    struct AstNode *lchild;
    struct AstNode *rchild;
    struct AstNode *next;
} AstNode;

/* 记号名称数组，报错时用于打印记号名字 */
const char *syn_name[] = {
    "int", "float", "if", "while", "print", "ID", "NUM",
    "=", "+", "-", "*", "/", "(", ")", "{", "}", ";", "$", "ERR"
};

char input[MAX_BUF];    /* 存放输入的源代码 */
char token[MAX_ID];     /* 当前识别出的单词字符串 */
int p_input;            /* 源码缓冲区字符指针 */
int p_token;            /* token 字符串填充指针 */
char ch;                /* 当前正在处理的字符 */
int syn;                /* 当前记号类型编号 */
int line_no;            /* 当前行号，用于报错定位 */
int error_cnt;          /* 语法错误总数 */

/* 函数声明：语法分析入口与各个非终结符分析函数 */
AstNode *program(void);
AstNode *stmt_list(void);
AstNode *stmt(void);
AstNode *decl_stmt(void);
AstNode *type_node(void);
AstNode *assign_stmt(void);
AstNode *if_stmt(void);
AstNode *while_stmt(void);
AstNode *print_stmt(void);
AstNode *block_stmt(void);
AstNode *expr(void);
AstNode *expr_prime(AstNode *left);
AstNode *term(void);
AstNode *term_prime(AstNode *left);
AstNode *factor(void);

void scaner(void);
void match(int expect);
void panic_recover(void);
AstNode *new_node(NodeType t, const char *s);
void print_tree(AstNode *root, int depth);

/**
 * @brief 创建一个抽象语法树结点
 * @param t 结点类型
 * @param s 结点携带文本
 * @return 新结点指针
 */
AstNode *new_node(NodeType t, const char *s)
{
    AstNode *p = (AstNode *)malloc(sizeof(AstNode));
    p->type = t;
    strncpy(p->val, s, MAX_ID - 1);
    p->val[MAX_ID - 1] = '\0';
    p->lchild = NULL;
    p->rchild = NULL;
    p->next = NULL;
    return p;
}

/**
 * @brief 词法扫描器：读取字符，生成下一个 token
 */
void scaner(void)
{
    p_token = 0;
    ch = input[p_input++];

    /* 跳过空白字符，换行则行号 +1 */
    while (ch == ' ' || ch == '\t' || ch == '\r' || ch == '\n')
    {
        if (ch == '\n')
            line_no++;
        ch = input[p_input++];
    }

    /* 识别标识符 / 关键字 */
    if (isalpha((unsigned char)ch) || ch == '_')
    {
        while (isalnum((unsigned char)ch) || ch == '_')
        {
            token[p_token++] = ch;
            ch = input[p_input++];
        }
        p_input--;
        token[p_token] = '\0';

        if (strcmp(token, "int") == 0)
            syn = SYN_INT;
        else if (strcmp(token, "float") == 0)
            syn = SYN_FLOAT;
        else if (strcmp(token, "if") == 0)
            syn = SYN_IF;
        else if (strcmp(token, "while") == 0)
            syn = SYN_WHILE;
        else if (strcmp(token, "print") == 0)
            syn = SYN_PRINT;
        else
            syn = SYN_ID;
        return;
    }

    /* 识别无符号数字 */
    if (isdigit((unsigned char)ch))
    {
        while (isdigit((unsigned char)ch))
        {
            token[p_token++] = ch;
            ch = input[p_input++];
        }
        p_input--;
        token[p_token] = '\0';
        syn = SYN_NUM;
        return;
    }

    /* 识别运算符、分隔符 */
    switch (ch)
    {
        case '=': syn = SYN_EQ; break;
        case '+': syn = SYN_PLUS; break;
        case '-': syn = SYN_MINUS; break;
        case '*': syn = SYN_STAR; break;
        case '/': syn = SYN_SLASH; break;
        case '(': syn = SYN_LPAREN; break;
        case ')': syn = SYN_RPAREN; break;
        case '{': syn = SYN_LBRACE; break;
        case '}': syn = SYN_RBRACE; break;
        case ';': syn = SYN_SEMI; break;
        case '\0': syn = SYN_END; break;
        default: syn = SYN_ERR; break;
    }
}

/**
 * @brief 记号匹配函数
 * @param expect 期望读到的记号类型
 */
void match(int expect)
{
    if (syn == expect)
    {
        scaner();
    }
    else
    {
        printf("【第 %d 行 语法错误】期望：%s，当前读到：%s\n",
               line_no, syn_name[expect], syn_name[syn]);
        error_cnt++;
        panic_recover();
    }
}

/**
 * @brief 恐慌模式错误恢复
 * 不断吃掉 token，直到碰到同步记号：; { } if while
 */
void panic_recover(void)
{
    while (syn != SYN_END)
    {
        if (syn == SYN_SEMI || syn == SYN_LBRACE || syn == SYN_RBRACE
            || syn == SYN_IF || syn == SYN_WHILE)
        {
            return;
        }
        scaner();
    }
}

/**
 * @brief 打印抽象语法树，depth 控制缩进
 * @param root 当前结点
 * @param depth 当前深度
 */
void print_tree(AstNode *root, int depth)
{
    if (root == NULL)
        return;
    for (int i = 0; i < depth; i++)
        printf("    ");

    switch (root->type)
    {
        case NODE_PROG:
            printf("program\n");
            break;
        case NODE_STMTLIST:
            printf("stmt_list\n");
            break;
        case NODE_DECL:
            printf("decl_stmt\n");
            break;
        case NODE_ASSIGN:
            printf("assign_stmt\n");
            break;
        case NODE_IF:
            printf("if_stmt\n");
            break;
        case NODE_WHILE:
            printf("while_stmt\n");
            break;
        case NODE_PRINT:
            printf("print_stmt\n");
            break;
        case NODE_BLOCK:
            printf("block\n");
            break;
        case NODE_BINOP:
            printf("binary %s\n", root->val);
            break;
        case NODE_ID:
            printf("id: %s\n", root->val);
            break;
        case NODE_NUM:
            printf("NUM: %s\n", root->val);
            break;
        case NODE_TYPE:
            printf("type: %s\n", root->val);
            break;
        default:
            printf("unknown\n");
    }

    print_tree(root->lchild, depth + 1);
    print_tree(root->rchild, depth + 1);
    print_tree(root->next, depth);
}

/**
 * @brief 入口：分析整个程序 program → stmt_list
 */
AstNode *program(void)
{
    AstNode *root = new_node(NODE_PROG, "program");
    root->lchild = stmt_list();
    return root;
}

/**
 * @brief 语句序列 stmt_list → stmt stmt_list | ε
 */
AstNode *stmt_list(void)
{
    AstNode *head = NULL, *tail = NULL;
    while (syn == SYN_INT || syn == SYN_FLOAT || syn == SYN_ID
           || syn == SYN_IF || syn == SYN_WHILE || syn == SYN_PRINT
           || syn == SYN_LBRACE)
    {
        AstNode *s = stmt();
        if (head == NULL)
        {
            head = new_node(NODE_STMTLIST, "");
            head->lchild = s;
            tail = head;
        }
        else
        {
            tail->next = new_node(NODE_STMTLIST, "");
            tail->next->lchild = s;
            tail = tail->next;
        }
    }
    return head;
}

/**
 * @brief 语句分发 stmt，根据首记号选择语句种类
 */
AstNode *stmt(void)
{
    if (syn == SYN_INT || syn == SYN_FLOAT)
        return decl_stmt();
    else if (syn == SYN_ID)
        return assign_stmt();
    else if (syn == SYN_IF)
        return if_stmt();
    else if (syn == SYN_WHILE)
        return while_stmt();
    else if (syn == SYN_PRINT)
        return print_stmt();
    else if (syn == SYN_LBRACE)
        return block_stmt();
    else
    {
        printf("【第 %d 行 语法错误】不能作为语句开头：%s\n", line_no, syn_name[syn]);
        error_cnt++;
        panic_recover();
        return NULL;
    }
}

/**
 * @brief 变量声明 decl_stmt → type ID ;
 */
AstNode *decl_stmt(void)
{
    AstNode *n = new_node(NODE_DECL, "");
    n->lchild = type_node();
    char buf[MAX_ID];
    strcpy(buf, token);
    match(SYN_ID);
    n->rchild = new_node(NODE_ID, buf);
    match(SYN_SEMI);
    return n;
}

/**
 * @brief 类型结点 type → int | float
 */
AstNode *type_node(void)
{
    char buf[MAX_ID];
    strcpy(buf, token);
    if (syn == SYN_INT)
        match(SYN_INT);
    else
        match(SYN_FLOAT);
    return new_node(NODE_TYPE, buf);
}

/**
 * @brief 赋值语句 assign_stmt → ID = expr ;
 */
AstNode *assign_stmt(void)
{
    AstNode *n = new_node(NODE_ASSIGN, "");
    char buf[MAX_ID];
    strcpy(buf, token);
    match(SYN_ID);
    n->lchild = new_node(NODE_ID, buf);
    match(SYN_EQ);
    n->rchild = expr();
    match(SYN_SEMI);
    return n;
}

/**
 * @brief if 语句 if_stmt → if ( expr ) stmt
 */
AstNode *if_stmt(void)
{
    AstNode *n = new_node(NODE_IF, "");
    match(SYN_IF);
    match(SYN_LPAREN);
    n->lchild = expr();
    match(SYN_RPAREN);
    n->rchild = stmt();
    return n;
}

/**
 * @brief while 语句 while_stmt → while ( expr ) stmt
 */
AstNode *while_stmt(void)
{
    AstNode *n = new_node(NODE_WHILE, "");
    match(SYN_WHILE);
    match(SYN_LPAREN);
    n->lchild = expr();
    match(SYN_RPAREN);
    n->rchild = stmt();
    return n;
}

/**
 * @brief print 输出语句 print_stmt → print ( expr ) ;
 */
AstNode *print_stmt(void)
{
    AstNode *n = new_node(NODE_PRINT, "");
    match(SYN_PRINT);
    match(SYN_LPAREN);
    n->lchild = expr();
    match(SYN_RPAREN);
    match(SYN_SEMI);
    return n;
}

/**
 * @brief 复合语句块 block_stmt → { stmt_list }
 */
AstNode *block_stmt(void)
{
    AstNode *n = new_node(NODE_BLOCK, "");
    match(SYN_LBRACE);
    n->lchild = stmt_list();
    match(SYN_RBRACE);
    return n;
}

/**
 * @brief 表达式入口 expr → term expr_prime
 */
AstNode *expr(void)
{
    AstNode *left = term();
    return expr_prime(left);
}

/**
 * @brief 处理加减，消除左递归
 */
AstNode *expr_prime(AstNode *left)
{
    if (syn == SYN_PLUS || syn == SYN_MINUS)
    {
        char op[MAX_ID];
        strcpy(op, syn_name[syn]);
        match(syn);
        AstNode *right = term();
        AstNode *bin = new_node(NODE_BINOP, op);
        bin->lchild = left;
        bin->rchild = right;
        return expr_prime(bin);
    }
    return left;
}

/**
 * @brief term → factor term_prime
 */
AstNode *term(void)
{
    AstNode *left = factor();
    return term_prime(left);
}

/**
 * @brief 处理乘除，消除左递归
 */
AstNode *term_prime(AstNode *left)
{
    if (syn == SYN_STAR || syn == SYN_SLASH)
    {
        char op[MAX_ID];
        strcpy(op, syn_name[syn]);
        match(syn);
        AstNode *right = factor();
        AstNode *bin = new_node(NODE_BINOP, op);
        bin->lchild = left;
        bin->rchild = right;
        return term_prime(bin);
    }
    return left;
}

/**
 * @brief factor → ( expr ) | ID | NUM
 */
AstNode *factor(void)
{
    if (syn == SYN_LPAREN)
    {
        match(SYN_LPAREN);
        AstNode *res = expr();
        match(SYN_RPAREN);
        return res;
    }
    else if (syn == SYN_ID)
    {
        char buf[MAX_ID];
        strcpy(buf, token);
        match(SYN_ID);
        return new_node(NODE_ID, buf);
    }
    else if (syn == SYN_NUM)
    {
        char buf[MAX_ID];
        strcpy(buf, token);
        match(SYN_NUM);
        return new_node(NODE_NUM, buf);
    }
    else
    {
        printf("【第 %d 行 语法错误】因子位置错误，需要 ID / NUM / (expr)\n", line_no, syn_name[syn]);
        error_cnt++;
        panic_recover();
        return NULL;
    }
}

/**
 * @brief 主函数：读取输入、初始化、启动分析、输出结果
 */
int main(void)
{
    printf("===== C子集递归下降语法分析器（AST + 错误恢复）=====\n");
    printf("输入源码，以 # 结束输入：\n");

    p_input = 0;
    line_no = 1;
    error_cnt = 0;
    scanf("%[^#]s", input);

    printf("\n【你输入的源代码】\n%s\n", input);

    p_input = 0;
    scaner();
    AstNode *tree_root = program();

    if (error_cnt == 0)
    {
        printf("\n>>> 语法分析成功，无语法错误！\n");
    }
    else
    {
        printf("\n>>> 语法分析结束，一共发现 %d 处语法错误！\n", error_cnt);
    }

    printf("\n===== 抽象语法树 =====\n");
    print_tree(tree_root, 0);

    return 0;
}