优先关系 和树上的写法不一样,凑合用 Si≡S Si≥SjSi≤S 注意:≡,≥,≤之间不同于=,>和<。 由Si≥S不能导出Sj≤Si
优先关系 • 和树上的写法不一样，凑合用。 SiSj Si Sj Si Sj • 注意： ， ， 之间不同于=，>和<。 由Si Sj不能导出Sj Si
优先关系的例子 文法:z∷=bMbM:=LaL:=Ma) 语言:{bab,ba)b,b(a)b,} 可以从语法树里面到处部分优先关系 M b<aa≥b L≥b
优先关系的例子 • 文法：Z::=bMb M::=(L|a L::=Ma) • 语言：{bab, b(aa)b, b((aa)a)b, …} • 可以从语法树里面到处部分优先关系。 b M b a Z b a a b b M b Z ( L b ( (L L b
优先矩阵 可以将优先 关系填写到z 个矩阵, 得到优先矩 阵。(将矩阵a 作为关系的 ><< 表示形式)
优先矩阵 • 可以将优先 关系填写到 一个矩阵， 得到优先矩 阵。 (将矩阵 作为关系的 表示形式） Z M L a b ( ) ZM = = L > > a > > ( < = < < b = < < ) > > =
识别过程(例子) 文法:G52 Z∷∵=bMb M: L a L: =Ma) 输入:b(a)a)b 过程 #b((aa)a)b井 <<< 句柄:a归纳为M #b((ma)a)b# << 句柄:Ma)归纳为L #b((l a)b# <<=> 句柄L归纳为M
识别过程(例子) • 文法: G5.2 Z::=bMb M::=(L | a L::=Ma) • 输入: b((aa)a)b • 过程: # b ( ( a a ) a ) b # < < < < > 句柄: a 归纳为M # b ( ( M a ) a ) b # < < < < = = > 句柄: M a) 归纳为L # b ( ( L a ) b # < < < = > 句柄: (L 归纳为M
识别过程例子续) b(ma)b# < 句柄Ma)归纳为L #b(lb# <=> 句柄:L归纳为M #b(ma)b# 句柄:Ma)归纳为L #b(l b# <=> 句柄L归纳为M # bmb # 句柄:bMb归纳为Z
识别过程(例子续) # b ( L b # < < = > 句柄: (L 归纳为M # b ( M a ) b # < < < = = > 句柄: Ma) 归纳为L # b ( M a ) b # < < < = = > 句柄: Ma) 归纳为L # b M b # < = = > 句柄: bMb 归纳为Z # b ( L b # < < = > 句柄: (L 归纳为M