shiftkit/
grammar.rs

1//! Defines the core grammar structures, including tokens, AST nodes,
2//! grammar rules, and the grammar itself
3
4pub mod builder;
5
6/// Each token type has a unique ID
7#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
8pub struct TokenType(pub u32);
9
10/// Each AST node type has a unique ID
11#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
12pub struct AstNodeType(pub u32);
13
14/// A single entry in a grammar rule - either a token type or AST node type
15#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
16pub enum GrammarItem {
17    /// Represents a terminal token type
18    Token(TokenType),
19    /// Represents a non-terminal AST node type
20    AstNode(AstNodeType),
21}
22
23impl From<TokenType> for GrammarItem {
24    fn from(token: TokenType) -> Self {
25        Self::Token(token)
26    }
27}
28
29impl From<AstNodeType> for GrammarItem {
30    fn from(node: AstNodeType) -> Self {
31        Self::AstNode(node)
32    }
33}
34
35/// Index into the token slice provided to the parser
36#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
37pub struct TokenId(pub usize);
38
39/// Index into the AST Vec
40#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
41pub struct AstNodeId(pub usize);
42
43/// Index is either a token position or AST node position
44#[derive(Debug, Copy, Clone, PartialEq, Eq)]
45pub enum Index {
46    /// Refers to a token in the input stream
47    Token(TokenId),
48    /// Refers to an AST node in the parsed output
49    AstNode(AstNodeId),
50}
51
52impl Index {
53    /// Unwrap as `TokenId`
54    ///
55    /// # Panics
56    ///
57    /// Panics if the index is not a `Token` variant
58    #[must_use]
59    pub fn as_token_id(&self) -> TokenId {
60        let &Self::Token(id) = self else {
61            panic!("Expected `Token`, found `AstNode`")
62        };
63        id
64    }
65
66    /// Unwrap as [`AstNodeId`]
67    ///
68    /// # Panics
69    ///
70    /// Panics if the index is not an `AstNode` variant
71    #[must_use]
72    pub fn as_ast_node_id(&self) -> AstNodeId {
73        let &Self::AstNode(id) = self else {
74            panic!("Expected `AstNode`, found `Token`")
75        };
76        id
77    }
78}
79
80/// Result of a reduction function - either creates a new node or forwards an existing one
81#[derive(Debug, Clone)]
82pub enum ReductionResult<A> {
83    /// Create a new AST node and append it to the `Vec`
84    NewNode(A),
85    /// Reuse an existing AST node (for pass-through rules like `Sum => Product`)
86    Forward(AstNodeId),
87}
88
89/// Trait that tokens must implement to provide their token type
90pub trait HasTokenType {
91    /// Returns the [`TokenType`] of the implementor
92    fn token_type(&self) -> TokenType;
93}
94
95/// Reduction function signature
96pub type ReductionFn<T, A> = fn(&[Index], &[T], &[A]) -> ReductionResult<A>;
97
98/// A grammar rule with its reduction function
99#[derive(Debug, Clone)]
100pub struct GrammarRule<T, A> {
101    /// The AST node type that this rule reduces to
102    pub result: AstNodeType,
103    /// The sequence of grammar items (tokens or AST nodes) that form this rule
104    pub components: Vec<GrammarItem>,
105    /// The function that is called when this rule is reduced
106    ///
107    /// Responsible for constructing the new AST node or forwarding an existing one.
108    pub reduction: ReductionFn<T, A>,
109}
110
111/// Each grammar rule has a unique ID (the index into the `Grammar#rules` array)
112#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
113pub struct GrammarRuleId(pub usize);
114
115/// A grammar defined as a set of grammar rules
116#[derive(Clone)]
117pub struct Grammar<T, A> {
118    /// The root AST node type of the grammar
119    pub root_ast_node: AstNodeType,
120    /// The list of all grammar rules
121    pub rules: Vec<GrammarRule<T, A>>,
122}
123
124impl<T, A> Grammar<T, A> {
125    /// Create a new empty grammar
126    #[must_use]
127    pub fn new(root_ast_node: AstNodeType) -> Self {
128        Self {
129            rules: vec![GrammarRule {
130                result: root_ast_node,
131                components: vec![root_ast_node.into()],
132                reduction: |indices, _, _| ReductionResult::Forward(indices[0].as_ast_node_id()),
133            }],
134            root_ast_node,
135        }
136    }
137
138    /// Add a production rule to the grammar
139    pub fn add_rule(
140        &mut self,
141        result: AstNodeType,
142        components: &[GrammarItem],
143        reduction: ReductionFn<T, A>,
144    ) {
145        self.rules.push(GrammarRule {
146            result,
147            components: components.to_vec(),
148            reduction,
149        });
150    }
151
152    /// Get a rule by its ID
153    #[must_use]
154    pub fn get_rule(&self, id: GrammarRuleId) -> &GrammarRule<T, A> {
155        &self.rules[id.0]
156    }
157}
shiftkit/grammar.rs

shiftkit/
grammar.rs
