Как создать парсер AST допускающий синтаксические ошибки?

Question

[Антон Медведев]

Для начала как вооще строятся AST (абстрактное синтаксическое дерево) деревья? Что почитать?

Как создать парсер для языка, например SQL, который генерирует AST дерево и прощает синтаксические ошибки?

Пример: "3+4*5":

+
 / \
3   *
   / \
  4   5

Но если пользователь допустил ошибку "3+4*+", парсер пытается все равно понять что имел ввиду пользователь:

+
 / \
3   *
   / \
  4   +
     / \
    ?   ?

С чего начать? Спасибо!

SQL:

---SELECT_________________
   /           \           \
  .           FROM        JOIN
 / \           |         /    \
a city_name  people   address  ON
                                |
                                =______________
                               /               \
                              .____             .
                             /     \           / \
                            p  address_id     a  id

Answer 1

[jcmvbkbc]

Для начала как вооще строятся AST (абстрактное синтаксическое дерево) деревья? Что почитать?

Книгу дракона.

Как создать парсер для языка, например SQL, который генерирует AST дерево и прощает синтаксические ошибки?

Предусмотреть в грамматике правила описывающие синтаксические ошибки и восстановление после них. В bison, например, для этого есть токен "error".