1.7　HTML

我曾承诺递归对操作层次化定义的数据结构有用，我还用了文件系统作为一个例子。但它是个稍微特殊的数据结构的例子，因为通常认为数据结构是在内存里，而不是在磁盘上。

文件系统的树型结构让人联想到目录，每个目录都含有一列其他文件。任何拥有一些包含其他条目列表的领域都将含有树型结构。一个极好的例子是HTML数据。

HTML数据是一系列元素和普通文本。每个元素含有一些内容，它们又是一系列更多的元素和更多的普通文本。这是个递归的描述，类似文件系统的描述，HTML文件的结构也类似于文件系统的结构。

元素有一个开始标签（start tag），如下：

<font>

与相应的结束标签（end tag），如下：

</font>

开始标签可以有一组 属性-值对（attribute杤alue pair），如下：

<font size=3 color="red">

结束标签总是一样的。它没有属性-值对。

在开始标签和结束标签之间可以存在任何HTML文本序列，包括其他元素，也包括普通文本。这里有一个简单的HTML文件例子：

<h1>What Junior Said Next</h1>

<p>But I don't <font size=3 color="red">want</font>
to go to bed now!</p>

这个文件的结构如图1-3所示：

文件主要有三个组成部分：<h1>元素与它的内容；<p>元素与它的内容；以及它们之间的空行。<p>元素依次有三个组成部分：在 <font>元素之前没有标记的文本；<font>元素与它的内容；以及<font>元素之后未标记的文本。<h1>元素有一个组成部分，就是未标记的文本What Junior Said Next。

第8章将介绍如何建立一个针对类似HTML语言的解析器。此刻将考察一个半标准的模块HTML::TreeBuilder，它把一个HTML文件转换成一个树型结构。

假设HTML数据已经在一个变量里了，如$html。下面的代码使用HTML::TreeBuilder把文本转换成一个清晰的树型结构：

use HTML::TreeBuilder;
my $tree = HTML::TreeBuilder->new;
$tree->ignore_ignorable_whitespace(0);
$tree->parse($html);
$tree->eof();

方法ignore_ignorable_whitespace()告诉HTML::TreeBuilder不允许丢弃某些空白符，如<h1>元素后的换行符，正常情况下这是可忽略的。

现在$tree表示树型结构。它是散列树，每个散列是树的一个节点并表示一个元素。每个散列有一个键_tag，它的值是它的标签名；还有一个键_content，它的值是元素内容依次排列的一个列表；_content列表中的每个条目或者是一个字符串，表示没有标签的文本，或者是另一个散列，表示另一个元素。如果标签还有属性-值对，那它们都直接存放在散列中，属性作为散列的键，相应的值作为散列的值。

例如，与例子中的<font>元素对应的树节点如下：

{ _tag => "font",
  _content => [ "want" ],
  color => "red",
  size => 3,
}

与<p>元素对应的树节点包含<font>节点，如下：

{ _tag => "p",
  _content => [ "But I don't ",
                { _tag => "font",
                  _content => [ "want" ],
                  color => "red",
                  size => 3,
                },
                " to go to bed now!",
              ],
}

建立一个函数遍历这些HTML树之一并为所有文本“去标签”，即剥离标签，并不困难。对于_content列表中的每个条目，都可以通过ref()函数把它识别成一个元素，前者对元素（即散列引用）产生真，对普通字符串则是假：

### Code Library: untag-html
sub untag_html {
  my ($html) = @_;
  return $html unless ref $html; # It's a plain string

  my $text = '';
  for my $item (@{$html->{_content}}) {
    $text .= untag_html($item);
  }

  return $text;
}

函数检查传入的HTML条目是否是一个普通的字符串，如果是，函数立即返回它。如果它不是一个普通的字符串，函数假设它是一个树节点，如前所述，并迭代它的内容，递归地把每个条目转换成普通文本，累积成结果字符串并返回它。对于这个例子，就是：

What Junior Said Next But I don't want to go to bed now!

Sean Burke，HTML::TreeBuilder的作者，告诉我如此获得HTML::TreeBuilder对象的内部信息是不规范的，因为他可能在未来改变它们。健壮的程序应该使用模块提供的访问器方法。在这些例子中，将继续直接获取内部信息。
可以向dir_walk()学习，通过把这个函数分成两部分而使它更有用：一部分处理HTML树，另一部分处理累积普通文本的专门任务：

### Code Library: walk-html
sub walk_html {
  my ($html, $textfunc, $elementfunc) = @_;
  return $textfunc->($html) unless ref $html; # It's a plain string

  my @results;
  for my $item (@{$html->{_content}}) {
    push @results, walk_html($item, $textfunc, $elementfunc);
  }
  return $elementfunc->($html, @results);
}

这个函数的结构和dir_walk()的完全一样。它以两个辅助的函数为参数：$textfunc计算一个普通文本字符串的某个有意思的值，$elementfunc接受元素与其间条目的值计算与一个元素相对应的值。$textfunc类似dir_walk()中的$filefunc，$elementfunc类似$dirfunc。

现在可以把剥离器写成如下这样：

walk_html($tree, sub { $_[0] },
                 sub { shift; join '', @_ });

参数$textfunc是一个函数，它原封不动地返回它的参数。参数$elementfunc是一个函数，它丢弃元素本身，然后连接为它的内容计算得到的文本，并返回连接的文本。输出和untag_html()的一样。

假设我们想要一个文件摘要，输出在<h1>标签内的文本，而丢弃其他东西：

sub print_if_h1tag {
  my $element = shift;
  my $text = join '', @_;
  print $text if $element->{_tag} eq 'h1';
  return $text;
}
walk_html($tree, sub { $_[0] }, \&print_if_h1tag);

这本质上和untag_html()一样，除了当元素函数看到它正在处理一个<h1>元素时，它就输出未标记的文本。
如果期望函数返回（return）头部文本而不是输出它，那么必须用点小技巧。考虑一个这样的例子：

<h1>Junior</h1>
Is a naughty boy.

***丢弃文本Is a naughty boy，这样它就不出现在结果中了。但是对于walk_html()，它只不过是另一个普通文本条目，和Junior看起来完全一样，而后者是不想丢弃的。也许应当简单地丢弃出现在非头部标签中的所有东西，但是这样行不通：

<h1>The story of <b>Junior</b></h1>

不能仅由于Junior出现在<b>标签里而丢弃它，因为<b>标签本身也在<h1>标签里，但是想保留它。

可以这样解决这个问题：从每个walk_html()的执行体把有关当前标签的上下文的信息传递到下一个执行体，但它以其他方式传回信息更简单。文件中的文本或者是“该留的”，因为知道它在一个<h1>元素内，或者是“也许该留的”，因为我们不知道。每当处理一个<h1>元素时，就将把它包含的所有“也许该留的”文本提升为“该留的”文本。最后，将输出“该留的”文本并丢弃“也许该留的”文本：

### Code Library: extract-headers
@tagged_texts = walk_html($tree, sub { ['MAYBE', $_[0]] },
                                 \&promote_if_h1tag);
sub promote_if_h1tag {
  my $element = shift;
  if ($element->{_tag} eq 'h1') {
    return ['KEEPER', join '', map {$_->[1]} @_];
  } else {
    return @_;
  }
}

从walk_htm()返回的值将是一列带标记的文本条目。每个文本条目是一个匿名数组，它的第一个元素是MAYBE或者KEEPER，而第二个条目是一个字符串。普通文本函数简单地标记它的参数为MAYBE。对于字符串Junior，它返回带标记的条目['MAYBE', 'Junior']；对于字符串Is a naughty boy.，它返回['MAYBE', 'Is a naughty boy.']。

元素函数更有趣。它得到一个元素和一列带标记的文本条目。如果元素表现为一个<h1>标签，那么函数从它的其他参数中抽取所有的文本，合并到一起，并把结果标记为KEEPER。如果元素是其他种类，函数原封不动地返回它的标签文本。这些文本将插入带标记文本的列表，然后传递给元素函数调用，作为上一层元素，比较这个与1.5节中最后的dir_walk()例子，后者以类似方式返回一列文件名。

因为最后从walk_html()返回的值是标记文本的列表，所以需要过滤它们并丢弃仍然标记为MAYBE的那些。这最后一步是不能省略的。由于函数区别对待顶层的和嵌入在<h1>标签内的不带标签的文本条目，因此就必须有某部分过程能知晓在顶层的东西。walk_html()无法做到，因为它在每层做同样的事情。所以必须建立一个最终的函数处理顶层：

sub extract_headers {
  my $tree = shift;
  my @tagged_texts = walk_html($tree, sub { ['MAYBE', $_[0]] },
                                      \&promote_if_h1tag);
  my @keepers = grep { $_->[0] eq 'KEEPER'} @tagged_texts;
  my @keeper_text = map { $_->[1] } @keepers;
  my $header_text = join '', @keeper_text;
  return $header_text;
}

或者可以写得更紧凑：

sub extract_headers {
  my $tree = shift;
  my @tagged_texts = walk_html($tree, sub { ['MAYBE', $_[0]] },
                                      \&promote_if_h1tag);
  join '', map { $_->[1] } grep { $_->[0] eq 'KEEPER'} @tagged_texts;
}

刚才看到了如何从HTML文件中抽取所有<h1>标签的文本。主要的过程是promote_if_h1tag()。但是下次也许会想要抽取更详细的摘要，包括来自<h1>、<h2>、<h3>以及其他存在的标签的所有文本。为做到这个，需要对promote_if_h1tag()做个小改动，把它变成一个新的函数：

sub promote_if_h1tag {
  my $element = shift;
  if ($element->{_tag} =~ /^h\d+$/) {
    return ['KEEPER', join '', map {$_->[1]} @_];
  } else {
    return @_;
  }
}

但是如果promote_if_h1tag能比最初意识到的更普遍适用，那将是个提取普遍有用的部分的好方法。可以把变化的部分参数化以达到此目的：

### Code Library: promote-if
sub promote_if {
  my $is_interesting = shift;
  my $element = shift;
  if ($is_interesting->($element->{_tag})) {
    return ['KEEPER', join '', map {$_->[1]} @_];
  } else {
    return @_;
  }
}

现在不必写个专门的函数promote_if_h1tag()了，可以把同样的行为表现成promote_if()的一个特殊情况。不用写成：

my @tagged_texts = walk_html($tree, sub { ['MAYBE', $_[0]] },
                                           \&promote_if_h1tag);

可以用这个：

my @tagged_texts = walk_html($tree,
                              sub { ['MAYBE', $_[0]] },
                              sub { promote_if(
                                       sub { $_[0] eq 'h1'},
                                       @_)
                              });

第7章将介绍完成此任务的更整齐的方式。