John Harrison - Введение в функциональное программирование (1108517), страница 29
Текст из файла (страница 29)
выше):#parser "sin(x + y) * cos(2 * x + y)";;- : term =Fn("*",[Fn ("sin", [Fn ("+", [Var "x"; Var "y"])]);Fn ("cos", [Fn ("+", [Fn ("*", [Const "2"; Var "x"]);Var "y"])])])#install_printer "print_term";;- : unit = ()#parser "sin(x + y) * cos(2 * x + y)";;- : term = ‘sin(x + y) * cos(2 * x + y)‘9.2.5Автоматический учёт приоритетовСинтаксический анализатор, рассмотренный выше, реализует разбордвух инфиксных операций в явном виде. Однако, для большего удобства исогласованности с нашим подходом к выводу выражений, следует учесть введенную126Глава 9.
Примеры9.2. Синтаксический анализранее информацию о множестве доступных инфиксных операций. Более того,наличие даже двух различных бинарных операций заставляет прибегать кискусственным приёмам при построении грамматики и программы разбора —нетрудно представить себе, во что превратится работа, например, с дюжиной такихопераций. Таким образом, несомненна полезность автоматического порожденияиерархии анализаторов для каждой доступной операции, упорядоченных согласноих приоритетам. Решение этой задачи достаточно просто.
Прежде всего, зададимобобщённую функцию, которая принимает в качестве аргумента анализаторсинтаксической категории, которая на данном уровне приоритета считаетсяатомарным выражением, и возвращает новый анализатор, предназначенный дляразбора последовательности таких атомарных выражений, объединенных заданнойоперацией. Заметим, что того же эффекта мы можем добиться при помощи нашегонабора комбинаторов, но функция, приведенная ниже, проще и эффективнее.l e t rec binop op p a r s e r i n p u t =l e t atom1 , r e s t 1 as r e s u l t = p a r s e r i n p u t ini f not r e s t 1 = [ ] & hd r e s t 1 = Other op thenl e t atom2 , r e s t 2 = binop op p a r s e r ( t l r e s t 1 ) inFn ( op , [ atom1 ; atom2 ] ) , r e s t 2else r e s u l t ; ;Далее определим функции, которые извлекают из нашего ассоциативного спискаочередную операцию с наименьшим (равным предыдущему) приоритетом. Еслисписок был заранее сортирован по приоритетам, мы можем просто выбиратьочередной элемент по порядку следования.let findmin l = i t l i s t( fun (_, pr1 as p1 ) (_, pr2 as p2 ) −> i f pr1 <= pr2 then p1 e l s e p2 )( t l l ) ( hd l ) ; ;l e t rec d e l e t e x ( h : : t ) = i f h = x then t e l s e h : : ( d e l e t e x t ) ; ;Обобщенный анализатор множества бинарных операций с приоритетами:l e t rec p r e c e d e n c e i l i s t p a r s e r i n p u t =i f i l i s t = [ ] then p a r s e r i n p u t e l s el e t opp = f i n d m i n i l i s t inl e t i l i s t ’ = d e l e t e opp i l i s t inbinop ( f s t opp ) ( p r e c e d e n c e i l i s t ’ p a r s e r ) i n p u t ; ;Использование этого вспомогательного анализатора позволяет упростить основнойи сделать его более общим:1279.2.
Синтаксический анализГлава 9. Примерыl e t rec atom i n p u t= ( name ++ a ( Other " ( " ) ++ t e r m l i s t ++ a ( Other " ) " )>> ( fun ( ( ( name ,_) , a r g s ) ,_) −> Fn ( name , a r g s ) )| | name>> ( fun s −> Var s )| | numeral>> ( fun s −> Const s )| | a ( Other " ( " ) ++ term ++ a ( Other " ) " )>> ( snd o f s t )| | a ( Other "−" ) ++ atom>> snd ) i n p u tand term i n p u t = p r e c e d e n c e ( ! i n f i x e s ) atom i n p u tand t e r m l i s t i n p u t= ( term ++ a ( Other " , " ) ++ t e r m l i s t>> ( fun ( ( h ,_) , t ) −> h : : t )| | term>> ( fun h −> [ h ] ) ) i n p u t ; ;l e t p a r s e r = f s t o ( term ++ f i n i s h e d >> f s t ) o l e x ; ;Пример разбора выражения:#parser "2 * sin(x)^2 + 2 * sin(y)^2 - 2";;- : term =Fn("+",[Fn ("*", [Const "2"; Fn ("^", [Fn ("sin", [Var "x"]);Const "2"])]);Fn("-",[Fn ("*", [Const "2"; Fn ("^", [Fn ("sin", [Var "y"]);Const "2"])]);Const "2"])])#install_printer "print_term";;- : unit = ()#parser "2 * sin(x)^2 + 2 * sin(y)^2 - 2";;- : term = ‘2 * sin(x) ^ 2 + (2 * sin(y) ^ 2 - 2)‘9.2.6Недостатки методаНаш подход к лексическому и синтаксическому анализу не отличается особойэффективностью.
Действительно, CAML и некоторые другие реализации языка MLвключают генератор синтаксических анализаторов для LR-грамматик, аналогичныйпопулярной в Unix-среде системе YACC (Yet Another Compiler Compiler) дляязыка C. Эти генераторы не только охватывают более широкий класс грамматик,но и производят более эффективные анализаторы. Однако, мы считаем, чтопредложенный метод достаточно прозрачен, приемлем в большинстве случаеви является хорошим введением в программирование с использованием функцийвысших порядков.Небольшая доработка некоторых особенно ресурсоёмких фрагментованализатора может заметно улучшить его общую эффективность.
Так, при128Глава 9. Примеры9.2. Синтаксический анализналичии в одной синтаксической категории нескольких продукций с общимпрефиксом, следует избегать его многократного анализа, который может оказатьсянетривиальным. Примером подобной ситуации служат правила вывода для термов:term −→ name(termlist)|name| ···Мы намеренно поместили в ходе реализации более длинное правило первым, таккак в противном случае успешное чтение имени приведёт в дальнейшем к отказупри попытке разбора списка аргументов.
Однако, возникающее при этом повторноесканирование избыточно. В данном случае цена избыточности невелика, посколькуповторному анализу подвергается лишь одна лексема, но потенциальные накладныерасходы при разборе termlist могут оказаться более существенными:let . . .and t e r m l i s t i n p u t= ( term ++ a ( Other " , " ) ++ t e r m l i s t>> ( fun ( ( h ,_) , t ) −> h : : t )| | term>> ( fun h −> [ h ] ) ) i n p u t ; ;В отличие от предыдущего примера, здесь повторному сканированию вслучае возврата подвергается целый терм, который может быть сколь угодносложным.
Существуют различные способы избежать этого. Например, мы можемпреобразовать правила вывода так, чтобы выбор одного из них происходил уже послетого, как прочитан начальный терм. Комбинатор many позволяет легко устранитьявную рекурсию:let . . .and t e r m l i s t i n p u t= term ++ many ( a ( Other " , " ) ++ term >> snd )>> ( fun ( h , t ) −> h : : t ) i n p u t ; ;Таким образом, итоговая реализация анализатора имеет вид:1299.2. Синтаксический анализГлава 9.
Примерыl e t rec atom i n p u t= ( name ++ a ( Other " ( " ) ++ t e r m l i s t ++ a ( Other " ) " )>> ( fun ( ( ( name ,_) , a r g s ) ,_) −> Fn ( name , a r g s ) )| | name>> ( fun s −> Var s )| | numeral>> ( fun s −> Const s )| | a ( Other " ( " ) ++ term ++ a ( Other " ) " )>> ( snd o f s t )| | a ( Other "−" ) ++ atom>> snd ) i n p u tand term i n p u t = p r e c e d e n c e ( ! i n f i x e s ) atom i n p u tand t e r m l i s t i n p u t= ( term ++ many ( a ( Other " , " ) ++ term >> snd )>> ( fun ( h , t ) −> h : : t ) ) i n p u t ; ;Общим недостатком нашего подхода и метода рекурсивного спуска в целомявляются проблемы с разбором леворекурсивных грамматик. Правило выводанекоторой синтаксической категории называется леворекурсивным, если его праваячасть начинается с этой же категории.
Например, если бы мы попытались определитьв нашей грамматике левоассоциативную операцию сложения, это можно было бывыразить так:term −→ term + mulexp|mulexpПрямое отображение этих правил вывода на язык ML приведет к зацикливанию,поскольку функция term будет вызываться для одного и того же подвыраженияснова и снова. Существуют различные, причём не слишком универсальные, способырешения проблемы. Например, мы можем реализовать в явном виде цикл вместорекурсии, применение которой в данном контексте не имеет под собой особыхоснований.
Для этого воспользуемся стандартными комбинаторами наподобие many,чтобы получить список деревьев разбора подвыражений вида mulexp, после чегопостроим по этому списку результирующее левоассоциативное дерево.В заключение отметим, что наша обработка ошибок разбора не отличаетсяособой элегантностью. При возникновении любого затруднения мы порождаемисключение Noparse, обработка которого представляет собой возврат. Такоеповедение, однако, не всегда подходит для типичных грамматик. В лучшем случае,оно приведёт к интенсивному повторному сканированию, но может вызвать ипоследовательность возвратов вплоть до корня дерева разбора. Например, встретивв ходе анализа подвыражение 5 + мы ожидаем, что вслед за символом + следуеточередной терм. Если он не был найден, следует выдать пользователю внятноесообщение об ошибке вместо простой генерации Noparse и, возможно, последующихбезуспешных попыток разобрать выражение другим путём.130Глава 9.
Примеры9.39.3. Точная арифметика вещественных чиселТочная арифметика вещественных чиселМашинная реализация вещественной арифметики обычно используетприближённое представление чисел в формате с плавающей точкой. В общемслучае, мы можем оперировать вещественными числами (либо вручную, либо припомощи компьютера) лишь в том случае, когда они имеют то или иное конечноепредставление. Возникает вопрос, уместно ли говорить о ‘существовании’ чисел,которые не представимы в конечной форме. Например, Кронекер признавал целыеи рациональные числа, поскольку их можно задать точно, а также алгебраическиечисла3 , представимые многочленами, корнями которых они являются. Однако, онотвергал трансцендентные числа, как не имеющие конечного представления.Говорят, что когда Кронекеру попалось на глаза известное доказательствотрансцендентности числа π Lindemann (1882), он якобы отозвался о нем так:«интересно, если не принимать во внимание того, что числа π не существует».Учитывая современные достижения, мы можем сказать, что конечноепредставление в принципе возможно для гораздо большего количества чисел,чем те, существование которых признавалось Кронекером.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
