Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, mefrill, Вы писали:

M>>Ну вот, из примера выше не ясно, какое дерево вывода использовать, для решения необходимо задействовать семантический анализатор, чтобы отбросить одно из деревьев, т.е. решить, к какому if относится else. обычно делается выбор в пользу варианта 1.

VD>О! Похоже нашелся человек который может рассудить один наш спор.

VD>С if/else все понятно. Это пример из учебников. Все парсеры и так по умолчанию парсят if/else так как требуют 99% язвеоа. А вот если взять немного боле сложный случай. Например, вот цитата из спецификации C# 2.0:
VD>

VD>9.2.3 Grammar ambiguities
VD>The productions for simple-name (§14.5.2) and member-access (§14.5.4) can give rise to ambiguities in the
VD>grammar for expressions. [Example: The statement:
VD>

VD>F(G<A, B>(7));
VD>

VD>could be interpreted as a call to F with two arguments, G < A and B > (7). Alternatively, it could be
VD>interpreted as a call to F with one argument, which is a call to a generic method G with two type arguments
VD>and one regular argument. end example]
VD>If a sequence of tokens can be parsed (in context) as a simple-name (§14.5.2), member-access (§14.5.4), or
VD>pointer-member-access (§25.5.2) ending with a type-argument-list (§26.5.1), the token immediately
VD>following the closing > token is examined. If it is one of
VD>

VD>( ) ] : ; , . ? == !=
VD>

VD>then the type-argument-list is retained as part of the simple-name, member-access or pointer-member-access
VD>and any other possible parse of the sequence of tokens is discarded. Otherwise, the type-argument-list is not
VD>considered to be part of the simple-name, member-access or pointer-member-access, even if there is no other
VD>possible parse of the sequence of tokens. [Note: These rules are not applied when parsing a type-argument-
VD>list in a namespace-or-type-name (§10.8). end note] [Example: The statement:
VD>

VD>F(G<A, B>(7));
VD>

VD>will, according to this rule, be interpreted as a call to F with one argument, which is a call to a generic
VD>method G with two type arguments and one regular argument. The statements
VD>

VD>F(G<A, B>7);
VD>F(G<A, B>>7);
VD>

VD>will each be interpreted as a call to F with two arguments. The statement
VD>x = F<A> + y;
VD>will be interpreted as a less-than operater, greater-than operator and unary-plus operator, as if the statement
VD>had been written x = (F < A) > (+y), instead of as a simple-name with a type-argument-list followed
VD>by a binary-plus operator. In the statement
VD>

VD>x = y is C<T> + z;
VD>

VD>the tokens C<T> are interpreted as a namespace-or-type-name with a type-argument-list. end example]

VD>Являются ли данные вещи всего лишь проблемами LL(1)/LALR(1) парсеров. Или все же это зависимость от контекста. И формально такую граматику нельзя назвать контекстно свободной?

VD>Если можно, дай максимально развернутый ответ.

Определение языка и, в частности, языка программирования также, в совю очередь, очень зависит от контекста . Например, если мы понимаем язык как множество текстов и, таким образом, абстрагируемся от смыслового содержания слов данного языка, то мы рассматриваем данный язык через призму теории формальных языков. Обычно, так как мы применяем машину для разбора или генерации строк языка, применяются порождающие грамматики Хомского — они дают хороший путь для определения алгоритма, хотя сами алгоритмом не являются. В этом смысле, сложность конструкций языка измеряется в терминах их алгоритмического определения. Т.е. один язык можно определить с помощью КС грамматики, другой нельзя. Получается, что мерой синтаксической сложности формального языка служит тип грамматики, которая этот язык порождает. Для данного язык существует, вообще говоря, бесконечное, хотя и счетное, множество грамматик, которые его порождают. Из этого множества можно выбрать подкласс грамматик наибольшего, в смысле определения Хомского, типа. Например, грамматики типа 2 — КС грамматики. Тогда формальный язык называется контекстно-свободным. Кстати, существует бесконечное множество языков (мощности континиума) для которых невозможно найти грамматику, их порождающую. итак, для формального языка мерой его сложности служит наибольший тип из типов всех грамматик, которые его попрождают. Когда же мы говорим о разборе языка программирования с помощью компилятора или, что тоже самое, об описаниии данного языка в некоем стандарте, мы уже имеем ввиду нечто большее, чем просто набор текстов. Мы описываем язык не только с помощью некоторой порождающей грамматики, но также и с помощью другого текста на некотором метаязыке, обычно, на человеческом. Та порождающая КС-грамматика, которая в приводится в стандартах, обычно описывает не сам язык, некоторое его надмножество. После чего, на метаязыке описаный надъязык сужается до требуемого языка. Т.е. из множества предложений надъязыка исключаются те, которые не удовлетворяют описанию на метаязыке. Относительно контекстной зависимости языков программирования известно, что условие предварительного объявления имен до их использования не может быть выражено синтаксически посредством КС-грамматики. Именно поэтому, при построении анализаторов, в грамматике надъязыка мы имеем дело с ID, а не с конкретными строками и способами их построения. Синтаксическая конструкция

Definition --> Type ID
Using ID

позволяет появляться в языке таким строкам, как Type ttt using aaa так как в синтаксисе не выражена связь между объявлением и использованием идентификатора. Связь эта выражена на метаязыке и реализуется обычно таблицей идентификаторов. Также известно, что эту связь можно выразить с помощью КЗ грамматики, убрав абстрактное ID и поставив вместо него синтаксические конструкции образования идентификаторов. Поэтому, рассматривая язык программирования как формальный язык, мы говорим, что такой язык не является КС, но есть КЗ, оценивая, таким образом, синтаксическую сложность данного языка как множества текстов. И только в таком контексте мы можем применять выражения типа "контекстно-свободный" или "контекстно-зависимый".

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

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

Вроде бы все.