上下文无关法
一个生动的例子
自然语言中的句子的典型结构 ：
- 主语 谓语 宾语
- 名词 动词 名词
例子：
- 名词：{羊、老虎、草、水}
- 动词：{吃、喝}
- 句子：羊吃草、老虎喝水、老虎吃草、老虎吃水、羊喝草等等（因为是语法分析，所以暂时不考虑语义的正确性）
用字母代替上述词语：名词N、动词V、羊s、老虎t、草g、水w、吃e、喝d。
形式化如下：
S -> N V N
N -> s
N -> t
N -> g
N -> w
V -> e
V -> d
//非终结符： {S, N, V}
//终结符： {s, t, g, w, e, d}
//开始符号： S- 由N可以推出{s, t, g, w}，V可以推出{e, d}，S可以推出N V N。
- N、V、S这些可以推出其他符号的叫非终结符
- s, t, g, w, e, d这些不能够再推出其他符号的叫终结符
- S是整个结构的开始，称为开始符号
- 像$S \rightarrow N V N$、$N \rightarrow s$这样的式子叫做产生式
- 这种写法又叫做文法
这里我们约定俗成大写字母表示非终结符号，小写字母表示终结符号。其他地方也有可能不一样。
得出公式
上下文无关文法G是一个四元组： $G=(T,N,P,S)$
- T是终结符集合
- N是非终极符集合
P是一组产生式规则
- 规则形式：$X \rightarrow β_1 β_2 ...$
- 其中$X ∈ N$，$β ∈ (T U N)$
- S是唯一的开始符号，切$S ∈ N $
另一个例子
E -> num
| id
| E + E
| E * E
// G = (N, T, P, S)
// N = {E}
// T = {num, id, +, *}
// S = E
// P = 略以后为了方便书写与直观感受，相同部分直接用或符号 “|”代替
分析树和二义性
分析树
推导可以表达成树状结构（和推导所用的顺序无关）
特点：
- 非叶子结点代表非终结符
- 叶子节点代表终结符
- 每一步推导代表如何从双亲节点生成它的直接孩子节点
示例
E -> num
| id
| E + E
| E * E
// 推导句子：3+4*5
E -> E + E
-> 3 + E
-> 3 + E * E
-> 3 + 4 * E
-> 3 + 4 * 5
// 推导方式2
E -> E * E
-> E + E * E
-> 3 + E * E
-> 3 + 4 * E
-> 3 + 4 * 5分析树分别如下(左右)：
分析树的含义取决于树的后序遍历。
二义性
- 给定文法G，如果存在句子s，它有两棵不同的分析树，那么称G是二义性文法。
- 从编译器角度，二义性文法使同一个程序会有不同的含义，因此程序运行的结果不唯一
- 解决方案： 文法的重写
E -> E + T
| T
T -> T * F
| F
F -> num
| id
// 推导句子：3+4*5
E -> E + T
-> T + T
-> F + T
-> 3 + T
-> 3 + T * F
-> 3 + F * F
-> 3 + 4 * F
-> 3 + 4 * 5其他基本概念
- 最左推导：每次总是选择最左侧的符号进行替换。
- 最右推导：每次总是选择最右侧的符号进行替换。
- 句柄：给定句型中的最左简单短语就是句柄。
- 句型：开始符号 S → x，其中x是非终结符or终结符。
- 句子：开始符号 S → x，其中x是终结符。(给定文法G，从G的开始符号S开始，用产生式的右部替换左侧的非终结符，此过程不断重复，直到不出现非终结符为止，最终的串称为句子)
给定文法G和句子s，语法分析要回答的问题：是否存在对句子s的推导。
- 活前缀：在得到一个规范句型的完整句柄之前所识别的符号串
从语法分析树看3个概念：
- 短语：一个句型的语法树中任一子树叶结点所组成的符号串
- 直接短语：子树中不再包含其他的子树，不能再推出其他的式子，即叶子结点。
- 句柄：给定句型中的最左简单短语就是句柄
短语/直接短语/句柄 案例
问：
解：
$E+T*F$为此文法的一个句型：
- 短语: $T*F$， $E+T*F$
- 直接短语/简单短语：$T*F$
- 句柄：$T*F$
简析：对于子树T来说，其所有叶子节点为：$T*F$，对于E来说，其所有叶子节点为：$E+T*F$，故短语为 $T*F$ 和 $E+T*F$， 直接短语为 $T*F$， 句柄为最左边的直接短语$T*F$
- - - 结束 - - -