解答

1. use thiserror::Error;
2. use std::iter::Peekable;
3. use std::str::Chars;

5. /// An arithmetic operator.
6. #[derive(Debug, PartialEq, Clone, Copy)]
7. enum Op {
8. Add,
9. Sub,
10. }

12. /// A token in the expression language.
13. #[derive(Debug, PartialEq)]
14. enum Token {
15. Number(String),
16. Identifier(String),
17. Operator(Op),
18. }

20. /// An expression in the expression language.
21. #[derive(Debug, PartialEq)]
22. enum Expression {
23. /// A reference to a variable.
24. Var(String),
25. /// A literal number.
26. Number(u32),
27. /// A binary operation.
28. Operation(Box<Expression>, Op, Box<Expression>),
29. }

31. fn tokenize(input: &str) -> Tokenizer {
32. return Tokenizer(input.chars().peekable());
33. }

35. #[derive(Debug, Error)]
36. enum TokenizerError {
37. #[error("Unexpected character '{0}' in input")]
38. UnexpectedCharacter(char),
39. }

41. struct Tokenizer<'a>(Peekable<Chars<'a>>);

43. impl<'a> Iterator for Tokenizer<'a> {
44. type Item = Result<Token, TokenizerError>;

46. fn next(&mut self) -> Option<Result<Token, TokenizerError>> {
47. let c = self.0.next()?;
48. match c {
49. '0'..='9' => {
50. let mut num = String::from(c);
51. while let Some(c @ '0'..='9') = self.0.peek() {
52. num.push(*c);
53. self.0.next();
54. }
55. Some(Ok(Token::Number(num)))
56. }
57. 'a'..='z' => {
58. let mut ident = String::from(c);
59. while let Some(c @ ('a'..='z' | '_' | '0'..='9')) = self.0.peek() {
60. ident.push(*c);
61. self.0.next();
62. }
63. Some(Ok(Token::Identifier(ident)))
64. }
65. '+' => Some(Ok(Token::Operator(Op::Add))),
66. '-' => Some(Ok(Token::Operator(Op::Sub))),
67. _ => Some(Err(TokenizerError::UnexpectedCharacter(c))),
68. }
69. }
70. }

72. #[derive(Debug, Error)]
73. enum ParserError {
74. #[error("Tokenizer error: {0}")]
75. TokenizerError(#[from] TokenizerError),
76. #[error("Unexpected end of input")]
77. UnexpectedEOF,
78. #[error("Unexpected token {0:?}")]
79. UnexpectedToken(Token),
80. #[error("Invalid number")]
81. InvalidNumber(#[from] std::num::ParseIntError),
82. }

84. fn parse(input: &str) -> Result<Expression, ParserError> {
85. let mut tokens = tokenize(input);

87. fn parse_expr<'a>(
88. tokens: &mut Tokenizer<'a>,
89. ) -> Result<Expression, ParserError> {
90. let tok = tokens.next().ok_or(ParserError::UnexpectedEOF)??;
91. let expr = match tok {
92. Token::Number(num) => {
93. let v = num.parse()?;
94. Expression::Number(v)
95. }
96. Token::Identifier(ident) => Expression::Var(ident),
97. Token::Operator(_) => return Err(ParserError::UnexpectedToken(tok)),
98. };
99. // Look ahead to parse a binary operation if present.
100. Ok(match tokens.next() {
101. None => expr,
102. Some(Ok(Token::Operator(op))) => Expression::Operation(
103. Box::new(expr),
104. op,
105. Box::new(parse_expr(tokens)?),
106. ),
107. Some(Err(e)) => return Err(e.into()),
108. Some(Ok(tok)) => return Err(ParserError::UnexpectedToken(tok)),
109. })
110. }

112. parse_expr(&mut tokens)
113. }

115. fn main() -> anyhow::Result<()> {
116. let expr = parse("10+foo+20-30")?;
117. println!("{expr:?}");
118. Ok(())
119. }