Удалить недоступные правила из грамматики в OCaml - PullRequest
Новая
       17

Удалить недоступные правила из грамматики в OCaml

2 голосов
/ 03 октября 2011

Я новичок в Ocaml и для домашнего задания я должен написать функцию filter_reachable это берет грамматику и возвращает уменьшенную грамматику с удаленными недостижимыми правилами. Единственными модулями, которые мне разрешено использовать, являются модули Pervasives и List, и никаких других модулей.

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

Мое решение ниже. Однако это не работает, и я не понимаю, почему. Может кто-нибудь помочь мне это исправить? 

let rec member x s=
match s with
[]->false
| y::ys-> (x = y) || member x ys
     (*the type of a symbol*)

type ('nonterminal, 'terminal) symbol =
  | N of 'nonterminal
  | T of 'terminal


let rec get_nont sl=
match sl with
|[]->[]
|h::t->match h with
      |N x-> x::get_nont t
      |T y-> get_nont t

let rec get_rea_nont (n,r) =
n::(match r with
|[]->[]
|h::t->match h with
   | a,b -> if a=n then (get_nont b)@(get_rea_nont (n,t))
            else get_rea_nont(n,t)
   | _-> [])

let rec fil (st,rl)=
let x = get_rea_nont(st,rl) in
(match rl with
|[]-> []
|h::t-> match h with
        |a,b -> if (member a x) then h::fil(st,t)
                else fil(st,t)
        |_->[]
|_->[]
)

let rec filter(st,rl)=
(st,fil(st,rl))

Ответы [ 2 ]

3 голосов
/ 03 октября 2011

Представьте себе второй последний рекурсивный вызов fil (st, rl).В этом вызове rl имеет только одно правило.Ваш код попытается выяснить, достижим ли нетерминал правила, просто взглянув на это одно правило.Это не сработает, если нетерминал не является начальным символом.

В общем, я бы сказал, что вам нужно иметь при себе немного больше контекста.Я не хочу отдавать слишком много, но это в основном классическая проблема обхода ориентированного графа.Каждое грамматическое правило - это узел в графе.Края переходят от правила R к другим правилам, определяющим нетерминалы, которые появляются в RHS для R. Этот известный алгоритм обхода графа обычно работает со списком «посещенных» узлов.Вам это нужно, потому что график может содержать циклы.

Вот грамматика с циклами: 

A ::= B | B '+' A
B :: = 'x' | 'y' | '(' A ')'
1 голос
/ 15 октября 2011

Некоторые замечания по вашему коду:

  1. Вместо member вы можете использовать List.mem

  2. Сопоставление с шаблоном в get_nont можно комбинировать: 

    let rec get_nont sl = match sl with
    | [] -> []
    | N x :: tl -> x :: get_nont tl
    | T _ :: tl -> get_nont tl;;

  3. В функциональном программировании каррирование используется для определения функций с более чем одним аргументом. См. Область действия, каррирование и списки , раздел «Функции с каррированием».

  4. Используйте мощность сопоставления с образцом, например, продемонстрированную для get_rea_nont: 

    let rec get_rea_nont_old n r = n :: (match r with
    | []->[]
    | (a, b) :: t when a = n -> (get_nont b) @ (get_rea_nont_old n t)
    | _ :: t -> get_rea_nont_old n t
);;

  5. Попробуйте модулировать ваш код, например, для get_rea_nont:

    • Первые фильтрующие элементы равны n (см. List.filter).
    • Для фильтруемых элементов примените функцию get_nont (см. List.map)
    • Рассмотрим List.flatten, чтобы получить ожидаемый результат.

    Таким образом, ... 

    let get_rea_nont n r =
    let filtered = List.filter (fun (a, _) -> a = n) r in
    let nonterminals = List.map (fun (_, b) -> get_nont b) filtered in
    n :: (List.flatten nonterminals);;
...