Эквивалентность (формальные языки)
В формального языка теории слабая эквивалентность двух грамматик означает, что они генерируют один и тот же набор строк, т.е. что генерируемый ими формальный язык один и тот же. В теории компиляторов это понятие отличается от сильной (или структурной ) эквивалентности , что дополнительно означает, что два дерева синтаксического анализа [ нужны разъяснения ] достаточно схожи в том смысле, что им обоим может быть присвоена одна и та же семантическая интерпретация. [1]
Виджай-Шанкер и Вейр (1994) [2] демонстрирует, что линейные индексированные грамматики , комбинаторные категориальные грамматики , древовидные грамматики и головные грамматики являются слабо эквивалентными формализмами, [ нужны разъяснения ] в том, что все они определяют одни и те же строковые языки.
С другой стороны, если две грамматики порождают один и тот же набор деревьев вывода (или, в более общем смысле, один и тот же набор абстрактных синтаксических объектов), то эти две грамматики строго эквивалентны. Хомский (1963) [3] вводит понятие сильной эквивалентности и утверждает, что только сильная эквивалентность важна при сравнении грамматических формализмов. Корнаи и Пуллум (1990) [4] и Миллер (1994) [5] предлагают уточненное понятие сильной эквивалентности, которое допускает изоморфные отношения между синтаксическими анализами, заданными различными формализмами. Ёсинага, Мияо и Цудзи (2002) [6] предлагает доказательство того, что для любого формализма LTAG существует строго эквивалентный формализм HPSG .
Пример бесконтекстной грамматики
[ редактировать ]
В качестве примера рассмотрим следующие две контекстно-свободные грамматики : [примечание 1] в форме Бэкуса-Наура :
<expression> ::= <expression> "+" <expression> | <expression> "-" <expression>
| <expression> "*" <expression> | <expression> "/" <expression>
| "x" | "y" | "z" | "1" | "2" | "3" | "(" <expression> ")"
<expression> ::= <term> | <expression> "+" <term> | <expression> "-" <term>
<term> ::= <factor> | <term> "*" <factor> | <term> "/" <factor>
<factor> ::= "x" | "y" | "z" | "1" | "2" | "3" | "(" <expression> ")"
Обе грамматики генерируют один и тот же набор строк, а именно. совокупность всех арифметических выражений, которые можно построить из переменных «x», «y», «z», констант «1», «2», «3», операторов «+», «-», « *", "/" и круглые скобки "(" и ")". Однако конкретное синтаксическое дерево второй грамматики всегда отражает обычный порядок операций , тогда как дерево первой грамматики не обязательно.
Для примера строки «1+2*3» в правой части изображения показано уникальное дерево разбора со второй грамматикой; [примечание 2] оценка этого дерева в постфиксном порядке даст правильное значение 7. Напротив, левая часть изображения показывает одно из деревьев синтаксического анализа для этой строки с первой грамматикой; вычисление его в постфиксном порядке даст 9.
Поскольку вторая грамматика не может генерировать дерево, соответствующее левой части изображения, а первая грамматика может, обе грамматики не являются строго эквивалентными.
Генеративный потенциал
[ редактировать ]В лингвистике слабая порождающая способность грамматики : определяется как совокупность всех порожденных ею строк [примечание 3] грамматики в то время как сильная порождающая способность относится к набору «структурных описаний». [примечание 4] порожденный им. [7] Как следствие, две грамматики считаются слабо эквивалентными, если их слабые порождающие способности совпадают; аналогично для сильной эквивалентности. Понятие генеративной способности было введено Ноамом Хомским в 1963 году. [3] [7]
Примечания
[ редактировать ]- ^ с начальным символом «<выражение>»
- ^ используя аббревиатуру «E», «T» и «F» для <выражение>, <термин> и <фактор> соответственно.
- ^ для контекстно-свободных грамматик: Контекстно-свободная грамматика#Контекстно-свободный язык». формальное определение см. в разделе «
- ^ для контекстно-свободных грамматик: конкретные синтаксические деревья
Ссылки
[ редактировать ]- ^ Стефано Креспи Региззи (2009). Формальные языки и компиляция . Спрингер. п. 57. ИСБН 978-1-84882-049-4 .
- ^ Виджей-Шанкер К. и Вейр Дэвид Дж. (1994). «Эквивалентность четырех расширений контекстно-свободных грамматик» . Теория математических систем . 27 (6): 511–546. дои : 10.1007/BF01191624 . S2CID 12336597 .
{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Jump up to: а б Ноам Хомский (1963). «Формальные свойства грамматики». В РД Люсе; Р.Р. Буш; Э. Галантер (ред.). Справочник по математической психологии . Том. II. Нью-Йорк: Уайли. стр. 323—418 .
- ^ Корнаи А. и Пуллум Г.К. 1990. Теория X-образной структуры фразы . Язык, 66:24-50.
- ^ Миллер, Филип Х. 1999. Сильная генеративная способность . Публикации ЦЛИ.
- ^ «Ёсинага Н., Мияо Ю. и Цудзи Дж. 2002. Формальное доказательство сильной эквивалентности для преобразования грамматики из LTAG в стиль HPSG . В материалах семинара TAG+6: 187-192. Венеция, Италия» (PDF) . Архивировано из оригинала (PDF) 28 августа 2011 г. Проверено 5 февраля 2012 г.
- ^ Jump up to: а б Эммон Бах; Филип Миллер (2003). «Генераторный потенциал» (PDF) . В Уильяме Дж. Фроули (ред.). Международная энциклопедия лингвистики (2-е изд.). Издательство Оксфордского университета. doi : 10.1093/acref/9780195139778.001.0001 . ISBN 9780195139778 .