Праволинейные грамматики и регулярные языки

Леволинейные и праволинейные грамматики. Автоматные грамматики

К регулярным относятся два типа грамматик: леволинейные и праволинейные.

Леволинейные грамматики G(VT,VN,P,S), V = VNVT могут иметь правила двух видов: АВγ или Аγ, где A,BVN, γVT*.

В свою очередь, праволинейные грамматики G(VT,VN,P,S), V= VNVT могут иметь правила также двух видов: АγВ или Аγ, где А,ВVN, γVT*.

Доказано, что эти два класса грамматик эквивалентны. Для любого регулярного языка, заданного праволинейной грамматикой, может быть построена леволинейная грамматика, определяющая эквивалентный язык; и наоборот – для лю­бого регулярного языка, заданного леволинейной грамматикой, может быть по­строена праволинейная грамматика, задающая эквивалентный язык.

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

Среди всех регулярных грамматик можно выделить отдельный класс – автомат­ные грамматики. Они также могут быть леволинейными и праволинейными.

Леволинейные автоматные грамматики G(VT,VN,P,S), V = VNVT могут иметь правила двух видов: ABt или At, где A,BVN, tVT.

Праволинейные автоматные грамматики G(VT,VN,P,S), V = VNVT могут иметь правила двух видов: AtB или At, где A,BVN, tVT.

Разница между автоматными грамматиками и обычными регулярными грам­матиками заключается в следующем: там, где в правилах обычных регулярных грамматик может присутствовать цепочка терминальных символов, в автомат­ных грамматиках может присутствовать только один терминальный символ. Любая автоматная грамматика является регулярной, но не наоборот – не всякая регулярная грамматика является автоматной.

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

Чтобы классы автоматных и регулярных грамматик были полностью эквивалент­ны, в автоматных грамматиках разрешается дополнительное правило вида S, где S – целевой символ грамматики. При этом символ S не должен встречаться в правых частях других правил грамматики. Тогда язык, заданный автоматной грамматикой G, может включать в себя пустую цепочку: L(G). В таком случае автоматные леволинейные и праволинейные грамматики, так же как обычные леволинейные и праволинейные грамматики, задают регулярные языки. Поскольку реально используемые языки, как правило, не содержат пустую цепочку симво­лов, разница на пустую цепочку между этими двумя типами грамматик значения не имеет и правила вида S далее рассматриваться не будут.

Существует алгоритм, который позволяет преобразовать произвольную регуляр­ную грамматику к автоматному виду – то есть построить эквивалентную ей ав­томатную грамматику. Этот алгоритм рассмотрен ниже. Он является исклю­чительно полезным, поскольку позволяет существенно облегчить построение распознавателей для регулярных грамматик.

2.1.2. Алгоритм преобразования регулярной грамматики
к автоматному виду

Имеется регулярная грамматика G(VT,VN,P,S), необходимо преобразовать ее в почти эквивалентную автоматную грамматику G’(VT,VN’,P’,S’). Для опреде­ленности будем рассматривать леволинейные грамматики, как уже было сказано выше (для праволинейных грамматик можно легко построить аналогичный ал­горитм).

Алгоритм преобразования прост и заключается он в следующей последователь­ности действий:

Шаг 1. Все нетерминальные символы из множества VN грамматики G перено­сятся во множество VN’ грамматики G’.

Шаг 2. Необходимо просматривать все множество правил Р грамматики G.

Если встречаются правила вида ABa1, А,ВVN, а1VT или вида Aa1, AVN, a1VT, то они переносятся во множество Р’ правил грамматики G’ без измене­ний.

Если встречаются правила вида АВ или вида А, то они переносятся во мно­жество правил Р’ грамматики G’ без изменений.

Шаг 3. Просматривается множество правил Р’ грамматики G’. В нем ищутся пра­вила вида АВ или вида А.

Если находится правило вида АВ, то просматривается множество правил Р’ грамматики G’. Если в нем присутствуют правила вида ВС, ВСа, Ва или В, то в него добавляются правила вида АС, АСа, Аа и А соответст­венно, A,B,CVN’, aVT’ (при этом следует учитывать, что в грамматике не должно быть совпадающих правил, и если какое-то правило уже присутствует в грамматике G’, то повторно его туда добавлять не следует). Правило АВ уда­ляется из множества правил Р’.

Если находится правило вида А, то просматривается множество правил Р’ грамматики G’. Если в нем присутствует правило вида ВА или ВАа, то в него добавляются правила вида В и Ва соответственно, A,BVN’, aVT’ (при этом следует учитывать, что в грамматике не должно быть совпадающих правил, и если какое-то правило уже присутствует в грамматике G’, то повторно его туда добавлять не следует). Правило А удаляется из множества правил Р’.

Шаг 4. Если на шаге 3 было найдено хотя бы одно правило вида АВ или А во множестве правил Р’ грамматики G’, то надо повторить шаг 3, иначе перейти к шагу 5.

Шаг 5. Целевым символом S’ грамматики G’ становится символ S.

Шаги 3 и 4 алгоритма в принципе можно не выполнять, если грамматика не со­держит правил вида АВ (такие правила называются цепными) или вида А (такие правила называются -правилами). Реальные регулярные грамматики обыч­но не содержат правил такого вида. Тогда алгоритм преобразования грамматики к автоматному виду существенно упрощается.

Источник

Иерархия Хомского формальных грамматик

Содержание

Класс 0 [ править ]

К нулевому классу относятся все формальные грамматики. Элементы этого класса называются неограниченными грамматиками (англ. unrestricted grammars), поскольку на них не накладывается никаких ограничений. Они задают все языки, которые могут быть распознаны машиной Тьюринга. Эти языки также известны как рекурсивно перечислимые (англ. recursively enumerable).

Правила можно записать в виде:

Практического применения в силу своей сложности такие грамматики не имеют.

Пример [ править ]

[math] S \rightarrow aBcc \\ B \rightarrow A \\ BAA \rightarrow d \\ Ac \rightarrow B \\ A \rightarrow AAA\ |\ dB \\ [/math]

Выведем в данной грамматике строку [math]addd[/math] :

Класс 1 [ править ]

Первый класс представлен неукорачивающими и контекстно-зависимыми грамматиками.

Языки, заданные этими грамматиками, распознаются с помощью линейно ограниченного автомата (англ. linear bounded automaton) (недетерминированная машина Тьюринга, чья лента ограничена константой, зависящей от длины входа.)

Известно, что неукорачивающие грамматики эквивалентны контекстно-зависимым.

Пример [ править ]

[math] S \rightarrow 012 \\ S \rightarrow 0AS2 \\ A0 \rightarrow 0A \\ A1 \rightarrow 11 [/math]

Класс 2 [ править ]

Второй класс составляют контекстно-свободные грамматики, которые задают контекстно-свободные языки. Эти языки распознаются с помощью автоматов с магазинной памятью.

То есть грамматика допускает появление в левой части правила только одного нетерминального символа.

Пример [ править ]

Продукции: [math]S\rightarrow\alpha S\alpha\,|\,\alpha\,|\,\varepsilon, \alpha \in \Sigma[/math]

Класс 3 [ править ]

К третьему типу относятся автоматные или регулярные грамматики (англ. regular grammars) — самые простые из формальных грамматик, которые задают регулярные языки. Они являются контекстно-свободными, но с ограниченными возможностями.

Все регулярные грамматики могут быть разделены на два эквивалентных класса следующего вида:

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

Также можно показать, что множество языков, задаваемых праволинейными грамматиками, совпадает со множеством языков, задаваемых конечными автоматами.

Пример [ править ]

[math] S \rightarrow aS\ |\ bA \\ A \rightarrow \varepsilon\ |\ cA [/math]

Источник

Слова, языки и грамматики

1.5. Классы грамматик

Пример 1.5.2. Грамматика

Пример 1.5.4. Грамматика

Определение 1.5.5. Линейной грамматикой (linear grammar ) называется порождающая грамматика, каждое правило которой имеет вид или , где , , , .

Пример 1.5.8. Грамматика

Пример 1.5.9. Грамматика

Пример 1.5.10. Грамматика

Пример 1.5.11. Грамматика

Определение 1.5.12. Правила вида называются — правилами или эпсилон-правилами.

Лемма 1.5.13. Каждая праволинейная грамматика является линейной. Каждая линейная грамматика является контекстно-свободной. Каждая контекстно-свободная грамматика без -правил является контекстной грамматикой.

Определение 1.5.14. Классы грамматик типа 0, 1, 2 и 3 образуют иерархию Хомского ( Chomsky hierarchy ).

Пример 1.5.16. Пусть дан произвольный алфавит

Упражнение 1.5.17. Какому классу принадлежит грамматика

Упражнение 1.5.18. Какому классу принадлежит грамматика

Упражнение 1.5.19. Найти праволинейную грамматику, порождающую язык .

Упражнение 1.5.20. Найти праволинейную грамматику, эквивалентную грамматике

Упражнение 1.5.21. Найти праволинейную грамматику, эквивалентную грамматике

Источник

Праволинейные грамматики и регулярные языки

Лингвистические основы информатики (ЛОИ)

Чем будем заниматься?

— Теорией компиляции. Узнаем:

В итоге будем знать, как работают и как написать (в теории) компиляторы.

Немного комментариев и истории:

Даже разбор формулы в Экселе использует какие-то приёмы компиляции!

В 50-x годах людям надоело писать на ассемблере, и они начали думать. К 60-м придумали.

Что такое компилятор?

По-простому – переводчик с языка на язык. Можно рассматривать как чёрный ящик с каким-то входом, выходом и магией внутри.

Принято разделять его работу на 2 фазы:

фронтенд: анализ исходного текста. Если есть ошибки, то останавливаемся.

Заниматься будем фронтендом!

лексический анализ: разбиваем текст на токены – знаки, переменные, идентификаторы.

синтаксический анализ (парсер): определяем, как можно получить такую терминальную строку

семантический анализ: проверка типов.

Синтаксис — правила построения предложений

Семантика — типы и подходящие им операции

семантика: тип, место хранения, время объявления

Написанию компилятора предшествует описание языка.

Рассмотрим язык с условным оператором. Что есть условный оператор с точки зрения синтаксиса? Опишем это с помощью форм Бэкуса–Наура[^1].

Соглашения

Таким образом, терминальные символы стоит понимать как символы, из цепочек которых ничего нельзя вывести.

Основная функция этого правила — порождение языка.

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

Получается, что грамматика для нас — просто набор правил вывода. Потому что всё остальное мы зафиксировали в обозначениях.

Если форма получена применением правила к самому левому нетерминалу в предыдущей форме, то она называется левой. Иначе — правой.

Пример

Рассмотрим вывод терминальной цепочки:

$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb$

Ещё пример

$S \Rightarrow ABS \Rightarrow ABABS \Rightarrow ^* (AB)^nS \Rightarrow (AB)^n$

Можем перейти к терминалам

$S \Rightarrow ^*ABABAB \Rightarrow ABBAAB \Rightarrow abbaab$

Хотим загнать буквы А в конец, а B в начало. Будем менять местами буквы по второму правилу.

На каждой стадии – новый язык. Значит, нужны новые способы порождения\описания. А этот способ порождает распознаватель.

Вспомним пример. Кажется, что это грамматика обычного вида.

$A \rightarrow aS|bAA$

Контекстно-свободные грамматики и языки

Опр. Упорядоченное дерево — дерево с заданным линейным порядком со следующими свойствами:

Порядок, возникающий при обходе в глубину слева направо

Пример:

$S \rightarrow SS|(s)|\lambda$

$S \rightarrow SS \rightarrow S \rightarrow (S) \rightarrow ((S)) \rightarrow (())$

Применили правило, в дереве появился куст вывода

Если с узлом лежит хотя бы один его сын, то и все его сыновья тоже лежат.

Пример по последнему языку:

Основная роль дерева вывода — связь синтаксиса и семантики выводимой цепочки. Например, семантика компьютерной программы — алгоритм решения задачи, а дерево вывода описывает структуру программы, т.е. порядок выполнения машинных операций, необходимых для реализации алгоритма.

Наша любимая грамматика, которая порождает арифметику:

$E \rightarrow E+E|E*E|(E)|x$

Следующая грамматика однозначна и эквивалентна предыдущей

$E \rightarrow E + T|T$

Плата за однозначность — увеличение длины вывода.

Чем плохи неоднозначные грамматики? Во время синтаксического разбора будет невозможно определить дерево разбора единственным образом. Значит, непонятно, что хотел сказать этим автор.

Теорема. Праволинейная грамматика порождает регулярный язык.

Суть: построим автомат и по теореме Клини[^4] — готово.

$F = $ — терминальные состояния — такие нетерминалы, из которых выводится пустое слово

$\delta(A,a)=B \iff (A \rightarrow aB) \in P$ — переход возможен, если есть такое правило вывода

$A \rightarrow bA|cB|\lambda$

Хотим научиться удалять лишние вещи, которые не несут никакой пользы.

== из него можно получить терминальную цепочку.

Опр. Грамматика приведённая, если все её нетерминалы достижимые и производящие.

Пример

$S \rightarrow bAc|AcB$

Если среди производящих нетерминалов нет аксиомы, то язык пустой.

$\Gamma_r^1 \leftarrow S$;

Выкинули правила вывода, которые и так не могли участвовать в выводе терминальных цепочек.

Пример

$S \rightarrow ab|bAc$

Больше не будем рассматривать неприведённые грамматики

Хотим, чтобы это множество было пустым. Ну или хотя бы только с аксиомой. Потому что тогда нам жить станет проще (почему? Сократим грамматику?).

Чтобы от аннулирующих нетерминалов избавиться, нужно их найти

Пример

$S \rightarrow aBC|AE$

$A \rightarrow bC|\lambda$

$C \rightarrow \lambda$

Смысл: добавим аксиому, которая справа встречаться нигде не будет.

Рассмотрим бинарное отношение на множестве форм:

$P’ = \left \beta \neq \lambda \\beta \preceq \gamma\(A \rightarrow \gamma) \in P \end \right. \right>$

Взяли все исходные правила. В новую грамматику положили их «части»-подстроки, в которых либо присутствует, либо удалён каждый из аннулирующих нетерминалов.

$S \Rightarrow_ \alpha_1 \Rightarrow_. \Rightarrow_ \alpha_n = w$

как построить такую же цепочку, используя другие правила? Непонятно.

Нормальная форма Хомского

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

Теорема. Любая КС грамматика эквивалентна некоторой грамматике в ХНФ.

Избавляемся от правил, где справа много терминалов.

Лемма. Любая грамматика эквивалентна некоторой ацикличной.

Пример

$S \rightarrow AB|aAb$

$A \rightarrow bB|aBC|\lambda$

$B \rightarrow AS|bA|a$

$S \rightarrow AB|B|_aAb_|_ab_$

$A \rightarrow _bB_|_aBC_$

$B \rightarrow AS|S|_bA_|b|a$

$S \rightarrow AB|B|A’AB’|A’B’$

$A \rightarrow B’B|A’BC$

$B \rightarrow AS|S|B’A|b|a$

$S \rightarrow AS|A’AB’|A’B’|B’A|b|a$

$A \rightarrow B’S|A’SC$

$S \rightarrow AS|A’D|A’B’|B’A|b|a$

Корень (вершина треугольника) — аксиома. Принадлежит пути.

Из двух (потому что ХНФ) потомков выберем того, из которого выводится больше выделенных позиций.

$\left.\begin<>A_ <нижнее>\Rightarrow^+ z\ A_ <верхнее>\Rightarrow^+ xzy\end\right> \Rightarrow A \Rightarrow^+xAy$

Тут надо нарисовать треугольник, и станет понятнее!

Рандомный комментарий: для всех слов высота дерева вывода одинаковая! Для ХНФ.

Пример

Суть: для любого КСЯ существуют натуральные константы такие, что любое слово определённой длины соответствует свойствам. Отсутствуют слова про выделенные позиции! То есть все символы выделены.

Следствия леммы о накачке

На экзамене будет вопрос про лемму о накачке и её следствия! Лемму доказывать не надо! Лемму Огдена надо. А следствия те, что ниже!

Если не можем накачать слово, то это точно не КСЯ

Накачать можем одну из половинок или что-то посередине.

Теорема об унарных языках

$\exists n,m : \forall a^n a^; (r \le m)$:

$a^n=$[по лемме о накачке]$=uxzyv=$[потому что язык унарный]$=uvzxy$

M — периодическое множество длин слов.

Что это была за картинка. 🙁

Пример.

Который показывает, что операции объединения, произведения и итерации — частные случаи подстановки.

$\tau (a_1) = L_1 \subseteq \Delta^*$

$\tau (a_2) = L_2 \subseteq \Delta^*$

$\tau (L) = \tau (a_1) \cup \tau(a_2) = L_1 \cup L_2$

$\tau (L) = \tau (a_1)\cdot \tau(a_2) = L_1\cdot L_2$

$\tau (L) = \tau (^) = \tau (\bigcup \limits_^\infty a_1^i) = \bigcup \limits_^\infty \tau (a_1^i) = \bigcup \limits_^\infty \tau (a_1)^i = \bigcup \limits_^\infty L_1^i = L_1^$

Теорема о подстановке.

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

$\bar <\Gamma>= \Gamma \cup \bigcup \limits_^n \Gamma_i$

То есть цепочку из исходных терминалов заменяем на подстановку, из которой можем получить что-то новенькое

$\Gamma_i$, потому что мы могли не дойти до самого низа дерева, где появляются терминалы (см. определение стандартного дерева)

$w \in L(H), \ w = w_1. w_k$, потому что мы изначально рассматривали такое слово

“$\in$”, а не “$=$”, потому что результат подстановки — множество.

Следствия теоремы о подстановке

$L_1 = \tau(a_1), L_2 = \tau(a_2)$ — КСЯ

$\tau( (КСЯ)) = L_1 \cup L_2$

Сл. 2. Класс КСЯ замкнут относительно перехода к гомоморфным образам.

Гомоморфизм — частный случай подстановки. Применение подстановки к одному символу даёт язык из одного слова

Предложение. Класс КСЯ не замкнут относительно пересечения и дополнения.

Языки получены с помощью произведения КСЯ на КСЯ, значит, тоже КСЯ

Выражаются через незамкнутое пересечение:

Теорема о пересечении КСЯ с РЯ

Пересечение КСЯ с регулярным языком — КСЯ Д-во:

Рассматриваем лямбда-свободные грамматики!

А что случится, если она будет не лямбда свободной? Дырки и лишние состояния?

$A =:(\Sigma, Q, \delta, q_0, F), M = L(A)$

Достаточно рассмотреть автоматы с единственным заключительным состоянием:

$A =:(\Sigma, \Gamma, \delta, q_0, f_i), f_i \in F$

$L \cap M = L \cap \bigcup\limits_L(A_)= \bigcup\limits_L\cap L(A_)$

Рассмотрим вспомогательную грамматику:

$\bar <\Gamma>= Q \times (\Gamma \cup \Sigma) \times Q$

Правила вывода состоят из правил двух типов:

Мы знаем, что регулярный язык можно распознать за линейное время. Про КСЯ пока ничего не знаем. Но, есть теорема, которая отвечает на этот вопрос. Попытаемся определить вхождение слова в КСЯ.

Сначала нужно построить табличку. Пусть есть слово, которое мы проверяем:

Для любой подстроки слова существует нетерминал, из которого эта самая подстрока выводится. При этом, так как справа стоят два нетерминала, из них тоже выводятся подстроки этой подстроки

Первый столбец заполняется по правилам ХНФ (2):

Остальные столбцы заполним, перебрав все возможные «распилы» строки на 2 части:

Автоматы с магазинной памятью — стеком, PDA — push-down automaton.

Автомат закончит работу, когда дочитает строку и остановится в заключительном состоянии.

Управляющая таблица для МП-автомата: по столбцам — символ, который читаем, по строкам — состояния и элемент на верхушке стека

Сколько мест в стеке, столько строк на каждое состояние

На каждом шаге обязательно надо читать из стека! Элемент при этом оттуда исчезает. Поэтому, если мы хотим, чтобы внизу всегда был символ ИКС, то в каждой команде нужно не забывать его туда класть.

в стеке будет лежать только открывающая скобка

При разборе — в левом префиксе открывающих скобок не меньше чем закрывающих

Варианты распознавания МП-автомата:

Вершина стека пишется слева! (пока)

На множестве конфигураций можно построить отношение: возможность перехода из одной конфигурации в другую.

$[q,w,\gamma] \vDash [q’,w’,\gamma’]$ — переход за 1 ход.

Опр. МПА распознаёт цепочку, если он дочитал её до конца и:

Введение дополнительных стековых символов позволяет сократить количество состояний

Пример

Когда будем пошагово воспроизводить работу МП-автомата, стек будем писать в правой колонке!

$fin$ — ограничиваем то, что складываем в стек, а то таблица станет бесконечной.

Теорема. Класс языков, распознаваемых НМПА, строго больше класса языков, распознаваемых ДМПА.

$ | w \in \Sigma^*, |\Sigma| \ge 2>$ — множество палиндромов.

$\Gamma = \Sigma \cup $ — стековый алфавит.

Что значит, что НМПА распознаёт символ?

Автомат с пустым стеком продолжать работу не может, так как на каждом шаге он что-нибудь берёт из стека.

Теорема. Любой КСЯ распознаётся НМПА с одним состоянием и одной командой допуска.

Если состояние одно, то нигде про него говорить не будем. Поэтому тройки станут двойками.

У нас остаётся входной и стековый алфавит

$(\nabla, \dashv) \rightarrow \checkmark$

$\forall a \in \Sigma : (a, a) \rightarrow (\lambda, \rightarrow)$

$\forall a \in \Sigma: (B, a) \rightarrow (\gamma, _)$

$\forall (B \rightarrow \gamma) \in P$

Заканчиваем работу успешно, если стек пуст, а входная строка дочитана до конца

Читаем символ входной строки только тогда, когда, когда на вершине стека — этот же символ

Команд будет столько, сколько разных правых частей есть для этого нетерминала.

$S \Rightarrow u_1B_1\gamma_1 \Rightarrow u_1u_2B_2\gamma_2 \Rightarrow … \Rightarrow u_1…u_B_\gamma_ \Rightarrow u_1…u_n$

$[w, S] = [u_1…u_, S] \vDash [u_1…u_n, u_1B_1\gamma_1] \vDash^* [u_2…u_n,B_1\gamma_1] \vDash [u_2…u_n,u_2B_2\gamma_2] \vDash^*$

$ \vDash^* [u_n, B_\gamma_] \vDash [u_n, u_n] \vDash^* [\lambda, \lambda]$

$u_1$ — цепочка из терминалов

$\gamma_i$ — цепочка из терминалов и нетерминалов

Пока мы не дойдём до нетерминала мы продолжим чтение входной строки

Есть оракул, который говорит, что данная последовательность реализуема

$[w, S] \vDash^* [\lambda, \lambda]$

С помощью этой последовательности закодировали типы применяющихся команд. Если там лямбда, то мы применяли команду типа 2 и не сдвигались по входной строке.

Левая форма — всё, что может возникнуть в процессе левостороннего вывода.

Д-во. По индукции.

прочитали из строки символ

$a_n \in \Sigma \Rightarrow \gamma_=a_n\gamma_n$.

$\beta_ = \beta_n = a_1. a_n\gamma_n$

ничего из строки не прочитали

$a_n=\lambda \Rightarrow \gamma_=B_\gamma’_$

$(\beta_ \rightarrow \gamma) \in P$

Вернёмся к доказательству теоремы.

Что даёт теорема? Есть КСЯ, можем построить НМПА, его распознающий.

Теорема. Класс КСЯ и класс языков, распознающихся НМПА, совпадают.

Следствие. ДМПА распознаёт собственный подкласс КСЯ.

Пример

$S \rightarrow (S)S|\lambda$

Стековый алфавит — все терминалы, нетерминалы и дно стека. В начале в стеке аксиома

NB: не забываем, что вершина стека — слева!

Суть таблички: начинаем с аксиомы. Если во входной строке — скобочки, значит аксиому нужно “развернуть“. Если вложенные — то в нужный момент надо будет “развернуть” ещё раз. Если видим одинаковые скобки в стеке и во входной строке — считываем их. Если число закрывающих скобок в кусочке строки и в стеке одинаковое, то нужно убирать аксиомы с помощью правила с лямбдой.

Слева — прочитанное, справа — стек. Наша цель — получить дерево

[^1]: Будем их использовать, чтобы не терять связь грамматики и компиляции. [^2]: Recursively Enumerable [^3]: с таким же деревом вывода [^4]: Классы регулярных и автоматных языков совпадают

Источник