Грамматика конкатенации диапазонов (RCG) - это грамматический формализм, разработанный Пьером Булье [1] в 1998 году как попытка охарактеризовать ряд явлений естественного языка, таких как китайские числа и шифрование порядка слов в немецком языке, которые выходят за рамки мягко говоря. контекстно-зависимые языки . [2]
С теоретической точки зрения любой язык, который может быть проанализирован за полиномиальное время, принадлежит подмножеству RCG, называемому грамматиками конкатенации положительного диапазона, и обратно. [3]
Хотя RCG задумывались как вариант грамматик Гроенинка Literal motion, они рассматривают грамматический процесс больше как доказательство, чем как производство. В то время как LMG производят терминальную строку из начального предиката, RCG стремятся уменьшить начальный предикат (который является предикатом конечной строки) до пустой строки, что является доказательством принадлежности конечных строк к языку.
Описание
Формальное определение
Положительный диапазон Concatenation Грамматик (PRCG) является кортежем, где:
- , а также являются непересекающимися конечными наборами (соответственно) имен предикатов , терминальных символов и имен переменных . Каждое имя предиката имеет связанную арность, заданную функцией.
- это имя начального предиката и проверьте .
- - конечный набор клозов вида, где являются предикаты вида с участием а также .
Отрицательный диапазон конкатенация Грамматика (NRCG) определяются как PRCG, но с добавлением , что некоторые предикаты , входящие в правой стороне пункта могут иметь форму. Такие предикаты называются отрицательными предикатами .
Range Concatenation Грамматика является положительным или отрицательным. Хотя группы PRCG технически являются группами NRCG, эти термины используются для обозначения отсутствия (PRCG) или присутствия (NRCG) отрицательных предикатов.
Диапазон в слове пара , с участием , где это длина . Два диапазона а также можно объединить, если и только если , и тогда мы имеем: .
На слово , с участием , точечное обозначение диапазонов:.
Распознавание струн
Как и LMG, статьи RCG имеют общую схему , где в RCG, либо пустая строка, либо строка предикатов. Аргументысостоят из строк терминальных символов и / или переменных символов, шаблон которых соответствует фактическим значениям аргументов, как в LMG. Смежные переменные составляют семейство совпадений с разделами, так что аргумент, с двумя переменными, соответствует буквальной строке тремя разными способами: .
Термины предикатов бывают двух видов: положительный (который создает пустую строку в случае успеха) и отрицательный (который создает пустую строку при неудаче / если положительный член не дает пустую строку). Отрицательные члены обозначаются так же, как и положительные, с чертой сверху, как в.
Семантика перезаписи для RCG довольно проста, идентична соответствующей семантике LMG. Учитывая строку предиката, где символы являются терминальными строками, если есть правило в грамматике, которой соответствует строка предиката, строка предиката заменяется на , заменяя согласованные переменные в каждом .
Например, учитывая правило , где а также являются переменными символами и а также являются терминальными символами, строка предиката можно переписать как , так как Спички когда . Точно так же, если бы было правило, можно переписать как .
Доказательство / признание строки делается путем демонстрации того, что производит пустую строку. Для отдельных шагов перезаписи, когда возможны совпадения нескольких альтернативных переменных, рассматривается любая перезапись, которая может привести к успеху всего доказательства. Таким образом, если есть хотя бы один способ создать пустую строку из начальной строки, доказательство считается успешным, независимо от того, сколько других способов потерпеть неудачу существует.
Пример
RCG способны распознавать язык нелинейных индексов. следующим образом:
Допустим, что x, y и z - символы переменных:
Доказательство для abbabbabb тогда
Или, используя более правильную точечную нотацию для диапазонов:
Рекомендации
- ^ Булье, Пьер (январь 1998). Предложение по синтаксической основе обработки естественного языка (PDF) (Технический отчет). 3342 . INRIA Rocquencourt (Франция).
- ^ Пьер Булье (1999). «Китайские числа, MIX, скремблирование и грамматики конкатенации диапазонов». Proc. EACL (PDF) . С. 53–60. Архивировано из оригинального (PDF) 15 мая 2003 года.
- ^ Лаура Каллмейер (2010). Анализ вне контекстно-свободных грамматик . Springer Science & Business Media. п. 37. ISBN 978-3-642-14846-0.со ссылкой на http://mjn.host.cs.st-andrews.ac.uk/publications/2001d.pdf