В.Н. Пильщиков - Язык Плэнер (1156455), страница 18
Текст из файла (страница 18)
Затем к сопоставляемому с этим образцом сегменту добавляется очередной злемент списка Е, и процесс сопоставления возобновляется с этой точки. Может окаааться, что в списке Р уже не осталось ии одного сегментного образца, для которого возможно наращивание сопоставляемого с ним сегмента. В таком случае сопоставление списков прекращается — оно неудачно. При этом все его побочные аффекты уничтожаются. Поясним описанный алгоритм сопоставления на следузощем примере: (!Я ((еХ еТ.Х !»Х) (А'+ В Х (А + В) / СЦ Здесь образцу )еХ сначала ставится в соответствии пустой сег- мент, поэтому переменная Х получает значение ().
Затем обраэец «У сопоставляется с атомом А, в результате чего переменной т присваивается вначение А. Теперь сопоставляются .Х и +. Зто сопоставление неудачно (неременная Х имеет сейчас эначение ()), поэтому переменные Х и г «теряют» свои значения () и А и происходит возврат к первому элементу обраэца-списка. На этот рав образцу 1«Х ставится в соответствии сегмент иэ одного элемента А, и переменная Х получает теперь значение (А).
После этого образец «У удачно сапоставится с атомом +, однако обраэцу .Х вновь не будет соответствия. Поэтому снова происходит воэврат к обраацу 1«Х, и т. д. В конце концов этому образцу будет поставлен в соответствие сегмент А + В, и переменная Х получит вначение (А + В). Далее образец « т' удачно сопоставится с атомом )(, в результате чего переменной х присвоится значение »(.
Сопоставление образца .Х с очередным элементом анализируемого списка — с подсписком (А + В) — на этот раэ удачно, поэтому далее ищется соответствие обраэцу 1«Е. Поскольку этот сегментный образец является последним в образцесппске, ему ставится в соответствие весь остаток аналиэируемого списка, т. е. сегмент иэ элементов / и С. Следовательно, переменная Е получает аначенке (/ С). Ыа атом сопоставление списков завершается, оно удачно. За переменными Х, г и Е сохраняются значения, полученные ими во время сопоставления: (А + В), )( и (/ С). Отметим, что иэ описанного алгоритма сопоставления списков вытекает следующее правило: если имеется несколько вариантов удачного сопоставления простого абраэца с выражением, то всегда рассматривается только один иэ иих. В частности, при сопоставлении списков невозможен возврат к сегментным образцам, находящимся не на верхнем уровне обрааца-списка.
В связи с этим сопоставление [Б ((1«Х А 1«У) .Х) ((А В А) (А В) Ц неудачно. Действительно, при сопоставленин первых элементов (подсписков) переменная Х получает эначение (), а перемениаи »' — значение (В А), после чего сопоставление вторых влементов окааывается неудачным.
Но несмотря на это, другой воэможиый вариант удачйого сопоставления подсписков, в котором переменная Х получила бы аначение (А В), а переменная г — эначение (), не рассматривается. 2.4. Примеры использования образцов Приведем два примера использования образцов для аналиаа структуры данных. Первый пример в это символьное дифференцирование много- членов. Под «многочлепом» будем понимать «одпочлеп» или до- Зб следовательность «одночленов», соединенных анаками +. «Одно- член> — это «переменная» (плэнерский идентификатор), либо неотрицательное число, либо «степень» вида х 7 и, где и — «переменная», а и — целое чнсло, большев или равное 2; либо последовательность таких конструкций, соедпненных сивками Х.
Весь многочлен эаключается в круглые скобки. Примеры таких много- членов: (2), (Х Х У), (6 Х Х + Х ) 3 Х У + Х [ 2) Следующая функция строкт список, представляющий собой запись производной многочлена Р по переменной Ч: ,[ВЕРН»)Е 01Р (ЬАМВВА (Р Ч) [РВОО (Т) [СОЖ0 ([1»(ОТ [МЕМВ .Ч .Р]] (О)) ([13 (Ч) .Р] (1)) ([13 (!»Т + гвР) .Р] (<01Р.Т.Ч>+ <01Р.Р.Ч>)) ([13 (!»Т Х !»Р) .Р] ((01Р .Т .Ч) Х !.Р + !.Т Х (01Р .Р Ч>)) ([13 ( Ч Ф 2) Р] (2 Х .Ч)) ([13 (.Ч ) «Т) .Р] (Т Х .Ч '! [ — .Т 1]))] ])] В первой клаузе условного выражения проверяется, входит лн в многочлен Р переменная, по которой ведется дифференг[ирование.
Во второй клаузе выявляется случай, когда многочлен состоит только иэ этой переменной. В остальных клауэах с помощью обраэцов определяется структура многочлена: сумма ли это, одно- член или степепь (особо выделен случай степени с понаэателем 2, чтобы избежать появления в производной степеней с показателем 1). Этими же обраэцами мпогочлеи раэбявается иа отдельные компоненты. Например, у многочлена (6 Х Х' + Х 7 3 Х У + Х ) 2) выделяются первое слагаемое Т = (6 Х Х) и остальные слагаемые Р = (Х 7 3 Х У + Х 7 2). После этого по соответствующей формуле дифференцирования строится список, являющийся проиаводной многочлена. Так, для укааанного выше многочлена применяется формула (Т + Р)' = (Т' + Р'), причем для получения производных Т' и Р' рекурсивно применяется сама функция 01Р (считаем, что значением Ч явлнется атом Х): (01Р.Т.Ч> -» О Х Х+ 6 Х 1 (01Р .Р Ч> 3 Х Х ] 2 Х У+ Х ( 3 Х О+ 2 Х Х Далее эти производные соединяются анаком + и ааключаются в круглые скобки, что и дает прои»водную исходного многочлена: (О Х Х+ 6 Х 1 + 3 Х Х ] 2 Х У + Х] 3Х О+2ХХ) 67 Как.видно, полученную производную следовало бы упростить, однако мы не будем ааниматься этой проблемой.
Следующий пример, который мы рассмотрим,— это задача интерпретации программ, записанных на некотором модельном языке. Синтаксис этого языка описывается следующпми металингвистическимн формулами (в ннх для большеи 'наглядности пробелы указываются явно, уголки же используются как метасимволы, а не как плзнерские скобки): (програмиа):: = ((описание) (операторы)) <описание):: = (ЧАК <переменные)) (переменные) :: = (пусто)!(переменная) (переменные) (операторы) :: = (пусто)((оператор) (операторы) (оператор)::= ((непомеченный оператор)) ) ((метка) : (непомеченный оператор)) (непомеченный оператор)::= (оператор перехода) [ (оператор вывода) ) (оператор присваивания) ) (условный оператор) (оператор перехода):: = СОТО (метка) (оператор вывода):: ОСТР()Т (выражение) (оператор присваивания):: = (переменная) = (выражение) (условный оператор>::= 1Р <условие) ТНЕХ ((непомеченный оператор)) ЕЬБЕ ((непомеченный оператор)) (условие):: = ((выражение) (знак отношения) (выраже.
ние)) (анак отношения):: = Ф [ = (выражение):: (чнсло) [ (переменная) [ (переменная) + (число) Под «моткойэ и «переменнойэ понимается любой плэнерский идентификатор, под «числом» вЂ” любое плзнерское число. Семантика описанного языка естественна и очевидна. Пример программы на атом языке: ((ЧАК Б 1) (Я = О) (1 = О) (1: 1 = 1 +.Ц (Я = Я + 2) (1Р (1 ~ 20) ТНЕН (СОТО Ь) Е1 ЯЕ (0()ТРСТ Я))) Интерпретатор этого языка мы опишем в виде нескольких функций.
Основной из них является функция 1г)ТЕКР, аргумент которой — интерпретируемая программа. [ВЕР1НЕ 1ХТЕКР (ЬАМВВА (РКОС) [РКОО (УАКЯ (АЬ ()) ОРЯ ОР ЬАВ) [СОХО ([1Я ((ЧАК !«УАКБ) (эРКОО) .РКОО)) (Т [ЕКК 1 ( )))) [100Р Ч .ЧАНЯ [СОНЭ ([10 .Ч] [БЕТ АЬ (!.АЬ (.Ч ())Ц) (Т [ЕВК 2 .Ч]Ц] [БЕТ ОРЯ .РКОО] Ь [СОР)П ([Р1Р! ОР ОРЯ] [КЕТОВА ЕР!О])] [18 («1.АЭ: !«ОР) .ОР] [ЕЧОР .ОР] [6(г ь]])] Эта функция строит список АЬ, в котором будут храниться переменные интерпретируемой программы и их значения. Первоначально этот список имеет вид ((«~ ( )) (из ( Ц ...
(«ь ( Ц),. где ие — переменные, описанные в начале интерпретируемой программы, а ( ) означает отсутствие значения у переменной. В дальнейшем в зтот список будут ааноситься значения, получаемые переменными зь Например, когда переменной из будет присвоено значение 5, список АЬ будет преобразован к виду ((и, 5) (о. ()) ") ' Возмошпо, что описание переменных в интерпретируемой программе задано неправильно. Тогда функция 1Р!ТЕКР передает управление функции ЕВК, которая печатает оообщение об ошиб-' ке и прекращает интерпретацию. После обработки описания функция 1г(ТЕКР начинает последовательное выполнение операторов интерпретируемой программы. Список всех операторов атой программы хранится в переменной РВОО, а список операторов, начиная с того, который должен быть выполнен в текущий момент,— в переменной ОРЯ. Если список ОРЯ пуст, тогда функция 1НТЕВР завершает интерпретацию и выдает значение ЕНП.
Иначе от списка ОРЯ отделяется первый оператор ОР, из которого удаляется метка, если она есть. Получившийся непомеченный оператор выполняется с помощью функции ЕЧОР. Далее описанный цикл повторяется. [ПЕР!г!Е ЕЧОР (ЬАМВРА (ОР) [РВ06 (Е Ь Ч В ОР! ОР2) [СОНЭ ([18 (ОСТРОТ !«Е) .ОР) [РВ1Р(Т [ЕЧЕХР,Е]]) ([18 (СОТО «Ь) .ОР] [СОТО .Ь]) ([18 («Ч = !»Е) .ОР] [РПТЧАЬ .Ч [ЕЧЕХР .Е]]) ([18 (1Р «В ТНЕ!Ч «ОР! ЕЬЯЕ «ОР2) .ОР) [СОг)П ([ЕЧВ001 .В] [ЕЧОР .ОРЦ) (Т [ЕЧОР .ОР2])]) (Т [ЕВВ 3 .ОР]Ц ]Ц 89 Функция ЕУОР интерпретирует действия непомеченного оператора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
