Blender V5.3
pratt_parser.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2026 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#pragma once
10
11#include "lexit/types.hh"
12
32template<typename Derived, typename ResultT, typename NodeT> class PrattParser {
33 public:
34 enum class ErrorType {
35 ExpectedParenthesis,
36 ExpectedColon,
37 InvalidOperator,
38 InvalidExpression,
39 };
40
41 struct BindingPower {
42 /* Unary operators must have the highest precedence. */
43 static constexpr int prefix = 120;
44 /* Let parenthesis evaluate everything until a closing parenthesis. */
45 static constexpr int parenthesis = 0;
46
48
50 };
51
52 ResultT expr(BindingPower right)
53 {
54 using namespace lexit;
55
56 Derived &self = static_cast<Derived &>(*this);
57
58 /* Parse unary operator, evaluate parenthesis, evaluate constant. */
59 ResultT left = nud(self.consume());
60
61 /* While left binding power is greater than the right, continue consuming binary operations. */
62 while (self.peek() != Invalid && left_binding_power(self.peek()) > right.binding_power) {
63 left = led(left, self.consume());
64 }
65
66 return left;
67 }
68
69 /* How a token evaluates without left context (e.g. unary operator).
70 * Also known as Null-Denotation or NUD. */
71 ResultT nud(const NodeT &t)
72 {
73 using namespace lexit;
74
75 Derived &self = static_cast<Derived &>(*this);
76 TokenType type = self.to_type(t);
77
78 switch (type) {
79 case Word:
80 return self.identifier(t);
81 case Number:
82 return self.number_literal(t);
83 case String:
84 return self.string_literal(t);
85 case Increment:
86 case Decrement:
87 case Plus:
88 case Minus:
89 case Not:
90 case BitwiseNot:
91 /* Note that '!' token is of MultiTok class and can contain many unary '!'.
92 * Implementation must take care of it. */
93 return self.prefix(t, BindingPower::prefix);
94 case ParOpen:
95 /* Parse the whole parenthesis expression. */
96 return self.parenthesis(t, BindingPower::parenthesis);
97 default:
98 return self.error(ErrorType::InvalidExpression, type);
99 }
100 }
101
102 /* How a token evaluates from left-to-right, on two operands.
103 * Also known as Left-Denotation or LED. */
104 ResultT led(ResultT left, const NodeT &t)
105 {
106 using namespace lexit;
107
108 Derived &self = static_cast<Derived &>(*this);
109 TokenType type = self.to_type(t);
110
111 switch (type) {
112 case Dot:
113 return self.member(left, t);
114 case SquareOpen:
115 return self.subscript(left, t);
116 case ParOpen:
117 return self.function_call(left, t);
118 case Increment:
119 case Decrement:
120 return self.suffix(left, t);
121 case Multiply:
122 case Divide:
123 case Modulo:
124 case Plus:
125 case Minus:
126 case LShift:
127 case RShift:
128 case LThan:
129 case LEqual:
130 case GThan:
131 case GEqual:
132 case Equal:
133 case NotEqual:
134 case And:
135 case Xor:
136 case Or:
137 case LogicalAnd:
138 case LogicalOr:
139 return self.binary(left, t, left_binding_power(type));
140 case Comma:
141 return self.comma(left, t, left_binding_power(type));
142 case Assign:
143 case AssignAdd:
144 case AssignSub:
145 case AssignMul:
146 case AssignDiv:
147 case AssignLShift:
148 case AssignRShift:
149 /* Subtract 1 to enforce Right-Associativity */
150 return self.binary(left, t, left_binding_power(type) - 1);
151 case Question:
152 /* The middle expression can be almost anything so use 0 so it only stops at the ':' (since
153 * Colon has a precedence of 0).
154 * Second expression uses (Question - 1) to handle right-associativity. */
155 return self.ternary(left, t, 0, left_binding_power(Question) - 1);
156 default:
157 return self.error(ErrorType::InvalidOperator, type);
158 }
159 }
160
161 /* C/C++ binding power. */
163 {
164 using namespace lexit;
165
166 Derived &self = static_cast<Derived &>(*this);
167
168 switch (type) {
169 case Increment:
170 case Decrement:
171 case SquareOpen:
172 case Dot:
173 return 130;
174 case Multiply:
175 case Divide:
176 case Modulo:
177 return 110;
178 case Plus:
179 case Minus:
180 return 100;
181 case LShift:
182 case RShift:
183 return 90;
184 case LThan:
185 case LEqual:
186 case GThan:
187 case GEqual:
188 return 80;
189 case Equal:
190 case NotEqual:
191 return 70;
192 case And:
193 return 60;
194 case Xor:
195 return 50;
196 case Or:
197 return 40;
198 case LogicalAnd:
199 return 30;
200 case LogicalOr:
201 return 20;
202 case Question:
203 return 10;
204 case Assign:
205 case AssignAdd:
206 case AssignSub:
207 case AssignMul:
208 case AssignDiv:
209 case AssignLShift:
210 case AssignRShift:
211 return 5;
212 case Comma:
213 return 2;
214 case Colon:
215 case ParOpen:
216 case ParClose:
217 return 0;
218 case Not:
219 case BitwiseNot:
220 /* Prefix operators don't bind to the left! */
221 return 0;
222 case Invalid: /* EndOfFile */
223 return -1;
224 default:
225 break;
226 }
227 self.error(ErrorType::InvalidOperator, type);
228 return -1;
229 }
230};
DBVT_INLINE bool NotEqual(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
Definition btDbvt.h:774
CodegenResult led(CodegenResult left, const ast::Node &t)
ResultT expr(BindingPower right)
bool Equal(const VectorAcc &r1, const VectorAcc &r2, double eps)
Definition frameacc.inl:157
ccl_device_inline float2 power(const float2 v, const float e)
TokenType
Definition types.hh:41
@ RShift
Definition types.hh:126
@ GThan
Definition types.hh:149
@ ParOpen
Definition types.hh:53
@ AssignSub
Definition types.hh:135
@ LThan
Definition types.hh:150
@ LogicalOr
Definition types.hh:93
@ Not
Definition types.hh:64
@ AssignAdd
Definition types.hh:133
@ SquareOpen
Definition types.hh:57
@ Question
Definition types.hh:63
@ Modulo
Definition types.hh:152
@ And
Definition types.hh:146
@ LogicalAnd
Definition types.hh:81
@ BitwiseNot
Definition types.hh:151
@ Multiply
Definition types.hh:145
@ Dot
Definition types.hh:48
@ ParClose
Definition types.hh:54
@ AssignLShift
Definition types.hh:138
@ AssignRShift
Definition types.hh:139
@ LEqual
Definition types.hh:104
@ Plus
Definition types.hh:68
@ Colon
Definition types.hh:65
@ Decrement
Definition types.hh:88
@ Increment
Definition types.hh:112
@ AssignDiv
Definition types.hh:137
@ String
Definition types.hh:154
@ Number
Definition types.hh:44
@ Divide
Definition types.hh:70
@ Xor
Definition types.hh:148
@ LShift
Definition types.hh:125
@ Assign
Definition types.hh:61
@ Minus
Definition types.hh:69
@ Word
Definition types.hh:43
@ AssignMul
Definition types.hh:136
@ Invalid
Definition types.hh:42
@ GEqual
Definition types.hh:94
@ Or
Definition types.hh:147
@ Comma
Definition types.hh:66
static constexpr int parenthesis
static constexpr int prefix