Как я могу выразить тип в F #, который необязательно повторяется сам по себе (бесконечно) - PullRequest
Новая
       28

Как я могу выразить тип в F #, который необязательно повторяется сам по себе (бесконечно)

0 голосов
/ 21 июня 2011

В качестве учебного упражнения я пытаюсь реализовать синтаксический анализатор для языка точек Graphviz ( Язык DOT ), используя функциональную библиотеку синтаксических анализаторов fparsec ( FParsec ).Язык описывает графики.

Глядя на определение языка, я был вынужден записать следующее определение: 

let rec pstmt_list = opt(pstmt .>> opt(pchar ';') >>. opt pstmt_list)

Где pstmt и pchar ';' - парсеры, .>> и>>. объединяет вхождение левого синтаксического анализатора с вхождением правого синтаксического анализатора, а opt анализирует необязательное вхождение его анализатора аргумента в качестве значения параметра.Однако это определение не работает с жалобой «... результирующий тип будет бесконечным ...».

Этот пример, вероятно, легче всего понять, если взглянуть на язык DOT, связанный выше.

Мне известны следующие, казалось бы, связанные вопросы:

Но моих знаний по F # может быть недостаточно для их перевода, если они применимы здесь вообще.

Ответы [ 2 ]

4 голосов
/ 21 июня 2011

FParsec предоставляет специальные комбинаторы для анализа последовательностей. Обычно вы предпочитаете, чтобы эти комбинаторы переопределяли их с помощью рекурсивной функции. Вы можете найти обзор доступных комбинаторов для анализа последовательностей здесь: http://www.quanttec.com/fparsec/reference/parser-overview.html#parsing-sequences

В этом примере pstmt_list - это последовательность операторов, разделенных и при желании оканчивающихся точкой с запятой, поэтому вы можете легко определить синтаксический анализатор как 

let pstmt_list = sepEndBy pstmt (pstring ";")
2 голосов
/ 21 июня 2011

Проблема в том, что ваш парсер pstmt_list создает некоторые значения некоторого типа, но когда вы используете его в определении, вы оборачиваете значения этого типа дополнительным типом option (используя комбинатор opt).

Компилятор F # считает, что тип значений, возвращаемых синтаксическим анализатором, например, 'a должен быть таким же, как и обернутый тип option 'a (что, конечно, невозможно).

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

Я думаю, вам, вероятно, нужно что-то вроде этого: 

let rec pstmt_list : Parser<int list, unit> = 
  parse.Delay(fun () ->
    opt(pstmt .>> pchar ';') .>>. opt pstmt_list
    |>> (function Some(prev), Some(rest) -> prev::rest
                | Some(prev), _ -> [prev]
                | _, Some(rest) -> rest
                | _ -> [] ))

Дополнительное использование Delay состоит в том, чтобы не объявлять значение, которое относится непосредственно к себе.

...