第10章-成分句法分析.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b53f78ca",
   "metadata": {},
   "source": [
    "\n",
    "以下是双仿射函数的代码实现。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "5d5fbc71",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 代码来源于GitHub项目Alibaba-NLP/ACE\n",
    "# （Copyright (c) 2020, Xinyu Wang, MIT License（见附录））\n",
    "import torch\n",
    "import torch.nn as nn\n",
    "\n",
    "class Biaffine(nn.Module):\n",
    "    def __init__(self, n_in, n_out=1, bias_x=True, bias_y=True,\\\n",
    "                diagonal=False):\n",
    "        super(Biaffine, self).__init__()\n",
    "        # n_in：输入特征大小\n",
    "        # n_out：输出的打分数量（边预测为1，标签预测即为标签数量）\n",
    "        # bias_x：为输入x加入线性层\n",
    "        # bias_y：为输入y加入线性层\n",
    "        self.n_in = n_in\n",
    "        self.n_out = n_out\n",
    "        self.bias_x = bias_x\n",
    "        self.bias_y = bias_y\n",
    "        self.diagonal = diagonal\n",
    "        # 对角线化参数，让原本的参数矩阵变成了对角线矩阵，\n",
    "        # 从而大幅度减少运算复杂度，一般在计算标签的得分时会使用\n",
    "        if self.diagonal:\n",
    "            self.weight = nn.Parameter(torch.Tensor(n_out,\n",
    "                                                    n_in + bias_x))\n",
    "        else:\n",
    "            self.weight = nn.Parameter(torch.Tensor(n_out,\n",
    "                                                    n_in + bias_x,\n",
    "                                                    n_in + bias_y))\n",
    "        self.reset_parameters()\n",
    "\n",
    "\n",
    "    def reset_parameters(self):\n",
    "        nn.init.normal_(self.weight)\n",
    "\n",
    "    def forward(self, x, y):\n",
    "        # 当bias_x或bias_y为True时，为输入x或y的向量拼接额外的1\n",
    "        if self.bias_x:\n",
    "            x = torch.cat((x, torch.ones_like(x[..., :1])), -1)\n",
    "        if self.bias_y:\n",
    "            y = torch.cat((y, torch.ones_like(y[..., :1])), -1)\n",
    "\n",
    "        # PyTorch中的einsum可以很简单地实现矩阵运算\n",
    "        # 思路是为输入的张量的每个维度分别定义一个符号\n",
    "        # （例如输入x、y的第一维是批大小，定义为b）\n",
    "        # 并且定义输出的张量大小，这个函数会自动地根据\n",
    "        # 前后的变化计算张量乘法、求和的过程\n",
    "        # 例如下面的einsum函数中的bxi,byi,oi->boxy，\n",
    "        # 表示的是输入的3个张量大小分别为b * x * i、b * y * i和o * i\n",
    "        # 输出则是b * o * x * y\n",
    "        # 根据这个式子，可以看出3个张量都有i这个维度，\n",
    "        # 在输出时被消除了\n",
    "        # 因此3个张量的i维通过张量乘法（三者按位相乘然后求和）\n",
    "        # 进行消除\n",
    "        # 这个算法的好处是相比于手动实现，\n",
    "        # einsum可以更容易地避免运算过程中出现很大的张量大幅占用显存\n",
    "        # 同时也避免了手动实现的流程\n",
    "        # 具体使用方法请参考PyTorch文档\n",
    "        if self.diagonal:\n",
    "            s = torch.einsum('bxi,byi,oi->boxy', x, y, self.weight)\n",
    "        else:\n",
    "            s = torch.einsum('bxi,oij,byj->boxy', x, self.weight, y)\n",
    "        # 当n_out=1时，将第一维移除\n",
    "        s = s.squeeze(1)\n",
    "\n",
    "        return s"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "90b793a4",
   "metadata": {},
   "source": [
    "现在我们举一个简单的例子来看双仿射函数是如何进行打分的："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "63b1c31c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tensor([[[0.7518, 4.9461],\n",
      "         [2.2237, 1.5331]]], grad_fn=<SqueezeBackward1>)\n"
     ]
    }
   ],
   "source": [
    "biaffine = Biaffine(4)\n",
    "# 假设批大小为1，句子长度为2，词数量为4\n",
    "x=torch.randn(1,2,4)\n",
    "y=torch.randn(1,2,4)\n",
    "scores = biaffine(x,y)\n",
    "print(scores)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "161ab212",
   "metadata": {},
   "source": [
    "下面给出具体的CKY算法实现。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "46063375",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 代码来源于GitHub项目yzhangcs/crfpar\n",
    "# （Copyright (c) 2020, Yu Zhang, MIT License（见附录））\n",
    "import torch\n",
    "\n",
    "def cky(scores, mask):\n",
    "    '''\n",
    "    scores：大小为批大小 * 序列长度 * 序列长度，\n",
    "    每个位置表示跨度的打分，例如scores[0,1,2]就表示\n",
    "    第0个输入样例上跨度(1,2)的打分（跨度(i,j)不包括j位置，\n",
    "    因此跨度(1,2)即对应的只有1个词的跨度的打分）。\n",
    "    \n",
    "    mask：与scores的大小一样，表示对打分的掩码，\n",
    "    根据句子长度的不同，掩码大小不同。假设句子0长度为5，\n",
    "    那么mask[0,:5,:5]中所有值都为1，mask[0]上的其余位置为0\n",
    "    '''\n",
    "    # 通过对掩码求和的方式找到每个句子的长度\n",
    "    lens = mask[:, 0].sum(-1).long()\n",
    "    # 批大小 * 序列长度 * 序列长度 -> 序列长度 * 序列长度 * 批大小，\n",
    "    # 方便后续运算\n",
    "    scores = scores.permute(1, 2, 0)\n",
    "    seq_len, seq_len, batch_size = scores.shape\n",
    "    \n",
    "    # 复制一个新的与scores大小相同的张量，其中s表示新计算出的跨度得分，\n",
    "    # p表示得分最高的位置（也就是max k），位置信息用long()表示\n",
    "    s = scores.new_zeros(seq_len, seq_len, batch_size)\n",
    "    p = scores.new_zeros(seq_len, seq_len, batch_size).long()\n",
    "    \n",
    "    # 设w为跨度，从小的跨度到大跨度进行遍历\n",
    "    for w in range(1, seq_len):\n",
    "        # 通过seq_len - w可以计算出当前长度有多少长度为w的跨度\n",
    "        n = seq_len - w\n",
    "        # 根据n生成0到n的列表\n",
    "        starts = p.new_tensor(range(n)).unsqueeze(0)\n",
    "        \n",
    "        # 当跨度w为1的时候，没有中间值k，\n",
    "        # 直接将结果赋值到s中作为max score\n",
    "        if w == 1:\n",
    "            # diagonal(w)表示抽取对角线，w的大小为偏置，\n",
    "            # 当偏置为0时，则直接为对角线，\n",
    "            # 当偏置大于0，则对角线上移（也就是(0,1),(1,2),……）\n",
    "            # 具体细节请查看PyTorch文档\n",
    "            s.diagonal(w).copy_(scores.diagonal(w))\n",
    "            continue\n",
    "\n",
    "        # 计算跨度为w情况下，s_best(i,k)+s_best(k,j)的值，\n",
    "        # strip()函数下面会介绍，\n",
    "        # 它每次取出大小为n * w-1 * batch_size的矩阵\n",
    "        s_span = stripe(s, n, w-1, (0, 1)) + stripe(s, n, w-1, (1, w), 0)\n",
    "        # n * w-1 * batch_size -> batch_size * n * w-1\n",
    "        s_span = s_span.permute(2, 0, 1)\n",
    "        # 计算max(s_best(i,k)+s_best(k,j))，以及对应的k值\n",
    "        s_span, p_span = s_span.max(-1)\n",
    "        # 更新s_best(i,j) = s(i,j)+max(s_best(i,k)+s_best(k,j))\n",
    "        s.diagonal(w).copy_(s_span + scores.diagonal(w))\n",
    "        # 保留最大的k值，由于p_span并不对应在原来的矩阵中的位置，\n",
    "        # 因此需要加上starts+1来还原\n",
    "        p.diagonal(w).copy_(p_span + starts + 1)\n",
    "\n",
    "    def backtrack(p, i, j):\n",
    "        # 通过分治法找到之前所有得分最大的span\n",
    "        if j == i + 1:\n",
    "            return [(i, j)]\n",
    "        split = p[i][j]\n",
    "        ltree = backtrack(p, i, split)\n",
    "        rtree = backtrack(p, split, j)\n",
    "        return [(i, j)] + ltree + rtree\n",
    "    \n",
    "    p = p.permute(2, 0, 1).tolist()\n",
    "    # 从最大的跨度(0,length)开始，逐渐找到中间最大的k值，还原整个成分\n",
    "    trees = [backtrack(p[i], 0, length)\n",
    "             for i, length in enumerate(lens.tolist())]\n",
    "\n",
    "    return trees\n",
    "\n",
    "\n",
    "\n",
    "def stripe(x, n, w, offset=(0, 0), dim=1):\n",
    "    r'''Returns a diagonal stripe of the tensor.\n",
    "    Parameters:\n",
    "        x：输入的超过2维的张量\n",
    "        n：输出的斜对角矩阵的长度\n",
    "        w：输出的斜对角矩阵的宽度\n",
    "        offset：前两个维度的偏置\n",
    "        dim：当其为0则抽取纵向斜对角矩阵；1则是横向斜对角矩阵\n",
    "    例子：\n",
    "    >>> x = torch.arange(25).view(5, 5)\n",
    "    >>> x\n",
    "    tensor([[ 0,  1,  2,  3,  4],\n",
    "            [ 5,  6,  7,  8,  9],\n",
    "            [10, 11, 12, 13, 14],\n",
    "            [15, 16, 17, 18, 19],\n",
    "            [20, 21, 22, 23, 24]])\n",
    "    >>> n = 2\n",
    "    >>> w = 3\n",
    "    >>> stripe(x, n, w-1, (0, 1))\n",
    "    tensor([[ 1,  2],\n",
    "            [ 7,  8]])\n",
    "    >>> stripe(x, n, w-1, (1, w) dim=0)\n",
    "    tensor([[  8,  13],\n",
    "            [ 14,  19]])\n",
    "    可以看出，当跨度长度为3时，\n",
    "    两个矩阵的第一行分别表示跨度为：\n",
    "    [(0,1),(0,2)]和[(1,3),(2,3)]，\n",
    "    可以看出枚举了对于跨度为(0,3)有两种跨度组合：\n",
    "    s(0,1)+s(1,3)\n",
    "    s(0,2)+s(2,3)\n",
    "    '''\n",
    "    x, seq_len = x.contiguous(), x.size(1)\n",
    "    # 根据x的形状创建步长列表，numel为批大小\n",
    "    stride, numel = list(x.stride()), x[0, 0].numel()\n",
    "    # 设置行和列的步长，假设当前位置为(i,j)，\n",
    "    # stride[0]会取出(i+1,j+1)的值，作为输出矩阵的下一行值\n",
    "    stride[0] = (seq_len + 1) * numel\n",
    "    # 假设当前位置为(i,j)，stride[1]会取出(i+1,j)的值，作为下一列的值\n",
    "    stride[1] = (1 if dim == 1 else seq_len) * numel\n",
    "    return x.as_strided(size=(n, w, *x.shape[2:]), stride=stride,\n",
    "        storage_offset=(offset[0]*seq_len+offset[1])*numel)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0947414c",
   "metadata": {},
   "source": [
    "给定一个句子“learning probalistic grammar is difficult”，为每个跨度打分（简单起见，这里没有考虑标签），并调用CKY算法得到句法树："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "de20299c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tensor([[[0., 1., 1., 1., 1., 1.],\n",
      "         [0., 0., 1., 1., 1., 1.],\n",
      "         [0., 0., 0., 1., 1., 1.],\n",
      "         [0., 0., 0., 0., 1., 1.],\n",
      "         [0., 0., 0., 0., 0., 1.],\n",
      "         [0., 0., 0., 0., 0., 0.]]])\n",
      "[[(0, 5), (0, 3), (0, 1), (1, 3), (1, 2), (2, 3), (3, 5), (3, 4), (4, 5)]]\n"
     ]
    }
   ],
   "source": [
    "# 句子“learning probalistic grammar is difficult”一共有5个词，\n",
    "# 额外加上根节点后，score的张量大小为1 * 6 * 6\n",
    "# score是一个上三角矩阵，其余部分用-999代替\n",
    "\n",
    "score = torch.Tensor([\n",
    "        [ -999,  1,  -1,  1,  -1, 1],\n",
    "        [ -999,  -999,  1,  1,  -1, -1],\n",
    "        [ -999, -999, -999, 1, -1, -1],\n",
    "        [ -999, -999, -999, -999, 1, 1],\n",
    "        [ -999, -999, -999, -999, -999, 1],\n",
    "        [ -999, -999, -999, -999, -999, -999]]\n",
    "    ).unsqueeze(0)\n",
    "\n",
    "# mask应该是一个上三角矩阵\n",
    "mask = torch.ones_like(score)\n",
    "mask = torch.triu(mask,diagonal=1)\n",
    "\n",
    "print(mask)\n",
    "\n",
    "trees=cky(score,mask)\n",
    "print(trees)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d4c9ff39",
   "metadata": {},
   "source": [
    "现在画出这个成分句法树。这里使用supar代码包来画成分句法树。supar是一个开源且好用的句法、成分、语义分析工具包。我们没有为标签进行打分，因此这里使用空标签。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "2e2c308f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                           TOP                    \n",
      "                            |                      \n",
      "                            |                     \n",
      "               _____________|_________             \n",
      "              |                       |           \n",
      "    __________|_______                |            \n",
      "   |                  |               |           \n",
      "   |           _______|_____       ___|______      \n",
      "   |          |             |     |          |    \n",
      "   |          |             |     |          |     \n",
      "   _          _             _     _          _    \n",
      "   |          |             |     |          |     \n",
      "learning probalistic     grammar  is     difficult\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from supar.models.const.crf.transform import Tree\n",
    "draw_tree=[(i,j,'|') for i,j in trees[0]]\n",
    "Tree.build(['learning', 'probalistic', 'grammar', 'is',\\\n",
    "    'difficult'],draw_tree,root='TOP').pretty_print()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c79ac426",
   "metadata": {},
   "source": [
    "内向算法的实现也和CKY算法类似。下面是具体的实现代码。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "56390d41",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 代码来源于GitHub项目yzhangcs/crfpar\n",
    "# （Copyright (c) 2020 Yu Zhang, MIT License（见附录））\n",
    "def inside(scores, mask):\n",
    "    # 大部分内容与cky()函数相同，相同部分不再复述\n",
    "    batch_size, seq_len, _ = scores.shape\n",
    "    scores, mask = scores.permute(1, 2, 0), mask.permute(1, 2, 0)\n",
    "    # 我们会对score求exponential，因此\n",
    "    s = torch.full_like(scores, float('-inf'))\n",
    "\n",
    "    for w in range(1, seq_len):\n",
    "        n = seq_len - w\n",
    "        if w == 1:\n",
    "            s.diagonal(w).copy_(scores.diagonal(w))\n",
    "            continue\n",
    "        s_span = stripe(s, n, w-1, (0, 1)) + stripe(s, n, w-1, (1, w), 0)\n",
    "        s_span = s_span.permute(2, 0, 1)\n",
    "        # 防止数据出现nan\n",
    "        if s_span.requires_grad:\n",
    "            s_span.register_hook(lambda x: \\\n",
    "                x.masked_fill_(torch.isnan(x), 0))\n",
    "        # 这里使用PyTorch中的logsumexp()函数实现指数求和的过程，\n",
    "        # logsumexp()可以有效防止exp后数据溢出的情况\n",
    "        s_span = s_span.logsumexp(-1)\n",
    "        s.diagonal(w).copy_(s_span + scores.diagonal(w))\n",
    "\n",
    "    return s\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "17647378",
   "metadata": {},
   "source": [
    "下面是计算损失函数的过程。首先计算人工标注句法树的得分，也就是将该树的所有跨度得分求和，然后用内向算法得出的所有可能的树的得分取幂之和，最终计算损失函数值。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "7b66fb2f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 代码来源于GitHub项目yzhangcs/crfpar\n",
    "# （Copyright (c) 2020 Yu Zhang, MIT License（见附录））\n",
    "@torch.enable_grad()\n",
    "def crf(scores, mask, target=None):\n",
    "    lens = mask[:, 0].sum(-1).long()\n",
    "    total = lens.sum()\n",
    "    batch_size, seq_len, _ = scores.shape\n",
    "    # 训练过程中需要保证scores能够返回梯度\n",
    "    training = scores.requires_grad\n",
    "    # 计算内向算法，求得可能的树的得分和\n",
    "    s = inside(scores.requires_grad_(), mask)\n",
    "    logZ = s[0].gather(0, lens.unsqueeze(0)).sum()\n",
    "    # (scores * target * mask).sum()可以求出目标树的得分和，\n",
    "    # 与logZ相减后求平均损失\n",
    "    loss = (logZ - (scores * target * mask).sum()) / total\n",
    "    return loss,\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd0120f1",
   "metadata": {},
   "source": [
    "接下来计算以下实际的损失函数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "e86fab75",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "目标矩阵： tensor([[[0, 1, 0, 1, 0, 1],\n",
      "         [0, 0, 1, 1, 0, 0],\n",
      "         [0, 0, 0, 1, 0, 0],\n",
      "         [0, 0, 0, 0, 1, 1],\n",
      "         [0, 0, 0, 0, 0, 1],\n",
      "         [0, 0, 0, 0, 0, 0]]])\n",
      "内部函数计算结果(即所有可能的成分树分数和)： tensor(9.4121)\n",
      "loss： (tensor(0.0824, grad_fn=<DivBackward0>),)\n"
     ]
    }
   ],
   "source": [
    "# score是一个上三角矩阵，其余部分用-999代替\n",
    "\n",
    "score = torch.Tensor([\n",
    "    [ -999,  1,  -1,  1,  -1, 1],\n",
    "    [ -999,  -999,  1,  1,  -1, -1],\n",
    "    [ -999, -999, -999, 1, -1, -1],\n",
    "    [ -999, -999, -999, -999, 1, 1],\n",
    "    [ -999, -999, -999, -999, -999, 1],\n",
    "    [ -999, -999, -999, -999, -999, -999]]).unsqueeze(0)\n",
    "\n",
    "# mask应该是一个上三角矩阵\n",
    "mask = torch.ones_like(score)\n",
    "mask = torch.triu(mask,diagonal=1).long()\n",
    "\n",
    "# 在本例子中，假设score预测树与训练的目标target一样\n",
    "target = torch.Tensor([\n",
    "    [ 0,  1,  0,  1,  0, 1],\n",
    "    [ 0,  0,  1,  1,  0, 0],\n",
    "    [ 0, 0, 0, 1, 0, 0],\n",
    "    [ 0, 0, 0, 0, 1, 1],\n",
    "    [ 0, 0, 0, 0, 0, 1],\n",
    "    [ 0, 0, 0, 0, 0, 0]]).unsqueeze(0)\n",
    "\n",
    "\n",
    "print('目标矩阵：',target)\n",
    "\n",
    "s=inside(score,mask)\n",
    "logZ = s[0].gather(0, lens.unsqueeze(0)).sum()\n",
    "\n",
    "print('内部函数计算结果(即所有可能的成分树分数和)：',logZ)\n",
    "\n",
    "loss = crf(score,mask,target)\n",
    "print('loss：',loss)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e002dd70",
   "metadata": {},
   "source": [
    "<!--#### 推理代码实现-->\n",
    "\n",
    "下面我们提供一套代码来展示在基于转移的句法分析过程中，如何根据转移动作的打分去对栈和缓存进行操作。如果读者想要运行该代码，需自行定义model。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "6b69ca97",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 部分代码参考了GitHub项目kmkurn/pytorch-rnng \n",
    "# (Copyright 2017 Kemal Kurniawan, MIT License（见附录）)\n",
    "# 假设当模型预测的SHIFT 操作id为0，REDUCE操作id为1，\n",
    "# 非终极符的标签为其他大于1的值\n",
    "SHIFT_ID=0\n",
    "REDUCE_ID=1\n",
    "\n",
    "# 这里假设只有3个标签\n",
    "label_set = {2: 'S', 3: 'NP', 4: 'VP'}\n",
    "\n",
    "class element:\n",
    "    # word_id：一个存储成分结构的列表，例如(S (NP 1 2) 3)\n",
    "    # 这棵树表示为[S [NP 1 2] 3]\n",
    "    def __init__(self,word_id,is_open_nt):\n",
    "        self.is_open_nt=is_open_nt\n",
    "        if self.is_open_nt:\n",
    "            self.word_id=[word_id]\n",
    "        else:\n",
    "            self.word_id=word_id\n",
    "\n",
    "\n",
    "def decode(words,model):\n",
    "    # words：每个元素为(word_idx, word_id)的元组，\n",
    "    # word_idx为句子中的位置，word_id则为词表中的id\n",
    "    # model：这里不具体构建模型，仅作为一个示例\n",
    "    # 缓存buffer初始化，将words翻转，能够保证pop()操作能够从前往后进行\n",
    "    buffer = words[::-1]\n",
    "    # 栈stack初始化\n",
    "    stack = []\n",
    "    # 保存操作历史\n",
    "    history = []\n",
    "    # 统计当前栈中开放的非终极符数量\n",
    "    num_open_nt = 0\n",
    "    # 循环转移迭代\n",
    "    while 1:\n",
    "        # 模型通过buffer，stack和history计算下一步操作的打分\n",
    "        log_probs = model(buffer,stack,history)\n",
    "        # 得到得分最高的操作id\n",
    "        action_id = torch.max(log_probs)[1]\n",
    "        # 当action_id分别为0,1和大于1时，\n",
    "        # 分别为其做SHIFT，REDUCE和push_nt操作\n",
    "        if action_id == SHIFT_ID:\n",
    "            buffer,stack = shift(buffer,stack)\n",
    "        elif action_id == REDUCE_ID:\n",
    "            stack = reduce(buffer,stack)\n",
    "            num_open_nt -= 1\n",
    "        else:\n",
    "            stack = push_nt(stack,action_id)\n",
    "            num_open_nt += 1\n",
    "        # 将当前操作记录到历史中\n",
    "        history.append(action_id)\n",
    "        # 当缓存为空，栈只有一个元素且它不是开放的非终极符时，则退出\n",
    "        if num_open_nt == 0 and len(buffer) == 0 and\\\n",
    "                len(stack) == 1 and stack[0].is_open_nt == False:\n",
    "            break\n",
    "    # 返回操作历史和整棵树\n",
    "    return history, stack[0]\n",
    "\n",
    "def shift(buffer,stack):\n",
    "    # 将buffer中的词移动到栈顶\n",
    "    word_id=buffer.pop()\n",
    "    stack.append(element(word_id,False))\n",
    "    return buffer, stack \n",
    "\n",
    "def reduce(stack):\n",
    "    children = []\n",
    "    # 重复地从栈中弹出完整的子树或终极符，直到遇到一个开放的非终极符\n",
    "    while len(stack) > 0 and stack[-1].is_open_nt == False:\n",
    "        children.append(stack.pop())\n",
    "    # 循环pop()过程会将顺序颠倒，这里将其变回原来的顺序\n",
    "    children = children[::-1]\n",
    "    # 这些节点的word_id将成为当前开放的非终极符的子节点，\n",
    "    # 我们将这些节点取出，成为一个新的列表\n",
    "    children_ids = [child.word_id for child in children]\n",
    "    # 将子节点放入非终极符的word_id中\n",
    "    stack[-1].word_id+=children_ids\n",
    "    # 将非终极符关闭\n",
    "    stack[-1].is_open_nt = False\n",
    "    \n",
    "    return stack\n",
    "\n",
    "def push_nt(stack,action_id):\n",
    "    # 将action_id转换为具体的标签，放入栈顶\n",
    "    stack.append(element(label_set[action_id],False))\n",
    "    return stack\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}