пятница, 8 октября 2010 г.

Удаление бесплодных и недостижимых символов из КС-грамматики


Не далее как сегодня утром я таки дошёл с флешкой и таки сдал эти задачки:)

Привожу тут код этих алгоритмов:

N, E - Set - мн-ва не\терминальных символов
P - Set> - мн-во правил грамматики


// функция построения Ni для DelSterileChar
    let rec del_char (N' : Set) : Set = 
        let Ni : Set = 
            Set.map (fun (a, b) -> 
                        if List.forall (fun e -> N'.Contains(e) || E.Contains(e)) b  
                            then a 
                            else "") P
            |> Set.filter (fun k -> k <> "")
        if Ni = N' then Ni
                   else del_char <| Set.union Ni N'
 
    // функци построения Ni для DelUnattChar
    let rec del_un_char (N' : Set) : Set =
        let Ni = Set.filter (fun (a, b) -> N'.Contains(a)) P
                 |> Set.fold (fun acc (a, b) -> b @ acc) []
                 |> Set.ofList
                 |> Set.union N'
        if Ni = N' then Ni
                   else del_un_char Ni
    
    // алгоритм удаления бесподных символов
    member x.DelSterileChar() : unit =
        N <- del_char <| Set []
        P <- Set.filter (fun (a, b) -> 
                            N.Contains(a) && 
                            List.forall (fun e -> N.Contains(e) || E.Contains(e)) b) P
                                
    // алгоритм удаление недостижимых символов
    member x.DelUnattChar() : unit =
        let Ni = del_un_char <| Set [S]
        N <- Set.intersect N Ni
        E <- Set.intersect E Ni
        P <- Set.filter (fun (a, b) -> Ni.Contains(a) &&
                                       List.forall (fun e -> Ni.Contains(e)) b) P

3 комментария:

  1. Круто. Моё почтение за исходники.

    ОтветитьУдалить
  2. Хм, думал разобраться будет проще. Ох уж эта функциональная парадигма.

    ОтветитьУдалить
  3. Что конкретно непонятно в коде? Тут как бы не весь код класса, а только часть, нету обвязки type ClassName (params) = ...

    ОтветитьУдалить