Как разобрать грамматику `(a | b)* a`

Нет, вы совершенно правы, pyparsing не выполняет откат, как вы могли бы из регулярного выражения, такого как "[ab]*a". Pyparsing не выполняет никакого упреждающего просмотра, если только вы не реализуете его явно.

Вот расширенная версия исходного парсера с добавленными вызовами setName и setDebug:

a = Literal('a').setName("A").setDebug()
b = Literal('b').setName("B").setDebug()
grammar = (a | b)[...] + a().setName("trailing_a").setDebug()

grammar.runTests("""\
    aba
    """)

При разборе аба вот вывод отладки:

Match A at loc 0(1,1)
Matched A -> ['a']
Match A at loc 1(1,2)
Exception raised:Expected A, found 'b'  (at char 1), (line:1, col:2)
Match B at loc 1(1,2)
Matched B -> ['b']
Match A at loc 2(1,3)
Matched A -> ['a']
Match A at loc 3(1,4)
Exception raised:Expected A, found end of text  (at char 3), (line:1, col:4)
Match B at loc 3(1,4)
Exception raised:Expected B, found end of text  (at char 3), (line:1, col:4)
Match trailing_a at loc 3(1,4)
Exception raised:Expected trailing_a, found end of text  (at char 3), (line:1, col:4)

aba
   ^
FAIL: Expected trailing_a, found end of text  (at char 3), (line:1, col:4

и вы можете видеть, что trailing_a сопоставляется как часть начального повторения, а не как trailing_a. Поскольку фактического завершающего «а» сейчас нет, синтаксический анализ завершается неудачно.

Вы можете либо определить специальную форму a для ведущего повторения (как вы сделали в одной строке), например, в двух строках:

leading_a = a + FollowedBy(a | b)
grammar = (leading_a | b)[...] + 'a'

С выводом отладки мы можем следовать логике парсера:

Match leading_a at loc 0(1,1)
Match A at loc 0(1,1)
Matched A -> ['a']
Match A at loc 1(1,2)
Exception raised:Expected A, found 'b'  (at char 1), (line:1, col:2)
Match B at loc 1(1,2)
Matched B -> ['b']
Matched leading_a -> ['a']
Match leading_a at loc 1(1,2)
Match A at loc 1(1,2)
Exception raised:Expected A, found 'b'  (at char 1), (line:1, col:2)
Exception raised:Expected A, found 'b'  (at char 1), (line:1, col:2)
Match B at loc 1(1,2)
Matched B -> ['b']
Match leading_a at loc 2(1,3)
Match A at loc 2(1,3)
Matched A -> ['a']
Match A at loc 3(1,4)
Exception raised:Expected A, found end of text  (at char 3), (line:1, col:4)
Match B at loc 3(1,4)
Exception raised:Expected B, found end of text  (at char 3), (line:1, col:4)
Exception raised:Expected {A | B}, found end of text  (at char 3), (line:1, col:4)
Match B at loc 2(1,3)
Exception raised:Expected B, found 'a'  (at char 2), (line:1, col:3)

aba
['a', 'b', 'a']

Или определите специальный trailing_a и используйте аргумент stopOn для ZeroOrMore:

trailing_a = a + ~FollowedBy(a | b)
grammar = OneOrMore(a | b, stopOn=trailing_a) + 'a'

чтобы получить аналогичные результаты.

РЕДАКТИРОВАТЬ Изменение грамматики только на (a | b)[...] показывает этот вывод отладки:

Match A at loc 0(1,1)
Matched A -> ['a']
Match A at loc 1(1,2)
Exception raised:Expected A, found 'b'  (at char 1), (line:1, col:2)
Match B at loc 1(1,2)
Matched B -> ['b']
Match A at loc 2(1,3)
Matched A -> ['a']
Match A at loc 3(1,4)
Exception raised:Expected A, found end of text  (at char 3), (line:1, col:4)
Match B at loc 3(1,4)
Exception raised:Expected B, found end of text  (at char 3), (line:1, col:4)

aba
['a', 'b', 'a']

Итак, да, просмотр вперед приводит к снижению производительности.

pyparsing включает в себя возможность внутреннего кэширования, также известную как синтаксический анализ packrat. Вот вывод отладки с кэшированными значениями, помеченными '*':

  Match trailing_a at loc 0(1,1)
  Match A at loc 0(1,1)
  Matched A -> ['a']
  Match A at loc 1(1,2)
  Exception raised:Expected A, found 'b'  (at char 1), (line:1, col:2)
  Match B at loc 1(1,2)
  Matched B -> ['b']
  Exception raised:Found unwanted token, FollowedBy:({A | B}), found 'b'  (at char 1), (line:1, col:2)
* Match A at loc 0(1,1)
* Matched A -> ['a']
  Match trailing_a at loc 1(1,2)
* Match A at loc 1(1,2)
* Exception raised:Expected A, found 'b'  (at char 1), (line:1, col:2)
* Exception raised:Expected A, found 'b'  (at char 1), (line:1, col:2)
* Match A at loc 1(1,2)
* Exception raised:Expected A, found 'b'  (at char 1), (line:1, col:2)
* Match B at loc 1(1,2)
* Matched B -> ['b']
  Match trailing_a at loc 2(1,3)
  Match A at loc 2(1,3)
* Matched A -> ['a']
  Match A at loc 3(1,4)
  Exception raised:Expected A, found end of text  (at char 3), (line:1, col:4)
  Match B at loc 3(1,4)
  Exception raised:Expected B, found end of text  (at char 3), (line:1, col:4)
  Matched trailing_a -> ['a']
* Match trailing_a at loc 2(1,3)
* Match A at loc 2(1,3)
* Matched A -> ['a']
* Matched trailing_a -> ['a']

Сводка операций сопоставления:

• Без просмотра: 6
• С опережением: 12
• С опережением+packrat: 9

И наконец, можно внедрить дополнительную логику во время синтаксического анализа, используя действия синтаксического анализа. Действия синтаксического анализа могут быть записаны как метод (который может возвращать измененный набор токенов или вызывать исключение) или как предикатная функция (которая возвращает True или False, а pyparsing вызовет исключение в случае возврата False).

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

grammar = (a | b)[...]
grammar.addCondition(lambda t: t[-1] == 'a', message="string does not end with 'a'")

Весьма вероятно, что экономии времени на синтаксический анализ будет достаточно, чтобы компенсировать дополнительные затраты на выполнение отдельной оценки условий.