Формальная грамматика для выражения внутреннего соединения

Question

У меня есть язык, который описывает домен с помощью предикатов произвольной арности.Например, в логике первого порядка я могу написать следующее правило:

PersonlivesInCountry(x,y) <-> person(x), PersonlivesInState(x,z), StateisInCountry(z,y)

В этом примере все пары в PersonLivesInCountry в точности соответствуют тем, которые соответствуют другим ограничениям.Ключевым моментом здесь является выражение объединения между другими ограничениями, например, z совместно с предикатами PersonLivesInState и StateIsInCountry.На моем языке у меня всегда есть такая структура, поэтому мне нужно написать грамматику, чтобы выразить это условие соединения.Можно ли гарантировать, что каждый выходной индекс отношения находится в (внутреннем) соединении с преемником?

Answer 1

Безконтекстные грамматики не могут выражать согласие имен (если только набор возможных имен не является конечным, и даже тогда это является болью).

Этот вид анализа обычно попадает в категорию «семантического анализа»,который обычно легче написать как (последовательность) обходов абстрактного синтаксического дерева (AST).В этой модели синтаксический анализатор просто строит AST.

Для простых синтаксических анализаторов семантический анализ может быть выполнен во время синтаксического анализа, прикрепляя семантические действия к каждому синтаксическому правилу.Тем не менее, это часто приводит к плохому фактору кода, который труднее поддерживать и модифицировать в долгосрочной перспективе.

Тем не менее, довольно часто можно увидеть семантические действия, используемые не только для создания AST, но и таблицы символов.Я не так люблю это, как раньше;в настоящее время я ограничиваю анализ символов в анализаторе вводом символа в таблицу интернированных символов, что упрощает управление памятью и ускоряет поиск символов во время семантического анализа.YMMV.Удачи в проекте.