£ то

св а: =з

Правая часть порождающего правила состоит из некоторого количества альтернатив, каждая из которых является списком символов:

type Alt type Rhs

[Symbol] [Alt]

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

type Gram= Env Symbol Rhs

Грамматики можно легко описать, используя нотацию БНФ. Мы напишем анализатор для этой нотации, который в качестве дерева разбора будет возвращать величину типа Gram. Парсер БНФ-грамматик параметризирован анализатором нетерминалов и анализатором терминалов, так что позже мы сможем принять различные соглашения относительно их представления. Мы будем использовать элементарные парсеры sptoken и spsymbol вместо token и symbol для того, чтобы допустить дополнительную свободу в представлении грамматик.

Parser Char String -> Parser Char String -> Parser Char Gram

bnf nontp termp

many rule where rule

(nont <*>

sptoken "::=" *> rhs <* spsymbol .) rhs = listOf alt (spsymbol ) alt = many (term <> nont) term = sp termp <@ Term nont = sp nontp <@ Nont

БНФ-грамматика состоит из правил «many», каждое из которых состоит из нетерминала, отделённого символом «::=» от rhs и оканчивается точкой. rhs - это список альтернатив, разделённых символами «», где каждая альтернатива состоит из символов «many», терминалов или нетерминалов. Терминалы и нетерминалы распознаются парсерами, заданными в качестве параметра функции bnf.

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

blockgram = "BLOCK ::= begin BLOCK end BLOCK ."

Здесь мы использовали соглашение обозначать нетерминалы заглавными буквами, а терминалы - строчными. Мы укажем эти соглашения при вызове функций bnf. Например:

where nont term

some (bnf nont term) blockgram greedy1 (satisfy isUpper) greedy1 (satisfy isLower)

Результатом работы этой функции test является следующее окружение:

[(Nont "BLOCK",[[Term "begin", Nont "BLOCK", Term "end", Nont "BLOCK"],[]])]

11.3. Деревья разбора

Мы больше не можем использовать структуры данных, специально созданные для одной конкретной грамматики, как, например, тип Expr из части 9. Вместо этого мы определим общую структуру данных, которая описывает деревья разбора для предложений произвольной грамматики. Мы просто назовём их Tree; они являются частными случаями сильноветвящихся деревьев:

data Tree= Node Symbol [Tree]

11.4. Парсеры вместо грамматик

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

parsGram:: Gram -> Symbol -> Parser Symbol Tree

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

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

parsGram

parsGram gram start

parsSym

parsSym s @ (Term t) parsSym s @ (Nont n)

parsAlt parsAlt

parsRhs parsRhs

Gram -> Symbol -> Parser Symbol Tree parsSym start

:: Symbol -> Parser Symbol Tree = symbol s <@ const [] <@ Node s = parsRhs (assoc gram s) <@ Node s

:: Alt -> Parser Symbol [Tree] = sequence . map parsSym

:: Rhs -> Parser Symbol [Tree] = choice . map parsAlt

Функция parsSym различает случаи функций для терминальных и нетерминальных символов. Для терминальных символов создается парсер, который просто распознаёт этот символ, а затем создается элемент Node для дерева разбора.

Упражнение 18. Для чего используется преобразование <@ const []?

В случае нетерминальных символов производится поиск соответствующего правила в грамматике, которое в итоге становится окружением. Затем используется функция parsRhs, создающая парсер для rhs. Функция parsRhs создаёт парсеры для каждой альтернативы и применяет к ним функцию choice. В заключение функция parseAlt создаёт парсеры для отдельных символов в альтернативе и комбинирует их с помощью функции sequence.

11.5. Генератор парсеров

В теоретических учебниках контекстно-свободная грамматика обычно описывается четверкой (N, T, R, S), состоящей из множества нетерминалов, множества терминалов, множества правил и начального символа. Давайте сделаем также, представляя множество символом с помощью парсера:

type SymbolSet type CFG

Parser Char String

(SymbolSet, SymbolSet, String, Symbol)

Теперь мы дадим определение функции, которая берёт такую четвёрку и возвращает парсер для этого языка. Не будет ли слишком самонадеянно назвать это «генератором парсеров»?

parsgen :: CFG -> Parser Symbol Tree parsgen (nontp, termp, bnfstring, start)

= some (bnf nontp termp <@ parsGram) bnfstring start

Множества нетерминалов и терминалов представлены их парсерами. Грамматикой является строка, записанная в нотации БНФ. Парсер, получающийся в результате, принимает на вход список элементов типа Symbol (терминальных символов), а возвращает величину типа Tree.

11.6. Лексические блоки трансляторов

Получаемый парсер принимает на вход элементы типа Symbol вместо элементов типа Char. Если мы хотим применить его к строке символов, эта строка предварительно должна быть представлена лексическим блоком транслятора в виде последовательности токенов.

Для этого мы создадим библиотечную функцию twopass, которая использует два парсера: один преобразовывает символы в токены, а другой - токены в деревья. Эта функция не нуждается ни в одном из свойств «символ», «токен» и «дерево» и таким образом имеет полиморфный тип:

twopass:: Parser a b -> Parser b c -> Parser a c