Алгоритм был ранее определен как алфавитный оператор с конечной системой правил преобразования. Для записи входных, промежуточных и выходных слов используется некоторый алфавит. Каким-то образом должны быть описаны и правила преобразования. Очевидно, для этого требуется некоторый язык. Пригоден ли для описания алгоритма обычный разговорный язык?

Любой естественный язык возникал как средство общения людей. Именно по этой причине ему присущи такие особенности как:

· изменчивость, которая состоит в непостоянстве словарного состава языка;

· неоднозначность трактовки фраз различными людьми;

· избыточность, о чем шла речь в главе «Кодирование символьной информации».

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

В любом языке - естественном или искусственном - можно выделить две составляющие: синтаксис и семантику. Синтаксис (грамматика языка) - это совокупность правил, согласно которым строятся допустимые в данном языке конструкции. Семантика - смысловая сторона языка - она соотносит единицы и конструкции языка с некоторым внешним миром, для описания которого язык используется.

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

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

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

Помимо синтаксиса устанавливается система правил, позволяющих конструкциям языка придать смысл - эти правила образуют семантику языка.

Формальная грамматика - система правил, описывающая множество конечных последовательностей символов формального алфавита.

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

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

Формальная грамматика задается упорядоченной четверкой {T , N, S, Р }, где Т и N - непересекающиеся конечные множества, образующие алфавит или словарь порождаемого формального языка; Т называется множеством (словарем) терминальных символов; N - множеством (словарем) нетерминальных (вспомогательных) символов. S - начальный (выделенный) вспомогательный символ из множества N. Р - набор правил вывода конструкций языка (подстановок) из выделенного вспомогательного символа, имеющие вид g → h, где g и h - цепочки, состоящие как из терминальных, так и нетерминальных символов.

Подстановки работают следующим образом: если в преобразуемой цепочке есть слово g , то оно заменяется словом h. Единственное ограничение на вид подстановок состоит в том, что слово g не может состоять только из терминальных символов. Это означает, что получение на некотором шаге цепочки, состоящей только из терминальных символов, свидетельствует о прекращении процесса порождения - эта цепочка является правильной, завершенной конструкцией порождаемого языка. Подстановки Р могут применяться к трансформируемой цепочке в произвольном порядке.

Транскрипт

1 ПРИМЕРЫ ПОСТРОЕНИЯ ГРАММАТИК Порождающие грамматики служат для точного, формального задания языков. На практике часто ставится обратная задача: построить грамматику на основе некоторого числа примеров «правильных» цепочек языка и интуитивных представления о правильности некоторых языковых конструкций. Разработка грамматики это неформальная процедура, которой можно научиться на примерах. Рассмотрим задачу построения грамматик для всех языков в примере выше. Пример: ;. Порождающие грамматики разработаны для задания бесконечных языков. Для конечных языков построение порождающих грамматик является простым. Для этого языка грамматика имеет вид: :

2 Пример: ;. 1. Любая цепочка, порождаемая искомой грамматикой, имеет структуру:, где цепочка, состоящая только из символов, цепочка, состоящая только из символов, и количества символов в цепочках и равны. 2. При выводе цепочек удобно одновременно порождать и, и, тогда это требование будет выполнено автоматически. 3. Если одним из правил грамматики будет, то многократным его применением можно построить:

3 4. Для получения терминальных цепочек требуемого вида достаточно в этих промежуточных цепочках убрать, что может быть сделано при наличии в грамматике правила. Для языка грамматика имеет вид: : Пример вывода:.

4 Пример: ;. 1. Структура любой цепочки языка, где цепочка, состоящая только из символов, цепочка, состоящая только из символов. 2. Поскольку количества символов в начале цепочек языка и в конце цепочек могут не совпадать, отдельные части структуры цепочек можно генерировать независимо. Для языка грамматика имеет вид: :

5 Пример вывода: Здесь на каждом шаге вывода в промежуточной цепочке заменялась самая левая подцепочка, которую можно было заменить в соответствие с правилами грамматики. Такой вывод называется левым. Определение: вывод цепочки из в КСграмматике называется левым (левосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого левого нетерминала.

6 Цепочку языка можно породить в грамматике и с помощью другого вывода, например заменяя самый правый нетерминал в промежуточной цепочке вывода. Такой вывод называется правым: Определение: вывод цепочки из в КСграмматике называется правым (правосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого правого нетерминала.

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

8 Для КС-грамматик можно ввести удобное графическое представление вывода, называемое деревом вывода, причем для всех эквивалентных выводов деревья вывода совпадают.

9 Определение: дерево называется деревом вывода (или деревом разбора) в КС-грамматике, если выполнены следующие условия: (1) каждая вершина дерева помечена символом из множества, при этом корень дерева помечен символом; листья - символами из; (2) если вершина дерева помечена символом, а ее непосредственные потомки - символами,..., где каждое, то - правило вывода в этой грамматике; (3) если вершина дерева помечена символом, а ее единственный непосредственный потомок помечен символом, то - правило вывода в этой грамматике.

10 Для трех, представленных выше последовательностей вывода цепочки дерево вывода в грамматике одно и тоже. :

11 Приведем ещё один пример грамматики языка: Пример вывода: : В приведенной последовательности вид промежуточных цепочек всегда определен это терминальная цепочка, заканчивающая одним нетерминалом. Дерево вывода цепочки имеет вид.

12 : Грамматики такого вида называются автоматными грамматиками (А-грамматиками).

13 Определение: грамматики называются эквивалентными, если они порождают один и тот же язык. Грамматики (). и эквивалентные грамматики Утверждение: Любой язык может быть порожден бесконечным числом грамматик.

14 Пример: ; - множество цепочек с одинаковым количеством вхождений символов и. Очевидно, что,. Можно придумать различные грамматики, прождающие этот язык. Очевидно. Что каждая грамматика отражает некоторую глубинную идею порождения цепочек с указанными свойствами.

15 Например, одной из идей может быть такая: 1. Любая цепочка с указанным свойством есть престановка символов уже известного нам языка. 2. Поэтому можно использовать грамматику для порождения цепочек и добавить в нее правило, разрешающее произвольную перестановку терминальных символов: Для языка грамматика: Пример вывода: Эта грамматика не является КС-грамматикой из-за последнего правила.

16 Попытаемся по-другому построить грамматику, порождающую язык. 1. Если в любой цепочке с совпадающим числом символов и первый символ -, то во всей остальной части цепочки число символов должно быть на единицу больше числа символов. 2. Пусть - нетерминал, из которого порождаются все цепочки с этим свойством.

17 3. Если первый символ такой цепочки, то в оставшейся части цепочки количества символов и одинаковы, а любая такая цепочка, очевидно выводится из., т.е. 4. Если первый символ такой цепочки, то это значит, что в оставшейся части цепочки число символов уже на два больше, чем символов, и следовательно, этот остаток всегда можно представить как две стоящие рядом подцепочки, каждая из которых содержит на одно вхождение символа больше, чем символа., т.е.

18 Аналогичные рассуждения по нетерминалу. Окончательно получаем грамматику: : Пример вывода: В этой грамматике возможен и другой вывод той же самой цепочки: Заметим, что грамматика - КС-грамматика.

19 :

20 Еще один пример грамматики, порождающей язык:

21 Пример:, бочных выражений. - множество правильных ско- Структуру скобочных выражений можно представить либо как конкатенацию двух стоящих рядом скобочных выражений, либо как вложенное в скобки, скобочное выражение. «Крайним частным случаем» является просто отсутствие скобок. :

22 :

23 Определение: КС-грамматика называется неоднозначной, если существует хотя бы одна цепочка, для которой может быть построено два или более различных деревьев вывода. Это утверждение эквивалентно тому, что цепочка имеет два или более разных левосторонних (или правосторонних) выводов. Определение: в противном случае грамматика называется однозначной. Определение: язык, порождаемый грамматикой, называется неоднозначным, если он не может быть порожден никакой однозначной грамматикой.

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

25 Утверждение: Если грамматика используется для определения языка программирования, то она должна быть однозначной. В приведенном выше примере разные деревья вывода предполагают соответствие разным. Если договориться, что должно соответствовать ближайшему к нему, и подправить грамматику, то неоднозначность будет устранена: Проблема, порождает ли данная КС-грамматика однозначный язык (т.е. существует ли эквивалентная ей однозначная грамматика), является алгоритмически неразрешимой.

26 Пример:,. Оказывается, что никакая грамматика, порождающая этот язык не является контекстно-свободной. Например одна из таких грамматик: : Пример вывода: Такая грамматика называется зависимой (КЗ-грамматика) контекстно-

27 Пример: ; - арифметические выражения, в которых операнды обозначаются символом. Наиболее простая грамматика рассматривает арифметическое выражение либо как арифметическое выражение, взятое в скобки, либо как пару стоящих рядом арифметических выражений, соединенных знаком операции: : Канонический левый вывод цепочки имеет следующий вид: Представленная грамматика неоднозначна. в

28 Пример: ;. Цепочки языка - это две идентичные копии произвольной цепочки из символов и, разделенные маркером. 1. // Порождаются одновременно как терминал (остающийся на своем месте), так и соответствующий ему нетерминал, который надо перегнать вправо и превратить терминал только сразу после разделителя. В конце концов, можно превратить в разделитель. Если нетерминалы не менять местами при их движении вправо, то они в том же порядке и останутся перед превращением в соответствующие терминалы. 2., // Нетерминал вправо. перегоняется

29 3. 4. // Терминал теперь может стать на свое место сразу после, 5. // Нетерминал вправо. перегоняется // Терминал теперь может стать на свое место сразу после Заметим, что нетерминалы не могут при движении вправо перепрыгнуть друг друга. Только когда нетерминал уже пришел к разделительной границе, он может превратиться в терминал после нее. Вывод цепочки:

31 ПРИМЕРЫ ЯЗЫКОВ Пример: ;. Цепочки языка - состоят из двух несовпадающих цепочек над словарем, разделенных маркером. Примеры цепочек языка: Очевидно, что,. Пример: словоформы русского языка; Цепочки языка - русский язык. Например, «молодая красивая студентка мчалась галопом в карете по пыльной дороге», «от дорогу по телеге к».

32 ПРИМЕРЫ ЯЗЫКОВ Пример: ; - язык Паскаль. Определение языка как подмножества множества всех возможных цепочек над конечным словарем является общим и неконструктивным.

33 Современные языки программирования высокого уровня задаются порождающими грамматиками Хомского. Грамматики эти состоят из нескольких десятков (а иногда и сотен) правил. Существуют различные нотации описания правил грамматики: 1. Хомского, 2. Хомского-Шутценберже, 3. НФБН, 4. РФБН, 5. диаграммы Вирта.

34 ИЕРАРХИЯ ПОРОЖДАЮЩИХ ГРАММАТИК ХОМКОГО Тип Вид правил Название языка Неограниченные грамма- Рекурсивнотики перечислимый Свободные грамматики язык Контекстно-зависимые КЗ-язык грамматики КЗ-грамматики Контекстно-свободные КС-язык грамматики КС-грамматики Автоматные грамматики Автоматный Регулярные грамматики язык А-грамматики Название грамматики

35 В грамматиках типа 0 на левую и правую части правил не накладывается никаких ограничений. Цепочки и в правилах грамматики могут быть любыми. Единственное ограничение - левая часть не может быть пустой цепочкой. Общего алгоритма распознавания для этого типа грамматик не существует - это класс рекурсивноперечислимых языков. В грамматиках типа 1 правила имеют вид. Здесь - некоторый нетерминал, и произвольные цепочки, фактически образующие контекст, в котором нетерминал может быть заменен цепочкой.

36 Рассмотрим грамматику: Кроме правила все остальные продукции удовлетворяют ограничениям грамматик типа 1. Следовательно, в таком виде грамматика является грамматикой типа 0. Но это не значит, что язык является рекурсивно-пречислимым. Оказывается, что вид продукции можно представить тремя продукциями с эквивалентными возможностями:,. Очевидно, что последовательное применение этих продукций приведет к перестановке и. Причем это

37 достигнуто только при помощи контекстно-зависимых продукций, удовлетворяющих ограничениям для грамматик типа 1. Итак, язык можно породить грамматикой с контекстно-зависимыми продукциями, и поэтому он является контекстно-зависимым языком (языком типа 1): :

38 Для грамматик типа 1 можно построить общий алгоритм распознавания, но он будет черезвычайно неэффективным. Грамматики типов 0 и 1 слабо исследованы, для них не существует простых алгоритмов распознавания, а известные алгоритмы очень медленны. Недостатком грамматик этого типа является также то, что понятие структуры цепочки языка скрыто неявно в последовательности шагов вывода этой цепочки. Грамматики типа 1 в задании и трансляции искусственных языков применяются редко.

39 В грамматиках типа 2, или контекстно-свободных грамматиках, вид продукций. Левая часть продукций состоит из единственного нетерминала, и замена нетерминала на цепочку может осуществляться в любом контексте: контекстные ограничения в этих правилах отсутствуют. Для КС-грамматик существуют сравнительно эффективные алгоритмы синтаксического анализа, применимые для распознавания цепочек языков, порождаемых любой грамматикой этого класса. Все языки в грамматиками. программировании задаются КС-

40 В грамматиках типа 3 ограничения накладываются на правую часть продукций. Эти ограничения приводят к тому, что порождаемые языки этого типа являются автоматными, и распознающее их автоматическое устройство это конечный автомат. Для языков типа 3 существует очень эффективный (линейный по сложности) алгоритм синтаксического анализа, описывающий работу конечного автомата. Определение: язык L(G) является языком типа k, если его можно описать грамматикой типа k.

41 Соотношения между типами грамматик и языков: (1) каждый регулярный язык является КС-языком, но существуют КС-языки, которые не являются регулярными (например,). (2) каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не являются КС-языками (например,). (3)каждый КЗ-язык является языком типа 0.

42 Примеры грамматик и языков. Замечание: если при описании грамматики указаны только правила вывода, то будем считать, что большие латинские буквы обозначают нетерминальные символы, - цель грамматики, все остальные символы - терминальные. 1) Язык типа 0: :) Язык типа 1:

43 :) Язык типа 2: :) Язык типа 3:, где цепочка не содержит двух рядом стоящих символов:

Теория формальных языков и грамматик. Определения 1. Цепочка символов в алфавите V - любая конечная последовательность символов этого алфавита. Пустая цепочка () - цепочка, которая не содержит ни одного

КС-грамматики Разбор цепочки - процесс построения вывода цепочки из цели грамматики G = (T, N, P,). Вывод цепочки T* из N в КС-грамматике G = (T, N, P,), называется: - левосторонним, если в нем каждая

Задание 6 Грамматики Ключевые слова 1:язык, регулярный язык, ДКА, НКА, алгебра регулярных выражений, грамматики, уравнения с регулярными коэффициентами. 1 Грамматики Одна из больших проблем науки, которую

Задание 10 LL-анализ Ключевые слова 1:язык, контекстно-свободный язык, магазинный автомат, грамматика, LL(k)-грамматика, LL(1)-анализатор, функции FIRST, FOLLOW. 1 Нисходящий и восходящий разбор Напомним

А. А. Вылиток Алгоритмы преобразования контекстно-свободных грамматик с помощью графов 1. Устранение бесполезных символов Рассмотрим пример контекстно-свободной грамматики c алфавитом терминальных символов

Формальные грамматики Основные понятия Алфавит - это конечное множество символов. Цепочка последовательность символов. Терминальная цепочка последовательность терминальных символов. Язык множество терминальных

Глава 4 КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ 4.1. Упрощение контекстно-свободных грамматик В этой главе мы опишем некоторые основные упрощения КС-грамматик и докажем несколько важных теорем о нормальных формах

22 Классификация грамматик и языков по Хомскому грамматики классифицируются по виду их правил вывода Четыре типа грамматик: тип 0, тип 1, тип 2, тип 3 Язык, порождаемый грамматикой типа k (k=0,1,2,3),

Московский государственный университет им. М.В. Ломоносова Факультет вычислительной математики и кибернетики И. А. Волкова, А. А. Вылиток, Т. В. Руденко Формальные грамматики и языки. Элементы теории трансляции

46 Приведенные КС-грамматики Символ x (T N) называется недостижимым в грамматике G=(T, N, P,), если он не появляется ни в одной сентенциальной форме этой грамматики. Символ А N называется бесплодным в

Московский государственный университет им. М. В. Ломоносова Факультет вычислительной математики и кибернетики И.А. Волкова, А.А. Вылиток, Т.В. Руденко Формальные грамматики и языки. Элементы теории трансляции

Теория конечных автоматов и формальных языков Матросов Александр Васильевич Цели и задачи Цель - знакомство слушателей с математическими моделями формальных языков: конечными автоматами и контекстносвободными

Лекция 2 Формальные языки и способы их задания Формальный язык Алфавит непустое конечное множество (символов) Σ = {a, c, f, h} Цепочка (слово) над алфавитом Σ конечная последовательность символов: α =

Глава 2 ГРАММАТИКИ 2.1. Мотивировка Имеется один класс порождающих систем, которые представляют для нас первейший интерес системы, называемые грамматиками. Первоначально понятие грамматики было формализовано

УДК 004.4"413 О структурировании синтаксических диаграмм С. З. Свердлов, А. А. Хивина Доказана теорема структурирования для синтаксических диаграмм, утверждающая, что произвольную синтаксическую диаграмму

Синтаксический анализ Задачи синтаксического анализа установить, имеет ли цепочка лексем структуру, заданную синтаксисом языка, т.е. решить задачу разбора по заданной грамматике, зафиксировать эту структуру.

А. А. Вылиток О регулярных языках Регулярные языки играют важную роль в математических теориях и в приложениях. К наиболее известным формализмам, описывающим регулярные языки, относятся: регулярные выражения,

Лекции по теории формальных языков Лекция 4. Контекстно-свободные грамматики и языки: определения и примеры. Лемма о накачке Александр Сергеевич Герасимов http://gas-teach.narod.ru Кафедра математических

207 - ТЕХНОЛОГИЧЕСКИЙ КОМПЛЕКС РАЗРАБОТКИ ЯЗЫКОВЫХ ПРОЦЕССОРОВ Б.К.Мартыненко Введение Многие проблемы применения ЗВМ для обработки текстовой информации представляются как проблемы спецификации и реализации

1 Элементы теории трансляции Транслятор позволяет преобразовать программу, написанную на ЯП, отличном от машинного языка, к виду, допускающему выполнение на ЭВМ. Компилятор на вход получает программу на

Формальные языки и грамматики 2 Цепочки символов Цепочка символов произвольная упорядоченная конечная последовательность символов, записанных один за другим Обозначение:, Символ базовое понятие в теории

Задание 9 Приложение КС-грамматик для сжатия данных. Преобразования КС-грамматик-1 Ключевые слова 1:язык, контекстно-свободный язык, магазинный автомат, грамматика, морфизм, метод математической индукции.

Найдем критерий применимости РС-метод примени м, если и только если левый вывод (или дерево нисходящим способом) можно построить, начиная с начального символа S, так, что на каждом шаге вывода решение

ТЕОРИЯ АВТОМАТОВ И ФОРМАЛЬНЫХ ЯЗЫКОВ множество (алфавит) из m символов. Операция конкатенации (соединения) из символов получает цепочку символов. Эту операцию можно применить и к цепочкам. Пример: из символов

1 Теория формальных языков лектор: Вылиток Алексей Александрович (кафедра алгоритмических языков) Материалы лекций: http://cmcmsu.no-ip.info/special.courses/ Литература 2 1. Пентус А.Е., Пентус М.Р. Теория

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования Ульяновский государственный технический университет Системное программное обеспечение:

ЗАДАЧИ К ЧАСТИ I Задачи к главе I-1 Задача I-1.1. Функция K(i, j) (i j 1)(i j 2) j отображает упорядоченные пары целых 2 на целые. Найти обратные функции I и J с таким свойством, что I(K(i, j)) = i

Глава 5 МАГАЗИННЫЕ АВТОМАТЫ 5.1. Неформальное описание В этой главе мы рассмотрим простое устройство магазинный автомат 7 (pda pushdown automaton), которое адекватно классу КС-языков в том смысле, что

Глава 9 ОПЕРАЦИИ НАД ЯЗЫКАМИ 9.1. Замкнутость относительно элементарных операций В этой главе мы применяем операции объединения, конкатенации, обращения, замыкания и т.д. к языкам разных типов. Интересно

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ

Лекции по теории формальных языков Лекция 3. Автоматы с магазинной памятью. Грамматики Александр Сергеевич Герасимов http://gas-teach.narod.ru Кафедра математических и информационных технологий Санкт-Петербургского

Лекции по теории формальных языков Лекция 14. LR-анализ с неоднозначными грамматиками. Обработка синтаксических ошибок при LR-анализе. LR(k)-грамматики. Итоги Александр Сергеевич Герасимов http://gas-teach.narod.ru

Фонд оценочных средств для проведения промежуточной аттестации обучающихся по дисциплине (модулю) Общие сведения 1. Кафедра Математики, физики и информационных технологий 2. Направление подготовки 44.03.05

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

Лекция 3 Распознавание формальных языков Метасинтаксис: EBNF Extended Backus-Naur Form - синтаксис для записи синтаксиса (КС-грамматики) левая часть = правая часть левая часть::= правая часть Принятые

Часть I: ЯЗЫКИ, ГРАММАТИКИ, АВТОМАТЫ Глава 1 ЯЗЫКИ ИХ ПРЕДСТАВЛЕНИЕ 1.1. Алфавиты и языки Приступая к изучению теории языков, прежде всего следует определить, что мы подразумеваем под термином язык. Энциклопедическое

Часть III Языки, грамматики, автоматы 137 Глава 10 Языки и конечные автоматы 10.1 Язык Дика Как мы знаем, правильные скобочные структуры перечисляются числами Каталана. Выпишем все правильные скобочные

Компьютерные науки и безопасность. 341 О ГЕНЕРАТОРЕ АНАЛИЗАТОРОВ ДЛЯ ГРАММАТИК ОСОБОГО ВИДА Конончук Д.О. e-mail: [email protected] Создание новых компиляторов и текстовых анализаторов является

Восходящий синтаксический анализ Восходящий синтаксический анализ соответствует построению дерева разбора для входной строки, начиная с листьев (снизу) и идя по направлению к корню (вверх) Алгоритм «сдвиг-свертка»

Лабораторная работа 1 Формальные грамматики и их свойства Цель работы: закрепить понятия «алфавит», «цепочка», «формальная грамматика» и «формальный язык», «выводимость цепочек», «эквивалентная грамматика»;

Лекции по теории формальных языков Лекция 6. Преобразования контекстно-свободных грамматик Александр Сергеевич Герасимов http://gas-teach.narod.ru Кафедра математических и информационных технологий Санкт-Петербургского

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

Билет 1 Задача 6A из списка. Задание языка с помощью формальных грамматик. Определение грамматики общего вида: алфавит метасимволов (нетерминалов), начальный метасимвол, правила грамматики, вывод цепочек

Задание 10 КС-языки: замкнутость и LL-анализ Ключевые слова 1:язык, контекстно-свободный язык, магазинный автомат, грамматика, метод математической индукции. 1 Лемма о накачке Одна из целей изучения леммы

Задание 7 Контекстно-свободные языки и магазинные автоматы Ключевые слова 1:язык, контекстно-свободный язык, магазинный автомат, грамматика, метод математической индукции. 1 МП-автоматы 1.1 Определения

Министерство образования и науки Украины Государственное высшее учебное заведение «Приазовский государственный технический университет» В. С. Молчанова, А. Г. Бурса ТЕОРИЯ ПРОГРАММИРОВАНИЯ Учебное пособие

46 Приведенные КС-грамматики Символ x (V T V N) называется недостижимым в грамматике G=(V T, V N, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики. Символ А V N называется

Решения и критерии проверки ноябрьской контрольной по ТРЯП ФУПМ 2016 Разбалловка неуд удовл хорошо отлично 0 Σ 10 11 Σ 15 16 Σ 22 23 Σ 33 1: 1-7, 2: 8-10 3: 11-13, 4: 14-15 5: 16-18, 6: 19-20, 7: 21-22

Глава 7 МАШИНЫ ТЬЮРИНГА: ПРОБЛЕМА ОСТАНОВКИ, ЯЗЫКИ ТИПА 0 7.1. Универсальная машина Тьюринга В этой главе мы покажем, что существует машина Тьюринга U, которая по заданному коду произвольной машины Тьюринга

Лабораторная работа 2 Грамматики и конечные автоматы Цель работы: изучить методы и средства, используемые при построении лексических анализаторов, в основе которых лежат регулярные грамматики. Краткие

Московский физико-технический институт Факультет инноваций и высоких технологий Математическая логика и теория алгоритмов, осень 2017 Семинар 1: язык записи формальных утверждений Алфавитом называется

Http://vmcozet/ Кодирование ВЕ Алексеев Задача оптимального кодирования Побуквенное кодирование Пусть A a a a } и B b b b } два алфавита Побуквенное кодирование состоит в том что в кодируемом тексте слове

РЕГУЛЯРИЗАЦИЯ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК НА ОСНОВЕ ЭКВИВАЛЕНТНЫХ ПРЕОБРАЗОВАНИЙ СИНТАКСИЧЕСКИХ ГРАФ-СХЕМ Федорченко Людмила Николаевна Специальность 05.13.11 Математическое и программное обеспечение

117 Определение: Пусть T 1 и T 2 алфавиты. Формальный перевод это подмножество множества всевозможных пар цепочек в алфавитах T 1 и T 2: (T 1 * T 2 *). Назовем входным языком перевода язык L вх ()=

Лекции по теории формальных языков Лекция 5. Операции над контекстно-свободными языками. Контекстно-свободные языки и автоматы с магазинной памятью. Контекстно-свободные грамматики и языки программирования.

Фонд оценочных средств для проведения промежуточной аттестации обучающихся по дисциплине (модулю) Общие сведения 1. Кафедра Математики, физики и информационных технологий 2. Направление подготовки 01.03.02

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ имени академика

Формируемая компетенция ФОНД ОЦЕНОЧНЫХ СРЕДСТВ ДЛЯ ПРОВЕДЕНИЯ ПРОМЕЖУТОЧНОЙ АТТЕСТАЦИИ ОБУЧАЮЩИХСЯ ПО ДИСЦИПЛИНЕ (МОДУЛЮ) Общие сведения 1. Кафедра Математики, физики и информационных технологий 2. Направление

Рабочая программа составлена на основании: 1) Государственного образовательного стандарта высшего профессионального образования по направлению подготовки 657100 (230400) «Прикладная матика» (регистрационный

Теория вычислительных процессов и структур Лекция 2. Стандартные схемы программ Содержание лекции Программа как объект исследования Стандартные схемы Класс стандартных схем Интерпретация схемы Программа

Л А Б О Р А Т О Р Н А Я Р А Б О Т А №1

Cоздание формальной грамматики и построение

Цель работы – изучение структуры языка программирования и запись ее в формальном виде; построение выводов на основе полученной грамматики для проверки ее правильности.

ОСНОВНЫЕ СВЕДЕНИЯ

Создание грамматики языка

Языки программирования, используемые в настоящее время для решения задач на ЭВМ, значительно отличаются друг от друга своей структурой и средствами описания алгоритмов. Различны также и методы отладки и выполнения программ, написанных на этих языках.

Каковы же основные принципы проектирования и разработки новых языков программирования? Каким требованиям должен удовлетворять язык, рассчитанный на широкое использование при решении задач на ЭВМ? В первую очередь, язык должен быть удобен для программиста. В частности, он должен быть легок в изучении, а также иметь средства, позволяющие с минимальными затратами времени подготовить задачи к решению на ЭВМ. С другой стороны, должны учитываться характеристики работы ЭВМ с программой: память, необходимая для обработки программы, количество машинного времени для решения задачи и пр. К сожалению, эти требования являются в известной степени трудно совместимыми. То, что «удобно» для ЭВМ, оказывается не совсем удобным для программиста и наоборот. Но, т.к. любая задача содержит, как правило и те, и другие требования к используемому языку, то при его создании необходимо учитывать обе стороны работы с ним.

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

Основным определением такого аппарата является определение формального языка. Всякий язык программирования можно определить как множество предложений – некоторое множество цепочек или конечных последовательностей элементарных единиц из некоторого непустого конечного множества символов, называемого словарем или алфавитом. При таком рассмотрении языка программирования задается только множество символов, которые можно использовать для записи программы, а также класс допустимых или синтаксически правильных программ и при этом не затрагивается вопрос зада­ния смысла каждой правильной программы. Чтобы отличать употребление слова «язык» в значении точно определенного множества цепочек от употребления этого слова в повседневной речи, множество цепочек иногда называют формальным языком .

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

Синтаксис – внешнее представление предложений языка.

Семантика – смысловое содержание предложений языка.

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

Формальная грамматика – абстрактное обобщение грамматики естественных языков – рассматривает строки (цепочки) символов.

Формальная грамматика есть четверка

G = { V , V , P , S },

где V- алфавит терминальных символов, т.е. символов, которые могут входить в левые части правил (соответствует набору слов и знаков языка);

V-алфавит нетерминальных символов (соответствует набору обобщающих понятий языка);

Р - набор порождающих правил вида

где  и  - цепочки терминальных и нетерминальных символов;

S - начальный символ грамматики (соответствует начальному понятию).

Грамматика G для любой цепочки    задает множество выводимых из нее цепочек, определяя их рекурсивно следующим образом: если  содержится в Р, то цепочка r =  непосредственно выводима из  (обозначается r), если  выводима из  и r , то r нетривиально выводима из  (  + r) ; если   + r или =r, то r выводима из  (=*r). Последо­вательность применения правил  1   2 ... r называется выводом цепочки , если  1 = S,  r =  .

Цепочка, выводимая из S, называется сентенциальной формой . Сентенциальная форма не содержащая нетерминальных символов, называется предложением . Множество предложений образует язык , порожденный грамматикой G (L(G)).

Формы Бэкуса-Науэ р а (БНФ)

Широко используемой формой записи правил грамматик являются формы Бэкуса-Науэра (БНФ).

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

Т.к. любое предложение языка можно рассматривать как цепочку основных символов этого языка, то в результате использования в определенном порядке форм Бэкуса, описывающих синтаксис языка, возможно построение любой правильной программы на этом языке.

Характерной особенностью языков программирования, так же как и естественных языков, является то, что в сложные синтаксические конструкции в качестве составных частей входят другие конструкции. Так, программа на языке TurboPascal является обычно блоком, который в свою очередь может включать в себя один или несколько внутренних блоков. Блок также является сложной конструкцией, включающей в себя описания, операторы; последние тоже имеют составные части и т.д. Таким образом, для того, чтобы написать программу, необходимо знать правила написания блоков и других конструкций, входящих в программу в качестве составных частей. Вторым классом объектов, используемых в формах Бэкуса, как раз и являются имена конструкций описываемого языка, или так называемые металингвистические переменные. Значение металингвистических переменных – это цепочки основных символов описываемого языка.

Каждая металингвистическая формула описывает правила построения некоторой конструкции языка и состоит из двух частей. В левой части находится металингвистическая переменная, обозначающая соответствующую конструкцию (нетерминальный (НТ) символ). Далее следует так называемая металингвистическая связка:: =, проставляемая вместо символа  и имеющая смысл глагола «быть». Она соединяет левую и правую части формулы. В правой части формулы указывается один или несколько вариантов построения конструкции, определенной в левой части. Каждый вариант представляет собой цепочку, состоящующую из металингвистических переменных и основных символов (терминальных(Т)). Для того, чтобы построить конструкцию, определяемую формулой, нужно выбрать некоторый вариант построения из правой части формулы и, используя соответствующие формулы вместо каждой металингвистической переменной некоторые цепочки основных символов. Варианты правой части формулы разделяются металингвистической связкой |, имеющей значение «или».

Наконец, необходимо отметить, что металингвистические переменная может обозначаться словами или некоторыми именами, заключенными в угловые скобки. Имя металингвистической переменной присваивается программистом и поясняет смысл описываемой конструкции, например: арифметическое выражение.

Пример формальной грамматики, записанной в формах Бэкуса-Науэра.

Опишем грамматику образования целых чисел. Каждое число может быть одноразрядным, т.е. состоять из одной цифры - 5, а может быть многоразрядным - 55, т.е. состоять более чем из одной цифры. Для того, чтобы образовать многоразрядное число, необходимо зациклить конструкцию на самою себя.

Грамматика G1 записи числа содержит следующие 13 правил:

(1) число::= чс

(2) чс::= чс цифра

(3) чс::= цифра

(4) цифра::= 0

(5) цифра::= 1

(6) цифра::= 2

(7) цифра::= 3

(8) цифра::= 4

(9) цифра::= 5

(10) цифра::= 6

(11) цифра::= 7

(12) цифра::= 8

(13) цифра::= 9

G1 = {{0,1,2,3,4,5,6,7,8,9}, {цифра, число, чс}, Р, число },

Где первое указанное множество – алфавит терминальных символов;

второе указанное множество – алфавит нетерминальных символов;

Р - 13 правил, указанных выше;

 число  - начальный символ грамматики.

Поскольку в формах Бэкуса-Науэра вариант “или” записывается знаком «|», то грамматику необходимо записать так:

число::= чс

чс::= чс цифра | цифра

цифра::= 0|1|2|3|4|5|6|7|8|9

Классификация Хомского

Грамматики можно классифицировать по виду их правил.

Существует четыре вида грамматик:

грамматика с фразовой структурой (на ней построены естественные языки);

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

контекстно-свободные (КС) грамматики, где каждое правило имеет вид:

   где  V, а  - цепочка в алфавите V V;

автоматные грамматики, где каждое правило имеет вид:

  х В или

  х, где

х  V, {,B}  V.

Язык L называется автоматным, контекстно-свободным, контекстно-зависимым или с фразовой структурой, если существует определяющая его грамматика G соответствующего типа, для которой L = L(G).

ВВЕДЕНИЕ………… ………………………………….…………….4

Глава 1. ЯЗЫКИ И ГРАММАТИКИ. ОБОЗНАЧЕНИЯ, ОПРЕДЕЛЕНИЯ И КЛАССИФИКАЦИЯ ………………………………………………………………………………6

1.1. Понятие грамматики языка. Обозначения……………………………………………7

1.2. Классификация грамматик по Хомскому………………………..…………………13

1.3. Техника построения КС- и А- грамматик…………………………………………..16

1.4. Синтаксические деревья вывода в КС-грамматиках. Представление

А-грамматик в виде графа состояний. Неоднозначность грамматик……………..19

1.5. Синтаксический анализ А-языков…………………………………………………..23

Упражнения……………………………………………………………………………….29

Глава 2. РАСПОЗНАВАТЕЛИ И АВТОМАТЫ .……………………………….….…………32

Глава 3. АВТОМАТНЫЕ ГРАММАТИКИ И КОНЕЧНЫЕ АВТОМАТЫ …………….35

3.1. Автоматные грамматики и конечные автоматы…………………………………….35

3.2.Эквивалентность недетерминированных и детерминированных А-грамматик…… 36

Упражнения………………………………………………………………………………… 41

Глава 4. ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ КОНТЕКСТНО-СВОБОДНЫХ

И АВТОМАТНЫХ ГРАММАТИК ………………………………………………..….42

4.2. Исключение тупиковых правил из грамматик………………………………………46

4.3. Обобщенные КС-грамматики и приведение грамматик к удлиняющей форме…….48

4.4. Устранение левой рекурсии и левая факторизация………………………………..…52

Упражнения………………………………………………………………………………….53

Глава 5. СВОЙСТВА АВТОМАТНЫХ И КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ …55

5.1. Общий вид цепочек А-языков и КС-языков………………………………………..55

5.2. Операции над языками………………………………………………………………….59

5.2.1. Операции над КС-языками………………………………………………………59

5.2.2. Операции над А-языками………………………………………………………62

5.2.3. Операции над К-языками………………………………………………………66

5.3. Выводы для практики…………….………………………………………………….67

5.4. Неоднозначность КС-грамматик и языков…………………………………………71

Упражнения…………………………………………………………………………....…74

Глава 6. СИНТАКСИЧЕСКИЙ АНАЛИЗ КС-языков ……………………………...……...75

6.1. Методы анализа КС-языков. Грамматики предшествования………………….…75

6.2. Грамматики предшествования Вирта……………………………………………...77

Грамматики предшествования Флойда…….……………………………………...79

Функции предшествования…………………………………………………………81

Упражнения………………………………………………………………………………84

Глава 7. ВВЕДЕНИЕ В СЕМАНТИКУ ……………………………………………………….85

7.1. Польская инверсная запись….……………………………………………………...85

7.2. Интерпретация ПОЛИЗа……………………………….………………………..….87

7.3. Генерирование команд по ПОЛИЗу………………………………….…………....89

7.4. Алгоритм Замельсона и Бауэра перевода выражений в ПОЛИЗ………..……….91

7.5. Атрибутные грамматики……………………………………………………………97

Упражнения……………………………………………………………………………..100

Глава 8. ОСНОВНЫЕ ФАЗЫ КОМПИЛЯЦИИ ……………………………………...……100

ЗАКЛЮЧЕНИЕ

ПРИЛОЖЕНИЕ …………………………………………………………………………………105

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ……………………………………………………….…….…115

Введение

Лингвистика - наука о языке. Математическая лингвистика - наука, занимающаяся формальными методами построения и изучения языков.

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

Импульсом к созданию и совершенствованию этой теории послужило развитие вычислительной техники и, как следствие, необходимость в средствах общения человека с ЭВМ. Во всех применениях ЭВМ должна понимать какой-либо язык, на котором пользователь может сообщить ей алгоритмы решения задач и исходные данные. Каждая ЭВМ имеет собственный язык машинных команд, представляемых в двоичном коде и отражающих отдельные операции процессора. На первых этапах развития вычислительной техники программисты общались с ЭВМ именно на этом примитивном языке, но человек не способен хорошо мыслить в категориях цифрового языка машины. Автоматизация программирования привела к созданию вначале языков ассемблера, а затем и алгоритмических языков высокого уровня, перевод с которых на родной машинный язык был поручен самой ЭВМ. Программы такого перевода называются трансляторами .

С проблемами объяснения языка машине сталкиваются многие разработчики программного обеспечения. Человеку свойственно изобретать новые языки. Здесь речь может идти не только о сложных компиляторах для новых алгоритмических языков программирования. Любая автоматизированная система должна понимать некоторый входной язык запросов. Новые информационные технологии предполагают привлечение конечного пользователя (ученого, конструктора, технолога, оператора) - специалиста в конкретной области, а не в области вычислительной техники и технологии программирования, к решению своих задач на ЭВМ. Для качественного решения этой проблемы между пользователем и ЭВМ должен существовать интеллектуальный интерфейс: пользователь должен ставить задачи и получать результаты их решения в терминах известной ему предметной области. То есть, необходима разработка широкого спектра предметно-ориентированных языков. Специалист в области программного обеспечения должен знать, как создаются языки и их программная поддержка.

Чтобы объяснить язык машине, необходимо четко представлять, как он устроен и как мы его понимаем. Задумавшись над этим, мы увидим, что не знаем, как мы понимаем наш родной язык. Процесс этого понимания подсознателен, интуитивен. Но чтобы создать транслятор, необходимо иметь алгоритм перевода текста в те действия, которые этот текст требует выполнить, а это, в свою очередь, требует формализации языка . Задачи формализации языка и решает математическая лингвистика. Естественные языки слишком сложны, и формализовать их полностью пока не удается. Алгоритмические языки, напротив, уже создаются в расчете на формализацию. Теория формальных языков - это наиболее развитая ветвь математической лингвистики, представляющая по сути методику объяснения языка машине. Прежде чем рассматривать определения, модели и методы этой теории, рассмотрим некоторые понятия на примерах из естественных языков.

Язык – это множество предложений (фраз), построенных по определенным правилам.

Грамматика - свод правил, определяющих принадлежность фразы языку.

Любой язык должен удовлетворять свойствам разрешимости и однозначности.

Язык разрешим , если за конечное время можно определить, что фраза или предложение принадлежит языку. Язык однозначен , если любая фраза понимается единственным образом.

Основными разделами грамматики являются синтаксис и семантика.

Синтаксис - свод правил, определяющих правильность построения предложений языка.

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

Предложение может быть синтаксически верным и семантически неверным.

Синтаксис обычно упрощается тем, что не все фразы языка обязаны иметь смысл. Зачастую трудно понять смысл футуристов или речь некоторых политиков. В этой связи интересен пример академика Л.В.Щербы: «Глокая куздра штеко будланула бокра и кудрячит бокренка». Это фраза на русском языке, так как её можно разобрать по членам предложения, но смысл её неясен.

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

<предложение>

Природу неоднозначности фразы можно объяснить на примере все того же дерева разбора для фразы «Мать любит дочь».

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

Формальный язык – это математическая абстракция, возникшая как обобщение обычных лингвистических понятий естественных языков. Теория формальных языков изучает в основном синтаксис языков и является фундаментом синтаксически управляемых процессов перевода, к которому можно отнести трансляцию, ассемблирование и компиляцию. Основы этой теории были заложены американским математиком Н. Хомским в конце 50-х начале 60-х годов и до настоящего времени продолжают развиваться вместе с развитием вычислительной техники. Остановимся на основных элементах этой теории.

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

Энциклопедичный YouTube

• 1 / 5

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

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

  Итак, грамматика определяется следующими характеристиками:

  Вывод

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

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

  Типы грамматик

  Терминальный алфавит:

  Σ {\displaystyle \Sigma } = {"0","1","2","3","4","5","6","7","8","9","+","-","*","/","(",")"}

  Нетерминальный алфавит:

  { ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА }

  1. ФОРМУЛА → {\displaystyle \to } ФОРМУЛА ЗНАК ФОРМУЛА (формула есть две формулы, соединенные знаком) 2. ФОРМУЛА → {\displaystyle \to } ЧИСЛО (формула есть число) 3. ФОРМУЛА → {\displaystyle \to } (ФОРМУЛА) (формула есть формула в скобках) 4. ЗНАК → {\displaystyle \to } + | - | * | / (знак есть плюс или минус, или умножить, или разделить) 5. ЧИСЛО → {\displaystyle \to } ЦИФРА (число есть цифра) 6. ЧИСЛО → {\displaystyle \to } ЧИСЛО ЦИФРА (число есть число и цифра) 7. ЦИФРА → {\displaystyle \to } 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (цифра есть 0 или 1, или... 9)

  Начальный нетерминал:

  ФОРМУЛА

  Вывод :

  Выведем формулу (12+5) с помощью перечисленных правил вывода. Для наглядности, стороны каждой замены показаны попарно, в каждой паре заменяемая часть подчеркнута.

  ФОРМУЛА → 3 {\displaystyle {\stackrel {3}{\to }}} (ФОРМУЛА) (ФОРМУЛА ) → 1 {\displaystyle {\stackrel {1}{\to }}} (ФОРМУЛА ЗНАК ФОРМУЛА ) (ФОРМУЛА ЗНАК ФОРМУЛА) → 4 {\displaystyle {\stackrel {4}{\to }}} (ФОРМУЛА + ФОРМУЛА) (ФОРМУЛА + ФОРМУЛА ) (ФОРМУЛА + ЧИСЛО ) (ФОРМУЛА + ЧИСЛО ) (ФОРМУЛА + ЦИФРА ) (ФОРМУЛА + ЦИФРА ) (ФОРМУЛА + 5 ) (ФОРМУЛА + 5) → 2 {\displaystyle {\stackrel {2}{\to }}} (ЧИСЛО + 5) (ЧИСЛО + 5) → 6 {\displaystyle {\stackrel {6}{\to }}} (ЧИСЛО ЦИФРА + 5) (ЧИСЛО ЦИФРА + 5) → 5 {\displaystyle {\stackrel {5}{\to }}} (ЦИФРА ЦИФРА + 5) (ЦИФРА ЦИФРА + 5) → 7 {\displaystyle {\stackrel {7}{\to }}} (1 ЦИФРА + 5) (1 ЦИФРА + 5) → 7 {\displaystyle {\stackrel {7}{\to }}} (1 2 + 5)