文法的形式化定义

$G=(V_T,V_N,P,S)$

• $V_T$ ：终结符集合
• $V_N$：非终结符集合

$V_T\cap V_N = \varnothing$

$V_T\cap V_N$ ：文法符号集

• $P$：产生式集合
• $S$：开始符号

e.g.

$G = (\{id, +, *, (, ), \}, \{E\}, P, E)$

$\begin{aligned} P=\{&E \to E+E \\ &E\to E*E\\ &E\to (E), \\ &E\to id \ \} \end{aligned}$

约定：不引起歧义的前提下，可以只写产生式

因此可以简写为：

$\begin{aligned} G：&E\to E+E\\&E\to E*E, \\ &E\to (E)\\ &E\to id \end{aligned}$

产生式的简写

对一组有相同左部的 $\alpha$ 产生式：

$\alpha \to \beta_1, \alpha \to \beta_2, ..., \alpha\to \beta_n$

可以简写为：$\alpha \to \beta_1|\beta_2|...|\beta_n$

读作： $\alpha$ 定义为 $\beta_1$, 或者 $\beta_2$, ... , 或者$\beta_n$