A simple parser without externally dependences
- Format
- Evaluate
#[test]
fn smoke() {
let expr = "1*2 (3/(4 (-5)))";
let ast = build_ast(expr).unwrap();
assert_eq!(-1, eval(&ast));
assert_eq!("1 * 2 3 / (4 (-5))", format(&ast));
}DFA = ( StateSet, InputSet, transition_fn, start, TerminatorSet )
- StateSet = { START, OPERATOR, ZERO, NUM }
- InputSet = { operator, whitespace, 0, 1-9 }
- start = START
- TerminatorSet = { OPERATOR, ZERO, NUM }
| op | ws | 0 | 1-9 | |
|---|---|---|---|---|
| ERR | E | E | E | E |
| START | 2 | 1 | 3 | 4 |
| OPERATOR | 2 | 1 | 3 | 4 |
| ZERO | 2 | 1 | E | E |
| NUM | 2 | 1 | 4 | 4 |
primitive grammar
<expr> ::= <add>
| <mul>
| <literal>
| "(" <expr> ")"
;
<add> ::= <expr> (" " | "-") <expr> ;
<mul> ::= <expr> ("*" | "/") <expr> ;
introduce operator precedence
<expr> ::= <add> ;
<add> ::= <add> (" " | "-") <mul>
| <mul>
;
<mul> ::= <mul> ("*" | "/") <factor>
| <factor>
;
<factor> ::= "(" <expr> ")"
| <literal>
;
eliminate left recursion
<expr> ::= <add> ;
<add> ::= <mul> <add'> ;
<add'> ::= (" " | "-") <mul> <add'>
| <empty>
;
<mul> ::= <factor> <mul'> ;
<mul'> ::= ("*" | "/") <factor> <mul'>
| <empty>
;
<factor> ::= "(" <expr> ")"
| <literal>
;
simplified
<expr> ::= <mul> ((" " | "-") <mul>)* ;
<mul> ::= <factor> (("*" | "/") <factor>)* ;
<factor> ::= "(" <expr> ")"
| <literal>
;