"ТРЯП (конспекты)"

конспекты занятий по курсу «Теория и реализация языков программирования» Занятие 2
^		=		_
2.1. Пример контекстно-зависимой грамматики На прошлой встрече студентам было предложено самостоятельно попробовать построить грамматику для задачи т.е. порождающей цепочки a, a⁴, a⁹, a¹⁶ и т.д.
Поэтому занятие началось с рассмотрения решения, предложенного студентом Александром С., основанного на том известном свойстве квадратов, что разности их степеней образуют арифметическую прогрессию (4-1 = 3, 9-4 = 5, 16-9 = 7 и т.д.) Решение оказалось правильным (желающие могут попробовать его воспроизвести), но не является единственным. Для разнообразия приведём ещё одно решение данной задачи, использующее более общий подход, который можно применить, к примеру, для порождения цепочек, длины которых являются кубами положительных целых чисел. Подход основан на собственно «квадратности» интересующих нас чисел, т.е. того, что каждое квадратное число представимо наподобие матрицы из n строк и
n столбцов единичных элементов (в связи с чем Пифагор и дал название подобным числам - квадратные, а среди других чисел по тому же принципу отметил треугольные, кубические, пирамидальные и т.п.).			Рис. Треугольные и квадратные числа по Пифагору
Для определённости поставим себе конечной целью создать неукорачивающую грамматику, т.е. такую, в которой ни одна из цепочек в ходе вывода не становится короче (желательность такого ограничения разъясняется в следующем параграфе). Итак, порождаем две группы по n элементов
Правила	Вид получаемой цепочки
S " CSD \| CD CD " DCA CA " AC A " a	Cⁿ Dⁿ C^n-1 DCA D^n-1 (A задерживает дальнейшее продвижение C) (DAⁿ)ⁿ Cⁿ (отработали все C) (Daⁿ)ⁿ Cⁿ
Получили , но что делать со знаками C и D? Сделав своё дело, они стали лишними. В грамматике общего вида такие знаки сокращают («увольняют»), а в КЗ-грамматиках – «переводят на другую работу» (в основные знаки). Но если мы просто дополним грамматику (пока даже не сдерживая решение неукорачиваемостью) правилами C " e, D " e, то вывод может закончиться в случайный момент времени, в том числе досрочно, и станет возможным порождение лишних цепочек. Например, S " CD " С " e (что уже не принадлежит языку, т.к. n > 0). Ниже будет приведено решение. Тем, кто настроился получить наибольшую отдачу от курса, советуем по возможности уделить несколько мгновений и попытаться самостоятельно осознать задачу и предложить её решение, а лишь затем сравнить его с нашим (может быть, у вас будет лучше!) * * * Итак, сложность состоит в том, что от знаков C и D необходимо освободиться, но только тогда, когда они полностью выполнят своё предназначение. Это противоречивое требование говорит не о нерешаемости данной задачи, а пока только о том, что она относится к определённому виду задач, по своему существу упирающихся в некоторое противоречие (что-то должно и быть и не быть, либо быть одновременно в разных местах или в разное время, быть сразу холодным и горячим, заряженным и незаряженным и т.д.) Общие подходы выявления и успешного разрешения противоречий в подобных задачах были собраны и обобщены более полувека назад (первая статья в 1956 г.) известным инженером Г.С. Альтшуллером в его Теории решения изобретательских задач [3]. В данном случае применяется типовой приём «изменение состава системы»: необходимо уточнить назначение и состав «действующих лиц» в правилах грамматики. Выделим для этого самый первый из команды знаков C (назовём его B) и самый последний из D (обозначим его E). Когда B и E встретятся, это и будет признаком полного завершения порождения знаков a. На основе подобных соображений до того единое древнее войско начали разделять на разные полки – передовые, засечные (заградительные), разведывательные и т.д. – каждые со своими задачами. Начнём вывод с начала (за S' обозначен новый вспомогательный знак):
Правила S " BS'E S' " CS'D \| CD CD " DCA CA " AC BD " B BA " AB CE " E BE " e A " a	Вид получаемой цепочки B S'E B Cⁿ Dⁿ E B C^n-1 (DA)ⁿ CE (C прошло первый раз) B\, (DAⁿ)ⁿ Cⁿ E (прошли все C) BAⁿ (DAⁿ)^n-1 Cⁿ E A^nn B Cⁿ E (ушли все D) A^nn B E (ушли все C) A^nn (ушли B и E) a^nn
Желаемое получили, но какой ценой (для B, C, D и E)? Прямо-таки сталинские приёмы. Точнее скажем, в военных или иных чрезвычайных условиях иначе, порой, и нет возможности поступить. А в более мирное время? Попробуем «соблюдать КЗОТ» и обойтись без сокращений. Снова:
Правила S' " BSE S " CSD \| CD CD " DCA CA " AC BD " aaB BA " AB CE " Eaa A " a BE " aaaa S " e \| a \| a⁴	Вид получаемой цепочки BSE B Cⁿ Dⁿ E B C^n-1 (DA)ⁿ C E (прошло первое C) B (DAⁿ)ⁿ Cⁿ E (прошли все C) a²BAⁿ(DAⁿ)^n-1CⁿE (a²Aⁿ)ⁿ BCⁿE (ушли все D) (a²Aⁿ)ⁿBEa²ⁿ (ушли все C) a^nn+2n BE a²ⁿ a^nn+4n+4 = a^{((n+2)*(n+2))} (восполнили частные решения)
Итак, если сокращать нельзя, достраиваем слово до ближайшего подходящего квадрата (ведь язык – это множество цепочек, а не одна «единственно верная»). В данном случае удобнее достроить слово до a^((n+2)(ⁿ⁺²⁾⁾, т.к. для достройки до a^((n+1)(ⁿ⁺¹⁾⁾ нам бы потребовалось перевести BE " a, т.е. опять что-то сократить. Некоторые дополнительные подробности решения данной задачи приведены в [1] (гл. 2). Чуть позже мы увидим в определениях, что в несокращающих грамматиках допускается переход аксиомы в пустую цепочку (e), если аксиома нигде более не встречается в правых частях правил (т.е. когда из начального ничего получают другое ничего). Заметим качественное отличие возможностей последней грамматики от ранее рассмотренных нами: она обладает своего рода памятью, т.е. возможностью учёта предыстории и обстоятельств вывода через учёт окружения заменяемого знака. Для порождения некоторых языков, включая последний из рассмотренных, эта возможность является существенной. Если бы мы могли заменять в каждом правиле только по одному знаку, то такой памяти грамматика была бы лишена. При более подробном изучении выразительных возможностей формальных грамматик в связи с накладываемыми на их правила ограничениями было предложено следующее деление грамматик (по Н.Хомскому).
2.2. Виды формальных грамматик 2.2.1. Грамматики общего вида (грамматики без ограничений или, по Хомскому, грамматики типа 0). Формальный вид правил грамматик j"y (j Î (NÈT)⁺; yÎ (NÈT)) Иными словами на их правила не накладывается никаких ограничений, т.е. одна любая цепочка из смеси знаков основного и вспомогательного алфавита языка (не нулевой длины) может заменяться на таким же образом составленную другую, в том числе нулевой длины, т.е. пустую. 2.2.2. Несокращающие* грамматики (или контекстно-зависимые грамматики (КЗГ) или грамматики типа 1). Англоязычное слово «контекст» (context) в данном случае переводится как «окружение» (заменяемого знака). Формальный вид правил грамматик j"y (j Î (NÈT)⁺; yÎ (NÈT)⁺; \|j\| £ \|y\|) То есть ни одно правило не должно сокращать длину цепочки в ходе вывода. Единственное уточнение связано со случаем, когда формальный язык содержит пустую цепочку. В этом случае её разрешается породить непосредственно из аксиомы (начального «Ничто»), причём знак аксиомы не должен встречаться в правых частях никакого из правил грамматики (когда он уже успел стать «чем-то»). 2.2.3. Контекстно-свободные грамматики (КСГ) или грамматики типа 2. Формальный вид правил грамматик A"y (A Î N; yÎ (NÈT); \|j\| £ \|y\|) То есть в левой части всех правил используется только один вспомогательный знак. Известна теорема, которая показывает, что использование в левой части правил только вспомогательных знаков (а не любого отдельного знака, в т.ч. из основного алфавита языка) не снижает выразительных возможностей грамматики. Эта теорема приведена, например, в [2] (гл. 1). 2.2.4. Праволинейные* грамматики (ПГ) или грамматики типа 3. Формальный вид правил грамматик A"yB \| y (A, B Î N; yÎ T) То есть в правой части любого правила может использоваться не более одного вспомогательного знака, причём если он есть, то он должен стоять справа от цепочки из основных знаков алфавита. Подобным образом вводятся и леволинейные грамматики, обладающие теми же выразительными возможностями: A"By \| y (A, B Î N; yÎ T). Задача 2.1. К каким видам относятся грамматики, рассмотренные нами на предыдущем и этом занятии? Пояснение. При определения вида грамматики обычно подразумевают ту грамматику, которая правильно описывает порождение языка и при этом имеет самые жёсткие ограничения на свои правила. Подобным образом определяют и вид языка (по виду самой простой, точнее самой ограниченной грамматики, которая его порождает). Задача 2.2. Попробуйте привести пример, показывающий, что смесь праволинейных и леволинейных правил в грамматике на деле позволяет строить КС-языки. Задача 2.3. Попробуйте самостоятельно доказать теорему, упомянутую в п. 2.2.3. Задача 2.4.** Вы можете попробовать свои силы в построении КЗГ, порождающих следующие языки: А. , т.е. цепочка с одинаковым числом вхождений букв a, b и c (винегрет). Б. (три богатыря) В. (Троица) Г. (лествица) Д. (зеркало)
2.3. Сравнительные достоинства и недостатки разных видов грамматик Из определений видно, что самыми большими выразительными возможностями и самыми малыми ограничениями на правила обладают грамматики общего вида. Возникает мысль – если они «самые мощные», то почему бы не использовать всегда только их? Тем более и примеры подобного подхода нам широко известны. Если мы, скажем, упоминаем об управляющей программе для ПЭВМ, то, скорее всего, подразумеваем Windows, если о текстовом редакторе для этой системы, то MsOffice. Такой подход сложился у нас в России во многом благодаря особенностям законодательства и его правоприменения, особенно в 90-е годы. Но в тех странах, где более строго осуществляется надзор за соблюдением авторского права (разумеется, не как главная и единственная мера, а как естественное продолжение поддержки законной предпринимательской деятельности и вплоть до воспитания и поддержания хороших привычек населения), где за дополнительные, в т.ч. редко используемые возможности Ms Word приходится доплачивать заметные суммы, мы наблюдаем большое разнообразие текстовых редакторов, в т.ч. более простых и, соответственно, более доступных. Так и в грамматиках за дополнительные выразительные возможности приходится расплачиваться большей сложностью и трудоёмкостью работы с ними. Для самых простых праволинейных грамматик (ПГ) известно множество формальных алгоритмов для работы с ними, в частности, как перейти от представления формального языка с помощью ПГ к его представлению в виде регулярного выражения или конечного автомата и обратно. Соответствующие языки получили название регулярных, а само слово формально означает возможность осуществить такое преобразование для любого регулярного языка, в частности, с помощью машины. Множество формальных алгоритмов известно и для контекстно-свободных языков, но эти алгоритмы уже более сложные. Наиболее заметно качественное различие между регулярными и КС-языками при сравнении устройства соответствующих формальных автоматов: для разбора КС-языков в автомат пришлось добавить ещё одно «устройство» - магазин (стек). Такие автоматы (они получили название магазинных) мы рассмотрим в нашем курсе несколько позже. Устройство соответствующих автоматов для КЗГ и грамматик общего вида (линейно-ограниченного автомата и его обобщения – машины Тьюринга) ещё более усложняются, а алгоритмы зачастую удаётся применить только для определённых частных случаев (каким являются и сами КЗГ для грамматики общего вида). Весьма сложно и трудоёмко (сравнительно с регулярными и КС-языками) использовать соответствующие грамматикам общего вида распознаватели и для программирования. Поэтому в огромном большинстве современных технических приложений стараются ограничиться использованием регулярных и КС-языков. Любопытно, что все наиболее распространённые языки программирования (от Fortran до С++) оказалось возможным осуществить с помощью подобного подхода. В тоже время известны и такие языки, представить которые с помощью КСГ невозможно, к примеру, LISP. Для понимания разницы между грамматиками общего вида и КЗГ обратим внимание на то, что линейно-ограниченный автомат – это, по существу, машина Тьюринга, только с ограничением на длину ленты. При создании технических устройств и программ это различие становится существенным. Заметив, что КЗГ являются естественной основой многих систем искусственного разума (в частности, баз знаний и основанных на них экспертных систем) и за их использованием видится большое будущее, в нашем вводном курсе мы основное внимание далее уделим более простым КС- и регулярным языкам и приёмам работы с ними.
== Ссылки == [1] Серебряков В.А. [и др.]. Теория и реализация языков программирования. М.: МЗ-Пресс, 2003 (1-е изд.) и 2006 (2-е изд). – 294 c. (681.3/ Т33). [2] Курочкин В.М., Столяров Л.Н., Сушков Б.Г., Флёров Ю.А. Теория и реализация языков программирования: Курс лекций. М.: МФТИ, 1978. [3] Альтшуллер Г.С. Найти идею. Теория решения изобретательских задач // Новосибирск: Наука (сиб. отд.), 1991 г. (имеется в библиотеке МФТИ) и др. книги автора. [4] Альтшуллер Г.С. Введение в ТРИЗ. Основные понятия и подходы // Электр. изд. Фонда Альтшуллера, условно-бесплатное для неком. распространения.
^		=		_