syntax_parser_generator/parsing/translator/
sdt.rs

1use std::fmt::Debug;
2
3use crate::handles::{Handle, Handled};
4use crate::handles::collections::{HandledVec, HandleMap};
5use crate::handles::specials::AutomaticallyHandled;
6use crate::lex::Lexeme;
7use crate::parsing::lr_parser::execute::{FinalDecision, LrParserDecision, LrParserExecution};
8use crate::parsing::lr_parser::LrParser;
9use crate::parsing::translator::build::Nonterminal;
10use crate::parsing::translator::handlers::{LeafSatelliteBuilder, SatelliteReducer};
11
12/// A syntax-directed translation engine based on a LALR parser.
13///
14/// Instances of this type are compiled parsers that's capable of consuming [Lexeme]s categorized
15/// by `LexemeType`, hold a translation context of type `Context`, and translate subtrees of the
16/// input syntax tree into instances of `Satellite`.
17///
18/// See [parsing](crate::parsing) and
19/// [SyntaxDirectedTranslatorBuilder](crate::parsing::SyntaxDirectedTranslatorBuilder) for more
20/// details on the parser and its specifications.
21pub struct SyntaxDirectedTranslator<LexemeType: Handled, Context, Satellite> {
22    pub(super) lr_parser: LrParser<LexemeType, Nonterminal, SatelliteReducer<Context, Satellite>>,
23    pub(super) default_leaf_satellite_builder: Option<LeafSatelliteBuilder<Context, Satellite>>,
24    pub(super) leaf_satellite_builder_map:
25        HandleMap<LexemeType, LeafSatelliteBuilder<Context, Satellite>>,
26    pub(super) satellite_reducers: HandledVec<SatelliteReducer<Context, Satellite>>,
27}
28
29impl<LexemeType: Debug, Context, Satellite> SyntaxDirectedTranslator<LexemeType, Context, Satellite>
30where
31    LexemeType: AutomaticallyHandled,
32{
33    /// Parses a sequence of input lexemes.
34    ///
35    /// Operating on the given translation `context`, the parser consumes the `streams`'s lexemes,
36    /// reconstructs their syntax tree, and translates it into an intermediate representation
37    /// (of type `Satellite`) according to the user-defined translation scheme specified when the
38    /// parser was built.
39    ///
40    /// Returns the translated syntax tree, or [None] if a syntactic error was found.
41    pub fn translate(
42        &self,
43        context: &mut Context,
44        stream: impl Iterator<Item=Lexeme<LexemeType>>,
45    ) -> Option<Satellite> {
46        let mut execution = SyntaxDirectedTranslatorExecution::new(self, context);
47        for lexeme in stream {
48            execution.feed(lexeme)?;
49        }
50        execution.finalize()
51    }
52
53    fn build_leaf(
54        &self,
55        context: &mut Context,
56        lexeme: Lexeme<LexemeType>,
57    ) -> (Handle<LexemeType>, Satellite) {
58        let terminal = lexeme.lexeme_type.handle();
59        let builder = if let Some(builder) = self
60            .leaf_satellite_builder_map
61            .get(lexeme.lexeme_type.handle())
62        {
63            builder
64        } else if let Some(builder) = &self.default_leaf_satellite_builder {
65            builder
66        } else {
67            panic!(
68                "Tried to build a leaf satellite for a lexeme type for which no leaf satellite \
69                    builder was specified, and no default builder was set"
70            )
71        };
72        (terminal, builder(context, lexeme.contents))
73    }
74
75    fn reduce_satellites(
76        &self,
77        reducer: Handle<SatelliteReducer<Context, Satellite>>,
78        context: &mut Context,
79        satellites: Vec<Satellite>,
80    ) -> Satellite {
81        self.satellite_reducers[reducer](context, satellites)
82    }
83}
84
85struct SyntaxDirectedTranslatorExecution<'a, LexemeType: AutomaticallyHandled, Context, Satellite> {
86    translator: &'a SyntaxDirectedTranslator<LexemeType, Context, Satellite>,
87    context: &'a mut Context,
88    satellite_stack: Vec<Satellite>,
89    lr_parser_execution:
90        LrParserExecution<'a, LexemeType, Nonterminal, SatelliteReducer<Context, Satellite>>,
91}
92
93impl<'a, LexemeType: AutomaticallyHandled + Debug, Context, Satellite>
94SyntaxDirectedTranslatorExecution<'a, LexemeType, Context, Satellite>
95{
96    fn new(
97        translator: &'a SyntaxDirectedTranslator<LexemeType, Context, Satellite>,
98        context: &'a mut Context,
99    ) -> Self {
100        Self {
101            translator,
102            context,
103            satellite_stack: Vec::new(),
104            lr_parser_execution: translator.lr_parser.new_execution(),
105        }
106    }
107
108    fn feed(&mut self, lexeme: Lexeme<LexemeType>) -> Option<()> {
109        let (terminal, satellite) = self.translator.build_leaf(self.context, lexeme);
110        loop {
111            match self.lr_parser_execution.decide(terminal)? {
112                LrParserDecision::Reduce { size, tag } => self.handle_reduce(size, tag)?,
113                LrParserDecision::Shift => {
114                    self.satellite_stack.push(satellite);
115                    break;
116                }
117            }
118        }
119        Some(())
120    }
121
122    fn finalize(mut self) -> Option<Satellite> {
123        while let FinalDecision::Reduce { size, tag } = self.lr_parser_execution.decide_final()? {
124            self.handle_reduce(size, tag);
125        }
126        self.satellite_stack.pop()
127    }
128
129    fn handle_reduce(
130        &mut self,
131        size: usize,
132        reducer: Handle<SatelliteReducer<Context, Satellite>>,
133    ) -> Option<()> {
134        if self.satellite_stack.len() < size {
135            // Satellite stack is too short for rule
136            return None;
137        }
138        let rhs_satellites = self
139            .satellite_stack
140            .drain((self.satellite_stack.len() - size)..)
141            .collect();
142        let lhs_satellite =
143            self.translator
144                .reduce_satellites(reducer, self.context, rhs_satellites);
145        self.satellite_stack.push(lhs_satellite);
146        Some(())
147    }
148}
syntax_parser_generator/parsing/translator/sdt.rs

syntax_parser_generator/parsing/translator/
sdt.rs
