Эквивалентность (формальные языки)
В теории формального языка слабая эквивалентность двух грамматик означает, что они генерируют один и тот же набор строк, т. е. формальный язык, который они генерируют, один и тот же. В теории компиляторов это понятие отличается от строгой (или структурной ) эквивалентности , что дополнительно означает, что два дерева синтаксического анализа [ требуется уточнение ] достаточно похожи в том, что им может быть присвоена одна и та же семантическая интерпретация. [1]
Виджай-Шенкер и Вейр (1994) [2] демонстрируют, что линейные индексированные грамматики , комбинаторные категориальные грамматики , грамматики, прилегающие к дереву , и грамматики головок являются слабо эквивалентными формализмами, [ требуется пояснение ] , поскольку все они определяют одни и те же строковые языки.
С другой стороны, если две грамматики порождают один и тот же набор деревьев вывода (или, в более общем случае, один и тот же набор абстрактных синтаксических объектов), то эти две грамматики строго эквивалентны. Хомский (1963) [3] вводит понятие сильной эквивалентности и утверждает, что только сильная эквивалентность имеет значение при сравнении грамматических формализмов. Корнаи и Пуллум (1990) [4] и Миллер (1994) [5] предлагают уточненное понятие строгой эквивалентности, которое допускает изоморфные отношения между синтаксическими анализами, заданными различными формализмами. Yoshinaga, Miyao, and Tsujii (2002) [6] предлагают доказательство того, что для любого формализма LTAG существует сильно эквивалентный HPSG .
Обе грамматики генерируют один и тот же набор строк, а именно. множество всех арифметических выражений, которые можно построить из переменных «х», «у», «z», констант «1», «2», «3», операторов «+», «-», « *", "/" и круглые скобки "(" и ")". Однако конкретное синтаксическое дерево второй грамматики всегда отражает обычный порядок операций , в то время как дерево из первой грамматики этого не требует.
Для примера строки "1+2*3" в правой части рисунка показано уникальное дерево разбора со второй грамматикой; [примечание 2] оценка этого дерева в постфиксном порядке даст правильное значение, 7. Напротив, левая часть изображения показывает одно из деревьев синтаксического анализа для этой строки с первой грамматикой; оценка его в постфиксном порядке даст 9.
Поскольку вторая грамматика не может генерировать дерево, соответствующее левой части изображения, в то время как первая грамматика может, обе грамматики не являются строго эквивалентными.
