Грамматика рекурсивного разбора потребляет входные данные и не может проанализировать последовательность

Question

Я пытаюсь написать расширенную форму Бэкуса-Наура синтаксический анализатор.Тем не менее, я сталкиваюсь с исключением переполнения стека всякий раз, когда я пытаюсь проанализировать альтернативы.Ниже приведен пример, который вызывает проблему:

#r @"..\packages\FParsec\lib\net40-client\FParsecCS.dll"
#r @"..\packages\FParsec\lib\net40-client\FParsec.dll"
open FParsec

type Parser<'t> = Parser<'t, unit>

type Element =
    | Alternates of Element list
    | ParsedString of string

let (pRuleElement, pRuleElementRef) : (Parser<Element> * Parser<Element> ref) = createParserForwardedToRef()

let pString =
    pchar '"' >>. manyCharsTill (noneOf ['"']) (pchar '"')
    |>> ParsedString

let pAlternates : Parser<_> =
    sepBy1 pRuleElement (many (pchar ' ') >>. (pchar '/') >>. many (pchar ' ') )
    |>> Alternates

do pRuleElementRef :=
    choice
        [
            pString
            pAlternates
        ]

"\"0\" / \"1\" / \"2\" / \"3\" / \"4\" / \"5\" / \"6\" / \"7\""
|> run (pRuleElement .>> (skipNewline <|> eof))

Проблема легко решается простым переупорядочением choice следующим образом:

do pRuleElementRef :=
    choice
        [
            pAlternates
            pString
        ]

Однако это вызывает переполнение стека.потому что он постоянно пытается проанализировать новую последовательность альтернатив без использования входных данных.Кроме того, этот метод затем нарушит приоритет ABNF:

1. Строки, формирование имен
2. Комментарий
3. Диапазон значений
4. Повтор
5. Группировка, необязательно
6. Объединение
7. Альтернатива

Мой вопрос сводится к следующему: Как я могу объединить разбор одного элемента, который может быть последовательностьюэлементов или один экземпляр элемента?Пожалуйста, дайте мне знать, если вам нужны какие-либо пояснения / дополнительные примеры.

Ваша помощь очень ценится, спасибо!

РЕДАКТИРОВАТЬ:

Я, вероятно, должен упомянуть, что есть различныеи другие виды группировок.Группа последовательностей (element[s]) и необязательная группа [optional element[s].Где element может быть вложенными группами / необязательными группами / строками / другими типами элементов.Ниже приведен пример с разбором групп последовательностей (необязательный разбор групп не включен для простоты):

#r @"..\packages\FParsec\lib\net40-client\FParsecCS.dll"
#r @"..\packages\FParsec\lib\net40-client\FParsec.dll"
open FParsec

type Parser<'t> = Parser<'t, unit>

type Element =
    | Alternates of Element list
    | SequenceGroup of Element list
    | ParsedString of string

let (pRuleElement, pRuleElementRef) : (Parser<Element> * Parser<Element> ref) = createParserForwardedToRef()

let pString =
    pchar '"' >>. manyCharsTill (noneOf ['"']) (pchar '"')
    |>> ParsedString

let pAlternates : Parser<_> =
    pipe2
        (pRuleElement .>> (many (pchar ' ') >>. (pchar '/') >>. many (pchar ' ')))
        (sepBy1 pRuleElement (many (pchar ' ') >>. (pchar '/') >>. many (pchar ' ') ))
        (fun first rest -> first :: rest)
    |>> Alternates

let pSequenceGroup : Parser<_> =
    between (pchar '(') (pchar ')') (sepBy1 pRuleElement (pchar ' '))
    |>> SequenceGroup

do pRuleElementRef :=
    choice
        [
            pAlternates
            pSequenceGroup
            pString
        ]

"\"0\" / ((\"1\" \"2\") / \"2\") / \"3\" / (\"4\" / \"5\") / \"6\" / \"7\""
|> run (pRuleElement .>> (skipNewline <|> eof))

Если я сначала пытаюсь проанализировать группы альтернатив / последовательностей, он завершается с исключением stack overflow, потому что затем пытаетсяповторно анализировать альтернативы.

Answer 1

Проблема в том, что когда вы запускаете синтаксический анализатор pRuleElement на входе, он правильно анализирует одну строку, оставляя некоторый неизрасходованный ввод, но затем происходит сбой за пределами choice, который будет возвращаться назад.

Вы можете запустить парсер pAlternates на главном входе, который на самом деле работает:

"\"0\" / \"1\" / \"2\" / \"3\" / \"4\" / \"5\" / \"6\" / \"7\""
|> run (pAlternates .>> (skipNewline <|> eof))

Я подозреваю, что вы, вероятно, можете просто сделать это - синтаксический анализатор pAlternates работает правильно, даже на одной строке - он просто вернет Alternates, содержащий одноэлементный список.

Answer 2

Похоже, что решение просто не пыталось проанализировать альтернативы во время синтаксического анализа альтернатив, чтобы избежать бесконечного цикла, приводящего к переполнению стека.Рабочая версия кода, размещенного в моем вопросе, выглядит следующим образом:

#r @"..\packages\FParsec\lib\net40-client\FParsecCS.dll"
#r @"..\packages\FParsec\lib\net40-client\FParsec.dll"
open FParsec

type Parser<'t> = Parser<'t, unit>

type Element =
    | Alternates of Element list
    | SequenceGroup of Element list
    | ParsedString of string

let (pRuleElement, pRuleElementRef) : (Parser<Element> * Parser<Element> ref) = createParserForwardedToRef()
let (pNotAlternatives, pNotAlternativesRef) : (Parser<Element> * Parser<Element> ref) = createParserForwardedToRef()

let pString =
    pchar '"' >>. manyCharsTill (noneOf ['"']) (pchar '"')
    |>> ParsedString

let pAlternates : Parser<_> =
    pipe2
        (pNotAlternatives .>>? (many (pchar ' ') >>? (pchar '/') >>. many (pchar ' ')))
        (sepBy1 pNotAlternatives (many (pchar ' ') >>? (pchar '/') >>. many (pchar ' ') ))
        (fun first rest -> first :: rest)
    |>> Alternates

let pSequenceGroup : Parser<_> =
    between (pchar '(') (pchar ')') (sepBy1 pRuleElement (pchar ' '))
    |>> SequenceGroup

do pRuleElementRef :=
    choice
        [
            pAlternates
            pSequenceGroup
            pString
        ]

do pNotAlternativesRef :=
    choice
        [
            pSequenceGroup
            pString
        ]

"\"0\" / (\"1\" \"2\") / \"3\" / (\"4\" / \"5\") / \"6\" / \"7\""
|> run (pRuleElement .>> (skipNewline <|> eof))

В дополнение к добавлению pNotAlternatives я также изменил его, чтобы он возвращался при сбое при разборе альтернативного разделителя / который позволяет ему продолжить после «понимания», что это не был список альтернатив в конце концов.