1use crate::{ProofExpr, ProofTerm};
32
33#[derive(Debug, Clone, PartialEq, Eq)]
35pub struct FormulaError {
36 pub message: String,
37}
38
39impl FormulaError {
40 pub(crate) fn new(message: impl Into<String>) -> Self {
41 FormulaError {
42 message: message.into(),
43 }
44 }
45}
46
47impl std::fmt::Display for FormulaError {
48 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
49 write!(f, "formula parse error: {}", self.message)
50 }
51}
52
53impl std::error::Error for FormulaError {}
54
55pub fn parse_formula(input: &str) -> Result<ProofExpr, FormulaError> {
60 let tokens = tokenize(input)?;
61 let mut p = Parser {
62 tokens: &tokens,
63 pos: 0,
64 };
65 let expr = p.parse_formula()?;
66 if p.pos != p.tokens.len() {
67 return Err(FormulaError::new(format!(
68 "unexpected trailing input near token {:?}",
69 p.tokens.get(p.pos)
70 )));
71 }
72 Ok(expr)
73}
74
75#[derive(Debug, Clone, PartialEq, Eq)]
80enum Tok {
81 Ident(String),
82 LParen,
83 RParen,
84 Comma,
85 Eq,
86 Arrow, Iff, And, Or, Not, Forall, Exists, }
94
95fn tokenize(input: &str) -> Result<Vec<Tok>, FormulaError> {
96 let chars: Vec<char> = input.chars().collect();
97 let mut toks = Vec::new();
98 let mut i = 0;
99 while i < chars.len() {
100 let c = chars[i];
101 if c.is_whitespace() {
102 i += 1;
103 continue;
104 }
105 match c {
106 '(' => {
107 toks.push(Tok::LParen);
108 i += 1;
109 }
110 ')' => {
111 toks.push(Tok::RParen);
112 i += 1;
113 }
114 ',' => {
115 toks.push(Tok::Comma);
116 i += 1;
117 }
118 '.' | ';' => {
121 i += 1;
122 }
123 '=' => {
124 toks.push(Tok::Eq);
125 i += 1;
126 }
127 '∧' => {
128 toks.push(Tok::And);
129 i += 1;
130 }
131 '∨' => {
132 toks.push(Tok::Or);
133 i += 1;
134 }
135 '¬' => {
136 toks.push(Tok::Not);
137 i += 1;
138 }
139 '∀' => {
140 toks.push(Tok::Forall);
141 i += 1;
142 }
143 '∃' => {
144 toks.push(Tok::Exists);
145 i += 1;
146 }
147 '→' => {
148 toks.push(Tok::Arrow);
149 i += 1;
150 }
151 '↔' => {
152 toks.push(Tok::Iff);
153 i += 1;
154 }
155 '-' if i + 1 < chars.len() && chars[i + 1] == '>' => {
156 toks.push(Tok::Arrow);
157 i += 2;
158 }
159 '<' if i + 2 < chars.len() && chars[i + 1] == '-' && chars[i + 2] == '>' => {
160 toks.push(Tok::Iff);
161 i += 3;
162 }
163 c if c.is_alphanumeric() || c == '_' => {
164 let start = i;
165 while i < chars.len() && (chars[i].is_alphanumeric() || chars[i] == '_') {
166 i += 1;
167 }
168 toks.push(Tok::Ident(chars[start..i].iter().collect()));
169 }
170 other => {
171 return Err(FormulaError::new(format!("unexpected character '{other}'")));
172 }
173 }
174 }
175 Ok(toks)
176}
177
178struct Parser<'a> {
183 tokens: &'a [Tok],
184 pos: usize,
185}
186
187impl<'a> Parser<'a> {
188 fn peek(&self) -> Option<&Tok> {
189 self.tokens.get(self.pos)
190 }
191
192 fn advance(&mut self) -> Option<&Tok> {
193 let t = self.tokens.get(self.pos);
194 if t.is_some() {
195 self.pos += 1;
196 }
197 t
198 }
199
200 fn peek_kw(&self) -> Option<String> {
202 match self.peek() {
203 Some(Tok::Ident(s)) => Some(s.to_lowercase()),
204 _ => None,
205 }
206 }
207
208 fn eat_kw(&mut self, kw: &str) -> bool {
209 if self.peek_kw().as_deref() == Some(kw) {
210 self.pos += 1;
211 true
212 } else {
213 false
214 }
215 }
216
217 fn peek_is_quantifier(&self) -> bool {
222 matches!(self.peek(), Some(Tok::Forall) | Some(Tok::Exists))
223 || matches!(
224 self.peek_kw().as_deref(),
225 Some("forall") | Some("for") | Some("exists") | Some("there") | Some("some")
226 )
227 }
228
229 fn parse_formula(&mut self) -> Result<ProofExpr, FormulaError> {
231 if matches!(self.peek(), Some(Tok::Forall)) {
235 self.advance();
236 return self.finish_quantifier(true);
237 }
238 if matches!(self.peek(), Some(Tok::Exists)) {
239 self.advance();
240 return self.finish_quantifier(false);
241 }
242 if self.eat_kw("forall") {
243 return self.finish_quantifier(true);
244 }
245 if self.eat_kw("for") {
246 if !self.eat_kw("all") {
247 return Err(FormulaError::new("expected 'all' after 'for'"));
248 }
249 return self.finish_quantifier(true);
250 }
251 if self.eat_kw("exists") {
252 return self.finish_quantifier(false);
253 }
254 if self.eat_kw("there") {
255 if !(self.eat_kw("exists") || self.eat_kw("is") || self.eat_kw("are")) {
256 return Err(FormulaError::new("expected 'exists' after 'there'"));
257 }
258 return self.finish_quantifier(false);
259 }
260 if self.eat_kw("some") {
261 return self.finish_quantifier(false);
262 }
263 self.parse_iff()
264 }
265
266 fn finish_quantifier(&mut self, universal: bool) -> Result<ProofExpr, FormulaError> {
269 let mut vars = Vec::new();
270 while let Some(Tok::Ident(s)) = self.peek() {
271 let low = s.to_lowercase();
273 if matches!(low.as_str(), "if" | "not" | "true" | "false") {
274 break;
275 }
276 vars.push(s.clone());
277 self.advance();
278 }
279 if vars.is_empty() {
280 return Err(FormulaError::new("quantifier with no bound variables"));
281 }
282 if matches!(self.peek(), Some(Tok::Comma)) {
284 self.advance();
285 }
286 let body = self.parse_formula()?;
287 Ok(vars.into_iter().rev().fold(body, |acc, var| {
288 if universal {
289 ProofExpr::ForAll {
290 variable: var,
291 body: Box::new(acc),
292 }
293 } else {
294 ProofExpr::Exists {
295 variable: var,
296 body: Box::new(acc),
297 }
298 }
299 }))
300 }
301
302 fn parse_iff(&mut self) -> Result<ProofExpr, FormulaError> {
304 let left = self.parse_implication()?;
305 if matches!(self.peek(), Some(Tok::Iff)) || self.peek_kw().as_deref() == Some("iff") {
306 self.advance();
307 let right = self.parse_implication()?;
308 return Ok(ProofExpr::Iff(Box::new(left), Box::new(right)));
309 }
310 Ok(left)
311 }
312
313 fn parse_implication(&mut self) -> Result<ProofExpr, FormulaError> {
316 if self.eat_kw("if") {
317 let cond = self.parse_disjunction()?;
318 if !self.eat_kw("then") {
319 return Err(FormulaError::new("expected 'then' to close an 'if'"));
320 }
321 let conseq = self.parse_implication()?;
322 return Ok(ProofExpr::Implies(Box::new(cond), Box::new(conseq)));
323 }
324 let left = self.parse_disjunction()?;
325 if matches!(self.peek(), Some(Tok::Arrow)) || self.peek_kw().as_deref() == Some("implies") {
326 self.advance();
327 let right = self.parse_implication()?;
328 return Ok(ProofExpr::Implies(Box::new(left), Box::new(right)));
329 }
330 Ok(left)
331 }
332
333 fn parse_disjunction(&mut self) -> Result<ProofExpr, FormulaError> {
335 let mut left = self.parse_conjunction()?;
336 loop {
337 if matches!(self.peek(), Some(Tok::Or)) || self.peek_kw().as_deref() == Some("or") {
338 self.advance();
339 let right = self.parse_conjunction()?;
340 left = ProofExpr::Or(Box::new(left), Box::new(right));
341 } else {
342 break;
343 }
344 }
345 Ok(left)
346 }
347
348 fn parse_conjunction(&mut self) -> Result<ProofExpr, FormulaError> {
350 let mut left = self.parse_negation()?;
351 loop {
352 if matches!(self.peek(), Some(Tok::And)) || self.peek_kw().as_deref() == Some("and") {
353 self.advance();
354 let right = self.parse_negation()?;
355 left = ProofExpr::And(Box::new(left), Box::new(right));
356 } else {
357 break;
358 }
359 }
360 Ok(left)
361 }
362
363 fn parse_negation(&mut self) -> Result<ProofExpr, FormulaError> {
365 if matches!(self.peek(), Some(Tok::Not)) || self.peek_kw().as_deref() == Some("not") {
366 self.advance();
367 let inner = self.parse_negation()?;
368 return Ok(ProofExpr::Not(Box::new(inner)));
369 }
370 self.parse_atom()
371 }
372
373 fn parse_atom(&mut self) -> Result<ProofExpr, FormulaError> {
379 if self.peek_is_quantifier() {
382 return self.parse_formula();
383 }
384
385 if matches!(self.peek(), Some(Tok::LParen)) {
386 self.advance();
387 let inner = self.parse_formula()?;
388 if !matches!(self.advance(), Some(Tok::RParen)) {
389 return Err(FormulaError::new("expected ')'"));
390 }
391 return Ok(inner);
392 }
393
394 let name = match self.advance() {
395 Some(Tok::Ident(s)) => s.clone(),
396 other => {
397 return Err(FormulaError::new(format!(
398 "expected an atom, found {other:?}"
399 )))
400 }
401 };
402
403 match name.to_lowercase().as_str() {
404 "true" => return Ok(ProofExpr::Atom("True".to_string())),
405 "false" => return Ok(ProofExpr::Atom("False".to_string())),
406 _ => {}
407 }
408
409 if matches!(self.peek(), Some(Tok::LParen)) {
411 self.advance();
412 let mut args = Vec::new();
413 if !matches!(self.peek(), Some(Tok::RParen)) {
414 loop {
415 args.push(self.parse_term()?);
416 if matches!(self.peek(), Some(Tok::Comma)) {
417 self.advance();
418 continue;
419 }
420 break;
421 }
422 }
423 if !matches!(self.advance(), Some(Tok::RParen)) {
424 return Err(FormulaError::new(
425 "expected ')' to close a relation's arguments",
426 ));
427 }
428 if name.eq_ignore_ascii_case("eq")
432 && args.len() == 2
433 && (is_arith_term(&args[0]) || is_arith_term(&args[1]))
434 {
435 let mut it = args.into_iter();
436 return Ok(ProofExpr::Identity(it.next().unwrap(), it.next().unwrap()));
437 }
438 return Ok(ProofExpr::Predicate {
439 name,
440 args,
441 world: None,
442 });
443 }
444
445 if matches!(self.peek(), Some(Tok::Eq)) {
447 self.advance();
448 let rhs = self.parse_term()?;
449 return Ok(ProofExpr::Identity(ident_to_term(&name), rhs));
450 }
451
452 Ok(ProofExpr::Atom(name))
454 }
455
456 fn parse_term(&mut self) -> Result<ProofTerm, FormulaError> {
457 let name = match self.advance() {
458 Some(Tok::Ident(s)) => s.clone(),
459 other => {
460 return Err(FormulaError::new(format!(
461 "expected a term, found {other:?}"
462 )))
463 }
464 };
465 if matches!(self.peek(), Some(Tok::LParen)) {
468 self.advance();
469 let mut args = Vec::new();
470 if !matches!(self.peek(), Some(Tok::RParen)) {
471 loop {
472 args.push(self.parse_term()?);
473 if matches!(self.peek(), Some(Tok::Comma)) {
474 self.advance();
475 continue;
476 }
477 break;
478 }
479 }
480 if !matches!(self.advance(), Some(Tok::RParen)) {
481 return Err(FormulaError::new(
482 "expected ')' to close a function's arguments",
483 ));
484 }
485 return Ok(ProofTerm::Function(name, args));
486 }
487 Ok(ident_to_term(&name))
488 }
489}
490
491fn is_arith_term(t: &ProofTerm) -> bool {
494 matches!(
495 t,
496 ProofTerm::Function(n, _)
497 if matches!(
498 n.as_str(),
499 "Add" | "Sub" | "Mul" | "Div" | "add" | "sub" | "mul" | "div" | "mod"
500 )
501 )
502}
503
504fn ident_to_term(s: &str) -> ProofTerm {
507 let leads_constant = s
508 .chars()
509 .next()
510 .map(|c| c.is_uppercase() || c.is_ascii_digit())
511 .unwrap_or(false);
512 if leads_constant {
513 ProofTerm::Constant(s.to_string())
514 } else {
515 ProofTerm::Variable(s.to_string())
516 }
517}