Существуют ли хорошо известные алгоритмы для определения «возвращаемых типов» правил парсера?

Question

Учитывая грамматику и прилагаемый код действия, есть ли какое-либо стандартное решение для определения того, к какому типу должен приводить каждый продукт (и, следовательно, какой тип должен вызывать вызывающий продукт)?

Я имею в виду ОО-программу и код действия, которые используют что-то вроде синтаксиса c # var (но я не ищу что-то специфичное для c #).

Это было бы довольно просто, если бы не перегрузка функций и рекурсивные грамматики.

Проблема возникает с такими случаями:

Foo ::= 
    Bar Baz { return Fig(Bar, Baz); }
    Foo Pit { return Pop(Foo, Pit); } // typeof(foo) = fn(typeof(Foo))

Answer 1

Если вы пишете код на функциональном языке, это легко; стандартный вывод типа Хиндли-Милнера прекрасно работает. Не делайте этого . В моем генераторе синтаксического анализатора EBNF (никогда не выпускавшегося, но исходный код доступен по запросу), который поддерживает Icon, c и Standard ML, я фактически реализовал идею , о которой вы спрашиваете для серверной части Standard ML: типы были выведены. Полученные грамматики практически невозможно отладить.

Если вы добавите перегрузку в микс, результаты будут сложнее для отладки . (Это верно! Это просто! Сложнее, чем невозможно! Больше, чем бесконечность! Мимо моего сна!) Если вы действительно хотите попробовать это сами, вы можете мой код . (Вы не делаете; есть причина, по которой я никогда не выпускал это.)

Answer 2

Возвращаемое значение действия грамматики на самом деле ничем не отличается от локальной переменной, поэтому вы должны иметь возможность использовать вывод типа C # для выполнения этой работы. См. в этом документе , чтобы узнать, как реализован вывод типа C #.

Стандартный способ сделать вывод типа - это алгоритм Хиндли-Милнера , но он не справится с перегрузкой "из коробки".

Обратите внимание, что даже генераторы синтаксического анализатора для языков вывода типов обычно не определяют типы грамматических действий. Например, ocamlyacc требует аннотации типов. Генератор синтаксических анализаторов Happy для Haskell может выводить типы , но, похоже, препятствует этой практике. Это может указывать на то, что выводить типы в грамматиках сложно, плохая идея или и то, и другое.

[ОБНОВЛЕНИЕ] Очень сильно от Нормана Рэмси, который обладает преимуществом горького опыта.