什么是外来的解析技术？

Question

在过去的一年里，我一直在解析扑克手的历史，并且已经学到了很多关于解析的知识。

我们从regexes开始，但很快意识到这并不容易扩展。我们跳过了从红宝石到c++的语言，最终意识到必须改变的是算法。

我们得到了提振：：精神和观看我们的速度急剧上升的订单超过10倍的原始速度。然后我们跳到java，目前正在使用antlr为每个站点创建语法。这绝对是最快的方法，它是非常彻底的，这是很好的，因为你知道你的立场，你的“完整的”语法。不幸的是，我花了大量的时间来研究这些语法--它们工作得很好，但还不是很完美。

总之，关于这个问题的背景已经够多了--我不知道有什么“异国情调”或不太为人所知的解析技巧吗？我只知道语法和其他低级正则/循环方法的词法/解析。

对于那些不熟悉扑克手的历史的人，我会发布一个，这样你就可以知道这个结构是什么。

Full Tilt Poker Game #12037626529: Table durrrr (heads up, deep) - $500/$1000 -
Pot Limit Omaha Hi - 2:00:48 ET - 2009/05/05
Seat 1: durrrr ($196,456.50)
Seat 2: Gus Hansen ($65,499)
durrrr posts the small blind of $500
Gus Hansen posts the big blind of $1,000
The button is in seat #1
*** HOLE CARDS ***
durrrr raises to $3,000
Gus Hansen raises to $9,000
durrrr calls $6,000
*** FLOP *** [3d 4d 7d]
Gus Hansen has 15 seconds left to act
Gus Hansen checks
durrrr checks
*** TURN *** [3d 4d 7d] [Jh]
Gus Hansen checks
durrrr checks
*** RIVER *** [3d 4d 7d Jh] [Ah]
Gus Hansen has 15 seconds left to act
Gus Hansen checks
durrrr has 15 seconds left to act
123stayfree (Observer): GUS I NOW BRING U LUCK
durrrr bets $7,600
Gus Hansen has 15 seconds left to act
Gus Hansen has requested TIME
Hernandez777 (Observer): Gus has the super-duper nuts
Gus Hansen calls $7,600
Podobed45 (Observer): fluuuuuuuuuush
*** SHOW DOWN ***
durrrr shows [Kc 3s Qd As] two pair, Aces and Threes
Gus Hansen mucks
durrrr wins the pot ($33,199.50) with two pair, Aces and Threes
*** SUMMARY ***
Total pot $33,200 | Rake $0.50
Board: [3d 4d 7d Jh Ah]
Seat 1: durrrr (small blind) collected ($33,199.50)
Seat 2: Gus Hansen (big blind) mucked

我很清楚收集信息的其他方法(如屏幕抓取和dll注入)，但是仍然需要将手工历史转换为结构化数据，所以我只关注获取信息的方法，比如regex/ grab .

我想如果我找不到东西，我会用ocamllex/ocamlyacc重写语法。

更新

fyi:恢复速度~60手/秒，而语法处理600+手/秒。数据整理完毕后，整个手就被转换成xml .每个站点都需要20-30个正则表达式(最后一次计数)，在语法方面，每个站点都有自己的语法，其中包含大量的词法/解析器规则(但代码大小仍然较小)。

我确实有一本龙书，并且一直在读它--这使我对使用ocamllex/ocamlyacc不感兴趣.速度是这里游戏的名字。

Answer 1

既然你在寻找异国情调，请阅读这篇关于沃恩·普拉特的“自上而下”的文章。

http://javascript.crockford.com/tdop/tdop.html

Answer 2

解析器组合器是一种非常流行的用函数语言(如Haskell )构建解析器的方法。

Answer 3

你必须问问自己，你真正想做的是玩解析器(诚然很有趣，我更喜欢自己)，还是你真的想在你的扑克机器人上完成工作。最有可能的是，异国情调的解析技术对你所需要的东西来说是过分的。只要选择一些简单易用的快速语言就行了。您可能应该能够处理10k手/秒与直C+ flex。或者，ocamllex + ocamlyacc应该足够了。如果你不得不修改你的代码，我认为你做错了什么。网络延迟应该是真正的瓶颈，而不是解析速度。你用的是哪种机器？

另一种选择是使用解析器生成器自动生成一个解析表，然后对其进行优化，或者使用NFA进行手动优化(您可能不会节省太多，程序员时间内的权衡可能不值得)。Combinator解析可能会慢一些。

平均而言，对于给定的等效幂LL文法，LL将比LALR慢。特别是，如果扑克手实际上是由LALR解析器解析的，那么bison/byacc + flex每次都会击败ANTLR的手。我个人对menhir很满意，虽然它是一个愤怒的婊子和一半的工作与戈迪+ ocamlbuild。

-尼科