Разные языки (включая те, которые перечислены в вашем заголовке) на самом деле имеют очень разные правила для шаблонов / обобщений (например, какие типы аргументов могут быть, где могут появляться шаблоны / обобщения, когда им разрешено иметь явный список аргументов). и каков синтаксис для аргументов шаблона / типа для методов generi c), которые сильно влияют на параметры, которые вы имеете для синтаксического анализа. Ни на одном из известных мне языков не правда ли, что значение x<T> a; зависит от того, является ли T типом.
Так что давайте go через языки C ++, Java, Rust и C#:
Во всех четырех из этих языков и типы, и функции / методы могут быть шаблонами / generi c. Таким образом, нам придется беспокоиться не только о неоднозначности с объявлениями переменных, но и о вызовах функций / методов: это f<T>(x) вызов функции / метода с явным аргументом шаблона / типа или два реляционных оператора с заключенным в скобки последним операндом ? На всех четырех языках шаблоны / generi c функции / методы могут вызываться без шаблона / типа, когда они могут быть выведены, но такой вывод не всегда возможен, поэтому просто запретить явные аргументы шаблона / типа для вызовов функций / методов не является опция.
Даже если язык не позволяет связывать реляционные операторы, мы можем получить неоднозначность в выражениях, подобных этому: f(a<b, c, d>(e)). Это вызов f с тремя аргументами a<b, c и d>e или с единственным аргументом a<b, c, d>(e), вызывающий функцию / метод с именем a с аргументами типа / шаблона b,c,d?
Теперь, помимо этой общей основы, большинство всего остального отличается в этих языках:
Rust
В Rust синтаксис для объявления переменной равен let variableName: type = expr;, поэтому x<T> a; не может не может быть объявлением переменной, потому что это совсем не соответствует синтаксису. Кроме того, это также недопустимое выражение выражения (больше), потому что операторы сравнения больше не могут быть связаны (*).
Так что здесь нет двусмысленности или даже проблемы с анализом. Но как насчет вызовов функций? Для вызовов функций Rust избежал неоднозначности, просто выбрав другой синтаксис для предоставления аргументов типа: вместо f<T>(x) синтаксис - f::<T>(x). Поскольку аргументы типа для вызовов функций являются необязательными, когда их можно вывести, к счастью, это уродство, к счастью, не нужно очень часто.
Итак, в итоге: let a: x<T> = ...; - это объявление переменной, f(a<b, c, d>(e)); вызывает f с тремя аргументы и f(a::<b, c, d>(e)); вызывает a с тремя аргументами типа. Разбор прост, потому что все они достаточно различны, чтобы их можно было различить только одним токеном.
Java
В Java x<T> a; фактически является действительным объявлением переменной, но это не допустимое выражение выражения. Причина этого в том, что грамматика Java имеет выделенный нетерминал для выражений, которые могут отображаться как оператор выражения, а приложения реляционных операторов (или любых других операторов не-присваивания) не сопоставляются этим нетерминалом. Назначения есть, но левая часть выражений присваивания также ограничена. Фактически, идентификатор может быть началом выражения выражения, только если следующий токен является =, ., [ или (. Таким образом, идентификатор, за которым следует <, может быть только началом объявления переменной, означая, что для анализа этого нам нужен только один токен упреждения.
Обратите внимание, что при доступе к stati c членам generi c class, вы можете и должны ссылаться на класс без аргументов типа (то есть FooClass.bar(); вместо FooClass<T>.bar()), поэтому даже в этом случае за именем класса будет следовать ., а не <.
Но как насчет вызовов метода generi c? Нечто подобное y = f<T>(x); все еще может столкнуться с неоднозначностью, потому что реляционные операторы, конечно, допустимы в правой части =. Здесь Java выбирает решение, аналогичное Rust, просто изменяя синтаксис для вызовов методов generi c. Вместо object.f<T>(x) используется синтаксис object.<T>f(x), где часть object. является необязательной, даже если объект this. Таким образом, чтобы вызвать метод generi c с явным аргументом типа для текущего объекта, вам нужно написать this.<T>f(x);, но, как и в Rust, аргумент типа часто можно вывести, что позволяет просто написать f(x);.
Итак, в итоге x<T> a; - это объявление переменной, и не может быть выражений, которые начинаются с реляционных операций; в общем случае this.<T>f(x) - это вызов метода c, а f<T>(x); - сравнение (ну, на самом деле, ошибка типа). Опять же, разбор прост.
C#
C# имеет те же ограничения на выражения выражений, что и Java, поэтому объявления переменных не являются проблемой, но в отличие от предыдущего два языка, это позволяет f<T>(x) в качестве синтаксиса для вызовов функций. Чтобы избежать неоднозначностей, реляционные операторы должны заключаться в скобки при использовании таким способом, который также может быть допустимым вызовом обобщенной c функции. Таким образом, выражение f<T>(x) является вызовом метода, и вам нужно добавить круглые скобки f<(T>(x)) или (f<T)>(x) для сравнения (хотя на самом деле это будут ошибки типа, потому что вы не можете сравнивать логические значения с < или >, но парсер не заботится об этом) и аналогично f(a<b, c, d>(e)) вызывает обобщенный c метод с именем a с аргументами типа b,c,d, тогда как f((a<b), c, (d<e)) будет включать два сравнения (и вы можете в Фактически пропустите одну из двух пар скобок).
Это приводит к более приятному синтаксису для вызовов методов с явными аргументами типа, чем в предыдущих двух языках, но синтаксический анализ становится довольно сложным. Учитывая, что в приведенном выше примере f(a<b, c, d>(e)) мы можем на самом деле поместить произвольное количество аргументов перед d>(e) и a<b - это совершенно правильное сравнение , если за ним не следует d> (e) , нам действительно нужно произвольное количество предвидения, обратного отслеживания или недетерминированности для анализа этого.
Итак, в итоге x<T> a; является объявлением переменной, нет выражения выражения, которое начинается со сравнения, f<T>(x) является вызовом метода Выражение и (f<T)>(x) или f<(T>(x)) будут (неправильно набраны) сравнениями. Невозможно проанализировать C# с помощью menhir.
C ++
В C ++ a < b; является допустимым (хотя и бесполезным) оператором выражения, синтаксис для вызовов функций шаблона с явными аргументами шаблона f<T>(x) и a<b>c могут быть совершенно корректными (даже хорошо напечатанными) сравнениями. Так что утверждения типа a<b>c; и выражения типа a<b>(c) на самом деле неоднозначны без дополнительной информации. Кроме того, аргументы шаблона в C ++ не обязательно должны быть типами. Таким образом, Foo<42> x; или даже Foo<c> x;, где c определен как const int x = 42;, например, может быть совершенно допустимым экземпляром шаблона Foo, если Foo определен, чтобы принимать целое число в качестве аргумента шаблона , Так что это облом.
Чтобы устранить эту неоднозначность, грамматика C ++ ссылается на правило template-name вместо identifier в тех местах, где ожидается имя шаблона. Так что, если бы мы относились к ним как к отдельным сущностям, здесь не было бы никакой двусмысленности. Но, конечно, template-name определяется просто как template-name: identifier в грамматике, так что это кажется довольно бесполезным, ... за исключением , что в стандарте также говорится, что template-name должно совпадать только тогда, когда данный идентификатор называет шаблон в текущей области. Точно так же говорится, что идентификаторы должны интерпретироваться как имена переменных только тогда, когда они не относятся к шаблону (или имени типа).
Обратите внимание, что, в отличие от предыдущих трех языков, C ++ требует все типы и шаблоны должны быть объявлены, прежде чем они могут быть использованы. Поэтому, когда мы видим оператор a<b>c;, мы знаем, что это может быть только создание экземпляра шаблона, если мы предварительно проанализировали объявление для шаблона с именем a и оно в настоящее время находится в области видимости.
Итак, если мы отслеживаем области при разборе, мы можем просто использовать операторы if, чтобы проверить, относится ли имя a к ранее проанализированному шаблону или нет в рукописном синтаксическом анализаторе. В генераторах синтаксических анализаторов, которые допускают предикаты semanti c, мы можем сделать то же самое. Для этого даже не требуется какой-либо оглядки назад или отслеживания.
Но как быть с генераторами синтаксических анализаторов, такими как ya cc или menhir, которые не поддерживают предикаты semanti c? Для этого мы можем использовать что-то, известное как хак лексера, то есть мы заставляем лексера генерировать разные токены для имен типов, имен шаблонов и обычных идентификаторов. Тогда у нас есть хорошо однозначная грамматика, которую мы можем подать нашему генератору синтаксического анализатора. Конечно, хитрость в том, чтобы заставить лексера это сделать. Для этого sh нам необходимо отслеживать, какие шаблоны и типы в настоящее время находятся в области видимости, используя таблицу символов, а затем обращаться к этой таблице символов из лексера. Нам также нужно будет сообщить лексеру, когда мы читаем имя определения, например x в int x;, потому что тогда мы хотим сгенерировать обычный идентификатор, даже если шаблон с именем x в настоящее время находится в scope (определение int x; будет затенять шаблон до тех пор, пока переменная не выйдет из области видимости).
Этот же подход используется для разрешения неоднозначности приведения (это (T)(x) приведение x к типу T или вызов функции с именем T?) В C и C ++.
Итак, в итоге, foo<T> a; и foo<T>(x) являются экземплярами шаблона тогда и только тогда, когда foo шаблон. Разбор - это сука, но возможен без произвольного просмотра или возврата назад и даже без использования менгира при применении хекса лексера.