Каковы некоторые экзотические методы синтаксического анализа?
https://stackoverflow.com/questions/940984
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я анализировал истории покерных рук в течение прошлого года и многое узнал об анализе в целом.
Мы начали с регулярных выражений, но быстро поняли, что их нелегко масштабировать.Мы перешли с Ruby на C++ и, наконец, осознали, что менять нужно именно алгоритм.
Мы выбрали Boost::Spirit и наблюдали, как наша скорость резко возросла, более чем в 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), но необходимость преобразования истории раздач в структурированные данные все еще существует, поэтому я рассматриваю только методы, которые получают информацию, например регулярное выражение/грамматика...
Думаю, если я что-то не найду, то перепишу нашу грамматику с помощью ocamllex/ocamlyacc.
обновлять
к вашему сведению:Скорость регулярного выражения составляла ~60 рук/сек, в то время как грамматики обрабатывали более 600 рук/сек...вся рука преобразуется в XML после того, как все данные отсортированы...требуется от 20 до 30 регулярных выражений (по последним подсчетам) для КАЖДОГО сайта, который вы хотите проанализировать... каждый сайт со стороны грамматики имеет свою собственную грамматику с безбожным количеством правил лексера/парсера (но это все равно меньший размер кода)
У меня есть книга о драконах, и я ее читал, что лишило меня интереса к использованию ocamllex/ocamlyacc....Скорость здесь главное..
Решение
Если вы хотите максимизировать скорость, возможно, вам лучше использовать OcamlYacc/FsYacc вместо ANTLR. OcamlYacc создает анализаторы LL(1), которые обычно имеют более высокую производительность, чем анализаторы LL(*) в стиле ANTLR (кто-то может поправить меня, если я ошибаюсь). [Изменить, чтобы добавить:] Похоже, кто-то меня поправил:OCamlYacc производит анализаторы LALR(1).Я не могу с уверенностью сказать, работают ли парсеры OcamlYacc быстрее, чем парсеры ANTLR.
OCaml/F# — очень хорошие языки для создания DSL, и, на мой взгляд, они гораздо более подходят для этой работы, чем Java, главным образом потому, что невероятно легко создавать и перемещаться по AST, представленному в виде структуры данных объединения.Я рекомендовал этот урок который демонстрирует, как анализировать SQL в F#.
Другие советы
Поскольку вы ищете экзотики, прочитайте эту статью о приоритете операторов сверху вниз Воана Пратта...
Парсер-комбинаторы — очень популярный метод создания парсеров в функциональных языках, таких как Haskell.
Вы должны спросить себя, действительно ли вы хотите поиграть с парсерами (по общему признанию, это весело, и я сам предпочитаю это) или вы действительно хотите поработать над своим покерным ботом.Скорее всего, экзотические методы синтаксического анализа являются излишними для того, что вам нужно.Просто выберите быстрый язык с простыми и простыми в использовании парсерами.Вероятно, вы сможете обрабатывать 10 тыс. рук в секунду с помощью прямого C + flex.Или ocamllex + ocamlyacc должно быть более чем достаточно.Если вам нужно модифицировать свой код, я думаю, вы делаете что-то не так.Вашим настоящим узким местом должна стать задержка в сети, а не скорость синтаксического анализа.На какой машине вы это запускаете?
Другая альтернатива - использовать генератор синтаксического анализатора для автоматического создания таблицы синтаксического анализа, а затем оптимизировать ее вручную или оптимизировать вручную из NFA (хотя вы, вероятно, не сэкономите много, и компромисс во времени программиста, вероятно, того не стоит).Синтаксический анализ комбинатора, вероятно, будет медленнее.
В среднем для данной грамматики эквивалентной мощности LL будет медленнее, чем LALR.В частности, если покерные руки действительно анализируются парсером LALR, то bison/byacc + flex каждый раз будет побеждать руки ANTLR.Лично я очень доволен менгиром, хотя работать с godi + ocamlbuild — это полторы ярости.
--Нико
Прочтите Книгу Дракона:http://www.amazon.com/Compilers-Principles-Techniques-Alfred-Aho/dp/0201100886
Он подробно охватывает лексический и синтаксический анализ (среди других тем).Вы можете использовать это, чтобы понять «язык», который вы пытаетесь проанализировать, и определить лучший способ сделать это.
В Википедии есть хороший обзор типов парсеров: здесь: http://en.wikipedia.org/wiki/Парсер
И сравнение инструментов-генераторов парсера здесь: http://en.wikipedia.org/wiki/Comparison_of_parser_generators
Я думаю ГЛР — это своего рода менее известный метод, который интересен тем, что касается языковой неоднозначности.
Рекурсивный анализ спуска может сработать для вас.Это очень настраиваемый.Это может быть немного медленнее, чем yacc/antlr, но может быть достаточно быстрым.Основная идея:Вы кодируете каждое грамматическое правило как функцию.
Поскольку вы говорите об использовании OCaml для синтаксического анализа, на этой странице представлен обзор различных вариантов синтаксического анализа для этого языка:
Генераторы парсеров для языка OCaml
Если вы решили довольствоваться ocamlyacc (или menhir), эти руководства могут быть немного проще, чем справочное руководство:
