nom_operator/
lib.rs

1// Copyright 2017 The nom-operator project developers
2//
3// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
4// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
5// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
6// option. This file may not be copied, modified, or distributed
7// except according to those terms.
8
9#![cfg_attr(feature="clippy", feature(plugin))]
10#![cfg_attr(feature="clippy", plugin(clippy))]
11
12#![cfg_attr(not(feature="clippy"), deny(unstable_features))]
13
14#![deny(missing_docs,
15        //missing_debug_implementations,
16        missing_copy_implementations,
17        trivial_casts,
18        trivial_numeric_casts,
19        unsafe_code,
20        unused_import_braces,
21        unused_qualifications)]
22
23// Remove this
24#![allow(dead_code,
25         unused_variables,
26         unused_macros,
27         unused_imports)]
28
29//#![deny(warnings)]
30#![doc(test(attr(allow(unused_variables), deny(warnings))))]
31
32//! This crate exposes convinient macros that can parse expressions
33//! based on set parameters
34
35#[cfg_attr(test, macro_use)]
36extern crate nom;
37
38#[macro_use]
39mod macros;
40
41pub mod expr;
42pub mod operator;
43
44pub use expr::Expr;
45pub use operator::Operator;
46pub use nom::IResult;
47use std::fmt::Debug;
48use operator::OperatorSize::*;
49
50type Parser = Box<Fn(&[u8]) -> IResult<&[u8], &[u8]>>;
51
52/// Operator parser state
53/// Is generic over the Atom return type and
54/// the Operator type (Usually an enum)
55//TODO: Should we require the Clone on `OperatorEnum`?
56//TODO: Remove the debug requirement from this
57pub struct OpParser<'a, OperatorEnum> where OperatorEnum: Sized + Copy + Debug {
58    /// List of operators
59    operators: Vec<Operator<OperatorEnum>>,
60
61    /// Atom parser
62    atom_parser: Parser,
63
64    expr_stack: Vec<Expr<&'a [u8], OperatorEnum>>,
65    op_stack: Vec<OperatorEnum>,
66}
67
68impl<'a, OpEnum> OpParser<'a, OpEnum>
69    where OpEnum: PartialEq + Copy + Debug {
70    /// Creates a new Operator parser
71    pub fn new(ap: Parser) -> Self {
72        OpParser {
73            operators: vec![],
74            atom_parser: ap,
75            expr_stack: vec![],
76            op_stack: vec![],
77        }
78    }
79
80    /// Adds a new operator to the list
81    pub fn add(&mut self, op: Operator<OpEnum>) {
82        self.operators.push(op)
83    }
84
85    fn log(&self, i: String, action: &'static str) {
86        use std::cmp::{min, max};
87        print!("{:?}\t", self.op_stack);
88
89        //let mod_stack = self.expr_stack.iter().map(|l| d(l)).collect();
90        print!("{:?}", self.expr_stack);
91        let l = format!("{:?}", self.expr_stack).len();
92        for i in 0..l + 20 - l  {
93            print!(" ");
94        }
95        print!("\t");
96        println!("{}\t{}", i, action);
97    }
98
99    fn find_operator(&self, openum: &OpEnum) -> Option<&Operator<OpEnum>> {
100        self.operators.iter()
101            .filter(|o| o.op == *openum)
102            .nth(0)
103    }
104
105    // if op != next
106    //  false when next.prec > op.prec
107    //  true when next.prec < op.prec
108    //
109    // if op == next
110    //  false when next.assoc == right
111    //  true when next.assoc == left
112    fn should_reduce(&self, next: OpEnum) -> bool {
113        use operator::OperatorSize::*;
114        use operator::Associativity;
115        if let Some(op) = self.op_stack.iter().peekable().peek() {
116            let operator = self.find_operator(*op)
117                .expect("Could not find operator in store");
118
119            let next_operator = self.find_operator(&next)
120                .expect("Could not find operator in store");
121
122            if operator.op == next {
123                return next_operator.associativity == Associativity::Left;
124            } else {
125                return next_operator.precedence <= operator.precedence;
126            }
127        }
128        false
129    }
130
131    fn reduce(&mut self) {
132        self.log(String::new(), "Reduce");
133        if self.expr_stack.len() < 1 { // TODO: TMP
134            return;
135        }
136        if let Some(op) = self.op_stack.pop() {
137            let operator = self.operators.iter()
138                .filter(|o| o.op == op)
139                .nth(0)
140                .expect("Could not find operator in store");
141
142            match operator.size {
143                Binary => {
144                    let right = self.expr_stack.pop().unwrap();
145                    let left = self.expr_stack.pop().unwrap();
146                    self.expr_stack.push(Expr::BinExpr{
147                        left: Box::new(left),
148                        op,
149                        right: Box::new(right)
150                    })
151                }
152                Unary => {
153                    let e = self.expr_stack.pop().unwrap();
154                    self.expr_stack.push(Expr::UnExpr{
155                        op,
156                        item: Box::new(e)
157                    })
158
159                }
160            }
161
162        }
163    }
164
165
166    fn shift<'b: 'a>(&mut self, i: &'b [u8]) -> Result<&'b [u8], &'b [u8]> {
167        self.log(d(i), "Shift");
168        for op in &self.operators {
169            if let IResult::Done(s, m) = (*op.parser)(i) {
170                self.op_stack.push(op.op);
171                return Ok(s);
172            }
173        }
174
175        if let IResult::Done(s, m) = (*self.atom_parser)(i) {
176                self.expr_stack.push(Expr::Atom(m));
177                return Ok(s);
178        }
179        Err(i)
180    }
181
182    fn try_parse_operator(&self, i: &[u8]) -> Option<OpEnum> {
183        for op in &self.operators {
184            if let IResult::Done(s, m) = (*op.parser)(i) {
185                return Some(op.op);
186            }
187        }
188        None
189    }
190
191    /// Parses a slice of bytes
192    // TODO: Change this back to IResult<&'b [u8], Expr<&'_ [u8], OpEnum>>
193    // when done
194    pub fn parse<'b: 'a>(&mut self, input: &'b [u8]) -> IResult<&'b [u8], &Expr<&[u8], OpEnum>> {
195
196        let mut mut_input = input;
197        while let Ok(rest) = self.shift(mut_input) {
198            mut_input = rest;
199
200            if let Some(op) = self.try_parse_operator(mut_input) {
201                if self.should_reduce(op) {
202                    self.reduce();
203                }
204            }
205        }
206
207        for o in 0..self.op_stack.len() {
208            self.reduce();
209        }
210        self.log(String::new(), "Done\n\n");
211
212        IResult::Done(mut_input, &self.expr_stack[0])
213    }
214
215}
216fn d(i: &[u8]) -> String {
217    let mut v = Vec::new();
218    v.extend_from_slice(i);
219    String::from_utf8(v).unwrap()
220}
221
222#[cfg(test)]
223mod tests {
224    use IResult;
225    use Expr;
226    use {OpParser, Operator};
227    use operator::Associativity::{Left, Right};
228    use operator::OperatorSize::{Unary, Binary};
229
230    use nom::digit;
231    #[derive(Debug, Clone, Copy, PartialEq)]
232    enum Ops {
233        Mul,
234        Add,
235        Sub,
236        Exp,
237        PreIncrement,
238        PreDecrement,
239    }
240
241    fn empty_parser(i: &[u8]) -> IResult<&[u8], &[u8]> {
242        panic!("Attempted to run empty_parser");
243    }
244
245    fn opparser_factory<'a>() -> OpParser<'a, Ops> {
246        let mut opp = OpParser::new(Box::new(|i| digit(i)));
247
248        opp.add(Operator::new(Ops::PreIncrement, Right, Unary,  8, Box::new(|i| tag!(i, "++"))));
249        opp.add(Operator::new(Ops::PreDecrement, Right, Unary,  7, Box::new(|i| tag!(i, "--"))));
250        opp.add(Operator::new(Ops::Add, Left, Binary, 10, Box::new(|i| tag!(i, "+"))));
251        opp.add(Operator::new(Ops::Mul, Left, Binary, 11, Box::new(|i| tag!(i, "*"))));
252        opp.add(Operator::new(Ops::Sub, Left, Binary,  9, Box::new(|i| tag!(i, "-"))));
253        opp.add(Operator::new(Ops::Exp, Right, Binary,  13, Box::new(|i| tag!(i, "^"))));
254
255        opp
256    }
257
258    #[test]
259    fn test() {
260        let mut p = opparser_factory();
261        println!("");
262
263        p.parse(b"--++10");
264    }
265
266    testcase!(parse_binary, b"20+10^43",
267              &t!(t!(20), Ops::Add, t!(t!(10), Ops::Exp, t!(43))));
268    testcase!(parse_unary, b"++10", &t!(Ops::PreIncrement, t!(10)));
269
270    testcase!(parse_unary_double,
271              b"++--10",
272              &t!(Ops::PreIncrement, t!(Ops::PreDecrement, t!(10))));
273}
nom_operator/lib.rs

nom_operator/
lib.rs
