Parser.java

import java.util.ArrayList;
import java.util.List;

/**
 * Исключение, возникающее при ошибках синтаксического анализа.
 * Содержит информацию о месте ошибки в исходном коде.
 */
class ParseError extends RuntimeException {
  /**
   * Конструктор ошибки парсинга.
   * @param message описание ошибки
   * @param token токен, на котором произошла ошибка
   */
  public ParseError(String message, Tok token) {
    super(String.format("[Парсер] строка %d, позиция %d: %s",
        token.ln, token.pos, message));
  }
}

/**
 * Синтаксический анализатор (парсер).
 * Реализует метод рекурсивного спуска для построения AST.
 */
public class Parser {
  private final List<Tok> tokens;  // список токенов от сканера
  private int idx = 0;              // текущая позиция в списке токенов

  /**
   * Конструктор парсера.
   * @param tokens список токенов для разбора
   */
  public Parser(List<Tok> tokens) {
    this.tokens = tokens;
  }

  /**
   * Возвращает текущий токен без продвижения по списку.
   * @return текущий токен
   */
  private Tok peek() {
    if (idx >= tokens.size()) {
      // Возвращаем фиктивный токен END, если вышли за границы
      return new Tok(TokType.END, null, 0, 0);
    }
    return tokens.get(idx);
  }

  /**
   * Возвращает текущий токен и продвигается к следующему.
   * @return текущий токен
   */
  private Tok consume() {
    Tok token = peek();
    idx++;
    return token;
  }

  /**
   * Проверяет, соответствует ли текущий токен заданному типу.
   * Если соответствует, продвигается к следующему токену.
   * @param type ожидаемый тип токена
   * @return true, если токен соответствует типу
   */
  private boolean match(TokType type) {
    if (peek().kind == type) {
      idx++;
      return true;
    }
    return false;
  }

  /**
   * Проверяет, что текущий токен имеет заданный тип.
   * Если нет, выбрасывает исключение.
   * @param type ожидаемый тип токена
   * @param errorMsg сообщение об ошибке
   * @return текущий токен
   * @throws ParseError если токен не соответствует типу
   */
  private Tok expect(TokType type, String errorMsg) {
    Tok token = peek();
    if (token.kind != type) {
      throw new ParseError(errorMsg, token);
    }
    idx++;
    return token;
  }

  /**
   * Проверяет, достигнут ли конец списка токенов.
   * @return true, если достигнут конец
   */
  private boolean isAtEnd() {
    return peek().kind == TokType.END;
  }

  /**
   * Разбор программы согласно грамматике:
   * <программа> ::= <объявления_функций> <вызов_функции> ";"
   * @return узел программы
   * @throws ParseError при нарушении синтаксиса
   */
  public ProgNode pProgram() {
    // Разбираем объявления функций
    List<FuncDeclNode> funcs = pFuncDecls();

    // Проверяем, что есть хотя бы один токен после объявлений
    if (isAtEnd()) {
      throw new ParseError("ожидается вызов функции после объявлений", peek());
    }

    // Разбираем главный вызов функции
    CallNode call = pCall();

    // Проверяем точку с запятой после вызова (если не конец)
    if (!isAtEnd()) {
      expect(TokType.SEMI, "ожидается ';' после вызова функции");
    }

    // Проверяем, что после точки с запятой нет лишних токенов
    if (!isAtEnd() && peek().kind != TokType.END) {
      throw new ParseError("неожиданные токены после завершения программы", peek());
    }

    return new ProgNode(funcs, call);
  }

  /**
   * Разбор списка объявлений функций:
   * <объявления_функций> ::= <объявление_функции>+
   * @return список узлов объявлений функций
   */
  private List<FuncDeclNode> pFuncDecls() {
    List<FuncDeclNode> funcs = new ArrayList<>();

    // Собираем все объявления функций, пока видим 'void' или 'int'
    while (!isAtEnd() && (peek().kind == TokType.VOID || peek().kind == TokType.INT)) {
      funcs.add(pFuncDecl());
    }

    return funcs; // Может быть пустым в некоторых тестах
  }

  /**
   * Разбор объявления функции:
   * <объявление_функции> ::= <тип_возврата> ИМЯ "(" <список_параметров> ")" "{" <тело> "}"
   * @return узел объявления функции
   */
  private FuncDeclNode pFuncDecl() {
    // Тип возвращаемого значения
    String retType = pRetType();

    // Имя функции
    Tok nameTok = expect(TokType.IDENT, "ожидается имя функции");

    // Открывающая скобка параметров
    expect(TokType.LPAR, "ожидается '(' после имени функции");

    // Список параметров
    List<Param> params = pParams();

    // Закрывающая скобка параметров
    expect(TokType.RPAR, "ожидается ')' после списка параметров");

    // Открывающая фигурная скобка тела
    expect(TokType.LBRACE, "ожидается '{' перед телом функции");

    // Тело функции
    List<ASTNode> body = pBody();

    // Закрывающая фигурная скобка тела
    expect(TokType.RBRACE, "ожидается '}' после тела функции");

    return new FuncDeclNode(retType, (String) nameTok.val, params, body);
  }

  /**
   * Разбор типа возвращаемого значения:
   * <тип_возврата> ::= "void" | "int"
   * @return строковое представление типа
   */
  private String pRetType() {
    if (match(TokType.VOID)) return "void";
    if (match(TokType.INT)) return "int";
    throw new ParseError("ожидается 'void' или 'int'", peek());
  }

  /**
   * Разбор списка параметров:
   * <список_параметров> ::= <параметр> ("," <параметр>)* | ε
   * @return список параметров
   */
  private List<Param> pParams() {
    List<Param> params = new ArrayList<>();

    // Если следующий токен не 'int', значит параметров нет
    if (peek().kind != TokType.INT) {
      return params;
    }

    // Первый параметр
    params.add(pParam());

    // Дополнительные параметры, разделенные запятыми
    while (match(TokType.COMMA)) {
      // После запятой должен быть параметр
      if (peek().kind != TokType.INT) {
        throw new ParseError("ожидается параметр после ','", peek());
      }
      params.add(pParam());
    }
    return params;
  }

  /**
   * Разбор параметра:
   * <параметр> ::= "int" ИМЯ
   * @return объект параметра
   */
  private Param pParam() {
    // Уже проверили, что текущий токен INT
    consume(); // Потребляем 'int'
    Tok nameTok = expect(TokType.IDENT, "ожидается имя параметра");
    return new Param("int", (String) nameTok.val);
  }

  /**
   * Разбор тела функции:
   * <тело> ::= <инструкция>*
   * @return список инструкций
   */
  private List<ASTNode> pBody() {
    List<ASTNode> stmts = new ArrayList<>();

    // Собираем инструкции, пока не встретим '}'
    while (!isAtEnd() && peek().kind != TokType.RBRACE) {
      stmts.add(pStmt());
    }

    return stmts;
  }

  /**
   * Разбор инструкции:
   * <инструкция> ::= <возврат> | <вызов_функции> ";" | "int" ИМЯ ";"
   * @return узел инструкции
   */
  private ASTNode pStmt() {
    if (peek().kind == TokType.RETURN) {
      // Инструкция return
      return pReturn();
    } else if (peek().kind == TokType.INT) {
      // Объявление переменной
      return pVarDecl();
    } else if (peek().kind == TokType.IDENT) {
      // Вызов функции
      ASTNode call = pCall();
      // Проверяем точку с запятой, если не конец тела
      if (peek().kind != TokType.RBRACE && peek().kind != TokType.END) {
        expect(TokType.SEMI, "ожидается ';' после вызова функции");
      }
      return call;
    } else {
      throw new ParseError("ожидается инструкция (return, int, или вызов функции)", peek());
    }
  }

  /**
   * Разбор инструкции return:
   * <возврат> ::= "return" <выражение>? ";"
   * @return узел return
   */
  private ReturnNode pReturn() {
    expect(TokType.RETURN, "ожидается 'return'");

    ASTNode expr = null;
    // Если следующий токен не ';', значит есть возвращаемое выражение
    if (peek().kind != TokType.SEMI) {
      expr = pExpr();
    }

    expect(TokType.SEMI, "ожидается ';' после return");
    return new ReturnNode(expr);
  }

  /**
   * Разбор объявления переменной:
   * <объявление_переменной> ::= "int" ИМЯ ";"
   * @return узел объявления переменной
   */
  private VarDeclNode pVarDecl() {
    consume(); // Потребляем 'int'
    Tok nameTok = expect(TokType.IDENT, "ожидается имя переменной");
    expect(TokType.SEMI, "ожидается ';' после объявления переменной");
    return new VarDeclNode((String) nameTok.val);
  }

  /**
   * Разбор вызова функции:
   * <вызов_функции> ::= ИМЯ "(" <список_аргументов> ")"
   * @return узел вызова функции
   */
  private CallNode pCall() {
    Tok nameTok = expect(TokType.IDENT, "ожидается имя функции");
    expect(TokType.LPAR, "ожидается '(' после имени функции");

    List<ASTNode> args = pArgs();
    expect(TokType.RPAR, "ожидается ')' после списка аргументов");

    return new CallNode((String) nameTok.val, args);
  }

  /**
   * Разбор списка аргументов:
   * <список_аргументов> ::= <выражение> ("," <выражение>)* | ε
   * @return список аргументов
   */
  private List<ASTNode> pArgs() {
    List<ASTNode> args = new ArrayList<>();

    // Если сразу ')', значит аргументов нет
    if (peek().kind == TokType.RPAR) {
      return args;
    }

    // Первый аргумент
    args.add(pExpr());

    // Дополнительные аргументы, разделенные запятыми
    while (match(TokType.COMMA)) {
      args.add(pExpr());
    }
    return args;
  }

  /**
   * Разбор выражения:
   * <выражение> ::= <слагаемое> (("+" | "-") <слагаемое>)*
   * @return узел выражения
   */
  private ASTNode pExpr() {
    // Первое слагаемое
    ASTNode left = pTerm();

    // Дополнительные слагаемые с операторами + или -
    while (peek().kind == TokType.PLUS || peek().kind == TokType.MINUS) {
      char op = (peek().kind == TokType.PLUS) ? '+' : '-';
      consume();
      ASTNode right = pTerm();
      // Создаем бинарный узел для операции
      left = new BinNode(op, left, right);
    }

    return left;
  }

  /**
   * Разбор слагаемого:
   * <слагаемое> ::= ЧИСЛО | ИМЯ | <вызов_функции>
   * @return узел слагаемого
   */
  private ASTNode pTerm() {
    Tok token = peek();

    if (token.kind == TokType.NUMBER) {
      // Числовая константа
      consume();
      return new NumNode((Integer) token.val);
    } else if (token.kind == TokType.IDENT) {
      // Проверяем, является ли идентификатор вызовом функции
      if (idx + 1 < tokens.size() && tokens.get(idx + 1).kind == TokType.LPAR) {
        // Если после идентификатора идет '(', это вызов функции
        return pCall();
      } else {
        // Иначе это переменная
        consume();
        return new VarNode((String) token.val);
      }
    } else {
      throw new ParseError("ожидается число, переменная или вызов функции", token);
    }
  }
}