А в чем проблема?
При парсинге математических выражений, наибольшую сложность, пожалуй, вызывают инфиксные операторы. Сложность заключается в том, что операторы имеют такие характеристики, как приоритет и ассоциативность. Эти характеристики меняют порядок вычисления в длинных выражениях с такими операторами, что в конечном итоге приводит к необходимости строить дерево несколько иной структуры нежели та, которая получилась бы, если бы операторы вычислялись в том порядке, в котором они встречаются в записи.
Приведу пару примеров. Возьмем простое выражение
a + b - c
Оно порождает дерево следующего вида
Если же мы вместо вычитания используем умножение
a + b * c
То дерево уже будет вот таким
Так работает приоритет операций. Что до ассоциативности, то картина примерно такая же, только применяется подобное правило для цепочек с одним оператором. Например, если мы возьмем выражение
a * b * c
То оно породит дерево
В то же время, если вместо умножения мы будем использовать оператор возведения в степень, который обычно бывает правоассоциативным, то выражение
a ** b ** c
породит дерево
В длинных цепочках поиск операторов, которые надо выполнить первыми, при том, что у каждого оператора свои приоритет и ассоциативность – довольно сложный процесс и простой комбинацией парсеров, как мы это делали при создании парсера HTML – здесь не обойтись. Но, к счастью, проблема типичная, поэтому в библиотеке FParsec уже все предусмотрено, вот с этим мы сейчас и будем разбираться.
Модель дерева
Для начала надо определиться с тем, какие конструкции мы будем использовать. Набор сделаем минимальным, но достаточным для понимания основных концепций. Нам понадобятся: унарные операторы (префиксные), бинарные операторы(инфиксные), тернарный оператор (?:), числа типа float, скобки для переопределения порядка действий, и вызов функции (набор доступных функций мы определим, но он не принципиален). Есть еще нюанс: поскольку мы вводим условный оператор, нам понадобится помимо числового типа еще и булев. Но для того, чтобы слишком не усложнять модель, мы обойдемся числовым типом, а булевы значения будут считаться так: 0.0 – false, все остальное – true.
Добавляем в проект модуль AST со следующим кодом
module AST
type MathExpression =
|Binary of
left : MathExpression *
op : string *
right : MathExpression
|Unary of op : string * expr : MathExpression
|Ternary of
condition : MathExpression *
trueCase : MathExpression *
falseCase : MathExpression
|Number of float
|Parenthesis of MathExpression
|Function of
name : string *
args : MathExpression list
with
member this.Calculate() =
match this with
|Binary(l, o, r) ->
match o with
|"|" -> if ((l.Calculate() <> 0.0) || (r.Calculate() <> 0.0)) then 1.0 else 0.0
|"&" -> if ((l.Calculate() <> 0.0) && (r.Calculate() <> 0.0)) then 1.0 else 0.0
|"<" -> if l.Calculate() < r.Calculate() then 1.0 else 0.0
|"<=" -> if l.Calculate() <= r.Calculate() then 1.0 else 0.0
|"=" -> if l.Calculate() = r.Calculate() then 1.0 else 0.0
|">" -> if l.Calculate() > r.Calculate() then 1.0 else 0.0
|">=" -> if l.Calculate() >= r.Calculate() then 1.0 else 0.0
|"+" -> l.Calculate() + r.Calculate()
|"-" -> l.Calculate() - r.Calculate()
|"*" -> l.Calculate() * r.Calculate()
|"/" -> l.Calculate() / r.Calculate()
|"**" -> l.Calculate() ** r.Calculate()
|_ -> 0.0
|Ternary(c,t,f) -> if c.Calculate() <> 0.0 then t.Calculate() else f.Calculate()
|Number(n) -> n
|Parenthesis(e) -> e.Calculate()
|Unary(op, exp) ->
match op with
|"-" -> -exp.Calculate()
|"!" -> if exp.Calculate() = 0.0 then 1.0 else 0.0
|_ -> 0.0
|Function(name, args) ->
match name with
|"sum" -> List.sumBy (fun (x : MathExpression) -> x.Calculate()) args
|_ -> 0.0
Здесь я добавил метод, который будет вычислять значение выражения. Как я и описал выше, булевы операторы возвращают 0.0 или 1.0, а все числа для приведения к булевому типу просто сравниваются с нулем. Функция пока поддерживается только одна для иллюстрации, она будет принимать произвольное количество аргументов и возвращать их сумму. Добавить можно любое их количество и потом мы рассмотрим пару вариантов того, как это можно сделать.
Класс OperatorPrecedenceParser
Добавляем модуль Parser и начинаем его стандартно
module Parser
open FParsec
open AST
let ws = spaces
let str_ws s = pstring s >>. ws
Для создания парсера, вычисляющего выражения с операторами,
нам понадобится экземпляр OperatorPrecedenceParser.
let opp = new OperatorPrecedenceParser<MathExpression, unit, unit>()
Теперь парсер выражения, содержащего операторы мы можем получить из этого объекта
let opexpr = opp.ExpressionParser
Пока что мы для него еще ничего не определили, поэтому на данный момент этот парсер ничего не может. Но по мере инициализации OperatorPrecedenceParser, наш opexpr будет прирастать функционалом.
Добавление унарных операторов
Для добавления унарного минуса и логического НЕ воспользуемся конструктором PrefixOperator следующим образом
opp.AddOperator(PrefixOperator("-", ws, 20, true, fun x -> Unary("-", x)))
opp.AddOperator(PrefixOperator("!", ws, 20, true, fun x -> Unary("!", x)))
Здесь первый аргумент – строка, представляющая оператор,
второй – парсер, который может следовать за оператором, в нашем случае это
необязательная пробельная литера,
третий – приоритет,
четвертый – булево значение, показывающее, является ли оператор ассоциативным,
пятый – функция, порождающая объект из значений, полученных при парсинге.
В данном случае, пожалуй, объяснения требует только понятие
ассоциативности для унарного оператора. Возьмем к примеру минус, если он
ассоциативен, то выражение типа
--5
будет интерпретироваться как
-(-5).
То есть сначала к пятерке будет применен один минус, а потом уже к результату
второй. В случае же, когда оператор неассоциативен – такое выражение будет
вызывать ошибку. Последний вариант актуален, например, в тех случаях, когда
помимо минуса определен еще и префиксный декримент, в этом случае непонятно как
интерпретировать два минуса и во избежание конфликтов, в такой ситуации пришлось
бы сделать минус неассоциативным.
Бинарные операторы
Бинарных операторов у нас будет много, поэтому для упрощения их создания мы напишем простенькую функцию
let addop op prior assoc =
opp.AddOperator(InfixOperator(op, ws, prior, assoc, fun x y -> Binary(x, op, y)))
Она принимает три аргумента: текст оператора, приоритет и ассоциатвность. Для этого используется класс InfixOperator.
addop "|" 7 Associativity.Left
addop "&" 8 Associativity.Left
addop "<" 9 Associativity.Left
addop "<=" 9 Associativity.Left
addop "=" 9 Associativity.Left
addop ">" 9 Associativity.Left
addop ">=" 9 Associativity.Left
addop "+" 10 Associativity.Left
addop "-" 10 Associativity.Left
addop "*" 11 Associativity.Left
addop "/" 11 Associativity.Left
addop "**" 12 Associativity.Right
Тернарный оператор
Тернарный оператор у нас будет только один, для его создания мы воспользуемся классом TernaryOperator.
opp.AddOperator(TernaryOperator("?", ws, ":", ws, 5, Associativity.None, (fun c t f -> Ternary(c, t, f)) ))
Есть также возможность добавлять постфиксные операторы с помощью PostfixOperator, типа постфиксный инкрементов и декрементов, но нам они не понадобятся.
Числа, скобки и фукнции
Для парсинга чисел мы воспользуемся готовым парсером pfloat.
let number : Parser<MathExpression, unit> = pfloat .>> ws |>> Number
Выражение в скобках разберем с помощью between.
let parenthesis = between (str_ws "(") (str_ws ")") opexpr
Ну и для определения парсера вызова функции ничего нового (имена функций должны состоять из букв)
let func =
manySatisfy isLetter .>> ws
.>>. between (str_ws "(") (str_ws ")") (sepBy opexpr (str_ws ","))
|>> fun (name, args) -> Function(name, args)
Определение TermParser
Ну и наконец, для того, чтобы наш парсер мог понимать, что именно надо считать операндами, к которым следует применять операторы, нам нужно инициировть свойство TermParser.
opp.TermParser <- choice [parenthesis; func; number]
Здесь следует обратить внимание на то, что при использовании choice мы не использовали attempt. Тем не менее здесь все будет работать правильно. Причина в том, что все типы выражений, которые мы добавили в choice отличаются уже первым символом. То есть по первому символу можно определить, подходит тот или иной парсер или нет. В таком случае возвраты к исходному состоянию нам не понадобятся, поскольку нужный парсер будет находиться без изменения состояния.
Тестирование
Для тестирования, как обычно, добавим в файл Proogram.fs две функции
let test p str =
match run p str with
| Success(result, _, _) -> printfn "Success: %A" result
| Failure(errorMsg, _, _) -> printfn "Failure: %s" errorMsg
let calc p str =
match run p str with
| Success(result:MathExpression, _, _) -> printfn "Result: %f" (result.Calculate())
| Failure(errorMsg, _, _) -> printfn "Failure: %s" errorMsg
Первая функция выведет дерево, полученное из выражения, вторая – вычислит значение.
test opexpr "1 + 2 * 3 ** finik(1, 2*3)"
calc opexpr "(1 + 2) * 3**2"
calc opexpr "5 * (2 + 3) * 4"
calc opexpr "(3 < 5 ? 6 : 8) * 2"
calc opexpr "(3 > 5 ? 6 : 8) * - - 2"
calc opexpr "(3 > 5 ? 6 : 8) * --2 - sum(1,2,3)"
calc opexpr "!(3 > 5 ? 6 : 8) * --2 - sum(1,2,3)"
Здесь несложно заметить, что для построения дерева нам совсем не обязательно, чтобы использовалась известная функция, главное, чтобы имя состояло из букв и за ним следовали скобки. А вот для вычисления можно использовать только заранее предопределенные функции, все остальные будут возвращать 0.0, таким образом, выражение из примера с функцией finik по идее должна возвратить 3.0.
О дополнительных функциях
Хоть это уже и не относится к основной теме, но все же проводить тесты будет куда интереснее, если будет поддерживаться неплохой набор функций, тем более, что грамматика довольно скудная и в какой-то мере это можно компенсировать полезными функциями. Можно каждую функцию добавить вручную прямо в коде метода, вычисляющего выражение, как это было показано выше, но можно сделать и по-другому.
Возьмем «оптом» все что ест у класса System.Math с помощью рефлексии. Перепишем метод MathExpression.Calculate и добавим в ветку Function, код, который будет искать совпадение по имени в классе Math и если найдет, то попытается вызывать метод с подходящим набором параметров.
member this.Calculate() =
match this with
|Binary(l, o, r) ->
match o with
|"|" -> if ((l.Calculate() <> 0.0) || (r.Calculate() <> 0.0)) then 1.0 else 0.0
|"&" -> if ((l.Calculate() <> 0.0) && (r.Calculate() <> 0.0)) then 1.0 else 0.0
|"<" -> if l.Calculate() < r.Calculate() then 1.0 else 0.0
|"<=" -> if l.Calculate() <= r.Calculate() then 1.0 else 0.0
|"=" -> if l.Calculate() = r.Calculate() then 1.0 else 0.0
|">" -> if l.Calculate() > r.Calculate() then 1.0 else 0.0
|">=" -> if l.Calculate() >= r.Calculate() then 1.0 else 0.0
|"+" -> l.Calculate() + r.Calculate()
|"-" -> l.Calculate() - r.Calculate()
|"*" -> l.Calculate() * r.Calculate()
|"/" -> l.Calculate() / r.Calculate()
|"**" -> l.Calculate() ** r.Calculate()
|_ -> 0.0
|Ternary(c,t,f) -> if c.Calculate() <> 0.0 then t.Calculate() else f.Calculate()
|Number(n) -> n
|Parenthesis(e) -> e.Calculate()
|Unary(op, exp) ->
match op with
|"-" -> -exp.Calculate()
|"!" -> if exp.Calculate() = 0.0 then 1.0 else 0.0
|_ -> 0.0
|Function(name, args) ->
match name with
|"sum" -> List.sumBy (fun (x : MathExpression) -> x.Calculate()) args
|_ when
(typeof<System.Math>).GetMethods()
|> Array.map (fun m-> m.Name)
|> Array.contains name ->
((typeof<System.Math>).GetMethods()
|> Array.filter (fun mi ->
mi.IsStatic && mi.IsPublic && mi.Name = name
&& mi.GetParameters().Length = args.Length
&& mi.GetParameters() |> Array.forall (fun p ->
p.ParameterType.IsAssignableFrom(typeof<float>)))).[0]
.Invoke(null, Array.ofList args
|> Array.map (fun m -> m.Calculate() :> obj)):?>float
|_ -> 0.0
Теперь можно добавить в тесты следующее
calc opexpr "Sin(2)**2 + Cos(2)**2"
и убедиться, что получается единица.
