pub struct Parser { /* private fields */ }
Expand description
Our hand-written parser. Use with parse().
Implementations§
Source§impl Parser
impl Parser
pub fn new() -> Parser
Sourcepub fn parse(
&mut self,
line: &str,
file_info: Option<String>,
) -> Result<Option<Ast>, String>
pub fn parse( &mut self, line: &str, file_info: Option<String>, ) -> Result<Option<Ast>, String>
Parse the string given in line
and returns the corresponding Ast.
Note that this function does not beta-reduce the expression.
This parser uses all usual rules for implicit parenthesization in lambda calculus, namely:
- Left associativity is assumed by default:
let mut parser = Parser::new();
assert_eq!(parser.parse("a b c d", None), parser.parse("(((a b) c) d)", None));
- The lambda body stretches as far as possible:
let mut parser = Parser::new();
assert_eq!(parser.parse("lambda x . a b c", None), parser.parse("(lambda x . a b c)", None));
let mut parser = Parser::new();
assert_eq!(parser.parse("lambda x . a lambda y . y", None),
parser.parse("(lambda x . (a (lambda y . y)))", None));
- Unnecessary parentheses are ignored:
let mut parser = Parser::new();
assert_eq!(parser.parse("((((a))))", None), parser.parse("a", None));
Additionally,
- Multiple variables may be put under a same lambda:
let mut parser = Parser::new();
assert_eq!(parser.parse("lambda x y z . x y", None),
parser.parse("lambda x . lambda y . lambda z . x y", None));
- Lambda terms may be bound to symbols and later used.
Note that the symbol substitution is lazy, meaning it is deferred until truly needed when perfoming a beta reduction:
let mut parser = Parser::new();
assert_eq!(parser.parse("K = lambda x y . x", None), Ok(None));
let redex = parser.parse("K a b", None).unwrap();
// we haven't asked for any beta reduction, so K has not been
// substituted yet
let expected = Ast::new(Expr::Redex(
Box::new(Ast::new(Expr::Redex(
Box::new(Ast::new(Expr::Var { name: "K".to_string(), is_free: true })),
Box::new(Ast::new(Expr::Var { name: "a".to_string(), is_free: true })),
))),
Box::new(Ast::new(Expr::Var { name: "b".to_string(), is_free: true })),
)); // ((K a) b)
assert_eq!(redex, Some(expected));
let reduced = redex.unwrap().beta_reduce_quiet(&parser);
let expected = Some(Ast::new(Expr::Var { name: "a".to_string(), is_free: true }));
assert_eq!(reduced, expected);
One must take care when binding an expression with free variables; because of the lazy substitution, these variables might misbehave when captured, e.g. in
let mut parser = Parser::new();
assert_eq!(parser.parse("foo = \\f -> f x", None), Ok(None));
let reduced = parser.parse("(\\x -> foo) a", None)
.unwrap()
.unwrap()
.beta_reduce_quiet(&parser);
// the "x" in foo's definition is never replaced with "a",
// because the definition is only substituted later
let expected = parser.parse("foo", None)
.unwrap()
.unwrap()
.beta_reduce_quiet(&parser);
assert_eq!(reduced, expected);
Sourcepub fn parse_file(&mut self, filename: Option<String>) -> Result<(), String>
pub fn parse_file(&mut self, filename: Option<String>) -> Result<(), String>
Parse all lines in the file named filename, or stdin if filename is None.
Sourcepub fn get_symbol_names_with_prefix(&self, prefix: &str) -> Vec<&str>
pub fn get_symbol_names_with_prefix(&self, prefix: &str) -> Vec<&str>
Get an iterator for symbol names starting with prefix. May be used to implement TAB completion.
Sourcepub fn get_symbol(&self, name: &str) -> Option<&Ast>
pub fn get_symbol(&self, name: &str) -> Option<&Ast>
Return an immutable reference to an expression if its name can be found in the symbol table.
Sourcepub fn insert_symbol(&mut self, name: &str, ast: Ast)
pub fn insert_symbol(&mut self, name: &str, ast: Ast)
Insert a symbol and its corresponding expression into the symbol table.
Sourcepub fn count_steps(&self) -> bool
pub fn count_steps(&self) -> bool
Return whether the count step mode is on or off.
Sourcepub fn set_non_interactive_mode(&mut self)
pub fn set_non_interactive_mode(&mut self)
Turn on non-interactive mode.