haar_lib/parser/ll1/
mod.rs

1//! LL(1)構文解析
2use std::{collections::HashMap, hash::Hash};
3
4/// 構文解析用の入力文字列
5#[derive(Clone, Debug)]
6pub struct Input<Char> {
7    input: Vec<Char>,
8    pos: usize,
9}
10
11impl Input<char> {
12    /// `str`から[`Input<char>`]を構築する。
13    pub fn new(s: &str) -> Self {
14        Self {
15            input: s.chars().collect(),
16            pos: 0,
17        }
18    }
19}
20
21impl<Char> Input<Char>
22where
23    Char: Copy + Eq,
24{
25    /// 現在の文字が`e`に等しければ、一文字だけ消費する。
26    pub fn consume_eq(&mut self, e: Char) -> Option<Char> {
27        let c = *self.input.get(self.pos)?;
28        (c == e).then(|| {
29            self.pos += 1;
30            c
31        })
32    }
33
34    /// 一文字だけ消費する。
35    pub fn consume(&mut self) -> Option<Char> {
36        let ret = *self.input.get(self.pos)?;
37        self.pos += 1;
38        Some(ret)
39    }
40
41    /// 現在の文字を返す。
42    pub fn peek(&self) -> Option<Char> {
43        self.input.get(self.pos).copied()
44    }
45}
46
47type Procedure<'a, S, Char, Output> = Box<dyn 'a + Fn(&S, &mut Input<Char>) -> Option<Output>>;
48type FirstChecker<'a, Char> = Box<dyn 'a + Fn(Char) -> bool>;
49
50type EmptyRule<'a, S, Char, Output> = Procedure<'a, S, Char, Output>;
51type NonEmptyRule<'a, S, Char, Output> = (FirstChecker<'a, Char>, Procedure<'a, S, Char, Output>);
52
53struct Rules<'a, S, Char, Output> {
54    empty_rule: Option<EmptyRule<'a, S, Char, Output>>,
55    non_empty_rules: Vec<NonEmptyRule<'a, S, Char, Output>>,
56}
57
58impl<S, Char, Output> Default for Rules<'_, S, Char, Output> {
59    fn default() -> Self {
60        Self {
61            empty_rule: None,
62            non_empty_rules: vec![],
63        }
64    }
65}
66
67#[allow(clippy::type_complexity)]
68#[derive(Default)]
69/// LL(1)構文解析器
70pub struct LL1Parser<'a, State, Char, Output> {
71    rules: HashMap<State, Rules<'a, Self, Char, Output>>,
72}
73
74impl<'a, State, Char, Output> LL1Parser<'a, State, Char, Output>
75where
76    State: Copy + Eq + Hash,
77    Char: Copy + Eq,
78{
79    /// [`LL1Parser`]を生成する。
80    pub fn new() -> Self {
81        Self {
82            rules: HashMap::new(),
83        }
84    }
85
86    /// 規則: $\mathtt{state} \rightarrow \alpha $ を導入する。
87    ///
88    /// $\alpha$は`proc`で解析される部分。
89    ///
90    /// $\alpha$の先頭は`check_first(c)`を満たす。
91    pub fn add_rule<F1, FP>(&mut self, state: State, check_first: F1, proc: FP)
92    where
93        F1: 'a + Fn(Char) -> bool,
94        FP: 'a + Fn(&Self, &mut Input<Char>) -> Option<Output>,
95    {
96        self.rules
97            .entry(state)
98            .or_default()
99            .non_empty_rules
100            .push((Box::new(check_first), Box::new(proc)));
101    }
102
103    /// 規則: $\mathtt{state} \rightarrow \varepsilon$ を導入する。
104    pub fn add_rule_empty<FP>(&mut self, state: State, proc: FP)
105    where
106        FP: 'a + Fn(&Self, &mut Input<Char>) -> Option<Output>,
107    {
108        self.rules
109            .entry(state)
110            .or_default()
111            .empty_rule
112            .replace(Box::new(proc));
113    }
114
115    /// `state`を開始状態として、`input`を構文解析する。
116    pub fn parse(&self, state: State, input: &mut Input<Char>) -> Option<Output> {
117        for (check_first, proc) in self.rules.get(&state)?.non_empty_rules.iter() {
118            if let Some(c) = input.peek() {
119                if check_first(c) {
120                    return proc(self, input);
121                }
122            }
123        }
124
125        if let Some(proc) = self.rules.get(&state)?.empty_rule.as_ref() {
126            return proc(self, input);
127        }
128
129        None
130    }
131}
132
133#[cfg(test)]
134mod test_yc_265;
haar_lib/parser/ll1/mod.rs

haar_lib/parser/ll1/
mod.rs
