Re: синтаксический анализатор
От: _Obelisk_ Россия http://www.ibm.com
Дата: 20.10.06 04:59
Оценка: +3
Здравствуйте, x-code, Вы писали:

XC>давно хочу сделать некую прогу, которая бы на входе получала например *.cpp файл, и строила в памяти синтаксическое дерево исходного кода по аналогии например с XML DOM. Все блоки — классы, функции, if'ы и т.д. — отдельные ветки.



Если хотите этим заниматься в порядке самообразования — выбирайте язык попроще (Java, Pascal, Modula-2 и т.п.). Если же вам парсер нужен для использования в реальном проекте — лучше купить готовый. Например тут
http://www.cocolab.com/en/parsers.html
Без серьезной подготовки в области теории и практики разработки компиляторов ничего путного у вас не выйдет.



Душа обязана трудиться! (с) Н.Заболоцкий.
Re[15]: синтаксический анализатор
От: Аноним  
Дата: 25.10.06 12:33
Оценка: +2 -1
WolfHound, у тебя есть несколько заблуждений в твоей теории, и именно это тебе мешает понять что же говорит Страуструп и мы с kl. Смотри как ты мыслишь.

Для тебя, неправильная С++ программа это которая явно нарушает синтаксические правила, например несбалансированные скобки или отсутствие точки с запятой. Ты понимаешь, что если начать со стартового нетерминала грамматики С++, то такую программу вывести нельзя, и посему она будет неправильной С++ программой которую компилятор соответственно откажется компилировать. Тут все ок. Далее, основываясь на этом рассуждении, ты автоматом приходишь к выводу, что если начать со стартового нетерминала грамматики С++ (ибо ты слышал что грамматика описывает синтаксис языка С++), то можно вывести бесконечное множество правильных С++ программ которые компилятор сможет скомпилировать. Выделенная часть в конце предыдущего предложения и есть твое первое заблуждение.

Далее, тебе известно что переменные в С++ должны быть объявлены до первого использования, но ты также понимаешь что КС-грамматикой такое требование выразить нельзя и автоматом делаешь заключение что для этого требуется КЗ-грамматика. Это есть твое второе заблуждение.

Идем дальше. Уверенный в том, что синтаксис языка С++ описывается КЗ-грамматикой (см. второе заблуждение) а также твердо полагая, что грамматика С++ описывает бесконечное множество правильных С++ которые скомпилирует компилятор (см. первое заблуждение), ты отказываешся принять во внимание, что требование об объявлении переменной перед использование не выражается через грамматику. Это и есть твое третье заблуждение. Оно мешает тебе взглянуть на проблему с другой стороны, и ты, таким образом, окружил себя замкнутым кругом. Как только ты приймешь, что требование об объявлении переменных перед использованием не выражается через грамматику, как аксиому, все станет легче. Посему предлагаю на минутку отбросить свою теорию (а ты уже начал понимать, что в ней что-то не так, и твой пост показывает об этом) и задуматься имеет ли смысл то, о чем я говорю ниже.

Важно понять, что язык программирования С++ != формальный язык описанный грамматикой языка С++. Язык программирования С++ это 1) лексика, 2) синтаксис и 3) семантика которую присваивает создатель языка программирования лексическим и синтаксическим конструкциям. Теперь, чтобы выяснить какие процессы происходят при компиляции на самом деле, нам нужно обратить свое внимание на четыре вида ошибок которые бывают в С++ программах.

1) Лексические ошибки. Например:
int main()
{
    return 1$5; // имелось в виду 145
}

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

2) Синтаксические ошибки. Например:
int main()
{
    return 0;
{ // неправильная скобка здесь

В этой программе нету лексических ошибок, но есть одна синтаксическая — неправильная скобка. За сообщение об этой ошибке отвечает уже синтаксический анализатор.

3) Семантические ошибки. Например:
int main()
{
    i = 15;

    return 0;
}

В этой программе нету ни лексических ошибок ни синтаксических, но есть одна семантическая — обращение к необъявленной переменной. За диагностику этого вида ошибок уже отвечает семантический анализатор. Другой пример что я привел — вызов приватной функции класса в мейне.

4) Логические ошибки. Разработчиков компиляторов они не интересуют и упоминаются здесь только для полноты картины.

Теперь, обрати внимание что сообщения об ошибках и останвка генерации кода могут происходить на разных стадиях компиляции (пункты 1 — 3). То есть последущая стадия может заявить что исходный текст неправильный хотя предыдущии стадии могут сказать что никаких ошибок замечено не было. Тоже самое и происходит с грамматикой синтаксиса языка С++. Все синтаксически верные тексты будут допущенны до семантического анализатора, и только семантический анализатор уже скажет, что да, это есть правильная С++ программа. Часть же синтаксически верных текстов будет откинута семантическим анализатором за неимением смысла. Его слово является последним. Перечитай это несколько раз.

Требование чтобы переменная была объявлена до использования не выражается грамматикой языка как ты думаешь, и цель моих примеров выше было показать ошибочность твоего первого заблуждения. Вместо этого, грамматика языка порождает бесконечное множество исходных текстов, часть из которых будет содержать объявление переменной, а часть нет (я говорю о третьем пункте выше, как пример). Все это множество будет синтаксически правильным, и только то бесконечное подмножество, которое будет содержать объявление переменной будет еще и семнатически верным и будет скомпилированно компилятором. Такое множество и называется правильными С++ программами, и об этом и говорит Страуструп. Другое множество будет отвергнуто с семантической ошибкой что-то вроде "переменная не объявлена." В роли же "генератора" правильных программ С++ выступает сам программист когда пишет код.

WH>

In particular, the grammar described here accepts a superset of valid C++ constructs.

WH>Те это не грамматика языка, а грамматика надмножества языка.
Об этом мы тебе и говорим. Грамматика синтаксиса С++ порождает бесконечное множество синтаксически правильных С++ текстов, и только часть из этих текстов будет иметь семантику и соответственно являться правильными С++ программами.

WH>Правда дальше он говорит какуюто фигню

Никакая это не фигня. Прийми за аксиому что грамматика С++ генерирует два бесконечных множества: одно из них будет правильными С++ программами, другое — нет.
WH>

Moreover, access control, ambiguity, and type rules must be used to weed out syntactically valid but meaningless constructs.

WH>Ибо это все часть синтаксиса.
Как только поймешь что язык программирования это лексика, синтаксис и семантика которую "накладывают" на лексические и синтаксические конструкции, все станет легче.

WH>Короче какой-то редиска устроил серьезную путаницу.

Да не, нормальный дядька! Защитил PhD диссертацию связанную с компиляторами и создал промышленный язык программирования.

kl>>Далее остается проверить, что данный синтаксически корректный текст, является корректной С++-программой. Это и делается семантическим анализатором.

Обрати внимание, kl тебе говорит то же самое что и мои примеры с возможными ошибками при компиляции.
WH>Корректная С++ программа это синтаксически корректная программа.
Вот это неправильно! Тебе нужно понять, что грамматика С++ генерирует два бесконечных множества синтаксически верных текстов, и только одно из этих множеств будет правильными С++ программами. Об этом и Страуструп тебе говорит, но только не так явно.

kl>>>>Здесь нет никакого недоразумения. Есть совершенно четкое понимаение, что такое семантика.

WH>>>Правда? Дай определение.
Представь, что ты не знаешь С++ и смотришь на синтаксис for цикла. Откуда ты узнаешь что вначале исполняется инициализация, потом проверка условиня а в конце апдейт? Или что проверка условия проверяется вначале а не в конце как у do while? Тебе нужен какой-то другой источник, который и объяснит значение (семантику) этой синтаксической конструкции. Семантика так просто не поддается формализации как синтаксис и лексика.

kl>>Смотрите выше, про разграничение синтаксиса и семантики. Это не определение, это именно понимание.

WH>Выше его нету.
Семантику надо именно понимать а не сковывать себя в рамках формального синтаксиса.

WH>Ну сам посуди как программа которую можно вывести из грамматики языка не является программой на этом языке?

А с чего ты решил, что текст который выводится из грамматики С++ ДОЛЖЕН БЫТЬнепременно правильной С++ программой? (см. свое первое заблуждение) Можешь не отвечать на этот вопрос, но хотелось бы чтобы ты призадумался о нем. Я на него ответил в самом начале поста.
Re[5]: синтаксический анализатор
От: Cephalopod  
Дата: 25.06.07 15:50
Оценка: +1 -1 :)
Здравствуйте, WolfHound, Вы писали:

WH>То-то до сих пор нет ниодного компилятора который может без ошибок распарсить С++...


По моему глубочайшему убеждению, C++ сам по себе — одна большая ошибка. Соответственно, и любой код на C++ изначально ошибочен.
Re[11]: синтаксический анализатор
От: Аноним  
Дата: 23.10.06 19:18
Оценка: 2 (1) +1
WH>Это ты поднял оооочень спорную тему. На RSDN об нее сломали очень много копий.
WH>Короче говоря я считаю что твоя точка зрения ошибочна.
А я считаю что твоя. Один из нас прав, другой нет. Третьего не дано.

WH>Ибо синтаксис языка задает множество допустимых текстов на этом языке.

Читай Драконову книгу чтобы понять почему программа может не скомпилироваться и что же реально задает синтаксис (описанный формальной грамматикой) языка программирования.

WH>Тк данная программа:

WH>
WH>struct s
WH>{
WH>private:
WH>    void f() const;
WH>};

WH>int main()
WH>{
WH>    s ms;
    
WH>    ms.f();
WH>}
WH>

WH>не является программой на С++ то она синтаксически не корректна.
Наоборот, эта программа синтаксически корректна но некорректна семантически и посему не является корректной С++ программой но не наоборот.

Или по-твоему компилятор каким-то чудом определяет что этот код не является С++ программой и на этом основании заключает что она "синтаксически" неверна?

Читай здесь что пишет Страуструп:

This summary of C++ syntax is intended to be an aid to comprehension. It is not an exact statement of the language. In particular, the grammar described here accepts a superset of valid C++ constructs. Disambiguation rules (§A.5, §A.7) must be applied to distinguish expressions from declarations.Moreover, access control, ambiguity, and type rules must be used to weed out syntactically valid but meaningless constructs.

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

WH>Таким образом все языки где необходимо объявлять переменную до ее использование являются контекстно зависимыми.

Ну ну. Если ты заглянешь в граматику языка, то увидишь что следущая программа выводится без проблем хотя i не объявлена.
int main()
{
    i = 0;
}

Такие требования как "переменная должна быть объявлена" или "к-во аргументов при вызове функции должно совпадать с количеством параметров, принимаемых функцией" проверяется семантическим анализатором.

WH>Но эффективные парсеры можно построить для некоторого подмножества контекстно свободных грамматик. Таким образом разработчики компиляторов идут на следующиею уловку: Они создают автоматизированными средствами типа яков и коков парсеры надмножества языка который они парсят. После чего над AST языка который является надмножеством того языка который пытаются парсить делают некоторые неформальные проверки которые по недразумению называют семантическими.

Это по чьему же недоразумению?

WH>Короче не нужно путать синтаксис те множество текстов на данном языке и семантику те то что обозначают эти тексты.

Во-во! Я об этом тебе и говорю!
Re[12]: синтаксический анализатор
От: mefrill Россия  
Дата: 24.10.06 09:21
Оценка: 2 (2)
Здравствуйте, kl, Вы писали:

WH>>Ибо синтаксис языка задает множество допустимых текстов на этом языке.

kl>Вот именно. Где под языком, в теоретическом смысле этого слова, понимается не язык программирования и не язык общения, а просто набор строк из конечного алфавита, не более.

Так что это меняет? Рассматривая Си++ как набор текстов программ, мы просто смотрим на этот язык немного с другой точки зрения. Это — типичный процесс рассуждений, когда об одном и том же понятии мы говорим разными языками. Си++ может рассматриваться и как набор корректных текстов-программ, и как некая концептуальная реальность — общее сознание программисткого сообщества, и как конкретно выраженное мироощущения отдельного человека, напрмиер Страуструпа или тебя. Кто скажет, что из этих рассмотрений правильно, а что нет? На самом деле, это спор о вкусах и методах. Мы здесь рассматриваем язык именно как набор текстов не потому, что нам так захотелось, но потому что мы вынужаемы к такому рассмотрению целью и инструментами. Цель состоит в том, чтобы научить машину понимать тексты языка Си++, а инструмент — алгоритм. Значит, мы просто вынуждены рассматривать формальные языки, а именно языки текстов, а не смыслов. Потому что, смысл — непонятно что, а текст — это конкретно и лишено мистики и может быть обработано машиной. Последнее и есть самое главное — нам необходимо что такой язык мог обрабатываться машиной. Для этого и вводится базовое разделение на синтаксис и семантику. Это не более чем технический прием, необходимый в данном случае для того, чтобы иметь возможность передать работу машине. Итак, формальный Си++ — это набор текстов корректных программ. Способ определения этих текстов называется грамматикой. Грамматика — это возможность конечным образом описать всевозможные корректные программы, составленные на языке Си++. Грамматика Си++, описанная в стандарте языка, на самом деле конечно не описывает все корректные тексты, точнее описывает не только их, а еще многие другие. Грамматика из стандарта — это просто удобный способ описать язык Си++ человеку, а не машине. Все это имеет только совсем отдаленное отношение к теории породающих грамматик Хомского. Если говорить конкретно об этой теории, то удобный способ оценить сложнотсь языка — это выделить классы грамматик, которые этот язык могут описывать. Эти классы удивительным образом совпадают с ограничениями на вид правил. Почему совпадают — это отдельная проблема на стыке философии, лингвистики и теории алгоритмов. Умные люди нашли, что множество текстов языка Си++ невозможно определить грамматикой типа 2, но возможно описать грамматикой типа 1. Но строить синтаксические анализаторы на основе грамматики типа 1 очень трудно для человека. Поэтому, разработчики синтаксических анализаторов придумали специальный технический прием: некоторую часть текстов они описывают порождающей грамматикой Хомского, причем для простоты понимания синтаксической структуры языка Си++ человеком эта грамматика достаточно проста, т.е. выбирается так, чтобы иметь тип 2. Затем, уже доопределяют грамматику "вручную", т.е. без использования теории порождающих грамматик Хомского. Эту часть доопредлеения называют семантикой языка, хотя конечно этот теормин в свете его употребления в теории моделей, не совсем верный и ведет к путанице. В теории моделей разделяет множество текстов — синтаксис языка или теория, и различные модели этой тоерии, т.е. интерпретации языка. Семантикой и называется множество интерпретаций этой самой теории. Например, выражение 1+2=3 может трактоваться и как сложение натуральных чисел и как, например, некая философская пифагорейская истина, в которой знаки 1, 2 и 3 означают некие мировые категории, а знаки + и = — некие отношения между этими категориями. Для языков программирвоания семантикой естественно считать то, как программа на этом языке должна выполняться на машине. Т.е. написано выражение 1+2=3, мы считаем, что семантически правильным будет исполнение некоторого вычислительного процесса, представляющего собой сложение двух чисел и получение третьего (все это, если конечно абстрагироваться от некооретности этого выражения для конкретного языка Си++). Описать семантику — тоже дело нелегкое, а на самом деле значительно более сложное, нежели описание синтаксиса. В стандарте Си++ для этого вводится специальная абстрактная модель вычислительного процесса — стековая машина. На этой стековой машине и интерпретируются тексты программ на Си++. Реализация в других вычислительных моделях, например Фон Нейммановских машинах, уже проектируется на основе абстракции стековой машины. Ты можешь спросить: ну и причем здесь "семантика" языка Си++, которая используется при разработке синтаксических анализаоторов? Совершенно верно, совершенно не причем, потому как, собственно, с семнтике Си++ эта "семантика" не имеет никакого отношения. Подчеркиваю еще раз, цель нашего рассмотрения языка Си++ — это обсуждение того, как программы этого языка представляют вычислительные процессы, т.е. попросту говоря, как программы этого языка выполняются машииной. Поэтому мы говорим о формальных языках. Мы могли бы рассмативать язык Си++ ч других точек зрения, например, как значимое социальное явление, или как особого рода психологическую реальность, "более интресную" нежели Ява или Си Шарп или еще каким угодно образом. Но мы должны придерживаться цели. Цель разработчика компилятора язфка Си++ в конечном итоге совпадет с целью программиста-ползователя этого языка: программы Си++ должны исполняться (интерпретирвоаться) на машинах. Из этого все остальное следует вполне естественных образом.
Re[3]: синтаксический анализатор
От: Vintik_69 Швейцария  
Дата: 18.10.06 21:22
Оценка: +2
Здравствуйте, Аноним, Вы писали:

А>не совсем изобретательство велосипедов, скорее самообразование совмещенное с интересным экспериментом (если получится, и самое главное — если будет время на разработку )

Просто самообразование идет не в ту сторону. Надо как раз изучать теорию формальных языков и то, как строятся синтаксические анализаторы. Писать руками сам анализатор — абсолютно бессмысленно.
Re[13]: синтаксический анализатор
От: kl Германия http://stardog.com
Дата: 24.10.06 13:49
Оценка: +2
Здравствуйте, mefrill, Вы писали:

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


kl>>Вот именно. Где под языком, в теоретическом смысле этого слова, понимается не язык программирования и не язык общения, а просто набор строк из конечного алфавита, не более.


M>Так что это меняет? Рассматривая Си++ как набор текстов программ, мы просто смотрим на этот язык немного с другой точки зрения. Это — типичный процесс рассуждений, когда об одном и том же понятии мы говорим разными языками... [unstructured thoughts skipped]


Ну да, разве я сказал что-то, что противоречит Вашим словам? Все правильно, только тяжело читать, когда законченные мысли не выделены в абзацы...
no fate but what we make
Re[18]: синтаксический анализатор
От: WolfHound  
Дата: 25.10.06 16:40
Оценка: -1 :)
Здравствуйте, <Аноним>, Вы писали:

А>Ну, что я могу сказать? Умный человек меня понял. Ты — нет.

Это ты так на бан по IP нарываешься?
А>Так и будешь пальцы гнуть при слове метапрограммирование (с которым не так уж и сложно разобраться), а глубины реально происходящих процессов никогда не поймешь.
Причем тут вобще матапрограммирование?

А>А также редиски Страуструпа который "правда дальше говорит какую-то фигню."

Вобщето я говорил не о Страуструпе, а о том кто ляпнул этот бред до него.

WH>> Ибо по определению множество всех текстов языка порождается грамматикой этого языка.

А>Это только справедливо для формальных языков. Не знаю с чего ты решил что это также справедливо для языков программирования.
Это справедливо для всех языков.

А>Так КЗ или нет? Мефрилл вон считает что в КЗ можно загнать однозначно. Определитесь уж там.

А он может это доказать?

WH>>Рассуждения поскипаны ибо рассуждения построеные на неверных посылках не имеют смысла.

А>Либо поскипаны из-за чьегото непонимания происходящих процессов.
А может это ты не понимаешь?

WH>>Например когда я пишу компиляторы я вобще не пользуюсь формальными грамматиками ибо пользоваться pattern-matching'ом гораздо удобней чем всякими коками и яками.

А>И как pattern-matching, помогает тебе с рекурсивной вложенностью?
Ты с функциональными языками вобще знаком?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[10]: синтаксический анализатор
От: WolfHound  
Дата: 23.10.06 16:50
Оценка: 3 (1)
Здравствуйте, <Аноним>, Вы писали:

А>Слово "контекст" в контекстно-свободных и контекстно-зависимых грамматиках не является тем контекстом о котором ты говоришь. Слово "контекст" в контекстно-зависимых грамматиках означает синтаксический контекст, и "область" где могут использоваться такие-то продукция/продукции определяется окружающими лексемами. В КС-грамматике такого контекста нет, и потому они (КС-грамматики) так и называются.


А>Ты же говоришь о семантическом контексте (которого, кстати, нет в теории формальных языков). Основываясь на полученной информации ранее, компилятор выбирает нужную продукцию из нескольких продукций которые могли бы породить указанное тобой предложение. Это все так, и я понимаю это.


А>А вот ты понимаешь разницу в контекстах о которых идет речь? Осознав эту разницу, ты поймешь почему грамматика синтаксиса С++ — КС.


Это ты поднял оооочень спорную тему. На RSDN об нее сломали очень много копий.
Короче говоря я считаю что твоя точка зрения ошибочна.
Ибо синтаксис языка задает множество допустимых текстов на этом языке.
Тк данная программа:
struct s
{
private:
    void f() const;
};

int main()
{
    s ms;
    
    ms.f();
}

не является программой на С++ то она синтаксически не корректна.

Семантика же означает то что скрывается за теми или иными конструкциями языка. Те на уровне синтаксиса языка не известно что значит ++i; извесно лишь то что данная конструкция может встречатся в определенных контекстах. Но на уровне семантики известно что за этой конструкцией скрывается увеличение переменной i на единицу.

Таким образом все языки где необходимо объявлять переменную до ее использование являются контекстно зависимыми.

Однако контекстно зависимые прасеры черизвычайно медленные. Болие того построить полную контекстно зависимую грамматику современного языка программирования также задачка не для слабонервных. Тем болие если в языке есть что-то типа вывода тапов.
Но эффективные парсеры можно построить для некоторого подмножества контекстно свободных грамматик. Таким образом разработчики компиляторов идут на следующиею уловку: Они создают автоматизированными средствами типа яков и коков парсеры надмножества языка который они парсят. После чего над AST языка который является надмножеством того языка который пытаются парсить делают некоторые неформальные проверки которые по недразумению называют семантическими.

Короче не нужно путать синтаксис те множество текстов на данном языке и семантику те то что обозначают эти тексты.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[14]: синтаксический анализатор
От: WolfHound  
Дата: 24.10.06 15:04
Оценка: 1 (1)
Здравствуйте, kl, Вы писали:

kl>Безусловно не любой, а только соответствующий грамматике. Насчет той строки, что Вы привели: позвольте, мы говорим о некой конкретной грамматике приведенной в документации или о любой, что может быть использована для построения компилятора С++? Если о той грамматике, что контекстно-свободна (из Стандарта), то Ваша строка не является корректной (скобки не отматчены, main нет, etc).

Ну во первых Страуструп сам говорит

In particular, the grammar described here accepts a superset of valid C++ constructs.

Те это не грамматика языка, а грамматика надмножества языка.Правда дальше он говорит какуюто фигню

Moreover, access control, ambiguity, and type rules must be used to weed out syntactically valid but meaningless constructs.

Ибо это все часть синтаксиса.
Короче какой-то редиска устроил серьезную путаницу.

kl>>>Нет, это не так. Рассуждая подобным образом, мы в итоге придем к тому, что программа семантически некорректна если выполняет не то, что хотел программист.

WH>>А ведь это именно так.
kl>Ну да, тогда всю область про верификацию ПО тоже стоит отнести к разработке компиляторов? По-моему, это все же разные вещт
Не понял логики.

kl>В чем же недетерминированность? Все очень четко — синтаксис заканчивается сразу как только определено, что текст программы может быть сгенерирован грамматикой С++.

Пока правильно.
kl>Далее остается проверить, что данный синтаксически корректный текст, является корректной С++-программой. Это и делается семантическим анализатором.
Корректная С++ программа это синтаксически корректная программа.

kl>Нет, не совсем так. Как только Вы вносите в грамматику конструкции недопустимые с точки зрения формальной теории, понятие "синтаксической корректности" исчезает. И его нет до тех пор, пока не будет формализовано, что означает Ваша звездочка (хотя, интуитивно понятно, разумеется).

kl>Кстати, а что мешает написать нормальную грамматику типа:
От вопроса не уходи.

kl>>>Здесь нет никакого недоразумения. Есть совершенно четкое понимаение, что такое семантика.

WH>>Правда? Дай определение.
kl>Смотрите выше, про разграничение синтаксиса и семантики. Это не определение, это именно понимание.
Выше его нету.

kl>Ну да, у нас исключительно терминологический спор. На самом деле, я понимаю, что Вы говорите и это безусловно имеет смысл на практике. Например, Вы бы проверки на unreachable code или деление на ноль считали бы семантическими, так? Ну я с этим не спорю, просто использую другую терминологию, которая (имхо!) лучше стыкуется с теорией формальных языков.

А по моему твоя терминология к теории формальных языков вобще не имеет отношения.
Ну сам посуди как программа которую можно вывести из грамматики языка не является программой на этом языке?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[3]: синтаксический анализатор
От: konsoletyper Россия https://github.com/konsoletyper
Дата: 20.10.06 17:41
Оценка: +1
Здравствуйте, x-code, Вы писали:

XC>интересно, а чем в смысле анализа Java или Pascal проще C++? только тем что в С++ по очередной лексеме и текущему контексту часто сразу не определить какой узел AST строить? или есть еще какие-то особенности?


Особенность как раз в контексте. Для Java или Pascal конекстом является только магазин. Для C++ нужна ещё и кое-какая семантическая инфа.

_O_>>Без серьезной подготовки в области теории и практики разработки компиляторов ничего путного у вас не выйдет.


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


Пока будете "доводить до нужного уровня" запутаетесь. Лучше вначале хорошенько изучить теорию, а затем сразу написать на нужном уровне. Для изучения интересной темы можно было бы распарсить более простой язык, причём не обязательно существующий — можно придумать свой (без новых концепций, такой, который легко распарсить).
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[3]: синтаксический анализатор
От: WolfHound  
Дата: 20.10.06 17:49
Оценка: +1
Здравствуйте, x-code, Вы писали:

XC>интересно, а чем в смысле анализа Java или Pascal проще C++? только тем что в С++ по очередной лексеме и текущему контексту часто сразу не определить какой узел AST строить? или есть еще какие-то особенности?

Ой там их столько что С++ вобще крайне хреново спроектирован.
XC>кстати, просьба к уважаемым форумчанам: приведите пожалуйста наиболее сложные элементы грамматики С++.
Ну например что это такое:
a<b>c;

Не зная что такое a, b и c сказать невозможно.

XC>да, начну с упрощенного варианта С++, а затем постепенно расширяя доведу до нужного уровня.

С С++ так не прокатит. Тут либо нужно проектировать компилятор так чтобы распарсить все его весьма и весьма многочисленные заморочки либо довести его до скольнибудь приемлемого уровня не получится никогда.
XC>это не коммерческий проект, для коммерческого я бы скачал бы что нибудь готовое и бесплатное это просто изучение интересной для меня темы.
Из бесплатного можно разве что g++ скачать.
Все остальное совсем мусор.
XC>Мне нужен полный доступ и полное понимание исходного кода анализатора. Это обязательно, т.к. мне нужны свои структуры данных для AST и особый набор функций и методов анализа, который автоматическими средствами скорее всего не предоставляется.
1) Возьми какойнибудь язык по проще типа паскаля. Ну или любой другой Виртовский язык. Вирт свои языки специально проектирует так чтобы парсить было просто.
2) Для реализации возьми мощьный язык. На данный момент я считаю что nemerle наиболие сбалансирован. Гемороя будет значительно меньше чем с С++ или жабой. Болие того раз уж ты занимаешься обучением то изучить язык отличающийся от С++ и C# тоже не повредит. Это позволит тебе смотреть на проблемы шире чем ты можешь делать зная только C++ или там какойнибудь C#.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[4]: синтаксический анализатор
От: cvetkov  
Дата: 23.10.06 10:35
Оценка: :)
Здравствуйте, <Аноним>, Вы писали:

C>>неполучиться. сиплюсплюсная граматика даже не контекстно независимая.

А>Позвольте, а какая она?
контекстно зависимая.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[9]: синтаксический анализатор
От: Аноним  
Дата: 23.10.06 16:14
Оценка: +1
А>>Все продукции в грамматике С++ содержат в левой части только один нетерминал что делает ее контекстно-свободной граматикой.
C>делало бы, если бы выбор между двумя продукциями производился вне зависимости от контекста.
Слово "контекст" в контекстно-свободных и контекстно-зависимых грамматиках не является тем контекстом о котором ты говоришь. Слово "контекст" в контекстно-зависимых грамматиках означает синтаксический контекст, и "область" где могут использоваться такие-то продукция/продукции определяется окружающими лексемами. В КС-грамматике такого контекста нет, и потому они (КС-грамматики) так и называются.

Ты же говоришь о семантическом контексте (которого, кстати, нет в теории формальных языков). Основываясь на полученной информации ранее, компилятор выбирает нужную продукцию из нескольких продукций которые могли бы породить указанное тобой предложение. Это все так, и я понимаю это.

А вот ты понимаешь разницу в контекстах о которых идет речь? Осознав эту разницу, ты поймешь почему грамматика синтаксиса С++ — КС.

C>суть в том что грамматика в той форме о которой ты говориш не описывает полностью синтаксис языка.

Я тебе скажу более. Грамматика использующаяся для описания синтаксиса С++ — которая является КС-грамматикой — описывает надмножество над синтаксисом языка С++ .
К примеру грамматика С++ позволяет вывести такую синтаксически правильную программу:
struct s
{
private:
       void f() const;
};

int main()
{
       s ms;

       ms.f();
}

Подумай почему так.

C>что, собственно, и демонстрирует мой пример.

Твой пример основан на неправильных предпосылках.
Re[5]: синтаксический анализатор
От: WolfHound  
Дата: 23.10.06 16:22
Оценка: :)
Здравствуйте, <Аноним>, Вы писали:

WH>>Ой там их столько что С++ вобще крайне хреново спроектирован.

А>Я бы поостерегся говорить что С++ "крайне хреново спроектирован."
А что ты можешь оспорить это утверждение?
А>В него напихали кучу фич со временем что и усложняет компиляцию.
Куча фич... ой не смешите мои тапочки... любой язык с метапрограммирование уделает все фичи С++ не напрягаясь. Это я тебе говорю как спец по "метапрограммированию" на С++.

А>Что-то я не вижу тут никакой сложности. Зная что есть a, b и c можно сказать два ли это сравнения или инстанциация шаблона и объявление переменной. Или ты собрался компилировать данный код не имея никакой информации об a, b и c?

Я нет. Я вобще не собираюсь С++ компилировать. Просто данный пример показывает насколько в С++ все запущено.

А>Вообще говоря, сложности которые возникают при разработке компиляторов С++ не связаны с синтаксическим разбором а более с семантическим анализом. К примеру, какую из кучи перегруженных функций программист намеревался вызвать? Позволю себе привести цитату отсюда:

Почти все тоже самое относится к nemerle. Плюс в немерле есть вывод типов.
Например у меня есть функция на 170 строк с кучей вложенных функций и на все эти 170 строк нет ни одного уточнения типа. При этом типизация полностью статическая.
А С++ так не может... тем не мение его компилятор гораздо сложнее...

А>IMHO эта цитата лучше говорит о том, с какими трудностями приходится бороться разработчикам компиляторов С++. А вообще, чтобы представить реальные трудности надо попытаться написать компилятор С++ самому, , или почитать научные статьи и диссертации.

Мда... диссертации по написанию компилятора С++... это ли не поддтверждение того что этот язык хреново спроектирован.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
синтаксический анализатор
От: x-code  
Дата: 18.10.06 17:06
Оценка:
давно хочу сделать некую прогу, которая бы на входе получала например *.cpp файл, и строила в памяти синтаксическое дерево исходного кода по аналогии например с XML DOM. Все блоки — классы, функции, if'ы и т.д. — отдельные ветки.
интересно написать это самому, без вспомогательных средств типа yacc, теории языков и грамматик и т.п. Чтобы было предельно просто, понятно и прозрачно, и в то же время универсально и гибко. И еще — как бонус — чтобы на основе этого дерева можно было бы реализовать простую кодогенерацию.
в общем, даже понятно что делать: лексический анализ я в свое время сделал за вечер, работает идеально. а дальше просто времени не было, только мысли... некий набор методов типа parseCppFile, parseNamespace, parseStruct... которые вызывают друг друга и строят соответствующее дерево. Наверняка потребуется вспомогательный стек для разрешения неоднозначных ситуаций, которых в C++ предостаточно. Можно скачать грамматику языка, перегнать ее в прогу и сделать все это автоматически, но сначала хочется все же вручную.
Собственно, проблема в том что задача довольно большая и сразу всего не охватить — мысли растекаются а хочется, поскольку если эту штуку реализовать то можно сделать много интересного. Поэтому вопрос: существуют ли реализации таких парсеров — не студенческие примитивные программы, но и не профессиональные компиляторы с оптимизацией, а нечто среднее, сделанное именно вручную и желательно на C/C++ (можно C#). Просто чтобы можно было посмотреть код и выявить идеи, возможные тонкости и т.д.
Re: синтаксический анализатор
От: Аноним  
Дата: 18.10.06 17:20
Оценка:
CodeDOM .NET не пойдет?
Re: синтаксический анализатор
От: DaBro  
Дата: 18.10.06 17:59
Оценка:
Здравствуйте, x-code, Вы писали:

XC>давно хочу сделать некую прогу, которая бы на входе получала например *.cpp файл, и строила в памяти синтаксическое дерево исходного кода

XC>интересно написать это самому, без вспомогательных средств типа yacc, теории языков и грамматик и т.п.

А зачем велосипед то изобретать? Не проще ли построить грамматику для C++ или найти где-нибудь готовое описание и рекурсивным спуском или еще как нить это сделать (если не получится к LL(1) грамматике привести).


XC>Собственно, проблема в том что задача довольно большая и сразу всего не охватить — мысли растекаются а хочется, поскольку если эту штуку реализовать то можно сделать много интересного.


Задачи синтаксического(построение дерева — контроль грамматики) и семантического анализа(разрешение неоднозначностей в коде) обычно разделяют. Последний производят над готовым деревом.

Ну а в конце оптимизации и генерация кода.

Так что начать стоит с синтаксического анализатора.
Очень толковая книга на эту тему — классика жанра http://masterpc.alfaspace.net/books/CCScience/AhoSetiUlman_Kompilyators-www.masterpc.alfaspace.net.djvu

Удачи с этим.
Re: синтаксический анализатор
От: konsoletyper Россия https://github.com/konsoletyper
Дата: 18.10.06 19:07
Оценка:
Здравствуйте, x-code, Вы писали:

XC>интересно написать это самому, без вспомогательных средств типа yacc, теории языков и грамматик и т.п. Чтобы было предельно просто, понятно и прозрачно, и в то же время универсально и гибко. И еще — как бонус — чтобы на основе этого дерева можно было бы реализовать простую кодогенерацию.

XC>в общем, даже понятно что делать: лексический анализ я в свое время сделал за вечер, работает идеально. а дальше просто времени не было, только мысли... некий набор методов типа parseCppFile, parseNamespace, parseStruct... которые вызывают друг друга и строят соответствующее дерево. Наверняка потребуется вспомогательный стек для разрешения неоднозначных ситуаций, которых в C++ предостаточно. Можно скачать грамматику языка, перегнать ее в прогу и сделать все это автоматически, но сначала хочется все же вручную.

Лексический анализ пишется гораздо быстрее, чем синтаксический. С синтаксическим анализом есть ряд сложностей. Во-первых, если писать рекурсивный спуск, то надо чётко представлять, что он неоптимален, а главное — позволяет парсить лишь некоторое подмножество контекстно-зависимых грамматик. Обычно, yacc не справляется с той же проблемой в общем случае, но охватывает более широкий класс грамматик, нежели рекурсивный спуск.

В общем, если так уж хочется (например, в самообразовательных целях) заняться изобретением велосипедов, то лучше сделать свой yacc. А ещё можно написать свой генератор анализаторов правых грамматик. Кстати, вопрос к all: а почему лексический анализ пишется ручками? Не проще взять тот же flex и скормить ему регулярные выражения, чем писать код, потенциально содержащий ошибки?

PS: У меня есть интеграция Немерле вместе с компилятором (недели две назад обновлял). Там зачем-то два лексера: один для компилятора, другой для подсветки. Причём второй глючит. Так зачем оно?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[2]: синтаксический анализатор
От: Аноним  
Дата: 18.10.06 20:34
Оценка:
Здравствуйте, konsoletyper, Вы писали:

K>Лексический анализ пишется гораздо быстрее, чем синтаксический. С синтаксическим анализом есть ряд сложностей. Во-первых, если писать рекурсивный спуск, то надо чётко представлять, что он неоптимален, а главное — позволяет парсить лишь некоторое подмножество контекстно-зависимых грамматик. Обычно, yacc не справляется с той же проблемой в общем случае, но охватывает более широкий класс грамматик, нежели рекурсивный спуск.


К сожалению, теоретическую часть в области написания компиляторов знаю поверхностно. Но сейчас мне не нужен собственный компилятор. Меня интересует другое, а именно возможность создания некоторого аналога CodeDOM. Даже выражения разбирать не нужно, вполне достаточно ограничиться уровнем блоков кода и объявлением переменных. Интуитивно все выглядит достаточно просто, но объем того, что нужно сделать _одновременно_ слишком большой... как минимум — переменные, функции, типы и объявление переменных. Т.е. чтобы разобрать void main(){}
например, в С/С++ уже здесь заложен косяк: прототип функции и объявление объекта почтие идентичны,
TYPE name(); // прототип функции
TYPE name; // переменная
хотя если бы не кривизна языка (никогда бы не подумал если бы не задумался над задачей анализа!) то первый вариант вполне логично мог бы быть объявлением переменной name типа TYPE с конструктором без параметров. ясно что рекурсивным спуском это тоже можно решить, но хотелось бы пооптимальнее... поэтому и спрашивал исходники. Думаю, что скорее пригодились бы исходники программ типа Visual Assist чем комиляторов.

K>В общем, если так уж хочется (например, в самообразовательных целях) заняться изобретением велосипедов, то лучше сделать свой yacc.

не совсем изобретательство велосипедов, скорее самообразование совмещенное с интересным экспериментом (если получится, и самое главное — если будет время на разработку )

K>PS: У меня есть интеграция Немерле вместе с компилятором (недели две назад обновлял). Там зачем-то два лексера: один для компилятора, другой для подсветки. Причём второй глючит. Так зачем оно?

P.S. А когда выложат на сайт полную версию статьи о макросах в Немерле? Крайне любопытно, особенно с учетом того что тут на форуме все восхищаются этим языком...
Re[2]: синтаксический анализатор
От: kl Германия http://stardog.com
Дата: 19.10.06 17:44
Оценка:
Здравствуйте, konsoletyper, Вы писали:

K> Кстати, вопрос к all: а почему лексический анализ пишется ручками? Не проще взять тот же flex и скормить ему регулярные выражения, чем писать код, потенциально содержащий ошибки?


А разве сканеры пишутся вручную?
no fate but what we make
Re[2]: синтаксический анализатор
От: cvetkov  
Дата: 19.10.06 18:01
Оценка:
Здравствуйте, DaBro, Вы писали:

DB>Здравствуйте, x-code, Вы писали:


XC>>давно хочу сделать некую прогу, которая бы на входе получала например *.cpp файл, и строила в памяти синтаксическое дерево исходного кода

XC>>интересно написать это самому, без вспомогательных средств типа yacc, теории языков и грамматик и т.п.

DB>А зачем велосипед то изобретать? Не проще ли построить грамматику для C++ или найти где-нибудь готовое описание и рекурсивным спуском или еще как нить это сделать (если не получится к LL(1) грамматике привести).

неполучиться. сиплюсплюсная граматика даже не контекстно независимая.

XC>>Собственно, проблема в том что задача довольно большая и сразу всего не охватить — мысли растекаются а хочется, поскольку если эту штуку реализовать то можно сделать много интересного.


DB>Задачи синтаксического(построение дерева — контроль грамматики) и семантического анализа(разрешение неоднозначностей в коде) обычно разделяют. Последний производят над готовым деревом.

для сиплюсплюса, опятьже, это не верно. там разрешать ссылки выгодней во время парсинга.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[3]: синтаксический анализатор
От: konsoletyper Россия https://github.com/konsoletyper
Дата: 19.10.06 21:06
Оценка:
Здравствуйте, kl, Вы писали:

K>> Кстати, вопрос к all: а почему лексический анализ пишется ручками? Не проще взять тот же flex и скормить ему регулярные выражения, чем писать код, потенциально содержащий ошибки?


kl>А разве сканеры пишутся вручную?


Я видел вручную написанный сканер для: Немерле, gcc, IronPython, Mono. Других исхожников у меня не было. А вот в имеющихся сканеры написаны вручную. Может, в остальных случаях они и генерируются, но лично я таких случаев не наблюдал.

Кстати, почему это для генерации сканера задаются регулярные выражения? Обычно в мануалах по языкам используется БНФ. Так вот я что подумал: а не проще ли написать тулзу, которая занимается удалением хвостовой рекурсии в БНФ, тогда правая грамматика обратится в цикл и получится код, эквивалентный тому, что сгенерирован по регулярным выражениеям?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[3]: синтаксический анализатор
От: konsoletyper Россия https://github.com/konsoletyper
Дата: 19.10.06 21:06
Оценка:
Здравствуйте, <Аноним>, Вы писали:

А>К сожалению, теоретическую часть в области написания компиляторов знаю поверхностно. Но сейчас мне не нужен собственный компилятор. Меня интересует другое, а именно возможность создания некоторого аналога CodeDOM. Даже выражения разбирать не нужно, вполне достаточно ограничиться уровнем блоков кода и объявлением переменных. Интуитивно все выглядит достаточно просто, но объем того, что нужно сделать _одновременно_ слишком большой... как минимум — переменные, функции, типы и объявление переменных.


А написание парсера — штука гораздо более тривиальная, чем написание полноценного компилятора. Парсер — это только часть компилятора, которая производит синтаксический анализ кода. Оптимизация и кодогенерация — вот где много подводных камней. А теория анализаторов очень хорошо исследована, так что если хорошенько изучить формальную теорию, то ТАКИХ труднойстей, как с написанием, скажем, оптимизатора, возникнуть не должно.

K>>В общем, если так уж хочется (например, в самообразовательных целях) заняться изобретением велосипедов, то лучше сделать свой yacc.

А>не совсем изобретательство велосипедов, скорее самообразование совмещенное с интересным экспериментом (если получится, и самое главное — если будет время на разработку )

Так я и пишу о том, что единственный смысл изобретать велосипеды — самообразование.

K>>PS: У меня есть интеграция Немерле вместе с компилятором (недели две назад обновлял). Там зачем-то два лексера: один для компилятора, другой для подсветки. Причём второй глючит. Так зачем оно?

А>P.S. А когда выложат на сайт полную версию статьи о макросах в Немерле? Крайне любопытно, особенно с учетом того что тут на форуме все восхищаются этим языком...

А слабо сходить на сайт Немерле и скачать руководство по макросам? Или просто скачать последнюю стабильную версию компилятора, к которому прилагается документация, в т.ч. и по макросам? И вообще, нужно уяснить, что сила Немерле не в макросах. Макросы — штука хоть и мощная, но сложная и опасная. Не стоит их использовать всюду, где возможно. Для широкого круга задач они вообще не нужны или даже вредны.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[4]: синтаксический анализатор
От: kl Германия http://stardog.com
Дата: 19.10.06 22:57
Оценка:
Здравствуйте, konsoletyper, Вы писали:


K>Кстати, почему это для генерации сканера задаются регулярные выражения? Обычно в мануалах по языкам используется БНФ. Так вот я что подумал: а не проще ли написать тулзу, которая занимается удалением хвостовой рекурсии в БНФ, тогда правая грамматика обратится в цикл и получится код, эквивалентный тому, что сгенерирован по регулярным выражениеям?


Потому что классический сканер — это DFA. Для любого регулярного выражения его можно построить (см. Thompson construction)
Если же у тебя задана грамматика, то она скорее всего нерегулярная и DFA по ней не построить даже если убрать рекурсию, факторизовать и т.д. Поэтому требуя в качестве input регэксп, генератор явно дает понять, что он может, а что не может.
no fate but what we make
Re[3]: синтаксический анализатор
От: DaBro  
Дата: 20.10.06 07:11
Оценка:
Здравствуйте, cvetkov, Вы писали:

Не буду спорить — компиляторы для таких навароченных языков создавать не приходилось.
Re[5]: синтаксический анализатор
От: konsoletyper Россия https://github.com/konsoletyper
Дата: 20.10.06 07:32
Оценка:
Здравствуйте, kl, Вы писали:

K>>Кстати, почему это для генерации сканера задаются регулярные выражения? Обычно в мануалах по языкам используется БНФ. Так вот я что подумал: а не проще ли написать тулзу, которая занимается удалением хвостовой рекурсии в БНФ, тогда правая грамматика обратится в цикл и получится код, эквивалентный тому, что сгенерирован по регулярным выражениеям?


kl>Потому что классический сканер — это DFA. Для любого регулярного выражения его можно построить (см. Thompson construction)

kl>Если же у тебя задана грамматика, то она скорее всего нерегулярная и DFA по ней не построить даже если убрать рекурсию, факторизовать и т.д. Поэтому требуя в качестве input регэксп, генератор явно дает понять, что он может, а что не может.

Дело в том, что в мунуалах и стандартах как правило и нет разделения на синтаксис и лексику — всё описывается в БНФ, правда, обычно указывается, что "здесь лексика, а там — синтаксис". Если есть такой мануал, то входной файл для синтаксического анализатора можно построить прямо скопировав нужные части стандарта, чуть подправив ручками и дописав нужный код — это позволяет минимизировать количество ошибок в парсере. Однако, для лексики такой трюк не работает: нужно поломать голову и самостоятельно составить регулярные выражения; при этом могут возникнуть ошибки. Так вот, есть ли аналоги flex, котрые принимают БНФ (точнее, что-то вроде того, что в yacc), проверяют её на "правость", и если она праволинейная, то удаляет рекурсию и строит ЛА, иначе ругается? Или даже проще — если БФН описывает праволинейную грамматику, то составляет регулярные выражения, которые можно скормить flex'у. Я что-то не видел подобных вещей.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[4]: синтаксический анализатор
От: WolfHound  
Дата: 20.10.06 12:00
Оценка:
Здравствуйте, Vintik_69, Вы писали:

V_>Просто самообразование идет не в ту сторону. Надо как раз изучать теорию формальных языков и то, как строятся синтаксические анализаторы. Писать руками сам анализатор — абсолютно бессмысленно.

Угу... раскажи это разработчиками nemerle...
А потом попробуй заставить какойнибудь генератор парсеров разобрать nemerle...
Короче все эти генераторы парсеров нужны исключительно для языков без pattern-matching'а и алгебраических типов.
Короче смотри на этот
Автор: WolfHound
Дата: 18.10.06
код и думай насколько нужны все эти яки и прочие коки если есть нормальные языки?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[4]: синтаксический анализатор
От: WolfHound  
Дата: 20.10.06 12:00
Оценка:
Здравствуйте, konsoletyper, Вы писали:

K>А написание парсера — штука гораздо более тривиальная, чем написание полноценного компилятора. Парсер — это только часть компилятора, которая производит синтаксический анализ кода. Оптимизация и кодогенерация — вот где много подводных камней. А теория анализаторов очень хорошо исследована, так что если хорошенько изучить формальную теорию, то ТАКИХ труднойстей, как с написанием, скажем, оптимизатора, возникнуть не должно.

То-то до сих пор нет ниодного компилятора который может без ошибок распарсить С++...
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[6]: синтаксический анализатор
От: kl Германия http://stardog.com
Дата: 20.10.06 14:12
Оценка:
Здравствуйте, konsoletyper, Вы писали:

K>Дело в том, что в мунуалах и стандартах как правило и нет разделения на синтаксис и лексику — всё описывается в БНФ, правда, обычно указывается, что "здесь лексика, а там — синтаксис". Если есть такой мануал, то входной файл для синтаксического анализатора можно построить прямо скопировав нужные части стандарта, чуть подправив ручками и дописав нужный код — это позволяет минимизировать количество ошибок в парсере. Однако, для лексики такой трюк не работает: нужно поломать голову и самостоятельно составить регулярные выражения; при этом могут возникнуть ошибки. Так вот, есть ли аналоги flex, котрые принимают БНФ (точнее, что-то вроде того, что в yacc), проверяют её на "правость", и если она праволинейная, то удаляет рекурсию и строит ЛА, иначе ругается? Или даже проще — если БФН описывает праволинейную грамматику, то составляет регулярные выражения, которые можно скормить flex'у. Я что-то не видел подобных вещей.


Ну все правильно, потому что БНФ не будет ни право ни леволинейной, это ж синтаксис языка, как он может быть регулярным?
Плюс, знаешь как вообще строятся регэкспы по грамматике? Грамматику и автомат легко построить по регэкспу, автомат элементарно построить по регулярной грамматике и обратно, а вот регэксп по грамматике — неудобно (часто строят через т.н. generalized DFA). Т.е. алгоритм как бы есть, но регэксп получается неудобоваримый. Поэтому это никто и не делает.
Гораздо проще из спеки выдрать список всех ключевых слов, добавить типы токенов для объявления функций, комментарией, переменных, т.д. и слепить руками регэксп

PS. Интересно, а для чего удалять рекурсию перед построением DFA?
no fate but what we make
Re[2]: синтаксический анализатор
От: x-code  
Дата: 20.10.06 14:28
Оценка:
Здравствуйте, _Obelisk_, Вы писали:

_O_>Если хотите этим заниматься в порядке самообразования — выбирайте язык попроще (Java, Pascal, Modula-2 и т.п.). Если же вам парсер нужен для использования в реальном проекте — лучше купить готовый. Например тут

_O_>http://www.cocolab.com/en/parsers.html

интересно, а чем в смысле анализа Java или Pascal проще C++? только тем что в С++ по очередной лексеме и текущему контексту часто сразу не определить какой узел AST строить? или есть еще какие-то особенности?
кстати, просьба к уважаемым форумчанам: приведите пожалуйста наиболее сложные элементы грамматики С++.

_O_>Без серьезной подготовки в области теории и практики разработки компиляторов ничего путного у вас не выйдет.


да, начну с упрощенного варианта С++, а затем постепенно расширяя доведу до нужного уровня. это не коммерческий проект, для коммерческого я бы скачал бы что нибудь готовое и бесплатное это просто изучение интересной для меня темы.
Мне нужен полный доступ и полное понимание исходного кода анализатора. Это обязательно, т.к. мне нужны свои структуры данных для AST и особый набор функций и методов анализа, который автоматическими средствами скорее всего не предоставляется.
Re[5]: синтаксический анализатор
От: konsoletyper Россия https://github.com/konsoletyper
Дата: 20.10.06 16:33
Оценка:
Здравствуйте, WolfHound, Вы писали:

K>>А написание парсера — штука гораздо более тривиальная, чем написание полноценного компилятора. Парсер — это только часть компилятора, которая производит синтаксический анализ кода. Оптимизация и кодогенерация — вот где много подводных камней. А теория анализаторов очень хорошо исследована, так что если хорошенько изучить формальную теорию, то ТАКИХ труднойстей, как с написанием, скажем, оптимизатора, возникнуть не должно.

WH>То-то до сих пор нет ниодного компилятора который может без ошибок распарсить С++...

Согласен. Только всё, что я пишу, относится, скорее, к Java или Python. Совершенно справедливо здесь уже заметили, что лучше начинать не с парсера C++.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[7]: синтаксический анализатор
От: konsoletyper Россия https://github.com/konsoletyper
Дата: 20.10.06 17:41
Оценка:
Здравствуйте, kl, Вы писали:

K>>Дело в том, что в мунуалах и стандартах как правило и нет разделения на синтаксис и лексику — всё описывается в БНФ, правда, обычно указывается, что "здесь лексика, а там — синтаксис". Если есть такой мануал, то входной файл для синтаксического анализатора можно построить прямо скопировав нужные части стандарта, чуть подправив ручками и дописав нужный код — это позволяет минимизировать количество ошибок в парсере. Однако, для лексики такой трюк не работает: нужно поломать голову и самостоятельно составить регулярные выражения; при этом могут возникнуть ошибки. Так вот, есть ли аналоги flex, котрые принимают БНФ (точнее, что-то вроде того, что в yacc), проверяют её на "правость", и если она праволинейная, то удаляет рекурсию и строит ЛА, иначе ругается? Или даже проще — если БФН описывает праволинейную грамматику, то составляет регулярные выражения, которые можно скормить flex'у. Я что-то не видел подобных вещей.


kl>Ну все правильно, потому что БНФ не будет ни право ни леволинейной, это ж синтаксис языка, как он может быть регулярным?


Так ведь разговор о той части языка которая регулярная, т.е. о лексике.

kl>Гораздо проще из спеки выдрать список всех ключевых слов, добавить типы токенов для объявления функций, комментарией, переменных, т.д. и слепить руками регэксп


В спеках как правило приводятся БНФ и для лексики. А регэкспы не приводятся. Почему бы не сделать генератор регэкспов по БНФ для того случая, когда БНФ описывает регулярную грамматику?

kl>PS. Интересно, а для чего удалять рекурсию перед построением DFA?


Генераторы синтаксических анализаторов могут удалять хвостовую рекурсию. Так почему бы, если кроме хвостовой, никакой рекурсии нет, строить не КА с магазинной памятью, а ДКА?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[8]: синтаксический анализатор
От: kl Германия http://stardog.com
Дата: 20.10.06 18:15
Оценка:
Здравствуйте, konsoletyper, Вы писали:

K>В спеках как правило приводятся БНФ и для лексики. А регэкспы не приводятся. Почему бы не сделать генератор регэкспов по БНФ для того случая, когда БНФ описывает регулярную грамматику?


Не знал, что такие приводятся. Я думал, грамматика одна и только для синтаксиса. Ну для регулярных грамматик — да, можно написать конвертилку в регэкспы.

kl>>PS. Интересно, а для чего удалять рекурсию перед построением DFA?


K>Генераторы синтаксических анализаторов могут удалять хвостовую рекурсию. Так почему бы, если кроме хвостовой, никакой рекурсии нет, строить не КА с магазинной памятью, а ДКА?


ДКА = DFA. Я и говорю, зачем если у нас регулярная грамматика, удалять рекурсию? Для контекстно-независимых языков это понятно, иначе не получается top-down parsing, а для DFA-то зачем?
Что плохого в такой леворекурсивной леволинейной грамматике с точки зрения сканера?
A -> Aa | b
no fate but what we make
Re[9]: синтаксический анализатор
От: konsoletyper Россия https://github.com/konsoletyper
Дата: 20.10.06 19:31
Оценка:
Здравствуйте, kl, Вы писали:

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


K>>В спеках как правило приводятся БНФ и для лексики. А регэкспы не приводятся. Почему бы не сделать генератор регэкспов по БНФ для того случая, когда БНФ описывает регулярную грамматику?


kl>Не знал, что такие приводятся. Я думал, грамматика одна и только для синтаксиса. Ну для регулярных грамматик — да, можно написать конвертилку в регэкспы.


Да хотя бы тот же Java Language Specification. Или стандарт ECMA C#. И там и там Lexical Structure описывается в БНФ.

kl>ДКА = DFA. Я и говорю, зачем если у нас регулярная грамматика, удалять рекурсию? Для контекстно-независимых языков это понятно, иначе не получается top-down parsing, а для DFA-то зачем?


Так если при удалении хвостовой рекурсии окажется, что никакой рекурсии не осталось, то это и означает, что у нас регулярная грамматика.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[3]: синтаксический анализатор
От: Аноним  
Дата: 23.10.06 03:39
Оценка:
C>неполучиться. сиплюсплюсная граматика даже не контекстно независимая.
Позвольте, а какая она?
Re[5]: синтаксический анализатор
От: Аноним  
Дата: 23.10.06 04:14
Оценка:
K>>А написание парсера — штука гораздо более тривиальная, чем написание полноценного компилятора. Парсер — это только часть компилятора, которая производит синтаксический анализ кода. Оптимизация и кодогенерация — вот где много подводных камней. А теория анализаторов очень хорошо исследована, так что если хорошенько изучить формальную теорию, то ТАКИХ труднойстей, как с написанием, скажем, оптимизатора, возникнуть не должно.
WH>То-то до сих пор нет ниодного компилятора который может без ошибок распарсить С++...
Теория синтаксического анализа в самом деле хорошо исследована, и все исследования сейчас направлены на оптимизацию кода. Грамматика С++ сложна, но это, имхо, не является причиной отсутсвия компиляторов которые могут распарсить весь С++ без ошибок. Тут дело больше в управлении проектами. Нужно ли большим корпорациям типа Майкрософта чтобы компилятор мог распознавать мало используемые конструкции языка? Плюс еще не стоит забывать обычный человеческий фактор. К примеру, кучи легаси кода который не всегда возможно [легко] исправить, что-то не так спроектированно с самого начала, приближающиеся дедлайны, дополнительная административная работа, имейлы, митинги, личные проблемы а не только написание кода.
Re[5]: синтаксический анализатор
От: Аноним  
Дата: 23.10.06 11:29
Оценка:
C>контекстно зависимая.
С чего ты это решил?
Re[6]: синтаксический анализатор
От: cvetkov  
Дата: 23.10.06 12:06
Оценка:
Здравствуйте, <Аноним>, Вы писали:

C>>контекстно зависимая.

А>С чего ты это решил?
как парситься
a b((c)d);

зависит от того какие символы были обьявлены ранее;
это может быть и декларацией метода идекларацией переменной.
это только один пример. их, на самом деле, больше.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[7]: синтаксический анализатор
От: Аноним  
Дата: 23.10.06 15:09
Оценка:
C>как парситься
C>
C>a b((c)d);
C>

C>зависит от того какие символы были обьявлены ранее;
C>это может быть и декларацией метода идекларацией переменной.
C>это только один пример. их, на самом деле, больше.
И на основе этого примера ты решил что граматика C++ контекстно-зависимая?

Все продукции в грамматике С++ содержат в левой части только один нетерминал что делает ее контекстно-свободной граматикой.
Re[8]: синтаксический анализатор
От: cvetkov  
Дата: 23.10.06 15:25
Оценка:
Здравствуйте, <Аноним>, Вы писали:

C>>как парситься

C>>
C>>a b((c)d);
C>>

C>>зависит от того какие символы были обьявлены ранее;
C>>это может быть и декларацией метода идекларацией переменной.
C>>это только один пример. их, на самом деле, больше.
А>И на основе этого примера ты решил что граматика C++ контекстно-зависимая?

А>Все продукции в грамматике С++ содержат в левой части только один нетерминал что делает ее контекстно-свободной граматикой.


делало бы, если бы выбор между двумя продукциями производился вне зависимости от контекста.
суть в том что грамматика в той форме о которой ты говориш не описывает полностью синтаксис языка.
что, собственно, и демонстрирует мой пример.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[4]: синтаксический анализатор
От: Аноним  
Дата: 23.10.06 15:41
Оценка:
XC>>интересно, а чем в смысле анализа Java или Pascal проще C++? только тем что в С++ по очередной лексеме и текущему контексту часто сразу не определить какой узел AST строить? или есть еще какие-то особенности?
WH>Ой там их столько что С++ вобще крайне хреново спроектирован.
Я бы поостерегся говорить что С++ "крайне хреново спроектирован." В него напихали кучу фич со временем что и усложняет компиляцию.

XC>>кстати, просьба к уважаемым форумчанам: приведите пожалуйста наиболее сложные элементы грамматики С++.

WH>Ну например что это такое:
WH>
WH>a<b>c;
WH>

WH>Не зная что такое a, b и c сказать невозможно.
Что-то я не вижу тут никакой сложности. Зная что есть a, b и c можно сказать два ли это сравнения или инстанциация шаблона и объявление переменной. Или ты собрался компилировать данный код не имея никакой информации об a, b и c?

Вообще говоря, сложности которые возникают при разработке компиляторов С++ не связаны с синтаксическим разбором а более с семантическим анализом. К примеру, какую из кучи перегруженных функций программист намеревался вызвать? Позволю себе привести цитату отсюда:

Parsing the syntax of C++ is the easy part of the problem. Once you have an abstract syntax tree, you need to do semantic analysis to figure out which functions are being called and which variables are being referenced at each point in your program. A call to "foo" somewhere in the application could refer to a top-level function called "foo", or a method within the current class, or one of its (possibly multiple) base classes. There could be several overloaded versions of "foo" with different argument types, possibly with some default parameters, in each of these places. There may be some other "foo"'s available which take arguments which are subtypes of the supplied arguments. And on top of that, C++ allows implicit coercion between types, so the types of the arguments could get totally changed. Your semantic analysis stage has to codify all of these rules, in the right order.

IMHO эта цитата лучше говорит о том, с какими трудностями приходится бороться разработчикам компиляторов С++. А вообще, чтобы представить реальные трудности надо попытаться написать компилятор С++ самому, , или почитать научные статьи и диссертации.
Re[10]: синтаксический анализатор
От: cvetkov  
Дата: 23.10.06 16:52
Оценка:
Здравствуйте, <Аноним>, Вы писали:

А>>>Все продукции в грамматике С++ содержат в левой части только один нетерминал что делает ее контекстно-свободной граматикой.

C>>делало бы, если бы выбор между двумя продукциями производился вне зависимости от контекста.
А>Слово "контекст" в контекстно-свободных и контекстно-зависимых грамматиках не является тем контекстом о котором ты говоришь. Слово "контекст" в контекстно-зависимых грамматиках означает синтаксический контекст, и "область" где могут использоваться такие-то продукция/продукции определяется окружающими лексемами. В КС-грамматике такого контекста нет, и потому они (КС-грамматики) так и называются.
да я это знаю.

А>Ты же говоришь о семантическом контексте (которого, кстати, нет в теории формальных языков). Основываясь на полученной информации ранее, компилятор выбирает нужную продукцию из нескольких продукций которые могли бы породить указанное тобой предложение. Это все так, и я понимаю это.

если этого контекста нет в теории то как можно что-либо выбирать основываясь на нем?

А>А вот ты понимаешь разницу в контекстах о которых идет речь? Осознав эту разницу, ты поймешь почему грамматика синтаксиса С++ — КС.

если
C>>суть в том что грамматика в той форме о которой ты говориш не описывает полностью синтаксис языка.
А>Я тебе скажу более. Грамматика использующаяся для описания синтаксиса С++ — которая является КС-грамматикой — описывает надмножество над синтаксисом языка С++ .
притом граматика эта неоднозначная.
чтобы сделать ее однозначной ее придеться переписать в контекстно зависимом виде.
на практике этого не делают, а используют нестандартные алгоритмы парсинга учитывающие контекст.
построит синтаксическое дерево не учитывая контекст для с++ невозможно.

А>К примеру грамматика С++ позволяет вывести такую синтаксически правильную программу:

А>
А>struct s
А>{
А>private:
А>       void f() const;
А>};

А>int main()
А>{
А>       s ms;

А>       ms.f();
А>}
А>

А>Подумай почему так.
про семантику мы сейчас вообще не говорим.
C>>что, собственно, и демонстрирует мой пример.
А>Твой пример основан на неправильных предпосылках.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[6]: синтаксический анализатор
От: Аноним  
Дата: 23.10.06 17:20
Оценка:
WH>>>Ой там их столько что С++ вобще крайне хреново спроектирован.
А>>Я бы поостерегся говорить что С++ "крайне хреново спроектирован."
WH>А что ты можешь оспорить это утверждение?
А ты можешь обосновать свое утверждение? Пока что я увидел одну голословность.

А>>В него напихали кучу фич со временем что и усложняет компиляцию.

WH>Куча фич... ой не смешите мои тапочки... любой язык с метапрограммирование уделает все фичи С++ не напрягаясь. Это я тебе говорю как спец по "метапрограммированию" на С++.
С++ развивается с 1983 года а ты мне говоришь о каких-то новых языках которые учли накопленный опыт предшественников.

А>>Что-то я не вижу тут никакой сложности. Зная что есть a, b и c можно сказать два ли это сравнения или инстанциация шаблона и объявление переменной. Или ты собрался компилировать данный код не имея никакой информации об a, b и c?

WH>Я нет. Я вобще не собираюсь С++ компилировать.
Имелось в виду мысленное представление как решить задачу а не садиться и писать код. И ты это понял.

WH>Просто данный пример показывает насколько в С++ все запущено.

Что-то я не увидел что запущено. ИМО это не реальная сложность.

А>>Вообще говоря, сложности которые возникают при разработке компиляторов С++ не связаны с синтаксическим разбором а более с семантическим анализом. К примеру, какую из кучи перегруженных функций программист намеревался вызвать? Позволю себе привести цитату отсюда:

WH>Почти все тоже самое относится к nemerle. Плюс в немерле есть вывод типов.
При чем тут Немерле? Разговор как-то сворачивается в другую плоскость.

WH>Например у меня есть функция на 170 строк с кучей вложенных функций и на все эти 170 строк нет ни одного уточнения типа. При этом типизация полностью статическая.

Буду признателен если покажешь эти 170 строк. Только чем так вложенные функции хороши? Попахивает Паскалем.

WH>А С++ так не может... тем не мение его компилятор гораздо сложнее...

Ну что я могу сказать? gcc написан на си, немерле на намерле... А вот на чем они написали самую первую версию компилятора и много ли было функциональности в этой версии? Взял бы да написал научную статью сравнивающую реализацию gcc и Немерле.

Кстати, Немерле пока что не промышленный язык программирования...

А>>IMHO эта цитата лучше говорит о том, с какими трудностями приходится бороться разработчикам компиляторов С++. А вообще, чтобы представить реальные трудности надо попытаться написать компилятор С++ самому, , или почитать научные статьи и диссертации.

WH>Мда... диссертации по написанию компилятора С++... это ли не поддтверждение того что этот язык хреново спроектирован.
Чего-чего? По-твоему что ли все, о чем пишут диссертацию представляет х...? Кстати, Немерле начал разрабатываться в учебных целях, и эти парни пишут о нем свои научные работы. Тоже будешь утверждать что это свидетельство того, что Немерле хреново спроектирован?
Re[7]: синтаксический анализатор
От: WolfHound  
Дата: 23.10.06 18:33
Оценка:
Здравствуйте, <Аноним>, Вы писали:

А>А ты можешь обосновать свое утверждение? Пока что я увидел одну голословность.

Ну например где модули? Ы? Что мешало ввести в язык модули и оставить препроцессор исключительно для совместимости? Это позволило бы избехать огромного колличества проблем.

А>С++ развивается с 1983 года а ты мне говоришь о каких-то новых языках которые учли накопленный опыт предшественников.

Напомни мне когда лисп появился?...

А>Буду признателен если покажешь эти 170 строк.

Указания типов есть только в сигнатуре функции таковы правила немерле. Внутри все выводится из типов используемых и создаваемых объектов.
    public static GetTokens(text : string) : list[Token]
    {
        mutable pos = 0;
        mutable line = 1;
        mutable linePos = 1;
        mutable deep = 0;

        def end() { pos >= text.Length }

        def curPos() { Pos(pos, line, linePos) }

        def substr(start) { text.Substring(start.Pos, curPos().Pos - start.Pos) }

        def isAlpha(c)    { ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z') }
        def isNum(c)      { ('0' <= c && c <= '9') }
        def isAlphaNum(c) { isAlpha(c) || isNum(c) }
        def isSpace(c)
        {
        | ' ' | '\t' | '\n' | '\r' => true
        | _ => false
        }

        def ch() { text[pos] }
        def nextCh()
        {
            def pos1 = pos + 1;
            if (pos1 >= text.Length)
                '\0'
            else
                text[pos1]
        }
        
        def checkEnd()
        {
            when (end())
                throw CompileError(line, linePos, $"Unexpected end of file.");
        }

        def check(c)
        {
            checkEnd();
            when (ch() != c)
                throw CompileError(line, linePos, $"$c expected.");
        }

        def unexpected(pos, c)
        {
            CompileError(pos.Line, pos.LinePos, $"Unexpected symbol: '$c'");
        }

        def move1()
        {
            when (ch() == '\n')
            {
                ++line;
                linePos = 0;
            }
            ++pos;
            ++linePos;
        }

        def move(n)
        {
            for (mutable i = 0; !end() && i < n; ++i)
                move1();
        }

        def moveWhile(fn)
        {
            while (!end() && fn(ch()))
                move1();
        }

        def skipSpace()
        {
            moveWhile(isSpace);
        }

        def parseIdentifier()
        {
            def start = curPos();
            moveWhile(isAlphaNum);
            def end = curPos();
            def name = substr(start);
            skipSpace();
            if (ch() == '.')
            {    
                def start = curPos();
                move(1);
                skipSpace();
                if (isAlpha(ch()))
                {
                    def (names, end) = parseIdentifier();
                    (name :: names, end);
                }
                else
                    throw unexpected(start, '.');
            }
            else
                ([name], end);
        }

        def parse()
        {
            skipSpace();
            if (end())
            {
                [];
            }
            else 
            {    
                def start = curPos();
                match (ch())
                {
                | c when isAlpha(c) => 
                    def (name, end) = parseIdentifier();
                    Token.Identifier(start, end, name) :: parse();
        
                | '{' => parseBrace() :: parse()
                | '}' when deep > 0 => []
        
                | '(' => parseRound() :: parse()  
                | ')' when deep > 0 => []
        
                | ':' => move(1); Token.Colon     (start, curPos()) :: parse();
                | ';' => move(1); Token.Semicolon (start, curPos()) :: parse();
                | ',' => move(1); Token.Comma     (start, curPos()) :: parse();
        
                | '!' | '?' | '*' | '+' | '|'
                      => move(1); Token.Operator(start, curPos(), substr(start)) :: parse();

                | '-' when nextCh() == '>'
                      => move(2); Token.Operator(start, curPos(), substr(start)) :: parse();

                | _   => throw unexpected(start, ch());
                } 
            }
        }
        and parseBracket(close)
        {
            def start = curPos();
            move(1);
            ++deep;
            def tokens = parse();
            --deep;
            check(close);
            move(1);
            (start, tokens)
        }
        and parseBrace()
        {
            def (start, tokens) = parseBracket('}');
            Token.Brace(start, curPos(), tokens)
        }
        and parseRound()
        {
            def (start, tokens) = parseBracket(')');
            Token.Round(start, curPos(), tokens)
        }
        parse();
    }

Вот такой вот рукопашный лексер со сворачиванием по скобкам и первичной проверкой ошибок.
Дальше результат работы поступает в парсер
Автор: WolfHound
Дата: 18.10.06
там уточнения типов есть но их не много.
А>Только чем так вложенные функции хороши?
Это очень трудно оценить пока не попробуешь.
А>Попахивает Паскалем.
Нет. Паскаль нервно курит в углу.

А>Ну что я могу сказать? gcc написан на си, немерле на намерле... А вот на чем они написали самую первую версию компилятора и много ли было функциональности в этой версии? Взял бы да написал научную статью сравнивающую реализацию gcc и Немерле.

Вот мне делать больше нечего чем научные статьи строчить.

А>Чего-чего? По-твоему что ли все, о чем пишут диссертацию представляет х...? Кстати, Немерле начал разрабатываться в учебных целях, и эти парни пишут о нем свои научные работы. Тоже будешь утверждать что это свидетельство того, что Немерле хреново спроектирован?

В немерле ребята изобрели весьма изощеренный алгоритм вывода типов вот по нему и писали... А в С++ нет ничего нового. Те вобще ничего.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[8]: синтаксический анализатор
От: Аноним  
Дата: 23.10.06 19:24
Оценка:
10х за код Немерле! Посмотрю как-нибудь на этот язык.
Re[2]: синтаксический анализатор
От: IT Россия linq2db.com
Дата: 23.10.06 19:44
Оценка:
Здравствуйте, konsoletyper, Вы писали:

K>PS: У меня есть интеграция Немерле вместе с компилятором (недели две назад обновлял). Там зачем-то два лексера: один для компилятора, другой для подсветки. Причём второй глючит. Так зачем оно?


Эта проблема уже устранена.
Если нам не помогут, то мы тоже никого не пощадим.
Re[11]: синтаксический анализатор
От: kl Германия http://stardog.com
Дата: 24.10.06 01:34
Оценка:
Здравствуйте, WolfHound, Вы писали:

А>>Слово "контекст" в контекстно-свободных и контекстно-зависимых грамматиках не является тем контекстом о котором ты говоришь. Слово "контекст" в контекстно-зависимых грамматиках означает синтаксический контекст, и "область" где могут использоваться такие-то продукция/продукции определяется окружающими лексемами. В КС-грамматике такого контекста нет, и потому они (КС-грамматики) так и называются.


А>>А вот ты понимаешь разницу в контекстах о которых идет речь? Осознав эту разницу, ты поймешь почему грамматика синтаксиса С++ — КС.


WH>Это ты поднял оооочень спорную тему. На RSDN об нее сломали очень много копий.

WH>Короче говоря я считаю что твоя точка зрения ошибочна.

По-моему, анонимный коллега в данном случае совершенно прав.

WH>Ибо синтаксис языка задает множество допустимых текстов на этом языке.


Вот именно. Где под языком, в теоретическом смысле этого слова, понимается не язык программирования и не язык общения, а просто набор строк из конечного алфавита, не более.

WH>Тк данная программа:

WH>
WH>struct s
WH>{
WH>private:
WH>    void f() const;
WH>};

WH>int main()
WH>{
WH>    s ms;
    
WH>    ms.f();
WH>}
WH>

WH>не является программой на С++ то она синтаксически не корректна.

Нет, это не так. Рассуждая подобным образом, мы в итоге придем к тому, что программа семантически некорректна если выполняет не то, что хотел программист. Что разумеется абсурд (по крайней мере, в терминологии разработчиков трансляторов). Если я неправ, то приведите, пожалуйста, пример _семантически_ некорректной программы и мы обсудим, насколько эта некорректность похожа на вышеприведенную.

WH>Семантика же означает то что скрывается за теми или иными конструкциями языка. Те на уровне синтаксиса языка не известно что значит ++i; извесно лишь то что данная конструкция может встречатся в определенных контекстах. Но на уровне семантики известно что за этой конструкцией скрывается увеличение переменной i на единицу.


WH>Таким образом все языки где необходимо объявлять переменную до ее использование являются контекстно зависимыми.


Нет, это не так. Они были бы контекстно-зависимыми только если бы это условие было явно внесено в грамматику языка. Тогда — да. А пока оно не внесено, то _язык_ — это только то, что генерируется данной конкретной грамматикой. И он в данном случае — контекстно-свободен. Строго говоря, все что явно не отражено в грамматике, не является частью формального языка (в данном случае — С++)

WH>Однако контекстно зависимые прасеры черизвычайно медленные. Болие того построить полную контекстно зависимую грамматику современного языка программирования также задачка не для слабонервных. Тем болие если в языке есть что-то типа вывода тапов.


Угу, если быть точным, то конекстно-зависимый парсинг — PSPACE-задачка. А насчет грамматики, то это как минимум потребует _явного_ указания всех возможных используемых идентификаторов, что в условиях длинных имен переменных нереализуемо. Можно построить attributive grammar, но похоже это Кнутовское детище благополучно почило в бозе.

WH>Но эффективные парсеры можно построить для некоторого подмножества контекстно свободных грамматик. Таким образом разработчики компиляторов идут на следующиею уловку: Они создают автоматизированными средствами типа яков и коков парсеры надмножества языка который они парсят. После чего над AST языка который является надмножеством того языка который пытаются парсить делают некоторые неформальные проверки которые по недразумению называют семантическими.


Здесь нет никакого недоразумения. Есть совершенно четкое понимаение, что такое семантика. В данном случае, объявление приватной функции — это семантика слова private. И проверяется, как Вы и сказали, семантическим анализатором, который обрабатывает AST (кстати, не обязательно AST — любую intermediate representation, например, 3-address code или stack machine code тоже таковыми являются)

WH>Короче не нужно путать синтаксис те множество текстов на данном языке и семантику те то что обозначают эти тексты.


Да. Но самое главное, не путать C++ как _формальный_ язык, что есть не более чем, язык генерируемый его грамматикой, и C++ как множество конструкций, задаваемых Стандартом. Первый — контекстно-свободный, а второй просто не является формальным, соответственно говорить о его месте в иерархии Хомского, просто не имеет смысла.
no fate but what we make
Re[12]: синтаксический анализатор
От: WolfHound  
Дата: 24.10.06 07:29
Оценка:
Здравствуйте, kl, Вы писали:

WH>>Ибо синтаксис языка задает множество допустимых текстов на этом языке.

kl>Вот именно. Где под языком, в теоретическом смысле этого слова, понимается не язык программирования и не язык общения, а просто набор строк из конечного алфавита, не более.
Заметь не любой набор ибо тогда такая последовательность {(}}((())asd(fDSgS)gdsg+0- ++ +{{ тоже попадет под корректную С++ программу.

kl>Нет, это не так. Рассуждая подобным образом, мы в итоге придем к тому, что программа семантически некорректна если выполняет не то, что хотел программист.

А ведь это именно так.
kl>Что разумеется абсурд (по крайней мере, в терминологии разработчиков трансляторов). Если я неправ, то приведите, пожалуйста, пример _семантически_ некорректной программы и мы обсудим, насколько эта некорректность похожа на вышеприведенную.
Проблема данной терминологии в ее абсолютной недетерминированности. По этой терминологии невозможно сказать где заканчивается синтаксис и начинается семантика.
Взять тотже C#. Там есть объявление свойств. Так вот в этом объявлении можно объявить только один геттер и только один сеттер. Соответственно я могу описать это формально
prop = setter | getter | (setter getter) | (getter setter);

Либо не формально
prop = *(setter | getter);

после чего проверить дополнительной проверкой которая по твоему вдруг становится семантической.
Кстати кто такие эти мифические разработчики компиляторов? Я вот тоже компиляторы пишу.

kl>Нет, это не так. Они были бы контекстно-зависимыми только если бы это условие было явно внесено в грамматику языка. Тогда — да. А пока оно не внесено, то _язык_ — это только то, что генерируется данной конкретной грамматикой. И он в данном случае — контекстно-свободен. Строго говоря, все что явно не отражено в грамматике, не является частью формального языка (в данном случае — С++)

Если следовать такой логике то можно договорится до того что грамматика С++ регулярна. А что? Я могу задать регулярную грамматику по которой мне программу нашенкуют на токены, а дальше разбирать все по неформальным правилам.

kl>Здесь нет никакого недоразумения. Есть совершенно четкое понимаение, что такое семантика.

Правда? Дай определение.
kl>В данном случае, объявление приватной функции — это семантика слова private.
Вот только есть такой прикол что слово private не влияет на исполнение программы. Оно работает исключительно на стадии компиляции не давая компилятору принять ту или иную последовательность алфавита из которого можно собрать программу на С++.
kl>И проверяется, как Вы и сказали, семантическим анализатором,
Где я такое говорил? Я говорил о том что семантический анализатор называют семантическим анализатором по недразумению. Это синтаксический анализатор просто он не формализован по причине того что разработчики компилятора не смогли или не захотели это делать.
kl>который обрабатывает AST (кстати, не обязательно AST — любую intermediate representation, например, 3-address code или stack machine code тоже таковыми являются)
Это мелочи не существенные для нашего разговора.

kl>Да. Но самое главное, не путать C++ как _формальный_ язык, что есть не более чем, язык генерируемый его грамматикой, и C++ как множество конструкций, задаваемых Стандартом. Первый — контекстно-свободный, а второй просто не является формальным, соответственно говорить о его месте в иерархии Хомского, просто не имеет смысла.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[13]: синтаксический анализатор
От: kl Германия http://stardog.com
Дата: 24.10.06 13:46
Оценка:
Здравствуйте, WolfHound, Вы писали:

kl>>Вот именно. Где под языком, в теоретическом смысле этого слова, понимается не язык программирования и не язык общения, а просто набор строк из конечного алфавита, не более.

WH>Заметь не любой набор ибо тогда такая последовательность {(}}((())asd(fDSgS)gdsg+0- ++ +{{ тоже попадет под корректную С++ программу.

Безусловно не любой, а только соответствующий грамматике. Насчет той строки, что Вы привели: позвольте, мы говорим о некой конкретной грамматике приведенной в документации или о любой, что может быть использована для построения компилятора С++? Если о той грамматике, что контекстно-свободна (из Стандарта), то Ваша строка не является корректной (скобки не отматчены, main нет, etc).

kl>>Нет, это не так. Рассуждая подобным образом, мы в итоге придем к тому, что программа семантически некорректна если выполняет не то, что хотел программист.

WH>А ведь это именно так.

Ну да, тогда всю область про верификацию ПО тоже стоит отнести к разработке компиляторов? По-моему, это все же разные вещт

kl>>Что разумеется абсурд (по крайней мере, в терминологии разработчиков трансляторов). Если я неправ, то приведите, пожалуйста, пример _семантически_ некорректной программы и мы обсудим, насколько эта некорректность похожа на вышеприведенную.

WH>Проблема данной терминологии в ее абсолютной недетерминированности. По этой терминологии невозможно сказать где заканчивается синтаксис и начинается семантика.

В чем же недетерминированность? Все очень четко — синтаксис заканчивается сразу как только определено, что текст программы может быть сгенерирован грамматикой С++. Далее остается проверить, что данный синтаксически корректный текст, является корректной С++-программой. Это и делается семантическим анализатором.

WH>Взять тотже C#. Там есть объявление свойств. Так вот в этом объявлении можно объявить только один геттер и только один сеттер. Соответственно я могу описать это формально

WH>
WH>prop = setter | getter | (setter getter) | (getter setter);
WH>

WH>Либо не формально
WH>
WH>prop = *(setter | getter);
WH>

WH>после чего проверить дополнительной проверкой которая по твоему вдруг становится семантической.

Нет, не совсем так. Как только Вы вносите в грамматику конструкции недопустимые с точки зрения формальной теории, понятие "синтаксической корректности" исчезает. И его нет до тех пор, пока не будет формализовано, что означает Ваша звездочка (хотя, интуитивно понятно, разумеется).
Кстати, а что мешает написать нормальную грамматику типа:

property -> prop_list | prop;
prop -> setter | getter | (setter getter) | (getter setter)
prop_list -> prop; prop_list | prop;

?

WH>Кстати кто такие эти мифические разработчики компиляторов? Я вот тоже компиляторы пишу.


Я неудачно выразился. Имелась в виду литература, конечно.

kl>>Нет, это не так. Они были бы контекстно-зависимыми только если бы это условие было явно внесено в грамматику языка. Тогда — да. А пока оно не внесено, то _язык_ — это только то, что генерируется данной конкретной грамматикой. И он в данном случае — контекстно-свободен. Строго говоря, все что явно не отражено в грамматике, не является частью формального языка (в данном случае — С++)

WH>Если следовать такой логике то можно договорится до того что грамматика С++ регулярна. А что? Я могу задать регулярную грамматику по которой мне программу нашенкуют на токены, а дальше разбирать все по неформальным правилам.

Опять же, смотрите возражение выше насчет конкретной грамматики С++ или некой абстрактной.

kl>>Здесь нет никакого недоразумения. Есть совершенно четкое понимаение, что такое семантика.

WH>Правда? Дай определение.

Смотрите выше, про разграничение синтаксиса и семантики. Это не определение, это именно понимание.

kl>>В данном случае, объявление приватной функции — это семантика слова private.

WH>Вот только есть такой прикол что слово private не влияет на исполнение программы. Оно работает исключительно на стадии компиляции не давая компилятору принять ту или иную последовательность алфавита из которого можно собрать программу на С++.

Безусловно, разве я с этим спорил? Я просто говорил, что не все ошибки обнаруживаемые на стадии компиляции — синтаксические. Для пользователя — да, синтаксические.

kl>>И проверяется, как Вы и сказали, семантическим анализатором,

WH>Где я такое говорил? Я говорил о том что семантический анализатор называют семантическим анализатором по недразумению. Это синтаксический анализатор просто он не формализован по причине того что разработчики компилятора не смогли или не захотели это делать.

Ну да, у нас исключительно терминологический спор. На самом деле, я понимаю, что Вы говорите и это безусловно имеет смысл на практике. Например, Вы бы проверки на unreachable code или деление на ноль считали бы семантическими, так? Ну я с этим не спорю, просто использую другую терминологию, которая (имхо!) лучше стыкуется с теорией формальных языков.
no fate but what we make
Re[15]: синтаксический анализатор
От: kl Германия http://stardog.com
Дата: 24.10.06 15:40
Оценка:
Здравствуйте, WolfHound, Вы писали:


WH>Ну во первых Страуструп сам говорит

WH>

In particular, the grammar described here accepts a superset of valid C++ constructs.

WH>Те это не грамматика языка, а грамматика надмножества языка.Правда дальше он говорит какуюто фигню
WH>

Moreover, access control, ambiguity, and type rules must be used to weed out syntactically valid but meaningless constructs.


Вот-вот-вот! Вот именно об этом я и говорю. Есть syntactically valid but meaningless constructs. Это именно синтаксически корректные тексты, которые не являются корректными С++-программами.

WH>Ибо это все часть синтаксиса.

WH>Короче какой-то редиска устроил серьезную путаницу.

Нет, все совершенно четко. Путаница происходит при присвоении понятию "синтаксическая корректность" смысла, который изначально там не заложен. В данном случае семантика ключевого слова "private" не имеет отношения к синтаксису.

kl>>>>Нет, это не так. Рассуждая подобным образом, мы в итоге придем к тому, что программа семантически некорректна если выполняет не то, что хотел программист.

WH>>>А ведь это именно так.
kl>>Ну да, тогда всю область про верификацию ПО тоже стоит отнести к разработке компиляторов? По-моему, это все же разные вещт
WH>Не понял логики.

Логика очень проста — если мы говорим, что семантика программы — это смысл заложенный программистом, то тут уж извините, но придется идти до конца и выяснять что это за смысл и насколько программа ему соответствует. Верификация ПО именно этим и занимается. Только вот к синтаксическому и семантическому анализу все это не имеет _прямого_ отношения

kl>>Далее остается проверить, что данный синтаксически корректный текст, является корректной С++-программой. Это и делается семантическим анализатором.

WH>Корректная С++ программа это синтаксически корректная программа.

В таком случае, это Ваша личная (или Вашей компании) интерпретация слова "синтаксис". Я не говорю, что она ошибочная, я говорю, что она плохо стыкуется с теорией (что, впрочем, совершенно необязательно мешает успешному применению на практике).

kl>>Нет, не совсем так. Как только Вы вносите в грамматику конструкции недопустимые с точки зрения формальной теории, понятие "синтаксической корректности" исчезает. И его нет до тех пор, пока не будет формализовано, что означает Ваша звездочка (хотя, интуитивно понятно, разумеется).

kl>>Кстати, а что мешает написать нормальную грамматику типа:
WH>От вопроса не уходи.

А в чем был вопрос? Я просто сказал, что Вы используете нестандартные конструкции при описании грамматики, пока их смысл не формализован, нечего и говорить о том, что они генерят и какой язык им соответствует.

kl>>Смотрите выше, про разграничение синтаксиса и семантики. Это не определение, это именно понимание.

WH>Выше его нету.

Ну посмотрите еще раз на приведенную Вами цитату Страуструпа. Access control, ambiguity and type rules — это именно то, что Вы считаете частью синтаксиса, а я — частью семантического анализатора.

kl>>Ну да, у нас исключительно терминологический спор. На самом деле, я понимаю, что Вы говорите и это безусловно имеет смысл на практике. Например, Вы бы проверки на unreachable code или деление на ноль считали бы семантическими, так? Ну я с этим не спорю, просто использую другую терминологию, которая (имхо!) лучше стыкуется с теорией формальных языков.

WH>А по моему твоя терминология к теории формальных языков вобще не имеет отношения.

Интересно. Она ей где-то противоречит?

WH>Ну сам посуди как программа которую можно вывести из грамматики языка не является программой на этом языке?


А что Вас смущает? Вы же сами совершенно верно сказали, что есть вещи, которые тяжело внести в грамматику. Соответственно то что она описывает — один язык. То, что описывает стандарт — другой язык. Разница между ними — это syntactically valid but meaningless constructs.
no fate but what we make
Re[14]: синтаксический анализатор
От: mefrill Россия  
Дата: 25.10.06 05:39
Оценка:
Здравствуйте, kl, Вы писали:

kl>Ну да, разве я сказал что-то, что противоречит Вашим словам? Все правильно, только тяжело читать, когда законченные мысли не выделены в абзацы...


Ну как я понял из текста, ты утверждал, что неверно рассматривать язык как просто набор текстов программ, что язык — это нечто большее. Я попытался объяснить почему это утверждение на мой взгляд не соответствует истине. Здесь все упирается в понятие "формального языка". Это понятие появилось не просто так, но ввиду вполне конкретных причин. Кроме того, я попытался объяснить почему, на мой взгляд, применение термина "семантический анализ" для характеризации процесса достройки синтаксического дерева программы некорректно и вносит путаницу. Все это уже обсуждалось на рсдн и говорилось, что принято считать (и на мой взгляд вполне разымно), что все что относится к текстам программы — это синтаксис, а все что относится к исполнению программы — это семантика. Термином "грамматика" обозначается любой способ (алгоритм) задания языка неким конечным образом. Задать язык — значит описать множество его слов, применительно к Си++ — множество его корректных программных текстов. Та КС-грамматика, о которой ты говорил, конечно может определять программные тексты Си++, которые не являются корректными. Пример был приведен. Поэтому и говорить, что КС-грамматика — это грамматика языка си++ — неверно. Вообще, фундаментальным ограничением любого КС-языка является невозможность задать никаких отношений между его сущностями, кроме иерархических. Там где необходимы перекрестные связи — это язык бессилен. Контекстная зависимость, в широком смысле, это возможность задавать связи не только сверху вниз, т.е. от родителя дерева к детям, но и горизонтальные связи между элементами разных поддеревьев. В этом смсысле, если в языке есть свойство, что каждая переменная должна быть объявлена до того, как она используется в выражении, и есть пример контекстной зависимости. Доказать это можно и формально, исходя из общего случая, моделиируя такое свойство например языком L, состоящим из тсорок вида "def a t^n (use a)^n", и непосредственно, как 1964 году это было доказано для языка Алгол-60. Но можно привести простые соображения: объявление переменной и потенциально бесконечные случаи ее использования в выражениях — это разные поддеревья программы. Для того, чтобы выразить связь между этими поддеревьями недосточно контекстно-свободной грамматики.

Пример синтаксически корректной, но семантически некорректной программы на Си++:

int main()
{
   int a = 1 + 2;
   return 0;
}


Программа будет семантически некорректной, если при ее исполнении после присваивания в переменной a будет лежать например 4, а не 3. Я понимаю, что такое определение несколько шокирует, так как уводит из текстов программ содержание и дает возможность определять корректность программ только исходя из ее текста, но тем не менее это верно. Такую трактовку текстов прилдумал (или правильнее открыл?) Давид Гильберт. Он рассматривал тексты геометрических теорем точно также, только как тексты и ничего более. И оказалось, что этого вполне досточно чтобы описать все возможные геометрические теоремы. В это сосоит суть понятия "формальный язык" и есть целое направление в математике, даже господствующее направление, называется оно формализм. Для целей синтаксического анализа этот подход вполне адекватен.

Вот "структурирую" свои мысли абзацами дабы облегчить чтение. Но мне кажется, трудность чтения здесь не из-за неструктурированности текста, а ввиду слоджности обсуждаемых здесь вопросов.
Re[16]: синтаксический анализатор
От: WolfHound  
Дата: 25.10.06 13:06
Оценка:
Здравствуйте, <Аноним>, Вы писали:

А>Для тебя, неправильная С++ программа это которая явно нарушает синтаксические правила, например несбалансированные скобки или отсутствие точки с запятой. Ты понимаешь, что если начать со стартового нетерминала грамматики С++, то такую программу вывести нельзя, и посему она будет неправильной С++ программой которую компилятор соответственно откажется компилировать. Тут все ок. Далее, основываясь на этом рассуждении, ты автоматом приходишь к выводу, что если начать со стартового нетерминала грамматики С++ (ибо ты слышал что грамматика описывает синтаксис языка С++), то можно вывести бесконечное множество правильных С++ программ которые компилятор сможет скомпилировать. Выделенная часть в конце предыдущего предложения и есть твое первое заблуждение.

Нет. Это не мое, а твое заблуждение. Ибо по определению множество всех текстов языка порождается грамматикой этого языка.
Если грамматика порождает не все возможные тексты или порождает тексты которых нет в языке то это не грамматика данного языка.

Все!
Нет никакой ложки.

А>Далее, тебе известно что переменные в С++ должны быть объявлены до первого использования, но ты также понимаешь что КС-грамматикой такое требование выразить нельзя и автоматом делаешь заключение что для этого требуется КЗ-грамматика. Это есть твое второе заблуждение.

Как минимум КЗ. Не доказано что С++ можно загнать даже в КЗ.

Рассуждения поскипаны ибо рассуждения построеные на неверных посылках не имеют смысла.

А>Представь, что ты не знаешь С++ и смотришь на синтаксис for цикла. Откуда ты узнаешь что вначале исполняется инициализация, потом проверка условиня а в конце апдейт? Или что проверка условия проверяется вначале а не в конце как у do while? Тебе нужен какой-то другой источник, который и объяснит значение (семантику) этой синтаксической конструкции. Семантика так просто не поддается формализации как синтаксис и лексика.

Единственные верные слова во всем сообщении.
Вот только синаксису не нужно знать что последовательность вида int i = 0; означает объявление переменной (это семантика данной последовательности и в какомто другом языке эта последовательность может иметь другую семантику). Также ему нужно знать в каких контекстах допустима эта последователдьность. Те синаксису важно знать что в начале for эта конструкция допустима, а в середине нет.

Да и не путай формальную теорию языков и техники построения компиляторов ибо это совершенно не одно и тоже. Например когда я пишу компиляторы я вобще не пользуюсь формальными грамматиками ибо пользоваться pattern-matching'ом гораздо удобней чем всякими коками и яками.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[16]: синтаксический анализатор
От: mefrill Россия  
Дата: 25.10.06 13:26
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Важно понять, что язык программирования С++ != формальный язык описанный грамматикой языка С++. Язык программирования С++ это 1) лексика, 2) синтаксис и 3) семантика которую присваивает создатель языка программирования лексическим и синтаксическим конструкциям. Теперь, чтобы выяснить какие процессы происходят при компиляции на самом деле, нам нужно обратить свое внимание на четыре вида ошибок которые бывают в С++ программах.


Вот это очень интересно. Почему ты постулируешь принадлежность языку Си++ эти трех перечисленных выше тобой пунктов??? Кто сказал, что "Язык программирования С++ это 1) лексика, 2) синтаксис и 3) семантика которую присваивает создатель языка программирования лексическим и синтаксическим конструкциям"??? Сами по себе понятия "лексика, синтаксис и семантика" — это только особые технические приемы, облегчающие написание машинных распознавателей для программ языка Си++, не более того. Постулировать эти технические приемы как свойства языка (а тем более определять язык через них) — это все равно, что программисту — пользователю языка, сказать что язык Си++ — это множество объявлений типов и выражений и ни что другое. Рассматривать язык Си++ во всей его полноте мы не можем — это вообще невозможно ни для какого понятия. Мы можем выделять только его некоторые свойства и рассматривать их в отдельности от всех остальных. Это называется абстракцией. Абстракция, которую описываешь ты, т.е. рассмотрение Си++ как элементов, необходимых для трехступенчатого процесса компиляции программ на Си++ — вполне законна как и любая другая. Другое дело, что термины которые здесь используются (семантика и синтаксис) имеют в тех областях знаний, откуда они пришли, иное значение. Кроме того, они противоречат математической терминологии, связанной в том числе и с рассмотрением языков программирования. Это все равно как если бы в каком-то городе словом "стул" стали обозначать стол, а словом "стол" стул. Получился бы полный ужас — то из чего известный омомним одного из вышеупомянутых слов обычно появляется на Божий свет. Терминология она на то и дана, что это результат договоренности, чтобы одни и те же слова разные люди понимали примерно одинаково. Так давайте этому следовать.
Re[15]: синтаксический анализатор
От: kl Германия http://stardog.com
Дата: 25.10.06 13:55
Оценка:
Здравствуйте, mefrill, Вы писали:

kl>>Ну да, разве я сказал что-то, что противоречит Вашим словам? Все правильно, только тяжело читать, когда законченные мысли не выделены в абзацы...


M>Ну как я понял из текста, ты утверждал, что неверно рассматривать язык как просто набор текстов программ, что язык — это нечто большее.


Нет-нет, честно не пытался :) Я просто говорил, что язык описываемый грамматикой — это одно, а Стандартом С++ — немного другое.

M>Я попытался объяснить почему это утверждение на мой взгляд не соответствует истине. Здесь все упирается в понятие "формального языка". Это понятие появилось не просто так, но ввиду вполне конкретных причин. Кроме того, я попытался объяснить почему, на мой взгляд, применение термина "семантический анализ" для характеризации процесса достройки синтаксического дерева программы некорректно и вносит путаницу. Все это уже обсуждалось на рсдн и говорилось, что принято считать (и на мой взгляд вполне разымно), что все что относится к текстам программы — это синтаксис, а все что относится к исполнению программы — это семантика.


Я совершенно не против такой формулировки если она приносит плоды на практике. Ради бога!

M>Термином "грамматика" обозначается любой способ (алгоритм) задания языка неким конечным образом. Задать язык — значит описать множество его слов, применительно к Си++ — множество его корректных программных текстов. Та КС-грамматика, о которой ты говорил, конечно может определять программные тексты Си++, которые не являются корректными. Пример был приведен. Поэтому и говорить, что КС-грамматика — это грамматика языка си++ — неверно.


Безусловно неверно. А где я такое говорил? Я вообще написал свой первый пост только когда понял, что возникла путаница из-за того, что грамматикой С++ называли грамматику, которая описывает в том числе некорректные С++-программы. Просто кто-то считает их синтаксически некорректными, а я — семантически некорректными. Но это вопрос формулировки, не более.

M>Вообще, фундаментальным ограничением любого КС-языка является невозможность задать никаких отношений между его сущностями, кроме иерархических. Там где необходимы перекрестные связи — это язык бессилен. Контекстная зависимость, в широком смысле, это возможность задавать связи не только сверху вниз, т.е. от родителя дерева к детям, но и горизонтальные связи между элементами разных поддеревьев. В этом смсысле, если в языке есть свойство, что каждая переменная должна быть объявлена до того, как она используется в выражении, и есть пример контекстной зависимости. Доказать это можно и формально, исходя из общего случая, моделиируя такое свойство например языком L, состоящим из тсорок вида "def a t^n (use a)^n", и непосредственно, как 1964 году это было доказано для языка Алгол-60. Но можно привести простые соображения: объявление переменной и потенциально бесконечные случаи ее использования в выражениях — это разные поддеревья программы. Для того, чтобы выразить связь между этими поддеревьями недосточно контекстно-свободной грамматики.


С этим глупо спорить, но что с того? Что С++ может быть описан КЗ-грамматикой? Ну разумеется. Но на практике это тоже самое, что заявить, что он может быть описан r.e. грамматикой. Ибо все равно, что машину Тьюринга, что linear bounded automaton строить для парсинга никто не будет даже если удалось бы построить грамматику.

M>Пример синтаксически корректной, но семантически некорректной программы на Си++:


M>
M>int main()
M>{
M>   int a = 1 + 2;
M>   return 0;
M>}
M>


M>Программа будет семантически некорректной, если при ее исполнении после присваивания в переменной a будет лежать например 4, а не 3. Я понимаю, что такое определение несколько шокирует, так как уводит из текстов программ содержание и дает возможность определять корректность программ только исходя из ее текста, но тем не менее это верно.


Ладно, я Вас прекрасно понял. Но я предпочитаю не называть подобные ошибки семантическими. Просто потому что отыскание всех подобных ошибок лежит далеко за пределами теории формальных языков. Очень далеко. Когда-то я занимался подобными вопросами изучая Hoare Logic и с тех пор стараюсь отделить это от проблем компилятора при обработке IR.

В общем, я наверное все сказал что хотел в этом топике :) Спасибо всем за интересную дискуссию :)
no fate but what we make
Re[13]: синтаксический анализатор
От: Аноним  
Дата: 25.10.06 14:07
Оценка:
WH>>>Ибо синтаксис языка задает множество допустимых текстов на этом языке.
kl>>Вот именно. Где под языком, в теоретическом смысле этого слова, понимается не язык программирования и не язык общения, а просто набор строк из конечного алфавита, не более.

M>Так что это меняет? Рассматривая Си++ как набор текстов программ, мы просто смотрим на этот язык немного с другой точки зрения. Это — типичный процесс рассуждений, когда об одном и том же понятии мы говорим разными языками.

Язык программирования С++ неверно рассматривать как просто набор текстов программ. Есть формальный язык заданной грамматикой С++ который является только основой С++кого синтаксиса.

M>Си++ может рассматриваться и как набор корректных текстов-программ,

Выражайтесь точнее. Корректных С++ программ?

M>и как некая концептуальная реальность — общее сознание программисткого сообщества, и как конкретно выраженное мироощущения отдельного человека, напрмиер Страуструпа или тебя.

Вода.

M>Кто скажет, что из этих рассмотрений правильно, а что нет? На самом деле, это спор о вкусах и методах.

Ну если так выражаться пространно, то точно никто не сможет сказать.

M>Мы здесь рассматриваем язык именно как набор текстов не потому, что нам так захотелось, но потому что мы вынужаемы к такому рассмотрению целью и инструментами.

Можно поподробнее о цели и инструментах?

M>Цель состоит в том, чтобы научить машину понимать тексты языка Си++, а инструмент — алгоритм.

А еще цель состоит чтобы корректно перевести правильные С++ программы в машинные коды или ассемблер.

M>Значит, мы просто вынуждены рассматривать формальные языки, а именно языки текстов, а не смыслов.

Ну если не стоит задача перевести С++ программу в машинные коды или ассемблер, то о смысле можно забыть.

M>Потому что, смысл — непонятно что,

Как ты будешь транслировать программу если для тебя непонятно что есть смысл?

M>а текст — это конкретно и лишено мистики и может быть обработано машиной.

Согласен. Но только если нам нужно определить принадлежность исходного текста к такой-то грамматике и все.

M>Последнее и есть самое главное — нам необходимо что такой язык мог обрабатываться машиной.

Что значит обрабатываться машиной? Имхо слово "обрабатываться" уж очень абстрактно.

M>Для этого и вводится базовое разделение на синтаксис и семантику.

Не совсем понял. Разделение на синтаксис и семантику вводится для того, чтобы можно было что? Только обработать текст?

Я лично всегда считал что нам нужно уметь определить семантическую корректность программы и затем правильно ее оттранслировать.

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

Опять выражаешся абстрактно. Какую работу?

M>Итак, формальный Си++ — это набор текстов корректных программ.

Предполагаю что под формальным С++ имеется в виду язык программирования С++. Вообще, нужно недюжее усилие чтобы уследить за ходом твоих мыслей.

M>Способ определения этих текстов называется грамматикой.

Полностью согласен.

M>Грамматика — это возможность конечным образом описать всевозможные корректные программы, составленные на языке Си++.

Опять согласен полностью.

M>Грамматика Си++, описанная в стандарте языка, на самом деле конечно не описывает все корректные тексты, точнее описывает не только их, а еще многие другие.

Тоже согласен.

M>Грамматика из стандарта — это просто удобный способ описать язык Си++ человеку, а не машине.

Я бы сказал и человеку и машине. И только грамматика языка С++ описывает его лексику и синтаксис.

M>Все это имеет только совсем отдаленное отношение к теории породающих грамматик Хомского.

Что это? Грамматика или что? Если грамматика, то почему совсем отдаленное отношение? Я запутался уже, да думаю не только я .

M>Если говорить конкретно об этой теории, то удобный способ оценить сложнотсь языка — это выделить классы грамматик, которые этот язык могут описывать.

Начали о грамматике и абстрактно так перешли к теории...

M>Эти классы удивительным образом совпадают с ограничениями на вид правил. Почему совпадают — это отдельная проблема на стыке философии, лингвистики и теории алгоритмов.

Вода какая-то. Вы лекции случайно не читаете?

M>Умные люди нашли, что множество текстов языка Си++ невозможно определить грамматикой типа 2,

Тут уже ближе к теме. Как я понимаю, имеется в виду невозможность все правильные и только правильные программы на языке С++ используя КС-грамматику.

M>но возможно описать грамматикой типа 1.

Если честно, не знаю что сказать на это утверждение. Возможно КЗ-грамматики и позволяют вывести С++ программы в которых переменная будет объявленна до использования, но вот как она сможет "запомнить" что эта и именно эта переменная была объявлена раньше? Меня вот это интересует.

M>Но строить синтаксические анализаторы на основе грамматики типа 1 очень трудно для человека.

Я знаю что КЗ-грамматики используются для перевода с одного естественного языка на другой...

M>Поэтому, разработчики синтаксических анализаторов придумали специальный технический прием: некоторую часть текстов они описывают порождающей грамматикой Хомского, причем для простоты понимания синтаксической структуры языка Си++ человеком эта грамматика достаточно проста, т.е. выбирается так, чтобы иметь тип 2.

Согласен со всем кроме утверждения "некоторую часть текстов." Грамматика синтаксиса С++ порождает больше синтаксически верных текстов чем правильных С++ программ как ты уже заметил где-то выше.

M>Затем, уже доопределяют грамматику "вручную", т.е. без использования теории порождающих грамматик Хомского.

Согласен.

M> Эту часть доопредлеения называют семантикой языка, хотя конечно этот теормин в свете его употребления в теории моделей, не совсем верный и ведет к путанице.


M>В теории моделей разделяет множество текстов — синтаксис языка или теория, и различные модели этой тоерии, т.е. интерпретации языка. Семантикой и называется множество интерпретаций этой самой теории. Например, выражение 1+2=3 может трактоваться и как сложение натуральных чисел и как, например, некая философская пифагорейская истина, в которой знаки 1, 2 и 3 означают некие мировые категории, а знаки + и = — некие отношения между этими категориями.

Вода.

M>Для языков программирвоания семантикой естественно считать то, как программа на этом языке должна выполняться на машине.

Согласен.

M>Т.е. написано выражение 1+2=3, мы считаем, что семантически правильным будет исполнение некоторого вычислительного процесса, представляющего собой сложение двух чисел и получение третьего (все это, если конечно абстрагироваться от некооретности этого выражения для конкретного языка Си++).

Абстрактно как-то все.

M>Описать семантику — тоже дело нелегкое, а на самом деле значительно более сложное, нежели описание синтаксиса.

Согласен.

M>В стандарте Си++ для этого вводится специальная абстрактная модель вычислительного процесса — стековая машина. На этой стековой машине и интерпретируются тексты программ на Си++. Реализация в других вычислительных моделях, например Фон Нейммановских машинах, уже проектируется на основе абстракции стековой машины.


M>Ты можешь спросить: ну и причем здесь "семантика" языка Си++, которая используется при разработке синтаксических анализаоторов? Совершенно верно, совершенно не причем, потому как, собственно, с семнтике Си++ эта "семантика" не имеет никакого отношения.

Не стоит забывать что наложение смысловой нагрузки (семантику, то есть) на лексические и синтаксическии конструкции просто необходимо для генарации кода. Если же конечная цель проверить правильная ли это в синтаксическом плане программа, то на семантику можно забить.

M>Подчеркиваю еще раз, цель нашего рассмотрения языка Си++ — это обсуждение того, как программы этого языка представляют вычислительные процессы, т.е. попросту говоря, как программы этого языка выполняются машииной.

Ну да. Чтобы программа выполнялась машиной, нужно задать семантику ее лексическими и синтаксическим конструкциям и проследить чтобы в савокупности получившийся текст имел смысл.

M>Поэтому мы говорим о формальных языках.

Близится конец рассуждения, а я так и не понял о чем оно. Абстрактно как-то да все с темы на тему.

M>Мы могли бы рассмативать язык Си++ ч других точек зрения, например, как значимое социальное явление, или как особого рода психологическую реальность, "более интресную" нежели Ява или Си Шарп или еще каким угодно образом.

Опять вода.

M>Но мы должны придерживаться цели. Цель разработчика компилятора язфка Си++ в конечном итоге совпадет с целью программиста-ползователя этого языка: программы Си++ должны исполняться (интерпретирвоаться) на машинах. Из этого все остальное следует вполне естественных образом.

Хорошое заключение но как оно вяжется с формальными языками, языками программирования и их синтаксисом?

Струдомасилил и такиневъехал о чем собственно говоря и был этот пост.
Re[14]: синтаксический анализатор
От: mefrill Россия  
Дата: 25.10.06 14:33
Оценка:
Здравствуйте, Аноним, Вы писали:

Короче, если ты не въехал, объясняю проще: использовать термин "семантика" для обозначения процесса обработки текста программы неверное. В математическом сообществе традиционно все, что связано с текстом называется синтаксисом, а то что с текстом не связано — семантикой. Применительно к Си++ имеем: все что касается обработки текста программы — синтаксис, а то что касается ее исполнения — семантика. Синтаксический анализатор, тот который строит промежуточное представление, не имеет дела с семантикой, т.е. с исполнением программы. Совсем не имеет если не брать в расчет элементы метапрограммирвоания, но их мы сейчас не касаемся. Почему ты называешь семантикой часть процесса обработки текста программы?
Re[17]: синтаксический анализатор
От: Аноним  
Дата: 25.10.06 14:57
Оценка:
M>Вот это очень интересно. Почему ты постулируешь принадлежность языку Си++ эти трех перечисленных выше тобой пунктов??? Кто сказал, что "Язык программирования С++ это 1) лексика, 2) синтаксис и 3) семантика которую присваивает создатель языка программирования лексическим и синтаксическим конструкциям"???
Вот! Здесь так и написано!

Programming Language = Syntax + Semantics

Плюс мое собственное понимание предмета и очень сжатое изложение что есть язык программирования. У тебя этого понимания нету и как посмотрю никогда не будет; одна абстрактная вода!

Единственное что я добавил сюда это лексику как самый первый этап трансляции.

M>Сами по себе понятия "лексика, синтаксис и семантика" — это только особые технические приемы, облегчающие написание машинных распознавателей для программ языка Си++, не более того.

Если тебе нужно определить написан ли данный текст на С++, то синтаксиса хватит. Если тебе нужно сгенерировать машинный код, то без семантики не обойтись!

M>Постулировать эти технические приемы как свойства языка (а тем более определять язык через них) — это все равно, что программисту — пользователю языка, сказать что язык Си++ — это множество объявлений типов и выражений и ни что другое.

Полный ахтунг!

Для этого, как раз-таки, достаточно одного синтаксиса!

M>Рассматривать язык Си++ во всей его полноте мы не можем — это вообще невозможно ни для какого понятия.

Ты это о чем?

M>Мы можем выделять только его некоторые свойства и рассматривать их в отдельности от всех остальных.

Это не так.

M>Это называется абстракцией. Абстракция, которую описываешь ты, т.е. рассмотрение Си++ как элементов, необходимых для трехступенчатого процесса компиляции программ на Си++ — вполне законна как и любая другая.

Ноу комментс.

M>Другое дело, что термины которые здесь используются (семантика и синтаксис) имеют в тех областях знаний, откуда они пришли, иное значение.

Голословие!

M>Кроме того, они противоречат математической терминологии, связанной в том числе и с рассмотрением языков программирования.

Не знаю о чем ты.

M>Это все равно как если бы в каком-то городе словом "стул" стали обозначать стол, а словом "стол" стул. Получился бы полный ужас — то из чего известный омомним одного из вышеупомянутых слов обычно появляется на Божий свет.

Вода.

M>Терминология она на то и дана, что это результат договоренности, чтобы одни и те же слова разные люди понимали примерно одинаково. Так давайте этому следовать.

Следую и тебе также советую.
Re[17]: синтаксический анализатор
От: Аноним  
Дата: 25.10.06 15:30
Оценка:
Ну, что я могу сказать? Умный человек меня понял. Ты — нет. Так и будешь пальцы гнуть при слове метапрограммирование (с которым не так уж и сложно разобраться), а глубины реально происходящих процессов никогда не поймешь.

WH>Нет. Это не мое, а твое заблуждение.

А также редиски Страуструпа который "правда дальше говорит какую-то фигню."

WH> Ибо по определению множество всех текстов языка порождается грамматикой этого языка.

Это только справедливо для формальных языков. Не знаю с чего ты решил что это также справедливо для языков программирования.

WH>Если грамматика порождает не все возможные тексты или порождает тексты которых нет в языке то это не грамматика данного языка.

Супер но опять-таки, это только применительно к формальным языкам.

WH>Все!

WH>Нет никакой ложки.


А>>Далее, тебе известно что переменные в С++ должны быть объявлены до первого использования, но ты также понимаешь что КС-грамматикой такое требование выразить нельзя и автоматом делаешь заключение что для этого требуется КЗ-грамматика. Это есть твое второе заблуждение.

WH>Как минимум КЗ. Не доказано что С++ можно загнать даже в КЗ.
Так КЗ или нет? Мефрилл вон считает что в КЗ можно загнать однозначно. Определитесь уж там.

WH>Рассуждения поскипаны ибо рассуждения построеные на неверных посылках не имеют смысла.

Либо поскипаны из-за чьегото непонимания происходящих процессов.

WH>Да и не путай формальную теорию языков и техники построения компиляторов ибо это совершенно не одно и тоже.

А ты уверен что это именно я путаю а не ты?

WH>Например когда я пишу компиляторы я вобще не пользуюсь формальными грамматиками ибо пользоваться pattern-matching'ом гораздо удобней чем всякими коками и яками.

И как pattern-matching, помогает тебе с рекурсивной вложенностью?
Re[18]: синтаксический анализатор
От: LaptevVV Россия  
Дата: 25.10.06 16:30
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Вот! Здесь так и написано!

А>

А>Programming Language = Syntax + Semantics

А>Единственное что я добавил сюда это лексику как самый первый этап трансляции.
Лексика — тоже входит в КС-грамматику... Вспомните правила для определения идентификатора или целого числа...
Просто при реализации проще разделить простые (лексика называется) и более сложные (синтаксис называется) синтаксические аспекты
А>Если тебе нужно определить написан ли данный текст на С++, то синтаксиса хватит. Если тебе нужно сгенерировать машинный код, то без семантики не обойтись!
Абсолютно верно!
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[19]: синтаксический анализатор
От: mefrill Россия  
Дата: 26.10.06 06:45
Оценка:
Здравствуйте, LaptevVV, Вы писали:

А>>Если тебе нужно определить написан ли данный текст на С++, то синтаксиса хватит. Если тебе нужно сгенерировать машинный код, то без семантики не обойтись!

LVV>Абсолютно верно!

Ну кто с этим спорит? Для генерации кода необходимо знать модель вычислений Си++ и модель вычислений целевого языка, иначе говоря, их семантики. Но причем здесь генерация кода и синтаксис программы? Представлением синтаксиса является так называемое Промежуточное Представление программы. В англоязычной терминологии — это AST — Abstract Syntax Tree. Что такое промежуточное представление? Это фактически — та же программа, только записанная не в плоском текстовом виде, а в виде уже иерархическом. Но оба представления программы совершенно одинаковы, как говорят изоморфны. Итак, из текста программы неким алгоритмом строится промежуточное представление программы. Это на самом деле некий гипертекст, не более того. Абстрагируемся от способов реализации алгоритма такого преобразования и увидим, что слово "семантика" здесь вообще рядом не стоит. Лексика, синтаксис и семантика — это не более чем технические приемы, которые описаны в учебниках как наиболее популярный метод преобразования текста программы в ее ПП. Но в любом случае, все это относится к тектсу и есть преобразование текста. Кто мне объяснит, зачем для построения ПП знать что объявление переменной соответствует выделени в памяти какого-то объекта? Это совершенно ненужно, достаточно просто знать, что если какое-то имя было использовано в программе, то ранее в тексте программы имеется его объявление, т.е. просто некая синтаксическая конструкция с этим именем. Так где здесь семантика?
Re[19]: синтаксический анализатор
От: Аноним  
Дата: 26.10.06 07:49
Оценка:
А>>Вот! Здесь так и написано!
А>>

А>>Programming Language = Syntax + Semantics

А>>Единственное что я добавил сюда это лексику как самый первый этап трансляции.
LVV>Лексика — тоже входит в КС-грамматику... Вспомните правила для определения идентификатора или целого числа...
Лаптев! Грамматика просто обьединяет те две сущности, а именно лексику и синтаксис, которые без проблем поддаются формализации, и это я знаю. В действительности эти две сущности совершенно разные, и поэтому я произвел это разделение.

10х за КС-грамматику!
LVV>Просто при реализации проще разделить простые (лексика называется) и более сложные (синтаксис называется) синтаксические аспекты
И это тоже.
А>>Если тебе нужно определить написан ли данный текст на С++, то синтаксиса хватит. Если тебе нужно сгенерировать машинный код, то без семантики не обойтись!
LVV>Абсолютно верно!
Re[19]: синтаксический анализатор
От: Аноним  
Дата: 26.10.06 07:56
Оценка:
WH>>> Ибо по определению множество всех текстов языка порождается грамматикой этого языка.
А>>Это только справедливо для формальных языков. Не знаю с чего ты решил что это также справедливо для языков программирования.
WH>Это справедливо для всех языков.
Сдаюсь-сдаюсь! Пусть будет так!

WH>>>Рассуждения поскипаны ибо рассуждения построеные на неверных посылках не имеют смысла.

А>>Либо поскипаны из-за чьегото непонимания происходящих процессов.
WH>А может это ты не понимаешь?
Каюсь. Я. А заодно и Страуструп со мною который "правда дальше говорит какую-то фигню."
Re[2]: синтаксический анализатор
От: maggot  
Дата: 15.06.07 15:50
Оценка:
Здравствуйте, _Obelisk_, Вы писали:

_O_>Здравствуйте, x-code, Вы писали:


XC>>давно хочу сделать некую прогу, которая бы на входе получала например *.cpp файл, и строила в памяти синтаксическое дерево исходного кода по аналогии например с XML DOM. Все блоки — классы, функции, if'ы и т.д. — отдельные ветки.



_O_>Если хотите этим заниматься в порядке самообразования — выбирайте язык попроще (Java, Pascal, Modula-2 и т.п.). Если же вам парсер нужен для использования в реальном проекте — лучше купить готовый. Например тут

_O_>http://www.cocolab.com/en/parsers.html
_O_>Без серьезной подготовки в области теории и практики разработки компиляторов ничего путного у вас не выйдет.

Это заблуждение. GLR парсер, который разбирает все классы контекстно свободных грамматик можно спокойно написать в одиночку, почитав некоторые книги. (Книгу драгона и Parsing Techniques) и немного подумав. ИМХО сложнее написать оптимизацию.
Re[3]: синтаксический анализатор
От: konsoletyper Россия https://github.com/konsoletyper
Дата: 15.06.07 19:27
Оценка:
Здравствуйте, maggot, Вы писали:

_O_>>Если хотите этим заниматься в порядке самообразования — выбирайте язык попроще (Java, Pascal, Modula-2 и т.п.). Если же вам парсер нужен для использования в реальном проекте — лучше купить готовый. Например тут

_O_>>http://www.cocolab.com/en/parsers.html
_O_>>Без серьезной подготовки в области теории и практики разработки компиляторов ничего путного у вас не выйдет.

M>Это заблуждение. GLR парсер, который разбирает все классы контекстно свободных грамматик можно спокойно написать в одиночку, почитав некоторые книги. (Книгу драгона и Parsing Techniques) и немного подумав. ИМХО сложнее написать оптимизацию.


GLR? В Книге Дракона? Что-то странно это... Не видел такого никогда...

Кроме того, прочтение таких книг — это немаленький такой шажок к серьёзной подготовке в области теории и практики разработки комипляторов. Да и речь шал о C++. Вот для него никакие GLR не помогут.
... << RSDN@Home 1.2.0 alpha rev. 672>>
Re[4]: синтаксический анализатор
От: maggot  
Дата: 15.06.07 19:45
Оценка:
Здравствуйте, konsoletyper, Вы писали:

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


_O_>>>Если хотите этим заниматься в порядке самообразования — выбирайте язык попроще (Java, Pascal, Modula-2 и т.п.). Если же вам парсер нужен для использования в реальном проекте — лучше купить готовый. Например тут

_O_>>>http://www.cocolab.com/en/parsers.html
_O_>>>Без серьезной подготовки в области теории и практики разработки компиляторов ничего путного у вас не выйдет.

M>>Это заблуждение. GLR парсер, который разбирает все классы контекстно свободных грамматик можно спокойно написать в одиночку, почитав некоторые книги. (Книгу драгона и Parsing Techniques) и немного подумав. ИМХО сложнее написать оптимизацию.


K>GLR? В Книге Дракона? Что-то странно это... Не видел такого никогда...



В книге дракона вообще мало что написано про синтаксический анализ. Из полезного — только построение конечного автомата из регулярных выражений. Parsing Techniques уже другое дело... Хотя всё равно, по-моему, нет бесплатной литературы, где написано подробно как сделать GLR парсер. Но это не проблема. Тут и самому подуамть можно.

K>Кроме того, прочтение таких книг — это немаленький такой шажок к серьёзной подготовке в области теории и практики разработки комипляторов. Да и речь шал о C++. Вот для него никакие GLR не помогут.

И как же тогда по-вашему компиляторы делают? Некоторые умудряются даже записывать грамматику С++ для LALR(1) парсера, хотя, конечно, понятно, что это извращение... А GLR в самый раз.
Re: синтаксический анализатор
От: chukichuki  
Дата: 20.06.07 12:25
Оценка:
Смотри исходники OpenC++. Один из лучших парсеров С++, написанных "руками", из того что я видел (руками ли? Некоторые из моих колег в этом сомневаются). Все то, что до AST включительно сделано очень неплохо и понятно. Контекстный анализ специфичный и достаточно слабый. Для работы с памятью он использует Boehm GC, который в свою очередь имеет (по крайней мере раньше имел) некоторые проблемы с Win32. Но в целом вещь написана очень красиво и понятно.
Re[4]: синтаксический анализатор
От: chukichuki  
Дата: 20.06.07 12:34
Оценка:
Здравствуйте, konsoletyper, Вы писали:

K>Здравствуйте, x-code, Вы писали:


XC>>интересно, а чем в смысле анализа Java или Pascal проще C++? только тем что в С++ по очередной лексеме и текущему контексту часто сразу не определить какой узел AST строить? или есть еще какие-то особенности?


K>Особенность как раз в контексте. Для Java или Pascal конекстом является только магазин. Для C++ нужна ещё и кое-какая семантическая инфа.


Не только. Еще в С++ есть такие ужасы как ПРЕПРОЦЕССОР и ШАБЛОНЫ. Последние в совокупности с контекстно-зависимостью образуют гремучую смесь.
Re[3]: синтаксический анализатор
От: chukichuki  
Дата: 20.06.07 13:02
Оценка:
Здравствуйте, maggot, Вы писали:

M>Это заблуждение. GLR парсер, который разбирает все классы контекстно свободных грамматик можно спокойно написать в одиночку, почитав некоторые книги. (Книгу драгона и Parsing Techniques) и немного подумав. ИМХО сложнее написать оптимизацию.


Зачем его писать когда есть bison В крайнем случае LR с несколько кривыми правилами можно повзаимствовать из gcc. Только парсер си++ это капля в море. Контекстный анализ — вешь более сложная. Мы свой frontend Си++ в троем писали около двух лет. И то получилось не очень. Собирались переписывать, но проект закрыли
Re: синтаксический анализатор
От: Cephalopod  
Дата: 25.06.07 15:46
Оценка:
Здравствуйте, x-code, Вы писали:

XC>давно хочу сделать некую прогу, которая бы на входе получала например *.cpp файл, и строила в памяти синтаксическое дерево исходного кода по аналогии например с XML DOM. Все блоки — классы, функции, if'ы и т.д. — отдельные ветки.

XC>интересно написать это самому, без вспомогательных средств типа yacc, теории языков и грамматик и т.п. Чтобы было предельно просто, понятно и прозрачно, и в то же время универсально и гибко. И еще — как бонус — чтобы на основе этого дерева можно было бы реализовать простую кодогенерацию.

Ну вы замахнулись, батенька... C++ имеет один из самых уродливых и кривых синтаксисов из ныне здравствующих языков. По уму распарсить его очень непросто, практически все существующие реализации основаны на весьма грязных хаках (например, динамическое изменение таблиц лексера).

Единственный лучик света в тёмном царстве — творение товарища Томиты, GLR-parsing. В качестве примера того, как на основе GLR можно разбирать C++ — смотрите вот сюда:

http://www.cs.berkeley.edu/~smcpeak/elkhound/sources/elsa/

Там же много чего страшного рассказывают про проблемы с синтаксисом C++, почитайте, ужаснитесь, оцените невообразимый уровень трудозатрат, который вам потребуется для воспроизведения этой работы.

XC>в общем, даже понятно что делать: лексический анализ я в свое время сделал за вечер, работает идеально. а дальше просто времени не было, только мысли... некий набор методов типа parseCppFile, parseNamespace, parseStruct... которые вызывают друг друга и строят соответствующее дерево.


Этот лексический анализатор наверняка не может отделить, например, идентификатор от типа. Да и парсер тоже не сможет.


XC> Наверняка потребуется вспомогательный стек для разрешения неоднозначных ситуаций, которых в C++ предостаточно. Можно скачать грамматику языка, перегнать ее в прогу и сделать все это автоматически, но сначала хочется все же вручную.


Лес деревьев в GLR — это никак не "вспомогательный стек", это гораздо сложнее. Всё не так просто, как вам с ходу могло показаться.

XC>Собственно, проблема в том что задача довольно большая и сразу всего не охватить — мысли растекаются а хочется, поскольку если эту штуку реализовать то можно сделать много интересного. Поэтому вопрос: существуют ли реализации таких парсеров — не студенческие примитивные программы, но и не профессиональные компиляторы с оптимизацией, а нечто среднее, сделанное именно вручную и желательно на C/C++ (можно C#). Просто чтобы можно было посмотреть код и выявить идеи, возможные тонкости и т.д.


Ещё раз — Elsa. Развивается оно сейчас в проекте Oink:

http://www.cubewano.org/oink/
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.