上下文无关法
一个生动的例子
自然语言中的句子的典型结构 :
- 主语 谓语 宾语
- 名词 动词 名词
例子:
- 名词:{羊、老虎、草、水}
- 动词:{吃、喝}
- 句子:羊吃草、老虎喝水、老虎吃草、老虎吃水、羊喝草等等(因为是语法分析,所以暂时不考虑语义的正确性)
用字母代替上述词语:名词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$
- - - 结束 - - -