compiler_course_helper/grammar/
ll1_parsing_table.rs

1use crowbook_text_processing::escape::tex as escape_tex;
2use serde::Serialize;
3use std::collections::{HashMap, HashSet};
4
5use crate::Grammar;
6
7use super::{pretty_print::ProductionOutput, EPSILON};
8
9#[derive(Serialize)]
10pub struct LL1ParsingTable<'a> {
11    terminals: Vec<&'a str>,
12    rows: Vec<(&'a str, Vec<ProductionOutput<'a>>)>,
13}
14
15impl LL1ParsingTable<'_> {
16    pub fn to_plaintext(&self) -> String {
17        let mut header: Vec<String> = vec![String::new()];
18        header.extend(self.terminals.iter().map(|&t| t.to_string()));
19        let mut output: Vec<Vec<String>> = vec![header];
20        for (left, row) in &self.rows {
21            let mut line: Vec<String> = vec![left.to_string()];
22            line.extend(
23                row.iter()
24                    .map(|productions| productions.to_plaintext(left.len(), false)),
25            );
26            output.push(line);
27        }
28
29        let mut width = vec![0; self.terminals.len() + 1];
30        for j in 0..output[0].len() {
31            width[j] = output.iter().map(|line| line[j].len()).max().unwrap();
32        }
33        output
34            .iter()
35            .map(|line| {
36                line.iter()
37                    .enumerate()
38                    .map(|(i, s)| format!("{:>width$}", s, width = width[i]))
39                    .collect::<Vec<_>>()
40                    .join(" | ")
41            })
42            .collect::<Vec<_>>()
43            .join("\n")
44    }
45
46    pub fn to_latex(&self) -> String {
47        let mut header: Vec<String> = vec![format!(
48            "\\[\\begin{{array}}{{c{}}}\n",
49            "|l".repeat(self.terminals.len()),
50        )];
51        header.extend(
52            self.terminals
53                .iter()
54                .map(|&t| format!("\\text{{{}}}", escape_tex(t))),
55        );
56        let header = header.join(" & ");
57
58        let mut output: Vec<String> = Vec::new();
59        let termintal_set: HashSet<&str> = self.terminals.iter().cloned().collect();
60        for (left, row) in &self.rows {
61            let mut line: Vec<String> = vec![format!("{}", escape_tex(*left))];
62            line.extend(
63                row.iter()
64                    .map(|productions| productions.to_latex(false, &termintal_set)),
65            );
66            output.push(line.join(" & "));
67        }
68
69        let output = output.join("\\\\\n");
70
71        header + "\\\\\\hline\n" + &output + "\n\\end{array}\\]"
72    }
73}
74
75impl Grammar {
76    pub fn generate_ll1_parsing_table(&mut self) -> LL1ParsingTable {
77        if !self.is_nullable_first_follow_valid() {
78            self.calculate_nullable_first_follow();
79        }
80
81        let terminals: Vec<&str> = self.terminal_iter().map(|t| t.as_str()).collect();
82        let map: HashMap<usize, usize> = terminals
83            .iter()
84            .enumerate()
85            .map(|(i, t)| (self.get_symbol_index(t).unwrap(), i))
86            .collect();
87
88        let mut rows: Vec<(&str, Vec<ProductionOutput>)> = Vec::new();
89        for nt in self.non_terminal_iter() {
90            let left = nt.name.as_str();
91            let mut row: Vec<ProductionOutput> = vec![
92                ProductionOutput {
93                    left,
94                    rights: Vec::new()
95                };
96                terminals.len()
97            ];
98            for production in &nt.productions {
99                let first = self.calculate_first_for_production(production);
100
101                let production_string_iter =
102                    production.iter().map(|idx| self.get_symbol_name(*idx));
103
104                for col in first.iter().map(|idx| map[idx]) {
105                    row[col]
106                        .rights
107                        .push(production_string_iter.clone().collect::<Vec<_>>());
108                }
109            }
110
111            if nt.nullable {
112                for idx in &nt.follow {
113                    row[map[idx]].rights.push(vec![EPSILON]);
114                }
115            }
116
117            rows.push((left, row));
118        }
119
120        LL1ParsingTable { terminals, rows }
121    }
122}
compiler_course_helper/grammar/ll1_parsing_table.rs

compiler_course_helper/grammar/
ll1_parsing_table.rs
