Может ли BNF справиться с прямым потреблением?

В контекстно-независимой грамматике или в обычной грамматике, если на то пошло, нет такой вещи, как параметризованный размер. Числовые параметры, такие как ваш consume, не являются частью модели CFG, и можно доказать, что получить эффект другим способом невозможно. Однако вы можете написать производство для любой фиксированной длины, поэтому вы можете писать продукты для блока длиной 1, длиной 2, длиной 3 и т. Д .:

<block3> :: <number> <number> <number>

или, аналогично, соответствие длины в качестве префикса или даже в качестве пост-исправления:

<block3a> :: 3 <number> <number> <number>
<block3b> :: <number> <number> <number> 3

и т. д. Итак, чтобы делать то, что вы хотите, вам просто нужна грамматика, содержащая подобные правила для всех N, которые вам могут понадобиться.

Данный CFG будет включать только конечное число этих производств. Математически невозможно написать CFG (в BNF или любой другой форме), который может обрабатывать неограниченные параметризованные размеры, будь то как префикс или как постфикс. На практике вы могли бы иметь возможность обновлять свой CFG на лету, добавляя новые произведения по мере необходимости. Например, прочтите число N и создайте правило blockN для своей грамматики, если его еще нет. Но не существует единственного CFG, который может захватывать неограниченные параметризованные размеры.

Изменить, поскольку вы также спрашивали о контекстно-зависимых грамматиках: это все равно не поможет. Проблема заключается в использовании целочисленной арифметики, а не в классе грамматики. Любой формальный язык в иерархии Хомского определяется в терминах конечного числа символов (токенов), и, поскольку целых чисел бесконечно много, им нельзя присвоить различные значения (обратите внимание, что ваша процедура синтаксического анализа основывается на целочисленных арифметика).

Если бы вы предварительно обработали длину в последовательность из такого же количества звезд (* * * 4 7 10), парсер CFG был бы тривиален:

<group> :: * <group> <number>
<group> :: * <number>

Это просто так называемый a^n b^n язык. У вас также могут быть символы, означающие «десять» и т. Д. Но без предварительной обработки единственное решение (и то, что ваша процедура или машина Тьюринга делает на практике) - это интерпретировать числовые обозначения в вашей грамматике. Например, проанализируйте «21» как десять десять один. Я сомневаюсь, что это можно сделать в CFG (проблема заключается в обработке произвольно длинных чисел без отдельных правил для миллионов, миллиардов и т. Д.), Но я не совсем уверен. В любом случае это интересно только как академическое упражнение, поскольку использовать настоящие целые числа намного проще. Я уверен, что люди изучали свойства формальных языков с целыми числами, но я ничего не могу сказать по этому поводу.

Pyparsing включает помощника countedArray, который делает именно то, что вы просите. Он принимает единственный аргумент expr и анализирует целое число, за которым следует n экземпляров expr. В качестве входной строки вы можете написать:

from pyparsing import *
from pprint import pprint

# make a long string of integers, starting at 0
source = ' '.join(map(str, range(50)))

# define an integer as a 'word' of numeric digits
integer = Word(nums)

# add a parse action to convert the parsed strings to integers, at parse time
integer.setParseAction(lambda t:int(t[0]))

# parse the source string into counted strings of integers, and print out
# with pprint
lists = OneOrMore(countedArray(integer)).parseString(source)
pprint(lists.asList())

распечатывает:

[[],
 [2],
 [4, 5, 6],
 [8, 9, 10, 11, 12, 13, 14],
 [16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]]

• Действие синтаксического анализа, прикрепленное к integer, преобразует числовые строки обратно в целые числа (без кавычек вокруг чисел в списках).

• Обратите внимание на открывающийся пустой список, который был создан начальным «0» исходной строки.

• Несмотря на то, что исходная строка содержит больше чисел после 30, этого недостаточно для другого подсчитываемого массива.

countedArray достигает этого трюка, создавая выражение, которое соответствует начальному целому числу, за которым следует скрытое неопределенное прямое выражение. Действие синтаксического анализа, прикрепленное к ведущему целому числу, вводит выражение expr*n в подчиненный Forward, который затем анализирует следующие n выражений. С таким же успехом вы можете написать countedArray(Word(alphas)) и проанализировать "4 the quick brown fox", чтобы получить ['the', 'quick', 'brown', 'fox']. Как отмечает @Aaron в своем ответе, нет необходимости сохранять ведущий счетчик, так как вы можете легко получить его, получив len возвращенного списка.

pyparsing также поддерживает более традиционный просмотр вперед с использованием конструкций FollowedBy и NotAny (NotAny можно сократить с помощью оператора '~'). В этой строке «Четыре очка и семь лет назад ...» вы можете выделить строки, за которыми следуют слова, начинающиеся с гласных, используя Word(alphas) + FollowedBy(Word('aeiou',alphas)), что соответствует «счету» и «годам»; или слова, после которых не ставится точка с использованием Word(alphas) + ~Literal('.'), что соответствует каждому слову, кроме «назад». В этом случае, пытаясь найти совпадения по строке ввода, вы должны использовать searchString или scanString вместо parseString.

Не совсем.

Вся суть грамматики в том, что она позволяет определять данные понятным способом. Ваша демонстрационная строка читабельна, но почему 1 означает что-то другое, кроме 3?

Правильный ввод в вашем случае будет:

[[2], [4, 5, 6], [8, 9, 10, 11, 12, 13, 14], [16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]]

и грамматика будет выглядеть так:

<model> :: <term>
<list>  :: <term> | <term> <opt-whitespace> <list>
<term>  :: '[' <list> ']'

Затем вы можете восстановить недостающий элемент счетчика, посмотрев на длину списка.