Разбор пользовательских инфиксных операторов + реализация с FParsec

Question

Я немного застрял в том, как "настоящие парсеры", такие как F # или Haskell, делают для разбора пользовательских операторов.Для «нормального» языка мы бы просто определили узел AST, в котором были бы предопределенные возможности оператора, например: +, -, *, ==, >=, +=,... и т. д.

Но мне интересно, как это сделать на функциональном языке, который позволяет создавать пользовательские операторы, давайте возьмем в качестве примера OCaml, довольно близкий к F # (язык моей реализации), идовольно хорошо известны.

Таким образом, каждый оператор является функцией и имеет тип, а также определение, и мы можем создавать свои собственные операторы:

val (+) : 'a -> 'a -> 'a
let (+) x y = x + y

val (|>) : 'a -> ('a -> 'b) -> 'b
let (|>) x f = f x

Так что мне интересно, как этоработает с синтаксическим анализом, чтобы заставить его работать.

1) Как парсер узнает, что мы хотим использовать пользовательский оператор?Если мы используем функцию, которая принимает другую функцию в первом аргументе и другой элемент во втором, как он узнает, что мы вызываем функцию, а не используем оператор инфикса?

let example x =
    // Do we add up, or do we call the function "takeOpAndOther"?
    takeOpAndOther + x

2) Чтобы ответить на этот вопросВопрос, я подумал, как сделать это в F #, благодаря FParsec.Первое решение, которое пришло на ум, было просто использовать OperatorPrecedenceParser.Проблема заключается в том, что это средство работает только для предопределенных операторов (или, если есть способ сделать то, что я хочу, я не знаю как).

Затем я подумал о создании простого парсера:

open FParsec

type Expression =
    | Number of int
    | InfixF of Expression * string * Expression
    | DataName of string
    | FunctionCall of string * Expression list

let ws = skipMany (pchar ' ' <|> pchar '\t') <?> ""
let ws1 = skipMany1 (pchar ' ' <|> pchar '\t') <?> ""

let identifier = many1Satisfy (fun c -> isLetter c || isDigit c)

let allowedSymbols =
   [ '!'; '@'; '#'; '$'; '%'; '^'; '&';
     '§'; '*'; '°'; '.'; '~'; ':'; '-';
     '+'; '='; '?'; '/'; '>'; '<'; '|'; ]

let customOperatorIdentifier = many1SatisfyL (fun c -> allowedSymbols |> List.contains c) "valid custom operator"

// I call about this parser
let rec infixF () = parse {
        let! lvalue = ws >>? expression
        let! op = ws >>? customOperatorIdentifier
        let! rvalue = ws >>? expression
        return InfixF(lvalue, op, rvalue)
    }

and number = pint32 |>> Number

and dataName = identifier |>> DataName

and functionCall () = parse {
        let! id = ws >>? identifier
        let! parameters = sepEndBy1 (ws >>? expression) ws1
        return FunctionCall(id, parameters)
    }

and expression =
    attempt number <|>
    attempt dataName <|>
    attempt (functionCall ()) <|>
    infixF ()

let test code =
    match run (ws >>? expression .>>? ws .>>? eof) code with
    | Success (result, _, _) -> printfn "%A" result
    | Failure (msg, _, _)    -> printfn "%s" msg

test "87 + 12"

Кроме того, как и следовало ожидать, он не работает должным образом.Действительно, поскольку код представлен (потому что, когда я пытаюсь использовать infixF в одиночку и удаляю его из expression, он работает, но, очевидно, только для одного выражения: x + y, но не x + y + z), это приведет кошибка переполнения каждый раз.Я думаю, что это основная проблема, с которой я сталкиваюсь в своей реализации.

Однако два описанных решения не удовлетворяют одному из моих вопросов, а именно отправке функции-оператора.

Короче ... У меня есть несколько вопросов, о которых я хотел бы получить объяснения, и проблему с реализацией, которую я бы хотел решить.

Спасибо!:)

Answer 1

Итак, вы правы, что сложная часть - это приоритет.Я думаю, что есть приблизительно два способа справиться с этим для языка стиля ML

1. Приоритет определяется фиксированными правилами
2. Приоритет определяется пользователем

Ocaml делает вариант 1. Приоритет и ассоциативность оператора определяются его первым символом.

Haskell делает вариант 2. Приоритет и ассоциативность определяются с помощью операторов (и объявление может прийти после того, как используется оператор).

Довольно просто увидеть, как анализировать (1): вы просто анализируете его как обычно, за исключением того, что вместо разрешения оператора + на этом уровне приоритета вы определяете любой оператор, начинающийся с +.Это оставляет вопрос о том, как вам следует разбирать выражение типа a +* b +- c.Я не знаю, как ocaml связал бы это, но мое предположение было бы основано либо на втором символе, либо на том же уровне приоритета (например, как разбор + и - на том же уровне приоритета и ассоциирование слева такa + b - c + d анализируется как ((a + b) - c) + d).

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

type operator = Op of string
type expression =
  | Var of string
  | Operator of operator
  | App of expression * expression
  | Tuple of expression list
  | Infix of expression * (operator * expression) list

В частности, вы не можете иметь Infix of expression * operator * expression, потому что тогда как вы анализируете a OP b OP c?В основном у вас есть два варианта:

1. Infix (Infix (Var a, Op OP, Var b), Op OP, Var c)
2. Infix (Var a, Op OP, Infix (Var b, Op OP, Var c))

Вариант 1 эквивалентен (a OP b) OP c и работает для -и |>, но не в стиле Haskell $ и, конечно, не для a + b * c.Аналогично, вариант 2 работает для +, но не для - или /.Кроме того, недостаточно просто отменить это искажение перед сортировкой приоритета, потому что выражение (a OP b) OP c должно быть проанализировано как вариант 1, даже если оно не исправлено.

Обратите внимание, (если мы хотим язык стиля ML) нужен способ выразить функцию оператора в виде значения, например, (+), но это можно, например, включить в Var.

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

Некоторые другие вещи, которые могут быть полезныс конкретными символами, например, !.Haskell допускает использование постфиксных операторов в качестве расширения, но только с использованием срезов (т. Е. Расширение ослабляет определение (x*) с (\y -> (*) x y) до ((*) x), поэтому (*) может принимать один аргумент. Если вы хотите иметь возможность предварительно иПостфиксные операторы определяются пользователем, вы можете изменить тип, чтобы отбрасывать приложение и правило, что у вас может быть ровно один оператор между выражениями, а затем сделать шаг, чтобы проанализировать список expression | operator в нечто вменяемое, например, делает a * + bанализировать как a (*(+b)), (a) * (+b), (a*) (+b), (a*) + (b) или ((a*)+) b? Может быть, эта трудность тоже будет плохой для читателей-людей.

Как справиться с приоритетом? В Haskell вы выбираетецелое число от 0 до 9. В perl6 вы вместо этого просто говорите, что eg * является более жестким, чем +, и если два оператора с неопределенным отношением появляются вместе, язык требует, чтобы вы указали в скобках.

Это может бытьСтоит отметить путь perl6 в качестве другого варианта. В этом случае операторы должны иметь свой приоритет и ассоциативность / фиксированность, определенные доОн используется, и синтаксический анализатор динамически добавляет их между объявлением и использованием (можно также сделать это со всей грамматикой языка, поэтому анализ будущих выражений зависит от оценки более ранних выражений, что немного менее безумно).