MVP Блог. Заметки из книги дракона по лексерам и парсерам.

# Заметки из книги дракона по лексерам и парсерам.
Tags: компиляторы, грамматики

**Внимание! Это не статья, а мои заметки чтобы разобраться в теме статического анализа и грамматик. Я не уверен что сам смогу понять суть написанного через некоторое время, а вам даже пробовать не советую.**

#### Вопросы без ответа
- ПАРСЕР-КОМБИНАТОРЫ??? scaner-less
- ЧЕМ СЕЙЧАС ПАРСИТСЯ СИ, ПЛЮСЫ, ПИТОН, JAVA и прочие??? gcc, python-grammar, llvm, postgresSQL/MySQL
- Чем парсить bash? Чем пользуется shellcheck?
- Как разрабатывать грамматики, когда невозможно выделить в лексере ключевые слова. (Вроде как можно управлять лексером из синтаксического анализатора).

#### Ссылки изучить
- https://pygments.org/docs/lexers/?highlight=bash
- https://news.ycombinator.com/item?id=14550301
- http://www.aosabook.org/en/bash.html
- https://www.oilshell.org/blog/2019/02/07.html
- https://github.com/nil0x42/shnake/blob/master/shnake/lexer.py
- https://stackoverflow.com/questions/5491775/how-to-write-a-shell-lexer-by-hand
- abstract glr parsing
- abstract parsing (Doh)
- https://www.springer.com/gp/book/9783642032363 книга с новыми пейперами

#### TODO
- Добавить инфу про РБНФ https://ru.wikipedia.org/wiki/Расширенная_форма_Бэкуса_—_Наура

#### Типы синтаксичесих анализаторов
3 основных типа синтаксических анализаторов: универсальный, нисходящий и восходящий.

Универсальные методы - слишком неэффективные методы парсинга, но могут распарсить любую грамматику. Примеры алгоритмов:
- алгоритм Кока-Янгера-Касами
- алгоритм Эрли

Если представить дерево разбора - граф, где листьями являются конечные терминалы, а узлами - нетерминалы грамматики, то "нисходящие анализаторы" - это те, которые разбирая входящий поток строят его "сверху вниз" (от корня грамматики), а "нисходящие анализаторы" - снизу вверх (от конечных правил грамматики).\\

Примеры нисходящий анализаторов:
- рекурсивный анализ
- предиктивный синтаксический анализ
- LL(0), LL(1), LL(k)

Примеры восходящих анализаторов:
- LR(0), LR(1), LR(k)
- SLR
- LALR(1)

#### Определения

- Нейминг нетерминалов:
  - stmt (statement) - инструкция
  - expr (expression) - выражение
  - stmt -> if ( expr ) stmt else stmt

- Леворекурсивная грамматика - это грамматика, где есть продукции A => Aa (или A входит в FIRST(A))
- FIRST(), FOLLOW() - TODO
- Неоднозначная грамматика -
- Левая факторизация -
- Устранение левой рекурсии -

#### Восходящий синтаксический анализ

Восходящий синтаксический анализ связан с классом "правых порождений" - когда на каждом шаге переписывается крайний справа нетерминал.

Язык, который может быть сгенерирован грамматикой, называется контекстно-свободным языком.

В левых порождениях в каждом предложении выбирается крайний слева нетерминал, в правых - наоборот.

#### Лексический анализ

Четких правил что должно относится к лексическому, а что к синтаксическому анализу, нет. Регулярные языки болше подходят для определения идентификаторов, констант, ключевых слов и пробельных символов. Грамматики более приспособлены для описания вложенных структур, таких как сбалансированные скорбки, пары begin end, if then else итд. Эти вложенные структуры не могут быть описаны регулярными выражениями.

Неоднозначности грамматики должен исправлять разработчик грамматики, в то время как факторизация, устранение левой рекурсии - можно делать алгоритмами автоматически.

Алгоритмы нисходящего разбора могут потребовать операции отката, когда один из вариантов продукции не подошел и потребовался другой. Один из алгоритмов - рекурсивный спуск. Предисктивный синтаксический анализ - это частный случай анализа методом рекурсивного спуска, но не требующий отката. Предиктивный анализ выбирает нужную продукцию путем просмотра X входных символов вперед. Класс грамматик, для которых можно построить предиктивный синтаксический анализатор, которому нужно подсмотреть K символов называют классом LL(k). Его распространенная версия LL(1) - когда нужно посмотреть только 1 доп.символ входной строки.

Предиктивные синтаксические анализаторы могут быть построены для LL(1).
LL(1) - первая L это сканирование входного потока слева направо, вторая L это получение левого порождения, а 1 - использование на каждом шаге предпросмотра на 1 символ.

В LL(1) не может быть ни левой рекурсии ни неоднозначности.

Грамматика A -> a|b не принадлежит LL(1) если нарушается правило: Если из b выводится э, то a не порождает ни одну строку, начинающуюся с терминала из FOLLOW(A). Аналогично для a. (чтобы не было неоднозначности "выбрать эту ветку нетерминала A или закончить нетерминал A").

Популярный алгоритм для LR грамматик - это перенос/свертка. Когда входящий поток w "сворачивается" в обратном направлении от листьев к корню грамматики E. Для этого в грамматике находятся "основы", которые совпадут с частью вх.потока и их можно будет свернуть в нетерминал. A -> ab - здесь ab - это основа.

К LR не относятся грамматики с конфликтом "перенос/свертка" (когда непонятно делать перенос или свертку) и "свертка/свертка" (когда есть два подходящих основания и непонятно какой выбрать).

LR(k) - первая L это сканирование входного потока слева направо, R это построение правого порождения в обратном порядке.

Есть разные варианты построения анализаторов, например простой (simple) LR - SLR. Более распространены: канонический LR и LALR.

Плюсы LR перед LL:
- LR можно построить практически для всех КСГ, а неподходящие КСГ в типичных случаях (для типичных конструкция в языках программирования) - можно исправить
- LR - это один из самых эффективных методов анализа без возврата
- LR может обнаруживать синтаксические ошибки как только это становится возможным
- класс LR грамматик - это надмножество грамматик, которые можно проанализировать предиктивным или LL методами
- объяснение: если для LL(k) мы должны выбрать продукцию по k входным символам, то в LR(k) мы это делаем по k входным символам плюс по правосентенциальной форме продукции (части которая уже свернута и лежит в "стеке" анализатора)
Главный минус - сложность построения LR-анализатора, но тут можно использовать автоматические анализаторы, например Yacc (генератор LALR-анализаторов).

Канонический LR - добавляет в таблицы терминал, который должен слудовать за продукцией FOLLOW(A), чтобы можно было ее применить. Количество терминалов для канонического LR(1) - равно одному и т.п. Но это приводит к разростанию состояний таблицы (например до нескольких тысяч в С, где при использовании LALR всего несколько сотен состояний).
LALR (lookahead LR) - склеивает состояния с одинаковыми ядрами, но разными терминалами. Из-за этого количество состояний в таблице сравнимо с SLR.

Неоднозначные грамматики не могут быть LR-грамматикой. Но с помощью правил ассоциативности и приоритетов (операторов) можно настроить генератор LR грамматики, чтобы он устранил неоднозначности. Например:
- с помощью указания приоритета, что * выше чем +, мы можем устранить неоднозначность грамматики: E -> E + E | E * E | ( E ) | id. При разборе id + id * id возникнет такая ситуация: в стеке будет E + E, а в входе * id - это конфликт переноса/свертки, мы можем свернуть E -> E + E или сделать перенос и свернуть E -> E * E. Нл если мы укажем, что приоритет * выше, то анализатор поймет в какой ситуации как поступать
- с помощью указания ассоциативности, например что + левоассоциативен, при разборе id + id + id, когда на стеке 'id + id', а на входе '+ id' - анализатор не знает делать перенос или свертку. Но зная, что + левоассоциативен может понять, что сначала нужно делать свертку.

Неоднозначных грамматик можно избежать, исправив неоднозначность. Но это добавит новые правила в грамматику, она станет менее лаконичной и увеличится кол-во состояний LR таблицы. С другой стороны, при использовании неоднозначности - нужно быть очень аккуратным, чтобы она работала корректно.

В Yacc правила по-умолчанию для разрешения неоднозначности: конфликт свертка/свертка разрешается в пользу конструкции, которая находится в спецификации раньше; конфликт перенос/свертка решается в пользу переноса (авто-фикс висящего else).

#### Лексический анализ.

- Превращает Лексемы в Токены.
- Токен состоит из имени токена и значения атрибута (например, <number; ссылка на число>).
- Для простоты термин токен можно считать терминалом в синтаксическом анализаторе.

![Схема лексического анализатора](https://github.com/kolko/kolko.github.io/raw/master/data/static/2020-05-06_static_analysis/lexer_schema.jpg =550x733 "Схема лексического анализатора")

Лексический анализ редко бывает контекстно-независимым, часто в лексичейский анализатор передаются параметры состояния статического анализатора. Например, в с++ при использовании шаблонов раньше нужно было между >> ставить пробел, т.к. лексер был контекстно-независимый и парсил это как сдвиг: A<B<X> >  (контекстно-зависимая лексика).

А еще есть подход scaner-less. (TODO?) Парсер-комбинаторы.

#### Синтаксический анализ.

BNF (Backus-Naur Form) - контекстно-свободная грамматика.
Состоит из 4 компонентов:
1. Множество терминальных символов или токенов.
2. Множество нетерминалов.
3. Множество продукций (stmt -> if ( expr ) stmt else stmt )
4. Стартовый нетерминал (с которого начинается разбор).

Дерево разбора КСГ обладает свойствами:
1. Корень дерева помечен стартовым символом
2. Каждый лист помечен терминалом или e
3. Каждый внутренний узел - нетерминал

Левоассоциативные операторы ( +-/* )
```
list -> list + digit | digit
digit -> 1 | 2 | … | 9
```

Правоассоциативные ( = )
```
right -> letter = right | letter
letter -> a | b | … | z
```

#### Синтаксически управляемая трансляция

Синтаксически управляемая трансляция - это когда к продукциям грамматики мы присоединяем код, который принимает аттрибуты (символы или результаты кода продукций нетерминалов) и возвращающая новый стнтезированный аттрибут (как в ply). Порядок выполнения кода управляется грамматикой. Например, так можно сделать транслятор инфиксной записи в постфиксную, транслятор кода в синтаксическое дерево или для вычисления выражения.

#### Предиктивный синтаксический анализатор

Предиктивный синтаксический анализатор - анализатор, который использует нисходящий подход (от корня к листьям), он читает по одному символу и для каждого символа имеет одну процедуру, ее обрабатывающую. Соответственно, для каждого нетерминала(имеется в виду, что на каждом шаге анализа) грамматика должна соответствовать условию, что множества FIRST(a) FIRST(b) FIRST(..), где a b - все возможные варианты нетерминала, а FIRST - множетсво их первых символов - не пересекаются. Проще говоря, не должно быть случаев когда новый символ можно трактовать по-разному. (что-то типа ДКА, наверное)

#### Левая рекурсия
Левую рекурсию пораждает подобные продукции:
expr -> expr + term
(точнее, expr входит в FIRST(expr), т.к. могут быть не столь очевидные продукции)
Это вызывает проблемы в анализаторах, работающих методом рекурсивного спуска - они зациклятся.

Левую рекурсию можно устранить, например:
A -> Aa | b
переделать в
A -> bR
R -> aR | e

Предиктивный анализатор не может обработать леворекурсивную грамматику.

#### ?

Запись токена в таблицу символов (имя переменной) обычно делает синтаксический анализатор, лексический только возвращает лексему с токеном. Это происходит потому, что при работе с таблицей символов нужно учитывать блочную структуру языка (например, локальные перемееные в функции, которые переопределяют глобальную переменную модуля) - а ее понимает только синтаксический анализатор.

Основными используемыми промежуточными представлениями являются дерево разбора (например аст) и трехадресный код. Причем часто строится и то и другое: трехадресный код удобен для оптимизации, а дерево для проверки семантики.

Конкретный и абстрактный синтаксис.
Чтобы реализовать приоритеты операторов (например, сложения и умножения), в синтаксисе заводятся разные нетерминалы (term и factor), но часто в трехадресном коде или АСТ уже не нужно их различать и это будет переусложнением. Поэтому можно в правилах трансляции этих (конкретных) нетерминалов порождать абстрактные элементы. Например, сложение, вычитание, умножение и деление в языке java переводятся в узел Op(‘/‘, term1, factor2).

Вот таблица трансляции некоторых операций java (в порядке приоритета):
assign =
cond ||
cond &&
rel == !=
rel < <= >= >
op + -
op * / %
not !
minus -(unary)
access [ ]

#### Статические проверки
Некоторые проверки сложно или невозможно закодировать в грамматике и их выполняют отдельно. Например что операция break находится в конструкции switch или цикле, что декларация идентификатора в блоке выполнена только один раз, проверка типов и т. д.

Ода из проверок: проверка на L- и R-значения (r-value, l-value). L-значение располагается в левой стороне присваивания и должна быть ячейкой памяти (переменная, массив с индексом), а r-значние должен непосредственно иметь значние, которое можно присвоить.

#### Восходящий синтаксический анализ

Восходящий лексический анализ. LR(k) (L - слева направо, k - колическтво читаемых символов), обычно юзается если k=1, иначе большие накладные расходы.

LALR(1) могут анализировать Yacc и Bison и только их.

#### Синтаксически управляемая трансляция, синтаксически управляемое определение

Синтаксически управляемая трансляция - это трансляция, управляемая контекстно-свободной грамматикой. (грубо говоря, когда к каждому правилу КСГ мы прикручиваем код, например строим АСТ, генерируем промежуточный код или интерпретируем его).

Синтаксически управляемое определение - это КСГ с атрибутами и правилами. Атрибуты - это когда мы во время разбора добавляем инфу к нетерминалам (например тип). Правила - это код, выполняемый в продукциях.

Атрибуты бывают синтезированные и наследуемые.

СУО только с синтезируемыми атрибутами называют S-атрибутными определениями, такое СУО может быть удобно реализовано совместно с LR-анализатором, как например в Yacc.

СУО называется L-атрибутной, когда оно использует наследуемые атрибуты, но для вычисления наследуемого атрибута используются только синтезируемые атрибуты сестер, располагающиеся слева от вычисляемого нетерминала и наследуемые атрибуты родителя. Например: A -> B C, здесь B.i может зависеть только от A.s и не может от C.s(т.к. C еще не вычислен, расположен справа). Напротив, для вычисления C.i могут использоваться A.s и B.s. inh имеет смысл назначать еще не вычисленным нетерминалам (чтобы они при разборе им воспользовались), synt предназначены для возврата.

СУО без побочных эффектов называют атрибутной грамматикой. В них правила определяют значения атрибутов через значения других атрибутов и не делают ничего другого.

L-атрибутное СУО можно реализовать только в LL-анализаторе (точнее, в нисходящем анализаторе), т.е. работает только при нисходящем обходе. Использование наследуемых атрибутов в LR-анализаторе (хаками) в конце концов приведет к стратегии «составь все дерево разбора целиком и потом обойди его», т.е. универсальным алгоритмом.

Не все схемы управляемой трансляции можно реализовать во время LL или LR анализа. Чтобы была возможность реализовать все, то нужно сначала построить дерево разбора игнорируя действия, потом действия «навесить» на это дерево и выполнить обход дерева в прямом порядке.

#### Понятное объяснение когда язык перестает быть регулярным и когда перестает быть контекстно-свободным. [Оригинальная статья на хабре](https://habr.com/ru/post/491538/)

![Картинка из статьи 1](https://github.com/kolko/kolko.github.io/raw/master/data/static/2020-05-06_static_analysis/habr_1.jpg =550x257)

Осталось добавить, что грамматика называется контекстно-свободной (КС-грамматикой), если все левые части правил вывода — единичные нетерминалы.

![Картинка из статьи 2](https://github.com/kolko/kolko.github.io/raw/master/data/static/2020-05-06_static_analysis/habr_2.jpg =550x392)

В статье еще есть хороший пример грамматики общего вида. «У получившегося алгоритма есть интересная особенность: правила со сложной левой частью позволяют как бы «перемещать» группы символов; в данном случае нетерминалы перемещаются в правую часть строки. Похожий паттерн часто встречается в алгоритмах для машин Тьюринга.»

![Картинка из статьи 3](https://github.com/kolko/kolko.github.io/raw/master/data/static/2020-05-06_static_analysis/habr_3.jpg =550x472)

Другие "хинты" на этот счет, для определения типа грамматики:
- Регулярные языки: конечный автомат не умеет считать.
- КСГ: грамматика может считать только две вещи, но не три.
- Требование объявления переменных перед использованием не может быть проверено КСГ.
- Что нельзя в КСГ: переменная объявлена до ее использования, wcw где w - это рандомная строка, проверить что количество параметров в объявлении функции равно переданным. Такое в языках часто делается на этапе семантического анализа.

#### Примеры разбора нерегулярного языка с помощью регулярных выражений

В книге [Регулярные выражения](https://www.goodreads.com/book/show/583628.Mastering_Regular_Expressions) Джеффри Фридла было два решения для разбора нерегулярной грамматики на примере задачи парных скобок.

1. Вызов программного кода во время выполнения НКА регулярного выражения, на примере мощных регулярок Perl. После нахождения скобки, вызывается код:

```
my $NestedGuts = qr{
    (?{ local $OpenParents = 0 }) # инициализируем переменную, (?{ }) - конструкция вызова кода
    (?> # атомарная группировка (я уже и не помню что это, обидно)
        (?:
            [^()]+
            |
            $ (?{ $OpenParents++ }) # Увеличиваем счеткик на открывающейся скобке
            |
            $ (?(?{ $OpenParents != 0 }) (?{ $OpenParents-- }) | (?!) ) # Если счетчик равен нулю, то (?!) сгенерирует ошибку
        )*
    )
    (?(?{ $OpenParents != 0 }) (?!) ) # Если остались незакрытые скобки - генерируем ошибку
}x;
```

2. Динамические регулярные выражения (я где-то слышал название "Рекурсивные регулярные выражения"). Это возможность сохранить регулярное выражение в переменную и ссылаться на нее из самого регулярного выражения. Пример на Perl:

```
my $LevelN;
$LevelN = qr/ $ ( [^()] | (??{ $LevelN }) )* $ /x;

# Оптимизированная версия:
$LevelN = qr/ (?> [^()]+ | $ (??{ $LevelN }) $ )* /x;
```

Пример на Python и библиотеки https://pypi.org/project/regex/:

```
>>> regex.match(r'$((?:(?R)+|[^()]+)*)$', '(qwe(qw(q)(q)))').groups()
('qwe(qw(q)(q))',)

# Не получилось вывести вложенные группы и не получилось добавить якоря начала и конца строки. Но он ловит только парные скобки
```

#### Интересные лекции и статьи по теме

### Формальные грамматики и вычислительная сложность синтаксического анализа | Александр Охотин [Лекция 1](https://www.youtube.com/watch?v=_YuqR2Ov1II) [Лекция 2](https://www.youtube.com/watch?v=g5wye4l8tIY)
хороший лектор, интересный взгляд на грамматики с теоретической стороны.

Вероятностные грамматики, грамматики обертывания пар/надстройки деревьев, булевы грамматики.

Лектор рассказывает, что 1 и 2 типы по Хомскому - не используются. Все интересные и изучаемые грамматики находятся в 3 типе (= КСГ??). Так КСГ грамматики имеют ограничения, то ученые разрабатывают новые грамматики с новыми свойствами, которые обходят эти ограничения (туду добавить список). Самое важное при разработке новой грамматики - проверить ее вычислительную сложность, т.к. если для нее невозможно будет построить нормальный алгоритм разбора - грамматика неприменима даже теоритически, и летит в корзину.

Кубическое время для разбора грамматики - может подойти для задачи разбора естественного языка, но непременимо для ЯП. Для ЯП нужно линейное время.

"Определение через перезапись строк" - олдскул, и ни для чего не годится. В современном мире не используется. КЗГ по Хомскому - фигня.

*Иерархия грамматик:*
```
                                                  UnambTAG ------> TAG ------> Multi
                                                   ↗                ↗
                                                  ╱                ╱
                                                 ╱                ╱
                   LL ------> LR ------------> Unamb ------> ★ Ordinary ---
                 ↗            ↗ ↖              ↗   ╲          ↗            ↘         ?
                ╱            ╱   ╲            ╱     -------- ╱ ---          Conj  ------> Bool
               ╱            ╱    ╱           ╱              ╱      ╲        ↗              ↗
Reg ------> LLLin ------> LRLin ------> UnambLin ------> Lin        ↘     ?╱     ?       ?╱
 ╲                             ╱                            ╲       UnambConj ------> UnambBool
  ---------------             ╱                              ╲        ↗
                  ↘          ╱                                ↘      ╱
                   Bracketed -------------------------------> LinConj
```

Стрелочка - вхождение.
Звездочка (Ordinary) - обычновенная грамматика. (идеал)
Lin - линейные грамматики. Грамматики с правилами, где можно ссылаться только на 1 нетерминальный символ. В итоге дерево разбора будет "столбом".
Bracketed - скобочные языки. Типа html, где явно заданы структуры скобок.
Unamb - однозначные грамматики.
TAG (tree ... grammars) - грамматики надстройки деревьев (или обертывания пар).
Multi - многокомпонентные грамматики.
Conj - коньюктивные грамматики.
Bool - булевы грамматики.

Изображены грамматики, которые можно сравнивать. Например, вероятностных грамматик тут нет.

---

Пример грамматики, которую LL разобрать не может, а LR может.

{a^n c b^n} U {a^n d b^2n}

S -> C | D
C -> aCb | c
D -> aDbb | d

Строка aacbb распознается так:

(e, aacbb) -> (a, acbb) -> (aa, cbb) -> (aac, bb) -> (aaC, bb) -> (aaCb, b) -> (aC, b) -> (aCb, e) -> (C, e) -> (S, e)

Другими словами, чтобы разобрать грамматику LL требуется заранее принять решение, выбрать C или D, а LR откладывает это решение до момента, когда это станет ясно.  (??? но вроде как при алгоритме с возвратом или другими хаками реально это сделать и для LL, надо узнать. Нереально только с наивным рекурсивным алгоритмом LL)

----

### [Синтаксический анализ для встроенных языков | Андрей Бреслав](https://www.youtube.com/watch?v=PARloe1mPkc):
[Слайды](https://github.com/kolko/kolko.github.io/raw/master/data/static/2020-05-06_static_analysis/20110227csseminaralvorbreslav.pdf)

*Алгоритм рабоыт анализатора*
Задача: найти в программе на ЯП все вхождения DSL (в примере это SQL-строки в JAVA, может быть хоть XML, хоть форматные строки printf, итд) и проверить что эти строки корректны с точки зрения синтаксиса этого DSL.
(В принципе, можно расширить метод и анализировать на безопасность, например что нельзя изменить семантику DSL с помощью спец.ввода (инъекции))

Алгоритм:
1. находим все функции, которые принимают DSL, например sql.execute()
2. проводим синтаксический анализ переменной с DSL
3. условия, циклы, конкатенации и прочие *регулярные* действия мы преобразуем в регулярное выражение. Нерегулярные вещи (рекурсия например) мы исключаем. Другими словами, мы граф потока данных описываем неким регулярным выражением.
4. тут мы могли проверить вхождение одного регулярного выражения в другое, но регулярная (не полная) грамматика для SQL слишком огромна
5. с помощью абстрактного синтаксического парсера проверяем что регулярное выражение описывается КСГ

Более мощный способ анализа потоков данных описан в лекции [2019 LLVM Developers’ Meeting: A. Dergachev “Developing the Clang Static Analyzer”](https://www.youtube.com/watch?v=g0Mqx1niUi0)

Примеры регулярных выражений:
```
Код:
sql = "SELECT * FROM People WHERE ";
if (filterByAge)
    sql += "age > 18)"; #<< тут ошибка
else
    sql += "id IS NOT NULL";
sql += "ORDER BY name ASC";

execSQL(sql);

Выражение:
Abstract string: "SELECT * FROM People WHERE " ("age > 18)"|"id IS NOT NULL")"ORDER BY name ASC"
```

*Abstract Parsing* Doh, 2009 https://dl.acm.org/doi/10.1007/978-3-642-03237-0_18
Два регулярных языка мы можем сравнить, но если упростить КСГ SQL до регулярной грамматики - она будет очень большая.
В этом случае можно воспользоваться абстрактным парсером. В этом случае мы берем LR-парсер и подаем ему на вход не строку, а символы с ДКА регулярного выражения, а в местах ветвления - строим разные стеки. В итоге мы (не всегда) можем проверить что все порождения ДКА описываются КСГ SQL.

Хинты:
1. "общая точка, конечная точка, TODO вспомнить правильное название" - когда мы генерируем одинаковые стеки в цикле, мы останавливаем цикл, т.к. мы всегда будем порождать корректный поток.
2. ограничиваем глубину стека. Когда в стек нужно положить больше лимита, мы вместо последнего элемента кладем спец.символ, если мы его потом считаем - значит что мы не можем провести разбор. В реальной жизни мы часто завершаем анализ до того как дойдем до этого значения

### PEG-грамматика:

https://ru.wikipedia.org/wiki/Грамматика,_разбирающая_выражение

https://www.python.org/dev/peps/pep-0617/

https://habr.com/ru/post/471860/

<li><a href="https://habr.com/ru/post/471860/">PEG парсеры</a></li>
<li><a href="https://habr.com/ru/post/471862/">Реализация PEG парсера</a></li>
<li><a href="https://habr.com/ru/post/471864/">Генерация PEG парсера</a></li>
<li><a href="https://habr.com/ru/post/471866/">Визуализация работы PEG парсера</a></li>
<li><a href="https://habr.com/ru/post/471986/">Леворекурсивные PEG грамматики</a></li>
<li><a href="https://habr.com/ru/post/471988/">Добавление экшенов в грамматику PEG</a></li>
<li><a href="https://habr.com/ru/post/471990/">Мета-грамматика для PEG парсера</a></li>
<li><a href="https://habr.com/ru/post/471992/">Реализация остальных возможностей PEG</a></li>
<li><a href="https://habr.com/ru/post/471994/">PEG на Core Developer Sprint</a></li>

Классические парсеры используют отдельный токенизатор, который разбивает ввод (текстовый файл или строку) на серию токенов, таких как ключевые слова, идентификаторы (имена), числа и операторы. Парсеры PEG (как и другие современные парсеры, такие как ANTLR) часто объединяют токенизацию и парсинг

Враппер кэширует результат вызова метода для каждой входной позиции — вот почему он называется packrat-парсер! [прим. пер. packrat — "воришка", однако в рускоязычных источниках этот термин не переводится] Кэш — это словарь словарей, который хранится в экземпляре Parser. Ключ внешнего словаря — позиция в потоке входных данных; я добавил также self.memos = {} в Parser .__ init__() для его инициализации. Внутренние словари добавляются по мере необходимости; их ключи состоят из метода и его аргументов. (В текущем дизайне нет аргументов, но мы могли бы мемоизировать функцию expect(), у которой он есть, весьма тривиально)

PEG-парсер на Python: TatSu
TatSu is a tool that takes grammars in a variation of EBNF as input, and outputs memoizing (Packrat) PEG parsers in Python.
TatSu supports left-recursive rules in PEG grammars using the algorithm by Laurent and Mens. The generated AST has the expected left associativity.