Существуют ли хорошо известные алгоритмы для вывода "возвращаемых типов" правил синтаксического анализатора?
Учитывая грамматику и прилагаемый код действия, существует ли какое-либо стандартное решение для определения того, к какому типу должно привести каждое производство (и, следовательно, какого типа вызывающее производство должно ожидать от него)?
Я думаю об объектно-ориентированной программе и коде действий, в котором используется что-то вроде синтаксиса var в C# (но я не ищу что-то специфичное для C#).
Это было бы довольно просто, если бы не перегрузка функций и рекурсивные грамматики.
Проблема возникает в таких случаях:
Foo ::=
Bar Baz { return Fig(Bar, Baz); }
Foo Pit { return Pop(Foo, Pit); } // typeof(foo) = fn(typeof(Foo))
Ответы 2
Если вы пишете код на функциональном языке, это легко; стандартный вывод типа Хиндли-Милнера отлично работает. Не делайте этого. В моем генераторе синтаксического анализатора EBNF (никогда не выпускался, но исходный код доступен по запросу), который поддерживает Icon, c и Standard ML, я на самом деле реализовал идею, о котором вы спрашиваете, для серверной части Standard ML: все типы были выведены. Полученные грамматики было практически невозможно отладить.
Если вы добавите перегрузка в микс, результатом будет только труднее отлаживать. (Правильно! Это только что! Сложнее, чем невозможно! Больше бесконечности! Прошло время отходить ко сну!) Если вы действительно хотите попробовать это сами, добро пожаловать в мой код. (Вы этого не сделаете; есть причина, по которой я его не выпустил.)
Иконка была очень интересной; Жаль, что они слишком долго ждали, чтобы подумать об интерфейсе ОС. Его время прошло. Тем не менее, это все еще самая интересная модель обработки строк, которую я когда-либо видел. Подробное описание вывода типов см. В разделе research.microsoft.com/Users/simonpj/papers/higher-rank/….
Возвращаемое значение грамматического действия на самом деле не отличается от локальной переменной, поэтому вы должны иметь возможность использовать вывод типа C# для выполнения этой работы. См. Эта бумага для некоторого понимания того, как реализован вывод типа C#.
Стандартный способ вывода типа - это Алгоритм Хиндли-Милнера, но он не обрабатывает перегрузку из коробки.
Обратите внимание, что даже генераторы парсеров для языков с выводом типов обычно не определяют типы грамматических действий. Например, окамлячк требует аннотаций типов. Генератор парсера Счастливый для Haskell может использовать вывести типы, но, похоже, препятствует такой практике. Это может указывать на то, что определение типов в грамматике сложно, плохая идея или и то, и другое.
[ОБНОВЛЕНИЕ] Очень много выдвинул Норман Рэмси, у которого есть горький опыт.
Если бы я знал что-нибудь об Icon, я бы посмотрел. (примечание: да, я знаю, что я чокнутый ... Я задаю этот вопрос как предвестник добавления [еще] вывода к этому -> dsource.org/projects/scrapple/browser/trunk/dparser/tag/…)