Должно ли дерево абстрактного синтаксиса быть деревом?

Должен ли вывод синтаксического анализатора быть деревом или это также может быть общий граф?

Кроме того, существует ли какой-либо существующий или вероятный язык, который использует общее представление графов вместо деревьев для своего синтаксиса?

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

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

Есть такие вещи, как графические грамматики, хотя я не знаю, используются ли они для синтаксического анализа языков программирования.

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

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

Обратите внимание, что люди могут не согласиться с тем, что составляет синтаксис языка. Некоторые могут ограничить это чисто формальной основой языка, в то время как другие могут вводить немного более семантические соображения, такие как тип, жанр, число или другие более сложные (я не различаю НЛП или языки программирования). Большинство языков имеют функции, требующие представления графов, но «разработчик» (из-за отсутствия лучшего слова) должен решить, хочет ли он включить это в синтаксис.

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

В простом случае чистого анализа без контекста может подойти дерево разбора, за исключением проблемы неоднозначности, описанной ниже, или того факта, что вы можете захотеть немного изменить его, чтобы получить AST (см. Ниже).

Однако в более сложных случаях вам могут понадобиться разные структуры, часто представленные ссылками в дереве, что приводит к структуре графа. Это очень сильно зависит от вашего определения синтаксиса языка.

Кроме того, какое дерево вы должны вывести, не очевидно. Если вы берете случай древовидных грамматик (TAG), они работают таким образом, что синтаксическое дерево не совпадает с деревом деривации, хотя первое может быть получено из второго. То, что вы хотите вывести, может быть актуальным вопросом.

Есть еще одна проблема, связанная с неясностью. Данное предложение, хотя и относится к вашему языку, может делать это по-разному, но может иметь синтаксическую структуру по-разному.

Затем вы можете выбрать для вывода только одну из этих структур, выбранную случайным образом или согласно некоторому четко определенному критерию (например, вероятности). Вы также можете выбрать вывод нескольких или всех из них. Если вы хотите вывести несколько, обычно удобнее упаковать их в уникальную структуру, которая поделится тем, что у них общего. Это экономит пространство и вычислительное время, а сложность может быть реальной проблемой.

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

Об абстрактных синтаксических деревьях

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

Что касается AST в исторической перспективе, они берут свое начало с языка Lisp и систем манипулирования программами в 1960-1970 годах. Идея заключалась в том, чтобы рассматривать программы как большие выражения, как математические формулы, как для целей манипуляции, так и для анализа свойств или формального определения семантики, которую математики знают, как делать с формулами. Как формулы, они были естественно древовидной структуры, но могли быть украшены различной информацией, которая превратила эти деревья в графы. Это было удобно как формально, так и прагматично, и в дальнейшем использовалось компиляторами и системами программирования.

Итак, по сути, AST - это дерево, как следует из названия, но может нести дополнительную информацию. Все остальное зависит от выбора исполнителя и в глазах смотрящего. Это граф или украшенное дерево? Тем не менее, базовое дерево AS имеет значение, потому что это леса, на которых вы строите как в теории, так и в программировании.

Обратите внимание, что AST отличался от дерева синтаксического анализа (синтаксис не зависел от контекста), созданного алгоритмом синтаксического анализа, который изучался в теории формального языка. Причина заключалась в том, что дизайн синтаксиса был ограничен технологией синтаксического анализа того времени, что само ограничивалось низкой доступной вычислительной мощностью. Результатом стало то, что синтаксические деревья были всего лишь замученными вариантами того, что естественно было бы рассмотреть структуру программы, и для получения более чистой и простой версии, называемой AST, требовалась дальнейшая обработка, а не реальная часть основного процесса формального анализа.

Однако представление деревьев на компьютере, абстрактное или нет, несколько ограничено, когда вы хотите представить все структуры неоднозначного предложения. В частности, это скрывает проблемы сложности. Сохранение неоднозначностей в структуре графа при переводе с деревьев разбора на деревья AS также может быть проблемой. Однако, если вас это беспокоит, часто можно определить ваш конкретный синтаксис таким образом, чтобы дерево разбора могло служить AST. Это разрешено очень общими алгоритмами, которые обрабатывают неоднозначность, и мощью современных компьютеров.

Если вы анализируете с использованием анализа GLR (Generalized LR), и если анализ входных данных неоднозначен (существует несколько возможных способов анализа входных данных), то результат анализа можно рассматривать как анализ DAG, а не как разбирать дерево. Анализ DAG компактно кодирует множество возможных разборов: множество возможных деревьев разбора.

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

В НЛП представления абстрактного синтаксиса представляют собой ориентированные ациклические графы (DAG). Ситуация, когда два ребра указывают на один и тот же узел, называется «разделением структуры».

Однажды я написал интерпретатор для C, в котором «AST» для оператора + = (например) не был деревом. Посмотрим a[i++] += dгдеa[i++] это intи dесть double. Неявные операции преобразования и извлечения были явными в дереве, поэтому проблема заключается в том, куда поместить выборку a[i++]и преобразование в удвоение. Нашим решением было отказаться от деревьев. Получившийся «ASG» выглядел так

         +=
       / | \
      /  |  \
     /   |   \
    / convert \
    |     |    \
    |   fetch  fetch
    |   /       |
    index       d
    /  \
   a   postinc
       |
       i

Я был озадачен этим сам, пока не понял, что это не абстрактное дерево, не абстрактное синтаксическое дерево, а синтаксис абстрактный.

Итак, чтобы ответить на ваш вопрос, я пришел к выводу, что абстрактное синтаксическое дерево, а также конкретное синтаксическое дерево, дерево решений или любое другое дерево должно быть лучше деревом.

С другой стороны, ничто не должно мешать кому-либо использовать график абстрактного синтаксиса, или диаграмму абстрактного синтаксиса, или куб абстрактного синтаксиса, или спецификацию абстрактного синтаксиса.

Я предполагаю, что абстрактное синтаксическое дерево «абстрактного синтаксического дерева» помогло бы мне избежать путаницы.