- А в чем проблема?
- Модель дерева
- Класс OperatorPrecedenceParser
- Добавление унарных операторов
- Бинарные операторы
- Тернарный оператор
- Числа, скобки и фукнции
- Определение TermParser
- Тестирование
- О дополнительных функциях
А в чем проблема?
При парсинге математических выражений, наибольшую сложность, пожалуй, вызывают инфиксные операторы. Сложность заключается в том, что операторы имеют такие характеристики, как приоритет и ассоциативность. Эти характеристики меняют порядок вычисления в длинных выражениях с такими операторами, что в конечном итоге приводит к необходимости строить дерево несколько иной структуры нежели та, которая получилась бы, если бы операторы вычислялись в том порядке, в котором они встречаются в записи.
Приведу пару примеров. Возьмем простое выражение a + b - c. Оно порождает дерево следующего вида(Первая картинка вложения)
Если же мы вместо вычитания используем умножение a + b * c, то дерево уже будет вот таким (вторая картинка вложения)
Так работает приоритет операций. Что до ассоциативности, то картина примерно такая же, только применяется подобное правило для цепочек с одним оператором. Например, если мы возьмем выражениеa * b * c, то оно породит дерево (третья картинка вложения)
В то же время, если вместо умножения мы будем использовать оператор возведения в степень, который обычно бывает правоассоциативным, то выражение a ** b ** c породит дерево (четвертая картинка вложения).
В длинных цепочках поиск операторов, которые надо выполнить первыми, при том, что у каждого оператора свои приоритет и ассоциативность – довольно сложный процесс и простой комбинацией парсеров, как мы это делали при создании парсера HTML – здесь не обойтись.
Модель дерева
Для начала надо определиться с тем, какие конструкции мы будем использовать. Набор сделаем минимальным, но достаточным для понимания основных концепций. Нам понадобятся: унарные операторы (префиксные), бинарные операторы(инфиксные), тернарный оператор ?:, числа типа float, скобки для переопределения порядка действий, и вызов функции (набор доступных функций мы определим, но он не принципиален). Есть еще нюанс: поскольку мы вводим условный оператор, нам понадобится помимо числового типа еще и булев. Но для того, чтобы слишком не усложнять модель, мы обойдемся числовым типом, а булевы значения будут считаться так: 0.0 – false, все остальное – true.
Добавляем в проект модуль AST со следующим кодом
| F# | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| 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 |
|
Класс OperatorPrecedenceParser
Добавляем модуль Parser и начинаем его стандартно
| F# | 1
2
3
4
5
6
| module Parser
open FParsec
open AST
let ws = spaces
let str_ws s = pstring s >>. ws |
|
| F# | 1
| let opp = new OperatorPrecedenceParser<MathExpression, unit, unit>() |
|
| F# | 1
| let opexpr = opp.ExpressionParser |
|
Добавление унарных операторов
Для добавления унарного минуса и логического НЕ воспользуемся конструктором PrefixOperator следующим образом
| F# | 1
2
| opp.AddOperator(PrefixOperator("-", ws, 20, true, fun x -> Unary("-", x)))
opp.AddOperator(PrefixOperator("!", ws, 20, true, fun x -> Unary("!", x))) |
|
второй – парсер, который может следовать за оператором, в нашем случае это необязательная пробельная литера,
третий – приоритет,
четвертый – булево значение, показывающее, является ли оператор ассоциативным,
пятый – функция, порождающая объект из значений, полученных при парсинге.
В данном случае, пожалуй, объяснения требует только понятие ассоциативности для унарного оператора. Возьмем к примеру минус, если он ассоциативен, то выражение типа --5 будет интерпретироваться как -(-5).
То есть сначала к пятерке будет применен один минус, а потом уже к результату второй. В случае же, когда оператор неассоциативен – такое выражение будет вызывать ошибку. Последний вариант актуален, например, в тех случаях, когда помимо минуса определен еще и префиксный декримент, в этом случае непонятно как интерпретировать два минуса и во избежание конфликтов, в такой ситуации пришлось бы сделать минус неассоциативным.
Бинарные операторы
Бинарных операторов у нас будет много, поэтому для упрощения их создания мы напишем простенькую функцию
| F# | 1
2
| let addop op prior assoc =
opp.AddOperator(InfixOperator(op, ws, prior, assoc, fun x y -> Binary(x, op, y))) |
|
| F# | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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.
| F# | 1
| opp.AddOperator(TernaryOperator("?", ws, ":", ws, 5, Associativity.None, (fun c t f -> Ternary(c, t, f)) )) |
|
Числа, скобки и фукнции
Для парсинга чисел мы воспользуемся готовым парсером pfloat.
| F# | 1
| let number : Parser<MathExpression, unit> = pfloat .>> ws |>> Number |
|
| F# | 1
| let parenthesis = between (str_ws "(") (str_ws ")") opexpr |
|
| F# | 1
2
3
4
| let func =
manySatisfy isLetter .>> ws
.>>. between (str_ws "(") (str_ws ")") (sepBy opexpr (str_ws ","))
|>> fun (name, args) -> Function(name, args) |
|
Ну и наконец, для того, чтобы наш парсер мог понимать, что именно надо считать операндами, к которым следует применять операторы, нам нужно инициировть свойство TermParser.
| F# | 1
| opp.TermParser <- choice [parenthesis; func; number] |
|
Тестирование
Для тестирования, как обычно, добавим в файл Proogram.fs две функции
| F# | 1
2
3
4
5
6
7
8
9
| 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 |
|
| F# | 1
2
3
4
5
6
7
| 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)" |
|
О дополнительных функциях
Хоть это уже и не относится к основной теме, но все же проводить тесты будет куда интереснее, если будет поддерживаться неплохой набор функций, тем более, что грамматика довольно скудная и в какой-то мере это можно компенсировать полезными функциями. Можно каждую функцию добавить вручную прямо в коде метода, вычисляющего выражение, как это было показано выше, но можно сделать и по-другому.
Возьмем «оптом» все что ест у класса System.Math с помощью рефлексии. Перепишем метод MathExpression.Calculate и добавим в ветку Function, код, который будет искать совпадение по имени в классе Math и если найдет, то попытается вызывать метод с подходящим набором параметров.
| F# | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| 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 |
|
| F# | 1
| calc opexpr "Sin(2)**2 + Cos(2)**2" |
|
>>
|
