Сохранение государства в мире без гражданства - PullRequest
Новая
       11

Сохранение государства в мире без гражданства

7 голосов
/ 23 ноября 2010

Я преобразую контекстно-свободную грамматику в нормальную форму Грейбаха (GNF).Основное преобразование (от Хопкрофта и Уллмана) представляет собой последовательность итераций по индексированным переменным грамматики.Это по сути "без гражданства".Я реализовал его как последовательность сгибов по соответствующим индексам (реализация довольно проста): 

gnf :: Ord a => Set (Rule a) -> Set (Rule a)
gnf rl = foldl step1 rl [1..maxIndex rl]
 where step1 rl' k = foldl step2 rl' [1..k - 1]
        where step2 rl'' j = noLR k (subst rl'' k j)

maxIndex rl возвращает максимальный индекс переменной в наборе правил; subst rl kj выполняет подстановку по k -индексированным правилам по правилам, правая часть которых начинается с j -индексированной переменной.После выполнения gnf мне нужно выполнить последний проход по грамматике в обратном порядке.

Проблема заключается в noLR , который преобразует грамматику с левой рекурсивностью k -индексированные правила.Это функция с сохранением состояния, поскольку для каждого правила (или k -индексированного правила) должна быть создана уникальная переменная, к которой применяется noLR .Поэтому я написал функцию с состоянием 

noLR :: Ord a => Int -> Set (Rule a) -> State [Sym a] (Set (Rule a))
noLR rl = do (n:ns) <- get; put ns;
             let rl' = ... remove left recursion rl n ...
              in return rl'

Я могу упорядочить вместе noLR , чтобы обновить n , который noLR принимает какпараметр.Я не уверен, как выполнить noLR внутри step2 в вышеуказанной функции, хотя.Кажется, я не могу использовать схему let ... in , потому что вычисление с учетом состояния встроено в несколько рекурсивных функций.

Я хочу иметь n - глобальная переменная некоторого типа, похожая на явную многопоточность n , которую я могу вызывать и обновлять внутри step2 , поэтому я изначально написал функцию какскладка с расширением eta (для n ).Кто-нибудь знает, как я мог бы структурировать gnf внутри монады государства для достижения такого эффекта?За исключением последнего вычисления в сгибе, ничто иное не является «сохраняющим состояние», и мне удобно только использовать монаду состояний с «тривиальными» примерами.Я скорее заблудился.

Ответы [ 2 ]

4 голосов
/ 24 ноября 2010

Чтобы использовать noLR с указанным вами типом, вам нужно будет переписать вашу функцию gnf следующим образом: 

gnf :: Ord a => Set (Rule a) -> Set (Rule a)
gnf rl = evalState (foldM step1 rl [1..maxIndex rl]) ( ... generate the initial state [Sym a] here ...)
 where step1 rl' k = foldM step2 rl' [1..k - 1]
        where step2 rl'' j = noLR k (subst rl'' k j)

Ваша переменная состояния существует в течение всего вычисления, и этот факт должен быть явно указан в коде.

Если все, что вам нужно, это то, что вновь созданные имена переменных не сталкиваются друг с другом, тогда вы можете сделать noLR чистым, сгенерировав новое имя символа из индексов k и j - что-то вроде "foo_42_16" для k = = 42 и j == 16. Если входная грамматика уже содержит имена символов такого типа, вы можете столкнуться с проблемами.

Если вам нужно, чтобы ваши символы были уникальными в грамматике, то почему бы не сказать именно это? 

newSymbol :: Set (Rule a) -> Sym a
newSymbol rl = ... find a symbol name not used in rl ...

Это, безусловно, неэффективно, если только вы не замените Set (Правило a) другим типом, который позволит вам более эффективно реализовать операцию newSymbol.

3 голосов
/ 23 ноября 2010

Я бы попытался переписать noLR, чтобы быть чистым. Вы уверены, что не можете переписать его для создания символа, который зависит только от имени правила и его индекса (или чего-то подобного)? 

noLR k j = noLR' k j $ newSymbol k j
    where newSymbol k j = ... -- some concatenation of k and j
          noLR' k j sym = ... -- your now pure function
...