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记法"（因为没有更好的名字）是Backus-Naur形式的一个扩展，它提供了访问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或检查其代码时，请务必谨慎。