Работа с грамматической двусмысленностью (парсинг покерного файла)

В настоящее время я работаю над анализатором истории покерных рук в рамках своего бакалаврского проекта. За последние пару дней я провел небольшое исследование и наткнулся на несколько хороших генераторов парсеров (из которых я выбрал JavaCC, поскольку сам проект будет написан на Java).

Несмотря на то, что грамматика истории рук довольно проста и понятна, существует проблема неоднозначности из-за разрешенного набора символов в нике игрока.

Предположим, у нас есть строка следующего формата:

Seat 5: myNickname (1500 in chips)

Токен myNickname может содержать любой символ, а также пробелы. Это означает, что и (1500 in chip, и Seat 5: являются действительными псевдонимами, что в конечном итоге приводит к проблеме двусмысленности. Никаких ограничений по нику игрока нет, кроме длины (4-12 символов).

Мне нужно проанализировать и сохранить несколько данных вместе с ником игрока (например, положение места и количество фишек в данном конкретном случае), поэтому мой вопрос: какие у меня здесь варианты?

Я бы хотел сделать это с помощью JavaCC, что-то вроде этого:

SeatRecord seat() :
{ Token seatPos, nickname, chipStack; }
{
    "Seat" seatPos=<INTEGER> ":" nickname=<NICKNAME> "(" chipStack=<INTEGER> 
    "in chips)"
    {
        return new SeatRecord(seatPos.image, nickname.image, chipStack.image); 
    }
}

Что прямо сейчас не работает (из-за указанной проблемы)

Я также искал парсеры GLR (которые, по-видимому, обрабатывают неоднозначные грамматики), но в основном они кажутся заброшенными или плохо документированными, за исключением Bison, но он не поддерживает парсеры GLR для Java и может быть слишком сложным для работы с в любом случае (помимо проблемы двусмысленности, как я уже упоминал, сама грамматика довольно проста)

Или я должен сам придерживаться токенизации строки и использовать indexOf(), lastIndexOf() и т. Д. Для анализа нужных мне данных? Я бы пошел на это, только если бы это был единственный оставшийся вариант, так как это было бы слишком уродливо ИМХО, и я мог бы пропустить некоторые случаи (что привело бы к неправильному синтаксическому анализу)


java parsing ambiguity javacc
person m.t    schedule 18.06.2012    source источник
comment
Как насчет хранения вещей в двумерном массиве, где каждая функция - это столбец, а каждая строка - это ваше место. Вы можете обрабатывать каждую часть как строки и добавить собственный разделитель (возможно, какой-нибудь непонятный символ Unicode), чтобы имена не обрезались   -  person Azulflame    schedule 18.06.2012

Ответы (3)


arrow_upward
7
arrow_downward

Если ваш формат ввода настолько прост, насколько вы указали, вы, вероятно, можете обойтись простым регулярным выражением:

^Seat ([0-9]+): (.*) \(([0-9]+) in chips\)$

NFA механизма регулярных выражений в этом случае решает вашу двусмысленность, а круглые скобки - это группы захвата, чтобы вы могли извлечь интересующую вас информацию.

person Dave    schedule 18.06.2012

arrow_upward
2
arrow_downward

У вас есть два решения:

  • Добавьте некоторые ограничения к именам. Я не могу вспомнить какую-либо широко используемую систему, которая принимала бы такие ники. Просто позвольте им использовать буквенно-цифровые символы и разделители «_». Также вы можете добавить ключевые слова для места, например, что такое слово не может быть ником.
  • Также вы можете построить конечный автомат для синтаксического анализа на основе вашей грамматики. Я думаю, что FSM может справиться с такой грамматикой двусмысленности. Когда он у вас есть, вы можете анализировать все, что хотите.

В любом случае, думаю, проблема с оригинальным дизайном. Никнеймы не должны допускать такого набора имен. Также, почему нельзя использовать идентификаторы вместо имен - имена можно хранить в базе данных.

person SPIRiT_1984    schedule 18.06.2012
comment
Благодарю за ваш ответ. Проблема в том, что это внешнее программное обеспечение, которое позволяет использовать такие ники, и я ничего не могу с этим поделать. Они также генерируют эти файлы для анализа, так что мне ничего не остается, как разобраться с этим. :) - person m.t; 18.06.2012
comment
Ох, я понял. В этом случае используйте NFA с регулярным выражением, это должно вам помочь. Думаю, он справится с такой двусмысленностью. - person SPIRiT_1984; 18.06.2012

arrow_upward
2
arrow_downward

Грамматика для вашей системы может выглядеть так (написанная как контекстно-свободная грамматика):

S -> seating nickname chips

seating -> "Seat " number ":"
number -> "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
number -> number number

nickname -> "a" | "b" | "c" ...... | "z" | ...."+" | "?" | number
nickname -> nickname nickname 

chips -> "(" number "in chips)"

Обратите внимание на правило формы:

number -> number number

Это в основном допускает бесконечную грамматику. Обратите внимание, что «бесконечная грамматика» не означает, что вы инкапсулируете все. Вышеупомянутая строка в основном эквивалентна регулярному выражению (\d*).

Я считаю, что набор грамматики в CFG, а затем преобразование ее в обычную грамматику, помогает мне в большинстве случаев. Подробнее о том, как это сделать, можно узнать здесь. Удачи!

person Arnab Datta    schedule 18.06.2012