README

LocoX 是一个用于 PHP 的解析库和工具包。最终，它将支持其他语言作为输出目标。它默认是一个递归下降自顶向下的解析器。同样，最终也可能支持其他解析风格，并且它被设计得非常简单，以便支持这种支持。

这些解析器风格不需要单独的词法分析步骤，但如果你愿意，LocoX 仍然可以有一个单独的词法分析器/解析器。在 PHP 中执行解析的一种最快方式是使用正则表达式生成输入文本的词法分析，然后使用递归下降设置递归到令牌中。LocoX 支持这种解析风格。

或者，如果你愿意，你也可以完全跳过词法分析器，直接以递归方式解析原始文本。这并不很快，但在 99% 的情况下，“足够快”。同样，LocoX 支持这种解析风格。

实际上，LocoX 支持各种解析器风格（除了提到的表驱动解析器）

• LocoX 可以作为“现场”解析器或解析器生成器。你可以直接将对象式的解析器操作符列表（甚至可以创建自己的）作为数组提供给它，以创建所需的语法，或者使用以下许多语法表示法之一来生成语法。
• LocoX 可以使用以下语法表示法/表达式语法作为解析器生成器
  • BNF
  • EBNF
  • Wirth 表示法
  • 基本正则表达式（基于正则表达式片段生成解析器）
  • 全面支持 PEG 语法
  • 扩展自定义语法

LocoX 使用单值解析器，称为 MonoParser。传统的、“热情”的解析器返回一组可能的结果，如果无法解析，则该组为空。而“懒惰”的解析器在第一次调用时返回一个可能的结果，然后在每次后续调用时返回更多结果，直到没有更多结果为止。相比之下，MonoParser 仅返回一个结果或失败。这反过来使回溯成为不可能，这有两个影响

• 它将表达能力降低到仅限于某些 无歧义 的上下文无关文法
• 它阻止解析时间成为指数级。

LocoX 直接解析字符串，无需中间词法分析步骤。

LocoX 在语法创建时检测无限循环（例如 (|a)*）和 左递归（例如 A -> Aa）。

LocoX 中的解析器

MonoParser

所有解析器继承的抽象基类。不能实例化。“Mono”意味着解析器返回一个结果或失败。

Ab\LocoX\MonoParser 有一个重要的方法，match($string, $i = 0)，它要么以 array("j" => 9, "value" => "something") 的形式返回成功的匹配，要么抛出 Ab\LocoX\ParseFailureException。

还有一个更有用的方法 parse($string)，它要么返回解析值 "something"，要么在匹配失败或未占用提供的字符串的全部长度时抛出 Ab\LocoX\ParseFailureException。

EmptyParser

找到空字符串（总是成功）。回调函数不传递任何参数。默认回调返回 null。

new Ab\LocoX\Clause\Terminal\EmptyParser();
// returns null

new Ab\LocoX\Clause\Terminal\EmptyParser(
  function() { return array(); }
);
// return an empty array instead

StringParser

查找静态字符串。回调函数传递一个参数，即匹配到的字符串。是的，每次调用该函数都是同样的效果。默认回调函数返回第一个参数，即字符串。

new Ab\LocoX\Clause\Terminal\StringParser("name");
// returns "name"

new Ab\LocoX\Clause\Terminal\StringParser(
  "name",
  function($string) { return strrev($string); }
);
// returns "eman"

RegexParser

匹配正则表达式。正则表达式必须锚定在要匹配的子字符串的开始位置，使用 ^。否则，PHP 将无法停止在表达式其他位置进行匹配，这非常糟糕。注意：类似 /^a|b/ 的结构仅在字符串的开始位置锚定 "a"；"b" 可能在任何位置匹配！你应该使用 /^(a|b)/ 或 /^a|^b/。

为每个子匹配传递一个参数给回调函数。例如，如果正则表达式是 /^ab(cd(ef)gh)ij/，那么第一个参数是整个匹配，"abcdefghij"，第二个参数是 "cdefgh"，第三个参数是 "ef"。默认回调函数只返回第一个参数，即整个匹配。

new Ab\LocoX\Clause\Terminal\RegexParser("/^'([a-zA-Z_][a-zA-Z_0-9]*)'/");
// returns the full match including the single quotes

new Ab\LocoX\Clause\Terminal\RegexParser(
  "/^'([a-zA-Z_][a-zA-Z_0-9]*)'/",
  function($match0, $match1) { return $match1; }
);
// discard the single quotes and returns only the inner string

Utf8Parser

匹配单个 UTF-8 字符。你可以选择性地提供一个字符黑名单，其中包含 不会 匹配的字符。

new Ab\LocoX\Clause\Terminal\Utf8Parser(array("<", ">", "&"));
// any UTF-8 character except the three listed

回调函数传递一个参数，即匹配到的字符串。默认回调函数返回第一个参数，即字符串。

为了获得最佳结果，交替（参见下方的 Ab\LocoX\Clause\Nonterminal\OrderedChoice）使用 Ab\LocoX\Clause\Terminal\StringParsers，例如 "<"、">"、"&" 和其他 HTML 字符实体。

OrderedChoice

这通过在几个内部解析器之间交替来封装“交替”解析器组合器。这里的关键词是“惰性”。只要其中一个匹配成功，就返回该结果，这就是故事的结局。没有能力合并几个内部解析器的结果，也没有能力返回（回溯）到这个解析器并尝试获取其他结果，如果第一个结果被证明是无效的。

回调函数传递一个参数，即唯一的成功内部匹配。默认回调函数直接返回第一个参数。

new Ab\LocoX\Clause\Nonterminal\OrderedChoice(
  array(
    new Ab\LocoX\Clause\Terminal\StringParser("foo"),
    new Ab\LocoX\Clause\Terminal\StringParser("bar")
  )
);
// returns either "foo" or "bar"

Sequence

这通过连接有限序列的内部解析器来封装“连接”解析器组合器。如果序列为空，则这与上面的 Ab\LocoX\Clause\Terminal\EmptyParser 等价。

为每个内部解析器传递一个参数给回调函数，每个参数都包含该解析器的结果。例如，new Ab\LocoX\Clause\Nonterminal\Sequence(array($a, $b, $c), $callback) 将传递三个参数给它的回调函数。第一个包含解析器 $a 的结果，第二个包含解析器 $b 的结果，第三个包含解析器 $c 的结果。默认回调函数以数组的形式返回参数：return func_get_args();。

new Ab\LocoX\Clause\Nonterminal\Sequence(
  array(
    new Ab\LocoX\Clause\Terminal\RegexParser("/^<([a-zA-Z_][a-zA-Z_0-9]*)>/", function($match0, $match1) { return $match1; }),
    new Ab\LocoX\Clause\Terminal\StringParser(", "),
    new Ab\LocoX\Clause\Terminal\RegexParser("/^<(\d\d\d\d-\d\d-\d\d)>/",     function($match0, $match1) { return $match1; }),
    new Ab\LocoX\Clause\Terminal\StringParser(", "),
    new Ab\LocoX\Clause\Terminal\RegexParser("/^<([A-Z]{2}[0-9]{7})>/",       function($match0, $match1) { return $match1; }),
  ),
  function($name, $comma1, $opendate, $comma2, $ref) { return new Account($accountname, $opendate, $ref); }
);
// match something like "<Williams>, <2011-06-30>, <GH7784939>"
// return new Account("Williams", "2011-06-30", "GH7784939")

BoundedRepeat

这封装了“Kleene 星号闭包”解析器组合器来匹配单个内部解析器多次（有限次或无限次）。有限上限时，这几乎与上面的 Ab\LocoX\Clause\Nonterminal\Sequence 等价。无限上限时，这更有趣。名为 Ab\LocoX\Clause\Nonterminal\BoundedRepeat 的解析器，正如其名所示，会尽可能多地匹配，然后返回。没有同时返回多个匹配的选项；只返回最大的匹配。也没有回溯和尝试消费更多或更少实例的选项。

为每个匹配传递一个参数给回调函数。例如，new Ab\LocoX\Clause\Nonterminal\BoundedRepeat($a, 2, 4, $callback) 可以传递 2、3 或 4 个参数给它的回调函数。new BoundedRepeat($a, 0, null, $callback) 有无限上限，并可以向回调函数传递无限数量的参数。（PHP 似乎没有问题。）默认回调函数以数组的形式返回所有参数：return func_get_args();。

请记住，PHP 函数可以定义为 function(){...} 并仍然接受任意数量的参数。

new Ab\LocoX\Clause\Nonterminal\BoundedRepeat(
  new Ab\LocoX\Clause\Nonterminal\OrderedChoice(
    array(
      new Ab\LocoX\Clause\Terminal\Utf8Parser(array("<", ">", "&")),                         // match any UTF-8 character except <, > or &
      new Ab\LocoX\Clause\Terminal\StringParser("&lt;",  function($string) { return "<"; }), // ...or an escaped < (unescape it)
      new Ab\LocoX\Clause\Terminal\StringParser("&gt;",  function($string) { return ">"; }), // ...or an escaped > (unescape it)
      new Ab\LocoX\Clause\Terminal\StringParser("&amp;", function($string) { return "&"; })  // ...or an escaped & (unescape it)
    )
  ),
  0,                                                  // at least 0 times
  null,                                               // at most infinitely many times
  function() { return implode("", func_get_args()); } // concatenate all of the matched characters together
);
// matches a continuous string of valid, UTF-8 encoded HTML text
// returns the unescaped string

Grammar

以上内容都很好，但并不完整。首先，当它们嵌套得太深时，会使我们的解析器变得很大，难以阅读。其次，它使得递归变得非常困难；例如，解析器不能轻易地放在自己内部。没有递归，我们只能解析正则语言，而不是上下文无关语言。

Ab\LocoX\Grammar 类使这变得非常简单。在核心上，Ab\LocoX\Grammar 只是一个另一个 Ab\LocoX\MonoParser。但 Ab\LocoX\Grammar 接受一个解析器的关联数组作为输入——这意味着每个解析器都附带一个名称。同时，其中的解析器可以通过名称引用其他解析器，而不是直接包含它们。Ab\LocoX\Grammar 在实例化时解决这些引用，并检测诸如左递归、引用不存在的解析器的名称、危险的结构（例如新的 Ab\LocoX\Clause\Nonterminal\BoundedRepeat(new Ab\LocoX\Clause\Terminal\EmptyParser(), 0, null)）等问题。

这是一个简单的 Ab\LocoX\Grammar，它可以识别（一些）有效的 HTML 段落，并返回这些段落的文本内容

$p = new Ab\LocoX\Grammar(
  "paragraph",
  array(
    "paragraph" => new Ab\LocoX\Clause\Nonterminal\Sequence(
      array(
        "OPEN_P",
        "CONTENT",
        "CLOSE_P"
      ),
      function($open_p, $content, $close_p) {
        return $content;
      }
    ),

    "OPEN_P" => new Ab\LocoX\Clause\Terminal\StringParser("<p>"),

    "CONTENT" => new Ab\LocoX\Clause\Nonterminal\BoundedRepeat(
      "UTF-8 CHAR",
      0,
      null,
      function() { return implode("", func_get_args()); }
    ),

    "CLOSE_P" => new Ab\LocoX\Clause\Terminal\StringParser("</p>"),

    "UTF-8 CHAR" => new Ab\LocoX\Clause\Nonterminal\OrderedChoice(
      array(
        new Ab\LocoX\Clause\Terminal\Utf8Parser(array("<", ">", "&")),                         // match any UTF-8 character except <, > or &
        new Ab\LocoX\Clause\Terminal\StringParser("&lt;",  function($string) { return "<"; }), // ...or an escaped < (unescape it)
        new Ab\LocoX\Clause\Terminal\StringParser("&gt;",  function($string) { return ">"; }), // ...or an escaped > (unescape it)
        new Ab\LocoX\Clause\Terminal\StringParser("&amp;", function($string) { return "&"; })  // ...or an escaped & (unescape it)
      )
    ),
  )
);

$p->parse("<p>Your text here &amp; here &amp; &lt;here&gt;</p>");
// returns "Your text here & here & <here>"

示例

Loco 还附带了一系列公共领域的示例

examples/json.php

解析 JSON 表达式，并返回 PHP 数组。

examples/regEx.php

解析简单的正则表达式，并返回表示它们的 PHP 对象。

examples/simpleComment.php

使用 <h5>、<p>、<em> 和 <strong> 识别简单有效的 HTML 文本，带有平衡的标签和转义实体。

examples/bnf.php

定义 $bnfGrammar，它可以解析以 Backus-Naur 形式 表示的语法，并返回能够识别该语法的 Ab\LocoX\Grammar 对象。

BNF 通常技术含量不高，缺乏很多功能。

Backus-Naur 形式的示例语法

这出现在维基百科上。这是一个相当笨拙的例子，因为它没有处理空白，也没有定义很多变量，这些变量我必须自己定义。然而，它传达了要点。

<postal-address> ::= <name-part> <street-address> <zip-part>
<name-part>      ::= <personal-part> <name-part> | <personal-part> <last-name> <opt-jr-part> <EOL>
<personal-part>  ::= <initial> "." | <first-name>
<street-address> ::= <house-num> <street-name> <opt-apt-num> <EOL>
<zip-part>       ::= <town-name> "," <state-code> <ZIP-code> <EOL>
<opt-jr-part>    ::= "Sr." | "Jr." | <roman-numeral> | ""

<last-name>     ::= 'MacLaurin '
<EOL>           ::= '\n'
<initial>       ::= 'b'
<first-name>    ::= 'Steve '
<house-num>     ::= '173 '
<street-name>   ::= 'Acacia Avenue '
<opt-apt-num>   ::= '7A'
<town-name>     ::= 'Stevenage'
<state-code>    ::= ' KY '
<ZIP-code>      ::= '33445'
<roman-numeral> ::= 'g'

示例语法中的字符串

Steve MacLaurin \n173 Acacia Avenue 7A\nStevenage, KY 33445\n

examples/wirth.php

定义 $wirthGrammar，它可以解析以 Wirth 语法表示法 表示的语法，并返回能够识别该语法的 Ab\LocoX\Grammar 对象。

Wirth 语法表示法还不错，但我不喜欢使用 .（在我的思维中通常表示“任何字符”（在正则表达式中使用）或字符串连接运算符）作为行结束符（我通常认为它是分号或实际的 \n）。我也不喜欢使用方括号表示可选项，以及花括号表示 Kleene 星号闭包。这些在意义上都不够明确。

Wirth 语法表示法中的示例语法

SYNTAX     = { PRODUCTION } .
PRODUCTION = IDENTIFIER "=" EXPRESSION "." .
EXPRESSION = TERM { "|" TERM } .
TERM       = FACTOR { FACTOR } .
FACTOR     = IDENTIFIER
           | LITERAL
           | "[" EXPRESSION "]"
           | "(" EXPRESSION ")"
           | "{" EXPRESSION "}" .
IDENTIFIER = letter { letter } .
LITERAL    = """" character { character } """" .
digit      = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
upper      = "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" 
           | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" 
           | "U" | "V" | "W" | "X" | "Y" | "Z" .
lower      = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" 
           | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" 
           | "u" | "v" | "w" | "x" | "y" | "z" .
letter     = upper | lower .
character  = letter | digit | "=" | "." | """""" .

这个示例语法恰好是描述 Wirth 语法表示法的语法本身——如果从中移除了所有空白。观察

示例语法中的字符串

SYNTAX={PRODUCTION}.

examples/ebnf.php

定义 $ebnfGrammar，它可以解析以 扩展 Backus-Naur 形式 表示的语法，并返回能够识别该语法的 Grammar 对象。

这是对原始 BNF 的一次重大改进（注释是必需的！）但需要在标记之间添加逗号令人烦恼，而且在我看来，花括号和方括号也不理想。

$ebnfGrammar 无法处理“特殊”项（位于两个问号之间的字符串），因为这些没有明确的定义。它也无法处理“异常”（当使用 - 来排除某些可能性时），因为这些在上下文无关语法中不允许，也不可能在简单的 Ab\LocoX\MonoParser 中实现，因此需要修改 Loco 以处理。

扩展 Backus-Naur 形式的示例语法

(* a simple program syntax in EBNF - Wikipedia *)
program = 'PROGRAM' , white space , identifier , white space ,
           'BEGIN' , white space ,
           { assignment , ";" , white space } ,
           'END.' ;
identifier = alphabetic character , { alphabetic character | digit } ;
number = [ "-" ] , digit , { digit } ;
string = '"' , { all characters } , '"' ;
assignment = identifier , ":=" , ( number | identifier | string ) ;
alphabetic character = "A" | "B" | "C" | "D" | "E" | "F" | "G"
                     | "H" | "I" | "J" | "K" | "L" | "M" | "N"
                     | "O" | "P" | "Q" | "R" | "S" | "T" | "U"
                     | "V" | "W" | "X" | "Y" | "Z" ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
white space = ( " " | "\n" ) , { " " | "\n" } ;
all characters = "H" | "e" | "l" | "o" | " " | "w" | "r" | "d" | "!" ;

示例语法中的字符串

PROGRAM DEMO1
BEGIN
  A0:=3;
  B:=45;
  H:=-100023;
  C:=A;
  D123:=B34A;
  BABOON:=GIRAFFE;
  TEXT:=\"Hello world!\";
END."

examples/locoNotation.php

定义了 $locoGrammar，它解析以“Loco表示法”呈现的语法，并返回一个可以解析该语法的 Ab\LocoX\Grammar 对象。

“Loco表示法”（因为没有更好的名字）是巴科斯-诺尔范式的一种扩展，它提供了访问Loco提供的所有 Ab\LocoX\MonoParser 的途径。以下解析器已经在大多数语法表示法中有效可用

• Ab\LocoX\Clause\Terminal\EmptyParser - 只需有一个空字符串或一个规则的空右侧。一些表示法还允许显式的“epsilon”符号。
• Ab\LocoX\Clause\Terminal\StringParser - 总是需要一个简单的字符串字面量，使用单引号或双引号。
• Ab\LocoX\Clause\Nonterminal\Sequence - 通常你将多个标记排成一行，它们将被连续匹配。在EBNF中，逗号必须用作分隔符。
• Ab\LocoX\Clause\Nonterminal\OrderedChoice - 使用可能性之间的管道符（|）实现交替。
• Ab\LocoX\Clause\Nonterminal\BoundedRepeat - 大多数表示法提供了一些使匹配可选（通常是方括号）的能力，以及匹配无限次数（通常是星号或花括号）。

我不得不为以下内容发明新的表示法

• Ab\LocoX\Clause\Terminal\RegexParser - 在斜杠之间放置你的正则表达式，就像在Perl中一样。
• Ab\LocoX\Clause\Terminal\Utf8Parser - 要匹配任何单个UTF-8字符，请放置一个句点（.）。要黑名单某些字符，请将黑名单中的字符放在 [^ 和 ] 之间。

在这两种情况下，我都从标准正则表达式语法中借用了表示法，因为为什么不保持熟悉呢？

在所有提供“字面量”（字符串、正则表达式、UTF-8异常）的情况中，您可以通过使用反斜杠转义来在“字面量”内部放置相应的关闭定界符（即 "、'、/ 或 ]）。例如："\""、'\''、/\//、[^\]]。您还可以放置一个反斜杠本身，如果使用第二个反斜杠来转义它。例如："\\"、'\\'、/\\/、[^\\]。

Loco表示法中的示例语法

还记得 examples/simpleComment.php 吗？这里是这个语法在Loco表示法中的样子。

comment    ::= whitespace block*
block      ::= h5 whitespace | p whitespace
p          ::= '<p'      whitespace '>' text '</p'      whitespace '>'
h5         ::= '<h5'     whitespace '>' text '</h5'     whitespace '>'
strong     ::= '<strong' whitespace '>' text '</strong' whitespace '>'
em         ::= '<em'     whitespace '>' text '</em'     whitespace '>'
br         ::= '<br'     whitespace '/>'
text       ::= atom*
atom       ::= [^<>&] | '&' entity ';' | strong | em | br
entity     ::= 'gt' | 'lt' | 'amp'
whitespace ::= /[ \n\r\t]*/

看看我是如何放置 /[ \n\r\t]*/ 来匹配无限序列的空白。这可以通过使用更多的规则和StringParsers来实现，但RegexParsers更强大、更优雅。

还可以看到我是如何放置 [^<>&] 来匹配“除了 <、> 或 & 之外的任何UTF-8字符”。

示例语法中的字符串

<h5>  Title<br /><em\n><strong\n></strong>&amp;</em></h5>
   \r\n\t 
<p  >&lt;</p  >

关于Loco

Loco的创建是因为我想让人们在我的网站上使用XHTML注释，并希望以灵活的方式验证XHTML，从XHTML的狭小子集开始，并随着时间的推移添加对更多标签的支持。我相信编写解析库比手动编写（然后不断重写）解析器更有效、更有教育意义。

Loco以及Loco语法 examples/simpleComment.php 满足了第一个目标。这些被成功使用了几年。后来，我开发了 examples/locoNotation.php，这使事情对我而言更加简单。然而，也有一些缺点

• 每当评论提交PHP脚本运行时，都必须实例化语法，这既费力又不优雅。PHP无法检索回调的文本内容，因此将Loco从解析库转换为真正的解析生成器的过程停滞不前。
• 缺乏回溯意味着我必须非常小心地描述我的CFG，以确保它是无歧义且正确运行的。这种额外的工作量几乎抵消了其意义。
• 我现在意识到，在解析用户输入时，考虑在解析失败时生成有意义的错误信息是非常重要的。Loco在这方面做得不太好，用户发现很难创建正确的HTML来让它满意。
• PHP非常糟糕。

在开始这个项目之前，我还注意到PHP没有解析器组合库，我决定填补这个空白。同样，我也遇到了一些问题

• 当时我实际上并不了解“解析器组合”这个术语的含义。它并不是“由其他解析器组合而成的解析器”。它是指“一个接受一个或多个解析器作为输入并返回一个新的解析器作为输出的函数或运算符”。在上面，你可以看到这个术语被错误地使用了好几次。据我所知，PHP仍然没有解析器组合库。
• 我对一般的解析几乎一无所知，现在也是一样。
• PHP非常糟糕。

总的来说，我认为这个项目当时满足了我的需求，如果你现在用它也满足你的需求，那可能只是巧合。使用Loco或检查其代码时，请谨慎行事。