Разбор пользовательских инфиксных операторов + реализация с 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 и работает на -, а также |> но не стиль Хаскеля $ и, конечно, не для a + b * c, Аналогично вариант 2 работает для + но не для - или же /, Кроме того, недостаточно просто отменить это искажение перед сортировкой приоритета, потому что выражение (a OP b) OP c должен быть проанализирован как вариант 1, даже если он не исправлен.

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

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

Некоторые другие вещи, о которых стоит подумать:

1. Операторы префикса / постфикса: Ocaml позволяет операторам префикса, если они начинаются с определенных символов, например, !, Haskell допускает использование постфиксных операторов в качестве расширения, но только с использованием срезов (т. Е. Расширение ослабляет определение (x*) от (\y -> (*) x y) в ((*) x), так (*) может принять один аргумент. Если вы хотите, чтобы операторы pre и postfix определялись пользователем, вы можете изменить тип, чтобы отбрасывать приложение, и правило, чтобы между выражениями был ровно один оператор, а затем выполнить шаг для анализа списка: expression | operator во что-то вменяемое, например, делает a * + b разобрать как a (*(+b)), (a) * (+b), (a*) (+b), (a*) + (b), или же ((a*)+) b? Может быть, эта трудность была бы плоха и для читателей-людей.
2. Как бороться с приоритетом? В Haskell вы выбираете целое число от 0 до 9. В perl6 вы вместо этого просто говорите, что eg * является более жестким, чем +, и если два оператора с неопределенным отношением появляются вместе, язык требует, чтобы вы указали в скобках.

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