Как Pyparsing может сопоставить подсчитанный массив, не отбрасывая сложные выражения подсчета? - PullRequest
Новая
       19

Как Pyparsing может сопоставить подсчитанный массив, не отбрасывая сложные выражения подсчета?

1 голос
/ 16 января 2020

Я смотрю на формат ввода для этой проблемы ACM , а именно:

Описание NTA дается числом состояний n, за которым следует число принятие состояний на одной строке, разделенной пробелом. Таблица перехода n × n следует в основном порядке строк; каждая строка перехода задается в отдельной строке.

(игнорировать остальное, это не имеет значения.)

Так, например: 

3 1
a
a
c
ca
a
b
c
b
a

Это означает что 9 (3²) строк, следующих за первой строкой, являются переходами. В моем коде мне нужно сохранить как значение 3, так и значение 1, а также список из 9 переходов. В идеале я хотел бы, чтобы выражение, которое дает мне:

  • 3
  • 1
  • ['ab', 'a', 'c', 'a', 'ab', 'b', 'c', 'b', 'ab']

Моя первая мысль была попробовать выражение на основе countedArray(): 

from pyparsing import pyparsing_common, Word, alphas, countedArray

table_start = pyparsing_common.integer*2
table_start.addParseAction(lambda toks: toks[0]**2)
table_transitions = countedArray(Word(alphas), table_start)

Однако countedArray() подавляет выражение count, что означает, что я теряю значение 1 (число принимающих состояний) и могу получить только 3 обратно, взяв квадрат root длины результирующего списка.

Я не слишком обеспокоен полным анализом этой проблемы, так как проблемы ACM позволяют предположить, что входные данные будут правильно отформатированы. Таким образом, я мог легко использовать более простое выражение и простые Python манипуляции с результатами. Но я изучаю Pyparsing и хотел бы знать, возможно ли это простым способом с использованием этой библиотеки (тем более, что я сталкиваюсь с подобными грамматиками в реальных проектах, которые я хотел бы использовать Pyparsing для упрощения).

Ответы [ 2 ]

1 голос
/ 17 января 2020

Это вынудило меня узнать, как использовать функцию Forward() PyParsing: 

from pyparsing import pyparsing_common, Word, Group, Forward

import string

table_transitions = Forward()

def table_start_action(toks):
    num_states = toks[0]
    num_transitions = num_states**2
    table_transitions << Group(
        Word(string.ascii_lowercase[0:num_states])*num_transitions
    )

table_start = pyparsing_common.integer*2
table_start.addParseAction(table_start_action)

table_full = table_start + table_transitions

print(table_full.parseString("""
3 1
a
a
c
ca
a
b
c
b
a
"""))

Это дает дополнительное преимущество, заключающееся в том, что я могу ограничить соответствие таблицы переходов включением только допустимых символов (первый N строчные буквы ASCII).

1 голос
/ 16 января 2020

Это что-то вроде хака, но если вы развернете действие синтаксического анализа на table_start, чтобы также установить действие синтаксического анализа на table_transitions, вы можете добавить свои принимающие состояния в качестве именованного результата на table_transitions: 

def replace_count(toks):
    table_transitions.setParseAction(lambda t: t.__setitem__('num_accepting_states', toks[1]))
    toks[0] *= toks[0]
table_start.addParseAction(replace_count)

result = table_transitions.parseString(data)
print(result[0])
print(result.num_accepting_states)

Отпечатки: 

['a', 'a', 'c', 'ca', 'a', 'b', 'c', 'b', 'a']
1
...