CYK算法实现

概述

在计算机科学领域,CYK算法(也称为Cocke–Younger–Kasami算法)是一种用来对上下文无关文法(CFG,Context Free Grammar)进行语法分析(parsing)的算法。该算法最早由John Cocke, Daniel Younger and Tadao Kasami分别独立提出,其中John Cocke还是1987年度的图灵奖得主。CYK算法是基于动态规划思想设计的一种自底向上语法分析算法。

乔姆斯基范式

CNF(Chomsky Normal Form)是一种这样的语法标准: 如果一个CFG \(\epsilon-free\),而且它的规则只有如下两种形式:

  • \(A \rightarrow B C\)
  • \(A \rightarrow a\)

那么这个CFG就是CNF形式的,可见CNF语法都是二分叉的。任何语法都可以转化成一个弱等价的CNF形式,具体方法如下:

  • Step 1: Convert \(A \rightarrow Bc\) to \(A\rightarrow BC, C\rightarrow c\)
  • Step 2: Convert \(A \rightarrow BCD\) to \(A \rightarrow BX, X \rightarrow CD\)

CYK算法

CYK算法处理的语法必须是CNF形式的,所以如果输入的是任意文法,那么需要按照前面的步骤把CFG转换成CNF形式。

CYK算法是用来判断一个字符串是否属于某个CNF语法,故设输入的字符串w长度为n。

接下来我们需要用程序填一个动态规划的状态转移表,这里我们叫这个表parse table。

parse table的规模为\((n + 1) \times n\)

我们定义\(PT[n + 1][n]\)表示parse table,且\(PT[n, :]\)依次存储字符串w中的每一个符号(\(a_1, a_2, \dots, a_n\))。

\[ \begin{pmatrix} & &\dots & \\ & \vdots & \ddots & \\ a_1 & a_2 & \dots &a_n \end{pmatrix} \]

我们设根据给定CNF,即G能推导出w中第i到第j个字符的串的集合为\(x_{i,j}\)

为了填写这个表,我们一行一行,自下而上地处理。每一行对应一种长度的子串。最下面一行对应长度为1的子串,倒数第二行对应长度为2的子串,以此类推。最上面一行就对应长度为n的子串,即w本身。计算该表的任何一个表项的方法如下:

  1. 对于最下面一行的元素,即\(x_{i,i}\),是使得\(A \rightarrow a_i\)是G的产生式的变元A的集合
  2. 对于不在最下面一行的元素,我们需要找到符合以下条件的变元A的集合:
    1. 整数k满足\(i \leq k < j\)
    2. \(B \in X_{i,k}\)
    3. \(C \in X_{k+1, j}\)
    4. \(A \rightarrow BC\)是G的产生式

根据这样的方法,我们可以填出一个下三角矩阵。

例如:

CNF文法G的产生式:

\[ S \rightarrow AB|BC \\ A \rightarrow BA|a \\ B \rightarrow CC|b \\ C \rightarrow AB|a \] 对L(G)测试字符串\(w = baaba\)的成员性构造Parse Table如下:

\[ \begin{pmatrix} x_{1,5}=\{S, A,C\} & & & & \\ & x_{2,5}=\{S, A, C\} & & & \\ & x_{2,4}=\{B\} & x_{3,5}=\{B\} & & \\ x_{1,2} = \{S, A\} & x_{2,3}=\{B\} & x_{3,4}=\{S, C\} & x_{4,5}=\{S, A\} &\\ x_{1,1} = \{B\} & x_{2,2} = \{A, C\} & x_{3,3} =\{A, C\} & x_{4,4}=\{B \} & x_{5,5}=\{A,C\} \\ a_1 = b & a_2 = a & a_3 = a & a_4 = b & a_5 = a \end{pmatrix} \]

最终得到\(x_{1,5}\)集合之后,判断起始变元\(S\)是否属于\(x_{1,5}\)。如果是,则w可被G接受,反之不接受。

程序展示

CNF.cfg

1
2
3
4
S -> AB
A -> BC | a
B -> AC | b
C -> a | b

CYK_algo.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#!usr/bin/env/python 3.6.5
#-*- coding: utf-8 -*-
'''
Python 3.6.5
installed module:
- tkinter
'''

import re
import itertools
import tkinter
from tkinter import ttk


class CNF(object):
def __init__(self):
self.__rules = {}


def read_file(self, filename):
with open(filename, 'r') as inFile:
for line in inFile.readlines():
line = re.sub('[\n\t ]', '', line)
rec_begin = line[:line.find('-')]
for element in line[line.find('>') + 1:].split('|'):
if element in self._CNF__rules:
self.__rules[element].append(rec_begin)
else:
self._CNF__rules[element] = [rec_begin]


def get_inf(self, tar):
if isinstance(tar, list) == False: exit()
inf_set = []
for tarEle in tar:
inf_set.extend(self.__rules.get(tarEle, []))
return list(set(inf_set))


class CYK(object):
def __init__(self, filename):
if isinstance(filename, str) == False: exit()
self.__str = ''
self.__srtlen = 0
self.__canvas = []
self.__myCNF = CNF()
self.__myCNF.read_file(filename)


def get_str(self):
self._CYK__str = input('input string:\n').strip()
if len(self._CYK__str) == 0: exit()
self._CYK__srtlen = len(self._CYK__str)
# MaxRow == MaxCol + 1
self._CYK__canvas = list(list([] for tmp in range(self._CYK__srtlen)) for tmp in range(self._CYK__srtlen + 1))
for iter in range(self._CYK__srtlen):
self._CYK__canvas[self._CYK__srtlen][iter].append(self._CYK__str[iter])


def CYK_process(self):
# for lowest level
for col in range(self._CYK__srtlen):
self._CYK__canvas[self._CYK__srtlen - 1][col].extend(self._CYK__myCNF.get_inf(self._CYK__canvas[self._CYK__srtlen][col]))
# for upper level
for row in range(self._CYK__srtlen - 2, -1, -1):
for col in range(row + 1):
mid_set = set()
idx_i, idx_j = col + 1, col - row + self._CYK__srtlen
for mid_k in range(idx_i, idx_j):
fir_row, fir_col = idx_i - mid_k - 1 + self._CYK__srtlen, idx_i - 1
sec_row, sec_col = mid_k - idx_j + self._CYK__srtlen, mid_k
mid_set |= set(obj[0] + obj[1] for obj in itertools.product(self._CYK__canvas[fir_row][fir_col], self._CYK__canvas[sec_row][sec_col]))
self._CYK__canvas[row][col].extend(self._CYK__myCNF.get_inf(list(mid_set)))
# get answer
if 'S' in self._CYK__canvas[0][0]:
print ('%s can be accepted.' % self._CYK__str)
else:
print ('%s can not be accepted.' % self._CYK__str)


def GUI_show(self):
def exc(line, step, row):
if isinstance(line, list) == False and isinstance(line[0], list) == False: exit()
for col in range(len(line)):
line[col] = str('{' + '%s, ' * (len(line[col]) - 1) + '%s' * (len(line[col]) > 0) + '}') % (tuple(line[col]))
if col <= row: line[col] = 'X%d,%d = ' % (col + 1, step + col + 1) + line[col]
return (line)

# default
window = tkinter.Tk()
window.geometry('800x400')
window.title('CYK algorithm')
table = ttk.Treeview(window, height = 10, show = 'headings')
table['columns'] = (list(elem for elem in range(self._CYK__srtlen)))
for col in range(self._CYK__srtlen):
table.column(str(col), width = 100)
# y&x scrollbar
yscrollbar = tkinter.Scrollbar(window, orient = tkinter.VERTICAL, command = table.yview)
table.configure(yscrollcommand = yscrollbar.set)
yscrollbar.pack(side = tkinter.RIGHT, fill = tkinter.Y)

xscrollbar = tkinter.Scrollbar(window, orient = tkinter.HORIZONTAL, command = table.xview)
table.configure(xscrollcommand = xscrollbar.set)
xscrollbar.pack(side = tkinter.TOP, fill = tkinter.X)
# insert information
for row in range(self._CYK__srtlen):
table.insert('', row, values = exc(self._CYK__canvas[row], self._CYK__srtlen - row - 1, row))
table.insert('', self._CYK__srtlen, values = (self._CYK__canvas[self._CYK__srtlen]))

# end
table.pack(side = tkinter.TOP, expand = 1, fill = tkinter.BOTH)
window.mainloop()


def main():
myCYK = CYK('./CNF.cfg')
myCYK.get_str()
myCYK.CYK_process()
myCYK.GUI_show()


if __name__ == '__main__':
main()

实验效果:

commandline
GUI

CYK算法实现
https://blog.scubot.com/article/7120/
作者
贺翔/CarOL
发布于
2019年4月28日
许可协议