Грамматики буквального движения (LMG) - это грамматический формализм, введенный Гренинком в 1995 году [1], предназначенный для характеристики определенных явлений экстрапозиции естественного языка, таких как тематизация и кросс-последовательная зависимость . LMG расширяют класс контекстно-свободных грамматик (CFG), добавляя вводную семантику перезаписи функций, подобную шаблону, а также операции связывания переменных и удаления косой черты.
Описание
Основная операция перезаписи LMG очень похожа на операцию CFG с добавлением аргументов к нетерминальным символам. Если правило бесконтекстной перезаписи подчиняется общей схеме для некоторых нетерминальных и некоторая цепочка терминалов и / или нетерминалов, правило перезаписи LMG подчиняется общей схеме , где X - нетерминал с арностью n (называемый предикатом в терминологии LMG), ипредставляет собой строку «элементов», как определено ниже. Аргументыпредставляют собой строки терминальных символов и / или переменных символов, определяющих шаблон аргумента. В случае, когда в шаблоне аргумента есть несколько смежных символов переменных, шаблон аргумента будет соответствовать любым без исключения разделам фактического значения, которые объединяются. Таким образом, если предикат и фактический узор , есть три допустимых совпадения: . Таким образом, единое правило на самом деле представляет собой семейство альтернатив.
«Предмет» в грамматике буквального движения является одним из
- , предикат арности n,
- , переменная, связывающая x со строкой, созданной , или же
- , косая черта удаления строкой терминалов и / или переменных .
В правиле вроде , переменная y привязана к любой терминальной строке, которую создает предикат g, а в а также , все вхождения y заменяются этой строкой, и а также производятся так, как если бы терминальная строка всегда была там.
Пункт , где x - это то, что создает терминальную строку (либо саму терминальную строку, либо некоторый предикат), а y - это строка терминалов и / или переменных, переписывается как пустая строка () если и только если , а иначе вообще не может быть переписан.
Пример
LMG могут характеризовать язык, не относящийся к CF следующим образом:
Таким образом, вывод для aabbcc с использованием скобок также для группировки
Вычислительная мощность
Языки, генерируемые LMG, содержат контекстно-свободные языки в качестве надлежащего подмножества , поскольку каждый CFG является LMG, в котором все предикаты имеют арность 0, и ни одно производственное правило не содержит привязок переменных или удаления косой черты.
Рекомендации
- ^ Грёнинк, Анний В. 1995. Символьные движение грамматик. В материалах 7-й конференции EACL .