Здравствуйте, prVovik, Вы писали:
V>Здравствуйте, Шахтер, Вы писали:
Ш>>Ну так вы определитесь, о каких именно грамматиках говорите.
V>Ну я имел ввиду общую грамматику языка (то есть грамматику всех корректных программ), которая является ну ни как не ниже КЗ
Вот что это такое? Что такое "грамматика всех корректных программ"? Если ограничиться однофайловыми программами, то можно говорить о языке -- о множестве всех правильных программ. В том смысле, что компилятор может эту программу скомпилировать и сгенерировать выход (в кодах, на ассемблере -- не суть важно). Язык может быть задан разными грамматиками -- какую именно из них ты имеешь ввиду?
Прежде чем рассуждать о чем-то, неплохо было бы определить объект, о котором рассуждаешь.
Ш>Вот что это такое? Что такое "грамматика всех корректных программ"?
Граматика, порождающая корректные с точки зрения стандартного компилятора программы. Я знаю, что таких грамматик может быть много, но то, что среди них не будет ни одной КС грамматики — это однозначно.
AndrewVK,
> Паша, будь добр, поясни свою позицию. А то простановка плюсов vdimas за доказательства того что грамматика C# и С++ КС наряду с простановкой плюсов prVovik, доказывающего что грамматики и шарпа и С++ КЗ приводит меня в состояние ступора.
Как они уже между собой выяснили, они имели в виду немного разные грамматики: один — грамматику языка, другой — грамматику использующуюся для построения компилятора. При этом, оба правы, когда говорит, что одна из этих грамматик контекстно-свободна, а другая — нет
Грамматика любого языка, требующего предварительное объявление переменных, безусловно, не является КС. В том числе и C#, и C++. Это классика (Ахо, Сети, Ульман):
Рассмотрим абстрактный язык L1 = { wcw | w <принадлежит> (a|b)* }. L1 состоит из всех слов, образованных повторяющимися строками из a и b, разделенными символом c, например aabcaab. Можно доказать, что этот язык не является контекстно-свободным. Он абстрагирует проблему проверки объявления переменных до их использования — первое w в wcw представляет объявление переменной, а второе w — ее использование. Из того, что L1 не является контекстно-свободным языком, следует, что языки типа Algol или Pascal не есть контекстно-свободными, т.к. в них требуется объявление переменной до ее использования, а идентификаторы могут иметь произвольную длину.
Однако для реализации компиляторов, как уже было верно замечено, действительно, обычно используются КС грамматики, порождающие несколько большее количество предложений, чем входит в сам язык, с последующим "семантическим" анализом результата распознавания.
Соответственно, "контекстно-зависимые" ключевые слова вполне вписываются в КС грамматику, если таковая уже используется для синтаксического анализа, т.к. зависимостью от контекста (без кавычек) называется вовсе не зависимость значения терминала от положения, которую как раз КС грамматики описывают совершенно замечательно.
Впрочем, тут есть один нюанс: если то, будет ли данное "контекстно-зависимое" слово ключевым в данном месте зависит не только от его положения, но и, скажем, от того, есть ли в данной области видимости уже определенный идентификатор с таким же именем, то вот это уже будет действительной зависимостью от контекста, и КС грамматикой, как и требование предварительного объявления переменных, описываться не будет.
Posted via RSDN NNTP Server 1.9 gamma
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
P.S.
> Грамматика любого языка, требующего предварительное объявление переменных, безусловно, не является КС.
Любого реального, т.к. при некоторых ограничениях даже при наличии требования предварительного объявления/определения переменных КС грамматику построить можно.
Posted via RSDN NNTP Server 1.9 gamma
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Здравствуйте, prVovik, Вы писали:
V>Да. Потому что КС-грамматика по определению состоит из конечного числа продукций.
Нет такого в определении КС-грамматики. Впрочем неважно, ограничим длину исходного текста программы 1 пентабайтом. Очевидно что с практической точки зрения ничего не изменилось, однако множество всех возможных программ стало конечным.
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, prVovik, Вы писали:
V>>Да. Потому что КС-грамматика по определению состоит из конечного числа продукций.
AVK>Нет такого в определении КС-грамматики.
Formal definition
In the classic formalization of generative grammars first proposed by Noam Chomsky in the 1950s, a grammar G consists of the following components:
A finite set N of nonterminal symbols.
A finite set ? of terminal symbols that is disjoint from N. A finite set P of production rules where a rule is of the form
string in (? U N)* > string in (? U N)*
AVK>Впрочем неважно, ограничим длину исходного текста программы 1 пентабайтом. Очевидно что с практической точки зрения ничего не изменилось, однако множество всех возможных программ стало конечным.
Да, но это доказывает, что твой логический вывод AVK>Отсюда любая грамматика является КС
неверен
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, prVovik, Вы писали:
V>>Да. Потому что КС-грамматика по определению состоит из конечного числа продукций.
AVK>Нет такого в определении КС-грамматики. Впрочем неважно, ограничим длину исходного текста программы 1 пентабайтом. Очевидно что с практической точки зрения ничего не изменилось, однако множество всех возможных программ стало конечным.
Ты не понял. Сама грамматика — конечна, т.е. состоит из конечного множества продукций.
Множество порождаемых цепочек вполне может быть бесконечным, для этого достаточно даже 1-го рекурсивного правила.
Здравствуйте, prVovik, Вы писали:
Ш>>"Зависящие от контекста" токены не делают язык контекстно-зависимым.
V>Это почему еще? V>Если есть зависящие от контекста токены, то грамматика КЗ. А язык, порождаемый КЗ грамматикой по определению является КЗ.
Не только токены (терминалы), но и правила.
... << RSDN@Home 1.1.4 beta 3 rev. 207>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Шахтер, Вы писали:
Ш>Не путай ужа с ежём.
Я, то как раз не путаю.
Ш> "Зависящие от контекста" токены не делают язык контекстно-зависимым.
Токены в обязательном порядке. И не только токены. Любая зависимость от контекстов делает граматику не КС (т.е. КЗ).
Ш>Например, в языке арифметических выражений — может выступать как унарный оператор и как бинарный оператор. Что не делает этот язык контекстно-зависимым.
Хороший пример. Только он всего лишь показывает твое поверхностное знание предмета.
В данном случае минус в обоих случаях является один и мем же токеном (или выражаясь научно нетерминалом). А то будет ли он рассматриваться как бинарный оператор или как унарный целиком зависит от таких вещей как граматика и ассоциативность оператора.
Это сто-процентно чистая КСГ (контекстно свободная граматика). Причем это даже LL(1)-граматика, так что ее можно парсить методом рекурсивного спуска. Вот тут
приведен полный код парсера созданного с использованием построителей парсеров CocoR.
В случае же, например, нетерминала get все зависит от контекста. Один и тот же нетерминал может быть ключевым словом (при распозновании тела свойства), так и идентификатором (при распозновании любого другого участка кода).
Примет разрешения конфликтов с get/set я уже давал рядом
. Обрати внимание на то что вместо введения нетерминалов "get" и "set" в нем испоьзован нетерминал identifier, который является допустимым идентификатором C# — это говорит, что можно использовать ключевые слова get и set где угодно (например, в качестве имени перемнной или функции), и что по сути get и set не являются ключевыми словами. А вот про любое друго ключевое слово такого сказать нельзя. Например, назвать переменную class не удастся. Кстати, VS 2005 уже подсвечивает синтаксис на базе парсинга. Так что в ней сразу видно используется get как ключевое слово или как индентификатор. Например, вот такой вот код:
using System;
class get
{
static get set;
static get assembly { get { return set; } }
static void Main()
{
set = new get();
}
}
совершенно корректен для C# и даже врено подсвечивается VS 2005. В отличи от нашего колорера она подкрасит только get выделенный жирным.
ЗЫ
Всем наставившим плюсы советую их снять и пойти почитать определение КС, а так же какие-нубудь книжки по принципам построения компиляторов.
Здравствуйте, AndrewVK, Вы писали:
AVK>Паша, будь добр, поясни свою позицию. А то простановка плюсов vdimas за доказательства того что грамматика C# и С++ КС наряду с простановкой плюсов prVovik, доказывающего что грамматики и шарпа и С++ КЗ приводит меня в состояние ступора.
Дык глубокое знание С++ не дает таких же глубоких знаний в других областях (даже смежных).
Счего ты взял что ПК эксперт в этой области? Его плюсы говорят только о двух вещах: 1) поверхносном знании принципов постоения компиляторов, 2) желании поддержать всех кто несогласен с Владм (ну, и возможно с тобой).
И тут похоже что ничего поделать нельзя. Барикады штука такая затягивающая.
Хотя плюсы prVovik в общем-то безобидны. prVovik в общем-то прав. Только его правота это очередной сфероконик вакумный. Да семантика — это зависимость от контекста. Да теоритически можно создать супер-парсер кторый позволит обойтись без семантического анализатора (и то не всегда). И даже были попытки это сделать. Вот только ни одна из них не увенчалась успехом, так как их эфективность быала мягко говоря ужасно мала. Поэтому при построении компиляторов (или интерпретаторов) выделяются три фазы:
1. Сканирование (оно же лексический разбор).
2. Парсинг контекстно-независимой граматики.
3. Семантический анализ.
Первые две фазы могут быть целиком автоматизированы если для языка можно создать КСГ определенной формы.
Третий этап намного труднее автоматизировать.
Так вот. По жизни все построитили компиляторов стремятся создать КСГ. Но иногда они отходят от требований КСГ с целью сделать язык более интуитивным и простым. Так С++ требует знания о типе в некоторых местах, а C# попросту плюет на требования КСГ вводя понятие конфликта, и описывая, при этом способы, принципы разрешения конфликтов.
... << RSDN@Home 1.1.4 beta 3 rev. 207>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VD>Только его правота это очередной сфероконик вакумный. Да семантика — это зависимость от контекста. Да теоритически можно создать супер-парсер кторый позволит обойтись без семантического анализатора (и то не всегда). И даже были попытки это сделать. Вот только ни одна из них не увенчалась успехом, так как их эфективность быала мягко говоря ужасно мала. Поэтому при построении компиляторов (или интерпретаторов) выделяются три фазы: VD>1. Сканирование (оно же лексический разбор). VD>2. Парсинг контекстно-независимой граматики. VD>3. Семантический анализ.
VD>Первые две фазы могут быть целиком автоматизированы если для языка можно создать КСГ определенной формы.
VD>Третий этап намного труднее автоматизировать.
Ну вот, сначала назвал мои слова сферокоником, а потом сам же их и повторил
Здравствуйте, VladD2, Вы писали:
V>>гм... ход мыслей понятен, но посмотри там же определение КЗ-грамматики. Если мне удасться твой т.н. "контекст" целиком расположить в правой части правил, то... VD>Неудастся. Вообще не удастся расположить в правиле. На то и зависимость от контекста.
Удастся. Просто придётся сильно расширить набор правил по отношеню к КЗ-грамматике.
... << RSDN@Home 1.1.3 stable >>
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, AndrewVK, Вы писали:
V>>Да. Потому что КС-грамматика по определению состоит из конечного числа продукций. AVK>Нет такого в определении КС-грамматики. Впрочем неважно, ограничим длину исходного текста программы 1 пентабайтом. Очевидно что с практической точки зрения ничего не изменилось, однако множество всех возможных программ стало конечным.
Мощность множества продукционных правил должна быть конечной. Если для выражения грамматики языка это множество должно быть бесконечным, то постулируется, что КС-грамматики для такого языка не существует. Только в этом случае. Даже грамматика из миллиона правил может быть КС-грамматикой. Её просто писать зашьёшься.
... << RSDN@Home 1.1.3 stable >>
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, AndrewVK, Вы писали:
V>>упрощенно: V>>PopertyDecl ::= GetPropertyDecl V>>PopertyDecl ::= SetPropertyDecl V>>PopertyDecl ::= GetSetPropertyDecl V>>GetProperty ::= TypeID VarID '{' 'get' FuncBody '}' V>>SetProperty ::= TypeID VarID '{' 'set' FuncBody '}' V>>GetSetProperty ::= TypeID VarID '{' 'set' FuncBody 'get' FuncBody '}' V>>GetSetProperty ::= TypeID VarID '{' 'get' FuncBody 'set' FuncBody '}' V>>если представимо в БНФ, то КС AVK>Здорово, а 'get' это что такое? В данном случае get это контекстно-зависимое ключевое слово. Для шарпа лексер без парсера корректный нельзя написать даже, вон студия get вне свойства как ключевое слово подсвечивает.
Это как посмотреть. Если, например, вместо правила
и ввести соответствующий комплект правил для GetPropertyBody, назначительно отличающийся от FuncBody в части допустимых идентификаторов, то получим КС-грамматику.
... << RSDN@Home 1.1.3 stable >>
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, AndrewVK, Вы писали:
V>>Да ты легко сам можешь написать КС парсер, который корректно разберет это несчатсное 'get' в различных синтаксических конструкциях AVK>Вряд ли. Все парсеры шарпа, которые я видел (а я видел их довольно много) были не КС. Случайность?
Возможно, поскольку отсутствие чего-то в обозримом пространстве не является доказательством невозможности существования этого чего-то. Этого просто нет сейчас и здесь. И всё.
... << RSDN@Home 1.1.3 stable >>
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, vdimas, Вы писали:
V>С использованием техники lexer->parser тебе действительно необходимы обходные пути, я полностью это признаю. Но, вроде бы, спорил совсем не с этим?
Извини, но спорили о конкретной ситуации, а не о сфероконях.
Если принять за истину, что граматика строится на базе треминалов (выдаваемых лексером), и "get" это один из терминалов, то граматика никак не может быть описана в терминах КСГ, так как значение терминала будет зависить от контекста.
Ты же предлагаешь строить парсер как тот изумительный Фортнан 77, т.е. из терминалов размером в симвовл и с учетом всех возможных поялений проблеов. Другими словами на другой лексической базе. Но и так построить корретный парсер будет неимоверно сложно, так как те же пробельные символы начнут быть зависимыми от контекста. Например, в следующем коде:
returnget; // ошибка! Но фортрано-подобный сканер ее не заметит!return(get);
В первом примере примере пробельные символы обязательно обязаны учитываться, так как иначе он как Фортране распознается правильно, а во втором не как необязательные. Ну, и как записать такую граматику?
... << RSDN@Home 1.1.4 beta 3 rev. 207>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
