V.1.4. Задачи из раздела "Синтаксис и компиляция"

55. (Распознавание регулярных цепочек символов.)

а) Следующая синтаксическая диаграмма дает правило конструирования регулярного выражения из букв , и :

Примерами регулярных выражений, полученных по этой диаграмме, являются: ,, ,.

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

Указание. Разрешен только однократный просмотр исходной последовательности, т.е. слева направо, без возвратов.

б) решить задачу а), считая, что регулярное выражение задается одной из следующих диаграмм (на выбор):

1) Вставить рисунок на стр. 22

2) Вставить рисунок на стр. 22

3) Вставить рисунок на стр. 23

4) Вставить рисунок на стр. 23

56. (Распознавание некоторых синтаксических конструкций.)

Используя синтаксические диаграммы, определим следующие конструкции:

Имя:

Целое:

integer

Описание имя:

, char

имя

множество [ ]

целое

,

список формальных параметров:

integer

( имя: )

, char

;

ВСТАВИТЬ РИСУНОК НА СТР. 23

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

57. (Правильная последовательность скобок.) Правильная последовательность скобок (сокращенно: ППС) - это конструкция, определяемая следующей диаграммой:

( )

ППС

Вставить рисунок на стр. 24

Для заданной последовательности символов установить, является ли она ППС.

Поясняющие примеры. Последовательности ″()(())″ и ″( ()() )″ являются ППС, а ″(()))(.)(″ и ″)()()()(″ не являются.

Указание. При просмотре последовательности слева направо необходимо контролировать, чтобы число просмотренных закрывающих скобок не превышало числа открывающих. К концу просмотра число закрывающих скобок должно сравняться с числом открывающих.

58. (Язык Дика .) Слова языка определяются следующей синтаксической программой:

( слово )

[ слово ]

Вставить рисунок на стр. 24

Для заданной последовательности символов установить, является ли она. словом языка .

Поясняющие примеры. Последовательность скобок ″[(([()]))]()″ является словом языка а последовательность″[(]]″ нe является.

Указание. От "правильной последовательности скобок "предыдущей задачи "слова" этой задачи отличаются лишь наличием двух сортов скобок. Для контроля правильности закрытия скобок удобно использовать специальный массив-стек. При просмотре исходного текста в стек помещаются только открывающие скобки; если встречается закрывающая скобка, то соответствующая открывающая исключается из стека. Подчеркиваем, что закрыться может только последняя (!) из незакрытых скобок, причем если только она парна текущей закрывающей скобке. Поэтому стек либо заполняется слева, направо, либо освобождается справа налево. Замечание. Можно устранить использование стека, применяя технику, известную в математической логике под названием "гёделизация". Вместо стека заведем целочисленную переменную с начальным значением . Запоминанию в стеке символа"(" (или "[") соответствует преобразование (или ). Исключению последней скобки из стека соответствует преобразование . Последняя, скобка в стеке суть "(", когда четно, и "[", когда нечетно. Почему текущее значениевсегда будет однозначно кодировать текущее состояние стека ? Как обобщить это кодирование на случай сортов скобок ?

59. (Использование стека.) Текст , составленный из букв "" и "", называется допустимым, если 1) число вхождений буквы "" не превышает числавхождений буквы "" при чтении слева направо и 2) число букв "" и "B " в тексте одинаково.

а) Установить, является ли заданный текст допустимым.

б) Пусть заданный допустимый текст длиныПреобразовать входной текст длины n (символов) в выходной текст, выполняя следующие действия. Пусть α и β − очередные символы соответственно текста и входного текста (при чтении текстов слева направо). Тогда, если, тоβ помещается в стек; Если же , то. символ, записанный в вершине стека, перемещается в выходной текст.

Пояснения. 1) Стек − это линейный список, в котором все включения и исключения осуществляются на правом конце, называемом вершиной стека. Таким образом, стек либо заполняется слева направо, либо освобождается справа налево. Для моделирования стека здесь рекомендуется использовать массив. 2) "" − пример допустимого текста . Применяя его к входному тексту "", получаем выходной текст "".

60. (Использование дека с ограниченным выходом.) Текст, составленный из букв , и , называется допустимым, если 1) число вхождений буквы не превышает суммарного числа вхождений букв ипри чтении слева направо; 2) общее число вхождений в текст буквы равно суммарному числу вхождений в текст букв и; (3) если при чтении текста слева направо в некоторый момент времени число вхождений буквы равно, а число вхожденийбукв итакже равно, то-ыйсимвол текста есть , 4) сочетание букв не допустимо, если это не противоречит 3).

а) Установить, является ли заданный текст допустимым.

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

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

61. (Выделение подтерма.) Термы образуются из переменных и функциональных символов. Функциональные символы − это имена функций; каждый функциональный символ имеет размерность (или местность, или арность) − число аргументов функции. Общее определение терма таково:

1) переменная есть терм;

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

X

Y

Z

О

Д

Т терм терм терм

Например, − терм, который для наглядности часто изображают в виде ,,,,).Одним из его подтермов является терм .

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

Указание. Чтобы вычислить номер конечной позиции подтерма, потребуется в процессе просмотра подтерма слева направо считать количество еще незаполненных аргументных мест. Подтерм, начинающийся с функционального символа , имеетаргументных места. Переменная заполняет в точности одно аргументное место. Функциональный символ размерности отменяет необходимость заполнить одно аргументное место, но вызывает необходимость заполнитьаргументных мест. Когда число аргументных мест, требующих заполнения, станет равным нулю, тогда подтерм и закончится.

62. (Синтаксический анализ простых арифметических выражений.) Арифметические выражения в скобочной () и бесскобочной() нотациях определяются следующим образом:

Пример записи одного и того же выражения в скобочной и бесскобочной нотациях: и.

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

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

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

63. (Перевод в прямую польскую запись. Обратный перевод.)

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

б) Выполнить обратное преобразование (переход от к).

Указания. Предположим, что строка символов представляетили.

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

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

64. (Обработка арифметических выражений. Перевод в польскую запись и вычисление значения.) Здесь рассматриваются арифметические выражения, составленные из переменных, знаков операций и круглых скобок. Для обозначения переменных используются одиночные буквы. В качестве знаков операций используются , , , и. Это − бинарные операции: сложение, вычитание, умножение, деление и возведение в степень. Операции имеют следующие приоритеты (отражающие старшинство операций):

операция	+−	∗ ∕
приоритет	1	2	3

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

а) Преобразовать инфиксную запись арифметического выражения в суффиксную.

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

Указания. а) Переход от инфиксной записи к суффиксной может быть осуществлен за один последовательный просмотр. Алгоритм преобразования основан на использовании стека − памяти, действующей по принципу "последним пришел – первым ушел":

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

2) Если − открывающая скобка, то заносится в стек с приоритетом .

3) Если − буква, то помещается в выходную строку.

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

5) Если − закрывающая скобка, то операции из стека последовательно переносятся в выходную строку до тех пор, пока на вершине стека не окажется открывающая скобка; эта скобка уничтожается.

6) Если просмотр выходной строки еще не закончен, то переходим на шаг 1); в противном случае из стека последовательно переносятся все оставшиеся операции.

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

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

2) Если очередной символ выражения есть знак операции , то из стека извлекаются два числовых значения. Пусть эти значения суть и, причемизвлечено первым. Над ними выполняется соответствующая операция и значение заносится в стек.

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