编译课程01
非形式语言讨论
较为平常、口语、通俗的口吻。
文法定义：对语言结构的定义与描述。也可以称为文法。如“他是好人”，其语法结构为主谓结构，这是由语法所决定的。
语法规则：通过建立一组规则，描述句子的语法结构。通过$::=$ or $\rightarrow $ 表示 由 …… 组成
如上述的主谓结构可以如下表述
\[<句子> ::= <主语><谓语>\\ <主语> ::= <代词>|<名词>\\ <代词> ::= 你|我|他\\ <名词> ::= 好人|坏人|大学生|英语\\ <谓语> ::= <动词><直接宾语>\\ <动词> ::= 是|学习 <直接宾语> ::= <代词>|<名词>\]由规则推导句子：通过规则推导或者产生句子，具体方式为从可识别的符号开始，用相应规则的右部替代左部
\[<句子> \Rightarrow <主语><谓语> \\ <主语><谓语> \Rightarrow <代词><谓语>(由‘或’连接的选一个即可)\\ \dots\]直到$<>$都被替代掉，这可以组成为 一个句子。将不含$<>$的符号称为终止符号
显然这样的推导是机械的替换，因此尽管语法上正确，但是语义上不一定正确，文法只管形式上的事情
上述的方法，我们总是从最左的语法，将左部有一次替换掉，这样的推导称为**最早推导
语法（推导）树：上述的组成方式，类似于表达式那样的递归组成，自然可以用树的形式进行表达。这样的树中，根结点称为识别符号，中间节点称为语法成分或者非终结符，叶子节点称为单词符号或者终结符号。
形式化表达
用数学的、严禁的语言再来规定一下。
文法定义
文法$G[Z]=(V_n, V_t, P, Z)$, 其中
\[\begin{align*} & V_n:\textsf{非终结符号表}\\ &V_t:\textsf{终结符号表} \\ &P:\textsf{产生式或规则的集合}\\ &Z:\textsf{开始符号} \\ \textsf{此外还有以下约定}\\ & V = V_n \cup V_t:\textsf{文法的字汇表} \\ & \textsf{规则}：U ::=x, \quad U \in V_n, x \in V^*\\ \end{align*}\]规则本质上就是一个满足限制条件的有序对。
以无符号整数的文法为例
\[\begin{align*} & G[<无符号整数>] = (V_n, V_t, P, Z) \\ & V_n = \left\{无符号整数>, <数字串>, <数字>\right\} \\ & P = \left\{<无符号整数> \rightarrow <数字串>,\right.\\ & \qquad <数字串> \rightarrow <数字串><数字>\\ & \qquad <数字串> \rightarrow <数字>\\ & \qquad <数字> \rightarrow 0 \\ & \qquad <数字> \rightarrow 1 \\ & \qquad \qquad \dotsb \dotsb \\ & \qquad <数字> \rightarrow 9 \left. \right\}\\ & Z = <无符号整数>\\ \end{align*}\]| 从上述可以看出，$V_n$中的元素都是在产生式的左部，且 $ Z \in V_n$中，此外，当左部一样时，可以用$ | $合并在一起，称为文法的BNF表示 |
推导的形式定义
\[\begin{align*} &\textsf{文法}G: v = xUy, \quad w = xuy \\ & \textsf{其中}x,y \in V^*， U \in V_n, u \in V^* \\ &若U::=u \in P, 则v \underset{G}{\Rightarrow}w\\ &若x=y=\epsilon, 有U::=u, 则U \underset{G}{\Rightarrow}u \end{align*}\]这个G也可以用规则来表示。当符号串没有终结符号时，推导终止
当我们通过至少一次推导得到一个符号，可以表示为$v\overset{+}{\Rightarrow}w$,若可以通过任意次推导(也可以0次)，，就记为$v\overset{*}{\Rightarrow}w$。
规范推导，当$xUy$中的$y \in V_t$时，称为规范推导 最右推导：若规则右端符号串有两个以上时，先推右边的(y) 最左推导：若规则右端符号串有两个以上时，先推左边的(x) 直观上，规范推导=最右推导（可以一步步的推进使其成为终结符）
语言的形式定义
\[\begin{align*} &\textsf{文法}G[Z] \\ &(1) x是句型 \Leftrightarrow Z \overset{*}\Rightarrow x, \text{and}\ x \in V^* \\ &(2) x是句子 \Leftrightarrow Z \overset{+}\Rightarrow x, \text{and}\ x \in V_t^* \\ &(3) x是语言 \Leftrightarrow L(G[Z]) = \{x|x \in V_t^*, Z \overset{+}\Rightarrow x \} \\ \end{align*}\]通过其定义可以看出，语言为文法产生的所有句子的集合。 而若句型仅有非终结符组成，那么其就是句子。由此，句子一定是句型，句型不一定是句子
由此也能得出，在已知文法的情况下，可以通过推导来判断一个符号串是否属于该文法的语言。而如果只已知语言，是无形式化的方法来判断文法的。通常的，一个语言可以对应多个文法。
例子如下：
\[\begin{align*} &\{a\underset{n}{\underbrace{b \dots b}}a | n \ge 1 \}为语言，构造文法 \\ G_1[Z]: \\ & Z \rightarrow aBa, \\ & B \rightarrow b|bB, \\ G_2[Z]: \\ & Z \rightarrow aBa, \\ & B \rightarrow b|Bb, \\ \end{align*}\]将语言相同的不同文法，即$L(G_1)=L(G_2)$,称为等价文法。
递归文法
如果文法中存在形如$A \rightarrow Aa$的产生式，称为递归文法。递归文法的语言是无限的，因为可以通过无限次的推导得到。其好处也就在于可以利用有限条件来描述无限的语言。
上述的这种情况成为左递归（相同的符号在左边），同理便有右递归，自嵌入递归(在中间的情况)。
短句、简单短语、句柄
\[\begin{align*} &给定文法G[Z], 句型 \ w = xuy \in V^+ \\ &若Z \overset{*}\Rightarrow xUy, and \ U \overset{+}\Rightarrow u 则称u是句型w相对于U的短语 \\ &若Z \overset{*}\Rightarrow xUy, and \ U \Rightarrow u 则称u是句型w相对于U的简单短语 \\ \end{align*}\]直观来看，短语就是任何非终结符能推出的符号串，每个句型都是相对于Z的短语
句柄任一句型的最左简单短语就是句柄。即有短语$\rightarrow$ 简单短语 $\rightarrow$ 句柄。因此句柄只有一个。而由于x,y对应的不同，短语和简单短语也都不同。
例子 文法G(<无符号整数>), 句型<数字串>1，则求短语、简单短语和句柄
推导过程如下:
\[<无符号整数> \Rightarrow <数字串>\Rightarrow<数字串> <数字> \Rightarrow <数字串>1\]- <无符号整数> $\overset{*}{\Rightarrow}$<无符号整数>，且<无符号整数>$\overset{+}\Rightarrow$<数字串>1，则<数字串>1是相对于<无符号整数>的短语。（证实句型都是相对于初始符号的短语\\
- <无符号整数> $\overset{*}{\Rightarrow}$<数字串>，且<数字串>$\overset{+}\Rightarrow$<数字串>1，则<数字串>1是相对于<数字串>的短语\\
- <无符号整数> $\overset{*}{\Rightarrow}$<数字串><数字>，且<数字> $\Rightarrow$ 1，则1是相对于<数字>的短语，且为简单短语
由于其唯一的简单短语是1，因此1便为这个这个句型的句柄
