이국적인 구문 분석 기술에는 어떤 것이 있나요?
https://stackoverflow.com/questions/940984
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 지난 1년 동안 포커 핸드 기록을 분석해 왔으며 일반적인 분석에 대해 많은 것을 배웠습니다.
우리는 정규식으로 시작했지만 쉽게 확장할 수 없다는 것을 금방 깨달았습니다.우리는 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로 문법을 다시 작성할 것 같아요.
업데이트
참고하세요:문법이 600+ 손/초를 처리하는 동안 정규식 속도는 ~60 손/초였습니다...데이터가 모두 정리된 후 손 전체가 xml로 변환됩니다.구문 분석하려는 각 사이트에 대해 (마지막 계산에서) 20-30개의 정규 표현식이 필요합니다....문법 측면의 각 사이트에는 엄청난 양의 어휘 분석기/파서 규칙이 포함된 자체 문법이 있습니다(그러나 여전히 코드 크기는 더 작습니다).
나는 드래곤 책을 가지고 있고 계속해서 읽고 있습니다. 이로 인해 ocamllex/ocamlyacc 사용에 대한 관심이 사라졌습니다....여기서 게임의 이름은 속도입니다..
해결책
속도를 최대화하려는 경우 ANTLR보다 OcamlYacc/FsYacc를 사용하는 것이 더 나을 수 있습니다. OcamlYacc는 일반적으로 ANTLR 스타일 LL(*) 파서보다 성능이 더 좋은 LL(1) 파서를 생성합니다(내가 틀렸다면 누군가가 나를 수정할 수 있습니다). [추가 편집:] 누군가가 내 말을 정정한 것 같습니다.OCamlYacc는 LALR(1) 파서를 생성합니다.OcamlYacc 파서가 ANTLR 파서보다 빠른지는 확신할 수 없습니다.
OCaml/F#은 DSL을 구축하는 데 매우 좋은 언어이며 내 생각에는 Java보다 해당 작업에 훨씬 더 적합합니다. 그 이유는 주로 통합 데이터 구조로 표현되는 AST를 생성하고 탐색하기가 엄청나게 쉽기 때문입니다.나는 추천했다 이 튜토리얼 F#에서 SQL을 구문 분석하는 방법을 보여줍니다.
다른 팁
이국적인 것을 찾고 계시다면 Vaughan Pratt의 하향식 연산자 우선 순위에 대한 이 기사를 읽어 보십시오...
파서 결합자 Haskell과 같은 기능적 언어로 파서를 구축하는 데 매우 널리 사용되는 방법입니다.
당신이 정말로 원하는 것이 파서를 가지고 노는 것인지(물론 재미 있고 내가 선호하는 것)인지 아니면 실제로 포커 봇에서 작업을 수행하고 싶은지 스스로에게 물어봐야 합니다.대부분의 경우 이국적인 구문 분석 기술은 필요한 것에 비해 과잉입니다.간단하고 사용하기 쉬운 파서가 있는 빠른 언어를 선택하세요.아마도 스트레이트 C + flex로 초당 10k 손을 처리할 수 있을 것입니다.아니면 ocamllex + ocamlyacc로도 충분합니다.코드를 hadoopify해야 한다면 뭔가 잘못하고 있는 것 같습니다.네트워크 대기 시간은 구문 분석 속도가 아니라 실제 병목 현상으로 이어져야 합니다.어떤 종류의 기계에서 이것을 실행하고 있습니까?
또 다른 대안은 파서 생성기를 사용하여 구문 분석 테이블을 자동 생성한 다음 이를 직접 최적화하거나 NFA에서 직접 최적화하는 것입니다(아마도 많은 비용을 절약하지 못할 것이며 프로그래머 시간의 절충은 가치가 없을 것입니다).조합자 구문 분석이 느려질 가능성이 높습니다.
평균적으로 동등한 전력의 특정 문법에 대해 LL은 LALR보다 느립니다.특히 포커 핸드가 LALR 파서에 의해 실제로 구문 분석 가능하다면 bison/byacc + flex는 매번 ANTLR 핸드 다운을 이길 것입니다.나는 개인적으로 선돌에 꽤 만족합니다. 비록 godi + ocamlbuild로 작업하는 것은 미친 짓이지만 말이죠.
--니코
드래곤 북을 읽어보세요:http://www.amazon.com/Compilers-Principles-Techniques-Alfred-Aho/dp/0201100886
이는 (다른 주제 중에서) 어휘 및 구문 분석을 심층적으로 다룹니다.이를 사용하면 구문 분석하려는 "언어"를 이해하여 가장 좋은 방법을 결정하는 데 도움이 될 수 있습니다.
Wikipedia에는 파서 유형에 대한 훌륭한 개요가 있습니다. http://en.wikipedia.org/wiki/Parser
파서 생성기 도구에 대한 비교는 다음과 같습니다. http://en.wikipedia.org/wiki/Comparison_of_parser_generators
제 생각에는 GLR 언어의 모호함을 다루기 때문에 흥미로운 일종의 잘 알려지지 않은 방법입니다.
재귀 하강 구문 분석 당신에게 도움이 될 수도 있습니다.매우 사용자 정의가 가능합니다.yacc/antlr보다 약간 느릴 수 있지만 충분히 빠를 수 있습니다.기본 아이디어:모든 문법 규칙을 함수로 인코딩합니다.
구문 분석을 위해 OCaml을 사용하는 것에 대해 이야기하고 있으므로 이 페이지에서는 해당 언어에 대한 다양한 구문 분석 옵션에 대한 개요를 제공합니다.
정착하기로 결정했다면 ocamlyacc (또는 menhir), 이 튜토리얼은 참조 매뉴얼보다 조금 더 쉬울 수 있습니다.
