Вычисления при помощи продукций

[mibori]

Интересно, а при помощи систем продуций можно реальные парсеры писать?

Под катом самописный модуль Prod, который экспортирует две функции runProd и sys:

• runProd (a, b) w - реализует срабатывание продукции a -> b над входным словом w
• sys [(a1, b1), (a2, b2), ...] w - реализует срабатывание системы продукции {a1 -> b1, a2 -> b2, ...} над входным словом w

module Prod (runProd, sys) where
import Data.List(splitAt)
import Control.Monad.State(get, put, runState, when)

-- однократное срабатывание подстановки
-- с флагом факта срабатывания
runOnce (x, y) w
        | null x = error "null->y error"
        | null y = error "x->null error"
        | x==y = error "x->x error"
        | otherwise = r w
        where
                lx = length x
                r'St [] = return []
                r'St word@(w:ws) = do
                        let (wx, wxs) = splitAt lx word
                        if x == wx then do {put True; return (y ++ wxs)}
                                else do {t <- r'St ws; return (w: t)}
                r w = runState (r'St w) False

-- однократное срабатывание продукции
runProd p w = case runOnce p w of
        (w', True) -> runProd p w'
        (w', False) -> w

-- однократное срабатывание продукции с фактом срабатывания
runProd' p w = case runOnce p w of
        (w', True) -> (runProd p w', True)
        (w', False) -> (w, False)

-- однократное срабатывание системы продукций
-- с фактом срабатывания хотя бы одной продукции из системы
-- через State
sysProd'St [] w = return w
sysProd'St (p: ps) w = do
        let (w', f) = runProd' p w
        when f $ put True
        sysProd'St ps w'

-- однократное срабатывание системы продукции
-- с фактом рабатывания хотя бы одной из системы
-- возвращает кортеж (результат, флаг)
sysProd' ps w = runState (sysProd'St ps w) False

-- срабатывание системы продукции
sys ps w = case sysProd' ps w of
        (w', True) -> sys ps w'
        (w', False) -> w'Syhi-подсветка кода
Попробуем проверить на чем-нибудь простом.
import Prod

-- тип булевского выражения
data BoolExpr = T | F | And | Or deriving (Show, Eq)

-- задаем правила вычислений при помощи
-- системы продукций
boolSystem = [
        -- правила для конъюнкции
        ([F, And, F], [F]),
        ([F, And, T], [F]),
        ([T, And, F], [F]),
        ([T, And, T], [T]),

-- правила для дизъюнкции
        ([F, Or, F], [F]),
        ([F, Or, T], [T]),
        ([T, Or, F], [T]),
        ([T, Or, T], [T])]

-- выражение для примера: 0&1 V 1&0 V 1&1 (== 1)
boolExpr = [F, And, T, Or, T, And, F, Or, T, And, T]Syhi-подсветка кодаТеперь в GHCi...
*Main> :l prodex1
[1 of 2] Compiling Prod ( Prod.hs, interpreted )
[2 of 2] Compiling Main ( prodex1.hs, interpreted )
Ok, modules loaded: Main, Prod.
*Main> sys boolSystem boolExpr
[T]
*Main>При дальнейшем развитии сюжета, может оказаться, что продукции - удобная технология построения парсеров. Только, к сожалению, дорогая по производительности, имхо. Вообще в Сети мало чего про это...