£ сс

10. ОБОБЩЁННЫЕ ВЫРАЖЕНИЯ

Арифметические выражения, в которых операторы имеют более двух уровней приоритета, могут быть разобраны путём написания дополнительных вспомогательных функций, промежуточных между term и expr. Функция chainr, имеющая в качестве первого параметра функцию с приоритетом на один уровень ниже, чем у chainr, используется в каждом определении.

Если существует девять уровней приоритетов, то мы получаем девять копий почти что одинакового текста. Так не должно быть. Наличие функций, напоминающих друг друга, является сигналом о том, что нам следует написать обобщённую функцию, в которой различия описываются дополнительными параметрами. Поэтому давайте внимательно рассмотрим отличия функций term и expr. Вот они:

1)Операторы и связанные конструкторы деревьев, используемые во втором параметре chainr.

2)Парсер, используемый в качестве первого параметра chainr.

Обобщённая функция будет иметь эти два отличия в качестве дополнительных параметров: первое в виде списка пар, второе в виде функции разбора:

type Op a gen

gen ops p where f (s, c)

(Char, a -> a -> a)

[Op a] -> Parser Char a -> Parser Char a chainr p (choice (map f ops)) symbol s <@ const c

Если, кроме того, мы определим для быстроты записи:

multis addis

то expr и term могут быть определены как частичная параметризация функции gen:

expr= gen addis term

term= gen multis fact

Подставляя определение функции term в определение функции expr мы получаем: expr= addis "gen" (multis "gen" fact)

что опытный функциональный программист сразу определит как применение функции foldr:

expr= foldr gen fact [addis, multis]

С помощью этого определения обобщение для случаев большего числа приоритетов производится просто путём расширения списка списков операторов.

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

11. ПРИМЕНЕНИЕ К САМОМУ СЕБЕ

Не смотря на то, что в предыдущих частях показано, что отдельные формализмы для грамматик не нужны, пользователи могут захотеть придерживаться, например, нотации БНФ для написания грамматик. Поэтому в этой части мы напишем функцию, преобразующую БНФ-грамматику в парсер. БНФ-грамматика задается в виде строки и подвергается анализу конечно же с помощью парсера. Этот парсер такой, что возвращаемое им «дерево» разбора также является парсером! Так что название этой части является обоснованным.

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

£ сс

11.1.Окружение

Окружением является список пар, в котором может быть представлено конечное отображение. Функция assoc может быть использована для связывания величины со своим образом, полученным данным отображением.

type Env a b= [(a, b)]

assoc :: Eq s => Envs d -> s -> d

assoc ((u, v) : ws) x x == u =v

otherwise =assoc ws x

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

mapenv:: (a -> b) -> Env s a -> Env s b

mapenv f []= []

mapenv f ((x, v) : ws) = (x, f v) : mapenv f ws

11.2.Грамматика

В грамматике используются терминальные и нетерминальные символы. И те и другие представлены последовательностью символов. Мы приводим тип данных, содержащий две альтернативы, используемые для представления двух типов символов:

data Symbol = Term String Nont String

ФП 02005-06 01