twopass lex synt xs

[(rest, tree)

(rest, tokens) <- many lex xs, ( , tree) <- just synt tokens]

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

blockgram block4tup upperId lowered final input

"BLOCK ::= begin BLOCK end BLOCK ." (upperId, lowerId, blockgram, Nont "BLOCK") greedy1 (satisfy isUpper) greedy1 (satisfy isLower)

twopass (sp lowerId <@ Term) (parsgen block4tup) "begin end begin begin end end"

Вот то, что действительно может получиться:

? some final input

Node (Nont "BLOCK") [Node (Term "begin") [], Node (Nontc"BLOCK") [], Node

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

[], Node (Nont "BLOCK") []], Node (Term "end") [], Node (Nont "BLOCK") []]] (1061 reductions, 2722 cells)

Упражнение 19. Мы использовали идентификаторы, состоящие из заглавных и строчных букв для того, чтобы различать терминальные и нетерминальные символы. Если пространство имён терминалов и нетерминалов пересекутся, то нам придется принять новые механизмы их различения, например, угловые скобки вокруг нетерминалов и кавычки вокруг терминалов. Как это можно сделать?

Упражнение 20. Сделайте парсер для вашего любимого языка.

12. БЛАГОДАРНОСТЬ

Я бы хотел поблагодарить Doaitse Swierstra и Erik Meijer за их комментарии к наброску данной статьи и стимулирующие идеи.

2) 3) 4) 5)

13. ССЫЛКИ

R. Bird and P. Wadler, Introduction to Functional Programming. Prentice Hall, 1988.

W.H. Burge, Parsing. In Recursive Programming Techniques, Addison-Wesley, 1975.

Graham Hutton, Higher-order functions for parsing. J. Functional Programming

2:323-343.

release

MarkJones,Gofer2.30

http: www.cs.nott.ac.uk:80/Department/Staff/mpj/ .

P. Wadler, How to replace failure by a list of successes: a method for exception handling, backtracking, and pattern matching in lazy functional languages. In Functional Programming Languages and Computer Architecture, (J.P.Jouannaud, ed.), Springer, 1985 (LNCS 201), pp. 113-128.

Philip Wadler, Monads for functional programming. In Program design calculi, proc. of the Marktoberdorf Summer School, (M. Broy, ed.) Springer, 1992.

Philip Wadler, Monads for functional programming. In Lecture notes of the First International Spring School on Advanced Programming Techniques, (J. Jeuring, ed.) Springer, 1995.