John Harrison - Введение в функциональное программирование (1108517), страница 28
Текст из файла (страница 28)
Аналогично, будемсчитать, что анализатор производит результат типа β. Этот результат можетбыть, например, деревом разбора, представленным рекурсивным типом данных,либо просто числом, если анализатор предназначен для разбора выражения иего вычисления одновременно. В общем случае, анализатор может не обработатьвходную последовательность полностью, так что нам потребуется вернуть в1219.2. Синтаксический анализГлава 9. Примерыдополнение к результату разбора еще и список необработанных лексем.
Такимобразом, тип анализатора:(α)list → β × (α)listНапример, для входной последовательности (x + y) * z функция atom должнаобработать (x + y) и вернуть * z. Результирующее дерево разбора принятой частивхода может быть представлено значением рекурсивного типа, введенного ранее.Отсюда мы имеемatom " ( x␣+␣y ) ␣∗␣ z " = Fn ( "+" , [ Var "x" ; Var "y" ] ) , "∗␣ z "Поскольку любое обращение к функции atom должно происходить изфункции mulexp, то последняя будет использовать результат, полученныйвычислением atom, а также обрабатывать оставшиеся лексемы, вызываяповторно atom для анализа подвыражения z.9.2.2Комбинаторы синтаксического анализаЕще одна причина, по которой предложенный метод разбора особенно хорошоподходит для реализации на языке ML, это возможность определения некоторыхполезных комбинаторов, при помощи которых новые анализаторы легко создаютсяна базе уже существующих.
Определив эти комбинаторы как инфиксные операции,мы в состоянии придать программе синтаксического анализатора вид, очень схожийсо структурой исходной грамматики.Для начала введём исключение, сигнализирующее об ошибках анализа.Далее определим инфиксную операцию ++, которая применяет два анализаторапоследовательно, объединяя их результаты, а также инфиксную операцию ||,которая вначале делает попытку применить один из анализаторов, а затем —второй. Операция many представляет собой свертку относительно ++, т.
е. применяетзаданный анализатор максимально возможное количество раз, выдавая списокрезультатов. Наконец, инфиксная операция >> применяется для завершающейобработки результатов анализа заданной функцией.Согласно синтаксису CAML, идентификаторы наподобие ++ автоматическисчитаются инфиксными операциями, поэтому определение операций включаетвременную блокировку этой возможности при помощи ключевого слова prefix.Приоритеты также задаются автоматически по первым символам идентификаторови полагаются равными приоритетам арифметических операций, обозначенных этимисимволами.
Таким образом, приоритет ++ наивысший, >> — средний, || — низший,что нам и требуется.122Глава 9. Примеры9.2. Синтаксический анализexception Noparse ; ;let p r e f i x | | parser1 parser2 input =try parser1 inputwith Noparse −> p a r s e r 2 i n p u t ; ;l e t p r e f i x ++ p a r s e r 1 p a r s e r 2 i n p u t =l e t r e s u l t 1 , r e s t 1 = p a r s e r 1 i n p u t inl e t r e s u l t 2 , r e s t 2 = p a r s e r 2 r e s t 1 in( result1 , result2 ) , rest2 ; ;l e t rec many p a r s e r i n p u t =t r y l e t r e s u l t , next = p a r s e r i n p u t inl e t r e s u l t s , r e s t = many p a r s e r next in( result : : results ) , restwith Noparse −> [ ] , i n p u t ; ;l e t p r e f i x >> p a r s e r t r e a t m e n t i n p u t =l e t r e s u l t , r e s t = p a r s e r i n p u t intreatment ( r e s u l t ) , r e s t ; ;Введём следующие универсальные функции, которые нам понадобятся вдальнейшем. Большая часть из них уже обсуждалась ранее, за исключениемфункции explode, преобразующей строку в список односимвольных строк.
Еёреализация использует встроенные функции sub_string и string_length, которыене рассматривались, но их назначение легко понять из примера.let rec itlist f =fun [] b -> b| (h::t) b -> f h (itlist f t b);;let uncurry f(x,y) = f x y;;let K x y = x;;let C f x y = f y x;;let o f g x = f(g x);;#infix "o";;let explode s =let rec exap n l =if n < 0 then l elseexap (n - 1) ((sub_string s n 1)::l) inexap (string_length s - 1) [];;Для начала, определим некоторые «атомарные» анализаторы.
Функция someпринимает любой входной символ, удовлетворяющий заданному предикату, ивозвращает его. Функция a выполняет схожее действие, с той разницей, чтоона проверяет входной символ на равенство заданному. Наконец, finishedпредназначена для проверки того, что вся входная последовательность былаобработана.1239.2. Синтаксический анализГлава 9. Примерыl e t some p =fun [ ] −> r a i s e Noparse| ( h : : t ) −> i f p h then ( h , t ) e l s e r a i s e Noparse ; ;l e t a tok = some ( fun item −> item = tok ) ; ;let f i n i s h e d input =i f i n p u t = [ ] then 0 , i n p u t e l s e r a i s e Noparse ; ;9.2.3Лексический анализКомбинаторы синтаксического анализа в сочетании с несколькими простымифункциями классификации символов хорошо подходят для построения лексическогоанализатора нашего языка термов.
Прежде всего, определим тип, представляющийлексемы (токены), после чего реализуем лексический анализатор, преобразующийвходную последовательность в список лексем. Лексической категории Otherсоответствуют обозначения операций и т. п., причем в нашем случае все они весьмапросты и состоят лишь из одного символа (в отличие от составных обозначений,таких как :=).type token = Name of s t r i n g | Num of s t r i n g | Other of s t r i n g ; ;let lex =l e t s e v e r a l p = many ( some p ) inl e t l o w e r c a s e _ l e t t e r s = " a" <= s & s <= " z " inl e t u p p e r c a s e _ l e t t e r s = "A" <= s & s <= "Z" inl e t l e t t e r s = l o w e r c a s e _ l e t t e r s o r u p p e r c a s e _ l e t t e r s inl e t a l p h a s = l e t t e r s o r s = "_" o r s = " ’ " inl e t d i g i t s = " 0" <= s & s <= "9 " inl e t alphanum s = a l p h a s o r d i g i t s inl e t s p a c e s = s = "␣" o r s = " \n" o r s = "\ t " inl e t c o l l e c t ( h , t ) = h^( i t l i s t ( p r e f i x ^) t " " ) inl e t rawname =some a l p h a ++ s e v e r a l alphanum >> (Name o c o l l e c t ) inl e t rawnumeral =some d i g i t ++ s e v e r a l d i g i t >> (Num o c o l l e c t ) inl e t r aw o t h e r = some (K t r u e ) >> Other inl e t token =( rawname | | rawnumeral | | r a w o t h e r ) ++ s e v e r a l s p a c e >> f s t inl e t t o k e n s = ( s e v e r a l s p a c e ++ many token ) >> snd inl e t a l l t o k e n s = ( t o k e n s ++ f i n i s h e d ) >> f s t inf s t o a l l t o k e n s o explode ; ;Например,124Глава 9.
Примеры9.2. Синтаксический анализ#lex "sin(x + y) * cos(2 * x + y)";;- : token list =[Name "sin"; Other "("; Name "x"; Other "+"; Name "y"; Other ")";Other "*"; Name "cos"; Other "("; Num "2"; Other "*"; Name "x";Other "+"; Name "y"; Other ")"]9.2.4Анализатор термовДля завершения перехода от анализа отдельных символов к анализу лексем,введём базовые анализаторы, принимающие лексемы заданной категории:l e t name =fun (Name s : : r e s t ) −> s , r e s t| _ −> r a i s e Noparse ; ;l e t numeral =fun (Num s : : r e s t ) −> s , r e s t| _ −> r a i s e Noparse ; ;let other =fun ( Other s : : r e s t ) −> s , r e s t| _ −> r a i s e Noparse ; ;С помощью этих функций мы можем определить анализатор термов в виде, оченьсхожем с исходной грамматикой.
Основное различие состоит в том, что каждойпродукции сопоставлено некоторое действие, результат которого возвращается какрезультат анализа.1259.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 mulexp i n p u t= ( atom ++ a ( Other "∗" ) ++ mulexp>> ( fun ( ( a ,_) ,m) −> Fn ( "∗" , [ a ;m] ) )| | atom ) i n p u tand term i n p u t= ( mulexp ++ a ( Other "+" ) ++ term>> ( fun ( ( a ,_) ,m) −> Fn ( "+" , [ a ;m] ) )| | mulexp ) 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 ; ;Наглядной иллюстрацией работы этой функции является её вызов до и послеустановки специализированной функции вывода (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
