10,000 英尺概览
您需要使用小型自定义解析器执行此操作:代码采用此形式的输入并将其转换为所需的形式。
在实践中,我发现根据解析问题的复杂性将此类问题分组到三个类别中是很有用的:
-
琐碎:可以通过几个循环和人性化的正则表达式来解决的问题。这个类别很诱人:如果你甚至有点不确定问题是否可以通过这种方式解决,那么一个好的经验法则是决定它不能。
-
容易:这些问题需要自己构建一个小解析器,但仍然足够简单,以至于带出大枪不太有意义。如果您需要编写超过约100行代码,请考虑升级到下一个类别。
-
涉及:对于需要正式化并使用已经存在的、经过验证的解析器生成器¹是有意义的问题。
我将这个特殊问题归类为属于第二类,这意味着您可以像这样处理它:
编写小型解析器
定义语法
为此,您必须首先定义 ( 至少非正式地,使用一些快速注释 - 要解析的语法。请记住,大多数语法在某些时候都是递归定义的。假设我们的语法是:
- 输入是一个序列
- 序列是零个或多个标记的序列序列
- 标记可以是单词、字符串或数组
- 标记由一个或多个空格字符分隔
- 单词是字母字符 (a-z) 的序列
- 字符串是括在双引号内的任意字符序列
- 数组是一系列用逗号分隔的一个或多个标记
你可以看到我们在一个地方有递归:一个序列可以包含数组,一个数组也是根据一个序列定义的(所以它可以包含更多的数组等)。
如上所述非正式地处理这个问题作为介绍更容易,但是如果你正式地这样做,关于语法的推理会更容易。
构建词法分析器
有了语法,您知道需要将输入分解为标记,以便可以对其进行处理。接受用户输入并将其转换为由语法定义的各个部分的组件称为词法分析器。词法师是愚蠢的;他们只关心输入的“外观”,并不试图检查它是否真的有意义。
这是我写的一个简单的词法分析器来解析上面的语法(不要用它来做任何重要的事情;可能包含错误):
$input = 'all ("hi there", (this, that) , other) another';
$tokens = array();
$input = trim($input);
while($input) {
switch (substr($input, 0, 1)) {
case '"':
if (!preg_match('/^"([^"]*)"(.*)$/', $input, $matches)) {
die; // TODO: error: unterminated string
}
$tokens[] = array('string', $matches[1]);
$input = $matches[2];
break;
case '(':
$tokens[] = array('open', null);
$input = substr($input, 1);
break;
case ')':
$tokens[] = array('close', null);
$input = substr($input, 1);
break;
case ',':
$tokens[] = array('comma', null);
$input = substr($input, 1);
break;
default:
list($word, $input) = array_pad(
preg_split('/(?=[^a-zA-Z])/', $input, 2),
2,
null);
$tokens[] = array('word', $word);
break;
}
$input = trim($input);
}
print_r($tokens);
构建解析器
完成此操作后,下一步是构建一个解析器:一个检查词法输入并将其转换为所需格式的组件。解析器是智能的;在转换输入的过程中,它还确保输入由语法规则正确形成。
解析器通常实现为状态机(也称为有限状态机或有限自动机),其工作方式如下:
- 解析器具有状态;这通常是适当范围内的数字,但每个状态也用更人性化的名称来描述。
- 有一个循环,一次读取一个读取的词法标记。根据令牌的当前状态和值,分析器可以决定执行下列一项或多项操作:
- 采取一些影响其输出的操作
- 将其状态更改为其他值
- 确定输入格式不正确并产生错误
¹ 解析器生成器是其输入是正式语法的程序,其输出是词法分析器和解析器,您可以“只需添加水”即可:只需扩展代码即可根据令牌的类型执行“采取一些操作”;其他一切都已经处理好了。关于这个主题的快速搜索给出了领先的PHP Lexer和Parser Generator?