Skip to main content

编译原理

字母运算​

Σ={ci∣i>0∧∣ci∣=1∧ci≠ε}(字母表)s="c1⋯cn",c∈Σ∧∣s∣≥1(字符串)ε(空串)\begin{matrix*}[l] \Sigma=\{ c_i \mid i>0 \land |c_i|=1 \land c_i \not = \varepsilon \} & \text{(字母表)} \\ s="c_1 \cdots c_n" , c \in \Sigma \land |s| \ge 1 & \text{(字符串)} \\ \varepsilon & \text{(空串)} \\ \end{matrix*}

sj⋅sk="sjsk"(字符串连接)sn=sn⋅sn−1(字符串方幂)s0=ε\begin{matrix*}[l] s_j \cdot s_k = "s_js_k" & \text{(字符串连接)} \\ s^n=s^n \cdot s^{n-1} & \text{(字符串方幂)} \\ s^0=\varepsilon \\ \end{matrix*}

Sj∪Sk={si∣si∈Sj∨si∈Sk}(合并字符串集)Sj⋅Sk={sjsk∣sj∈Sj∧sk∈Sk}(连接字符串集)Sn=Sn⋅Sn−1(符串集方幂)S0={ε}\begin{matrix*}[l] S_j \cup S_k = \{s_i|s_i \in S_j \lor s_i \in S_k\} & \text{(合并字符串集)} \\ S_j \cdot S_k = \{s_js_k|s_j \in S_j \land s_k \in S_k\} & \text{(连接字符串集)} \\ S^n = S^n \cdot S^{n-1} & \text{(符串集方幂)} \\ S^0 = \{\varepsilon\} \\ \end{matrix*}

S∗=⋃i≥0∞Si(克林闭包)S+=⋃i=1∞Si(正闭包)\begin{matrix*}[l] S^* = \displaystyle \bigcup^{\infty}_{i \ge 0} S^i & \text{(克林闭包)} \\ \\ S^+ = \displaystyle \bigcup^{\infty}_{i=1} S^i & \text{(正闭包)} \\ \end{matrix*}

文法​

G=(VN,VT,P,S)(文法)V=VN∪VT(词汇表)VN(非终结符集)VT(终结符集)P(产生式的有限集S,S∈VN(开始符号)\begin{matrix*}[l] G=(V_N,V_T,P,S) & \text{(文法)} \\ V=V_N \cup V_T & \text{(词汇表)} \\ V_N & \text{(非终结符集)} \\ V_T & \text{(终结符集)} \\ P & \text{(产生式的有限集} \\ S , S \in V_N & \text{(开始符号)} \\ \end{matrix*}
α→β(产生式)α∈V+(产生式左部)β∈V∗(产生式右部)\begin{matrix*}[l] \alpha \to \beta & \text{(产生式)} \\ \alpha \in V^+ & \text{(产生式左部)} \\ \beta \in V^* & \text{(产生式右部)} \\ \end{matrix*}

(产生式左部至少含有一个非终结符)∀α∃a={ai∣ai∈VN}⊆α∧∣a∣≥1\text{(产生式左部至少含有一个非终结符)} \\ \forall \alpha \\ \exists a=\{a_i \mid a_i \in V_N\} \subseteq \alpha \land |a| \ge 1

(候选式)∃α→βj,α→β⋯,α→βk  ⟺  α→βi∣⋯∣βk ⁣:βi(j≤i≤k)是α的候选式\text{(候选式)} \\ \exists \alpha \to \beta_j , \alpha \to \beta_{\cdots},\alpha \to \beta_k \\ \iff \alpha \to \beta_i \mid \cdots \mid \beta_k \\ \colon \beta_i (j \le i \le k) \text{是} \alpha \text{的候选式}