Здравствуйте, Сергей Губанов, Вы писали:
СГ>Книга Н. Вирта
СГ>Theory and Techniques of Compiler Construction. Addison-Wesley, Reading, April 1996.
СГ>http://www.cs.ucr.edu/~phf/mir/wirth-compiler-1996.pdf
Знаем такую, достойная вещь. Только не хватает страниц 58, 59, 74 и 75. А они довольно важны Вот их бы почитать.
Приходиться заниматься гадостью — зарабатывать на жизнь честным трудом (Б.Шоу)
Re: Theory and Techniques of Compiler Construction
Здравствуйте, Шахтер, Вы писали:
Ш>Здравствуйте, Сергей Губанов, Вы писали:
СГ>>Книга Н. Вирта
СГ>>Theory and Techniques of Compiler Construction. Addison-Wesley, Reading, April 1996.
СГ>>http://www.cs.ucr.edu/~phf/mir/wirth-compiler-1996.pdf
Ш>Дракон гораздо лучше.
ИМХО, вы несколько категоричны. У этих книг разные цели. "Дракон" фундаментальнее и в области компиляторов значит, наверное, почти то же самое, что "Искусство программирования" (кстати, в 1978 году был издан 2-х томник авторов "Дракона". Назывался он "Теория синтаксического анализа, перевода и компиляции", так вот он — куда солиднее по уровню подачи (конечно, сугубо ИМХО). "Дракон" в некотором смысле конспект этого двухтомника).
У Вирта задача иная — показать КАК можно построить компилятор типичного императивного ЯП. Не более. Что он и делает (кстати, на мой взгляд — превосходно и ясно): берешь книгу, кладешь перед собой и "ваяешь" компилятор прямо по ней
Приходиться заниматься гадостью — зарабатывать на жизнь честным трудом (Б.Шоу)
Re[3]: Theory and Techniques of Compiler Construction
Здравствуйте, fplab, Вы писали:
F>Здравствуйте, Шахтер, Вы писали:
Ш>>Здравствуйте, Сергей Губанов, Вы писали:
СГ>>>Книга Н. Вирта
СГ>>>Theory and Techniques of Compiler Construction. Addison-Wesley, Reading, April 1996.
СГ>>>http://www.cs.ucr.edu/~phf/mir/wirth-compiler-1996.pdf
Ш>>Дракон гораздо лучше. F>ИМХО, вы несколько категоричны. У этих книг разные цели. "Дракон" фундаментальнее и в области компиляторов значит, наверное, почти то же самое, что "Искусство программирования" (кстати, в 1978 году был издан 2-х томник авторов "Дракона". Назывался он "Теория синтаксического анализа, перевода и компиляции", так вот он — куда солиднее по уровню подачи (конечно, сугубо ИМХО). "Дракон" в некотором смысле конспект этого двухтомника). F>У Вирта задача иная — показать КАК можно построить компилятор типичного императивного ЯП. Не более. Что он и делает (кстати, на мой взгляд — превосходно и ясно): берешь книгу, кладешь перед собой и "ваяешь" компилятор прямо по ней
Вряд ли по книжке Вирта можно написать компилятор С++, например.
Здравствуйте, Шахтер, Вы писали:
F>>Здравствуйте, Шахтер, Вы писали:
F>>У Вирта задача иная — показать КАК можно построить компилятор типичного императивного ЯП. Не более. Что он и делает (кстати, на мой взгляд — превосходно и ясно): берешь книгу, кладешь перед собой и "ваяешь" компилятор прямо по ней
Ш>Вряд ли по книжке Вирта можно написать компилятор С++, например.
В какой-то степени Вы правы — С++ или Java слишком "мудреные" языки Но книга Вирта носит учебный характер и (позволю себе повториться) позволяет научиться строить компилятор ТИПИЧНОГО императивного ЯП. С++ к таковым, конечно, не относится, а вот обычный С — вполне.
P.S. Кстати, в "драконе", сколько мне помнится, тоже ничего нет о реализации объектно-ориентированных языков, классов, интерфейсов, таблицах виртуальных функций или callback-ах. Если я ошибаюсь — буду благодарен за точное указание тех глав, разделов или страниц из "дракона", где эти вопросы освещаются.
Приходиться заниматься гадостью — зарабатывать на жизнь честным трудом (Б.Шоу)
Re[2]: Theory and Techniques of Compiler Construction
Здравствуйте, fplab, Вы писали:
F>Здравствуйте, Сергей Губанов, Вы писали:
СГ>>Книга Н. Вирта
СГ>>Theory and Techniques of Compiler Construction. Addison-Wesley, Reading, April 1996.
СГ>>http://www.cs.ucr.edu/~phf/mir/wirth-compiler-1996.pdf F>Знаем такую, достойная вещь. Только не хватает страниц 58, 59, 74 и 75. А они довольно важны Вот их бы почитать.
А полного варианта не существует в природе ?
Re[2]: Theory and Techniques of Compiler Construction
Незнаю как эта. Но дракок откравенно говоря и устарел, и слабоват. А если барать русский вариант, то еще и безобразный перевод.
Вообще, явно назрел вопрос новой книги в этой области. А то все что есть появивилось в до ООП-ную эру и ценность на сегодня представляет очень сомнительную.
Я вот тут поглядел примеры к будущей версии АНТЛР-а... это земля и небо с тем что в книжках толкают.
... << RSDN@Home 1.2.0 alpha rev. 577>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Theory and Techniques of Compiler Construction
Здравствуйте, fplab, Вы писали:
F>В какой-то степени Вы правы — С++ или Java слишком "мудреные" языки
Ну, как раз Ява и Яками и АНТЛР-ом берется на ура. А вот для С++ яки без костылей не пригодны. А писать парсер плюсов на Яве — это уже позор (С++-ный АНТЛР совсем глюкавая вещь).
... << RSDN@Home 1.2.0 alpha rev. 577>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: Theory and Techniques of Compiler Construction
Здравствуйте, VladD2, Вы писали:
Ш>>Дракон гораздо лучше.
VD>Незнаю как эта. Но дракок откравенно говоря и устарел, и слабоват. А если барать русский вариант, то еще и безобразный перевод.
Присоединяюсь, безобразнейший перевод. Автор явно не понимал, что переводил. Например, простейшие и изящные алгоритмы трансформации недетерминированного конечного автомата в детерминированный там представлены просто ужасно. Лучше уж совсем эту книжку не читать.
Первое издание дракона вышло в оригинале в 1972 году. К тому времени, теория синтаксического анализа и формальных грамматик была, фактически, завершена. Так что, прочитать эту книжку полезно всякому. Хотя, для программиста она, фактически, не читаема. Очень много математики. Вообще, эта область трудная. По синтаксическому анализу есть великолепная книга двух голландтских авторов, не помню названия сейчас, что-то типа "практический синтаксический анализ" или еще как-то. Книжка на английском и на русский не переведена, но очень неплохо написана, особенно, для тех, кто с алгоритмами синтаксического анализа не на "ты". Вот эту бы книжку перевести. Когда-то я вроде перевел первую главу, но это дело забросил.
Дело же здесь не в синтаксическом анализе, методы которого не претерпели значащих изменений за последние 50 лет, а именно, в теории компиляции. Теория генерации кода была модным занятием в 80-е годы и разработана очень мощная теория. Затем, множество вероятностных методов компиляции, параллельная компиляция. И, наконец, семантика. Это довольно большая область исследований, к которой уже 20 лет подбираются, но ничего существенного пока не достигли.
VD>Вообще, явно назрел вопрос новой книги в этой области. А то все что есть появивилось в до ООП-ную эру и ценность на сегодня представляет очень сомнительную.
Ну, насколько я помню, авторы дракона собирались выпустить третье издание еще в 2003 году. Но потом, увидев изменения в теории компиляции, перенесли выпуск на 2006. Очень много работы нужно, чтобы войти в тему.
VD>Я вот тут поглядел примеры к будущей версии АНТЛР-а... это земля и небо с тем что в книжках толкают.
А что там интересного такого?
Re[5]: Theory and Techniques of Compiler Construction
Вообще, эта область трудная. По синтаксическому анализу есть великолепная книга двух голландтских авторов, не помню названия сейчас, что-то типа "практический синтаксический анализ" или еще как-то. Книжка на английском и на русский не переведена, но очень неплохо написана, особенно, для тех, кто с алгоритмами синтаксического анализа не на "ты". Вот эту бы книжку перевести.
Часом не DICK GRUNE, CERIEL JACOBS "PARSING TECHNIQUES" ? Если не эта приведите пожалуйста ссылочку Очень интересно было бы ознакомится .
Re[5]: Theory and Techniques of Compiler Construction
Здравствуйте, Aviator, Вы писали:
A>Часом не DICK GRUNE, CERIEL JACOBS "PARSING TECHNIQUES" ? Если не эта приведите пожалуйста ссылочку Очень интересно было бы ознакомится .
Ага, та самая.
Re[6]: Theory and Techniques of Compiler Construction
Здравствуйте, mefrill, Вы писали:
M>Здравствуйте, Aviator, Вы писали:
A>>Часом не DICK GRUNE, CERIEL JACOBS "PARSING TECHNIQUES" ? Если не эта приведите пожалуйста ссылочку Очень интересно было бы ознакомится .
M>Ага, та самая.
Володь, а у тебя её нет в электрическом виде? Огроменное спасибо, если на мыло кинешь
BTW как в Европу съездил?
Re[6]: Theory and Techniques of Compiler Construction
Здравствуйте, mefrill, Вы писали:
M>Здравствуйте, Aviator, Вы писали:
A>>Часом не DICK GRUNE, CERIEL JACOBS "PARSING TECHNIQUES" ? Если не эта приведите пожалуйста ссылочку Очень интересно было бы ознакомится .
M>Ага, та самая.
К большому сожалению так и не читал эту книжку, хотя давно уже валяется Выс считаете что стоящая книга и если заниматься компиляторами то необходимо прочитать ?
PS Кстати по результату пролистыванияне осталось впечатления что книга очень уж простая и сугубо практическая
Re[7]: Theory and Techniques of Compiler Construction
Здравствуйте, Aviator, Вы писали:
A>Здравствуйте, mefrill, Вы писали:
M>>Здравствуйте, Aviator, Вы писали:
A>>>Часом не DICK GRUNE, CERIEL JACOBS "PARSING TECHNIQUES" ? Если не эта приведите пожалуйста ссылочку Очень интересно было бы ознакомится .
M>>Ага, та самая.
A>К большому сожалению так и не читал эту книжку, хотя давно уже валяется Выс считаете что стоящая книга и если заниматься компиляторами то необходимо прочитать ?
A>PS Кстати по результату пролистыванияне осталось впечатления что книга очень уж простая и сугубо практическая
У меня есть такая. Кому надо — вышлю по запросу в мыло. Объем 1.2 Мб в zip
Приходиться заниматься гадостью — зарабатывать на жизнь честным трудом (Б.Шоу)
Re: Theory and Techniques of Compiler Construction
Здравствуйте, Сергей Губанов, Вы писали:
СГ>Книга Н. Вирта
СГ>Theory and Techniques of Compiler Construction. Addison-Wesley, Reading, April 1996.
СГ>http://www.cs.ucr.edu/~phf/mir/wirth-compiler-1996.pdf
Судя по контенту, довольно поверхностно. К тому же затронуты не самые интересные темы — Мучник, имхо, в качестве референса пополезнее будет. В общем, книжка студентам 1-3 курса.
Re[6]: Theory and Techniques of Compiler Construction
Здравствуйте, mefrill, Вы писали:
M>А что там интересного такого?
Ну, трешка похоже просто будет практически идеальным построителем парсеров. А 2.х просто довольно мощьный продукт. А есть там много чего. Декларативное заглядывание вперед (правда становится не актуальным в следующей версии). Декларативное построение АСТ. EBNF. Автоматическое пуравление памятью (ну, это скорее Ява себя проявляет).
В драконах же откровенно говоря каменный век. Куча времени посвящается мало актуальным вещам вроде управления памятью, а про VM вообще ничего нет. ООП даже не затрагивается. Хотя в конце книги приводятся граматики С++ и C#, но они а) даже не рассматриваются, б) они просто не корректны.
Ну, а в этом переводе ее читать вообще очень сложно. Чувствуешь себя недоразвитым идиомто. И это даже если ты знашь про что читаешь.
... << RSDN@Home 1.2.0 alpha rev. 578>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: Theory and Techniques of Compiler Construction
It supports the C++ language of the ISO/IEC 14882:2003 standard (the
/complete/ language; see our description of language features
<http://edg.com/cpp_ftrs.html>).
--
С уважением,
Alex Besogonov (alexy@izh.com)
Posted via RSDN NNTP Server 1.9
Sapienti sat!
Re[7]: Theory and Techniques of Compiler Construction
Здравствуйте, Курилка, Вы писали:
К>Володь, а у тебя её нет в электрическом виде? Огроменное спасибо, если на мыло кинешь
Привет Кирилл, да она в сети валяется бесплатная. Я вот погуглил, нашел здесь. Книжка классная, хотя читается не так легко, надо над ней работать, тема трудная.
К>BTW как в Европу съездил?
Нормально, пойдет.
Re[8]: Theory and Techniques of Compiler Construction
C>It supports the C++ language of the ISO/IEC 14882:2003 standard (the
C>/complete/ language; see our description of language features
C><http://edg.com/cpp_ftrs.html>).
Ага. На этом списк удачных попыток заканчивается.
Видимо эти парни имели некоторые потаенные знания почерпнутые из других книг или нажытые по жизни.
... << RSDN@Home 1.2.0 alpha rev. 578>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: Theory and Techniques of Compiler Construction
VladD2,
> C>У этих четырех парней получилось: http://edg.com/ > C>
> C>It supports the C++ language of the ISO/IEC 14882:2003 standard (the
> C>/complete/ language; see our description of language features
> C><http://edg.com/cpp_ftrs.html>).
> C>
> Ага. На этом списк удачных попыток заканчивается. > Видимо эти парни имели некоторые потаенные знания почерпнутые из других книг или нажытые по жизни.
Все проще: для них буквальное следование стандарту было важнее, чем для других.
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Re[5]: Theory and Techniques of Compiler Construction
Здравствуйте, eao197, Вы писали:
E>Здравствуйте, Сергей Губанов, Вы писали:
СГ>>Здравствуйте, VladD2, Вы писали:
VD>>> ...АНТЛР...
СГ>> АНТЛР — это что?
E>antlr.org
Ты знаешь, я глянул бегло сайт и ничего, кроме достаточно тривиальных вещей не нашел.
Что там круче дракона? Чисто конкретно, плиз.
Здравствуйте, fplab, Вы писали:
F>Здравствуйте, Шахтер, Вы писали:
F>>>Здравствуйте, Шахтер, Вы писали:
F>>>У Вирта задача иная — показать КАК можно построить компилятор типичного императивного ЯП. Не более. Что он и делает (кстати, на мой взгляд — превосходно и ясно): берешь книгу, кладешь перед собой и "ваяешь" компилятор прямо по ней
Ш>>Вряд ли по книжке Вирта можно написать компилятор С++, например.
F>В какой-то степени Вы правы — С++ или Java слишком "мудреные" языки Но книга Вирта носит учебный характер и (позволю себе повториться) позволяет научиться строить компилятор ТИПИЧНОГО императивного ЯП.
Точнее сказать -- простого, а не типичного.
Но в тои то и дело, что мы живём в эпоху непростых языков.
F>С++ к таковым, конечно, не относится, а вот обычный С — вполне.
F>P.S. Кстати, в "драконе", сколько мне помнится, тоже ничего нет о реализации объектно-ориентированных языков, классов, интерфейсов, таблицах виртуальных функций или callback-ах. Если я ошибаюсь — буду благодарен за точное указание тех глав, разделов или страниц из "дракона", где эти вопросы освещаются.
Эти вопросы там не рассматриваются. Но должен заметить, что как раз они не имеют такого уж принципиального значения при построении компиляторов, поскольку все эти объектно-ориентированные навороты легко ложатся поверх обычных процедурных языков.
Исключением является только С++ с его шаблонами, обработка которых -- действительно нетривиаьлный предмет.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, Шахтер, Вы писали:
Ш>>Вряд ли по книжке Вирта можно написать компилятор С++, например.
VD>А по какой книжке можно написать С++-компилятор?
Компиляторы пишут не по книжкам (за исключением самых простых языков).
Здравствуйте, Шахтер, Вы писали:
Ш>Эти вопросы там не рассматриваются. Но должен заметить, что как раз они не имеют такого уж принципиального значения при построении компиляторов, поскольку все эти объектно-ориентированные навороты легко ложатся поверх обычных процедурных языков. Ш>Исключением является только С++ с его шаблонами, обработка которых -- действительно нетривиаьлный предмет.
Шаблоны в C++ — это вообще что-то с чем-то. Попытка вывести невыводимую формулу и поженить несовместимые сущности — макросы и функции. Но несмотря на весь свой негатив, достойной альтернативы шаблонам пока что нет. Generics не считаем — это совершенно другая пара сапог, и эти вещи, можно сказать, ортогональны.
Но хотя бы распарсить шаблоны — задача действительно неприподъемной сложности. Только монстры могут, типа GCC или Comeau, да и то с огрехами.
А все началось с того, что в C++ разрешили использование сущностей вперед их декларации. Вот он, корень зла! Вирт подобные "штучки" считает полной ересью и в чем-то он прав. В самом деле, я могу писать на C++ в традиционном процедурном стиле (Сишном), имея один-единственный огромадный файл и заключив все функции в один класс следующим образом:
При этом, мне не надо никаких прототипов и/или пре-деклараций. То же самое в Java и C#. А теперь представим, что нам требуется написать парсер и (как это по-русски) symbol resolver для подобного класса бесконечного объема, используя конечный объем памяти (оперативной и дисковой). Для C++, C#, Java подобная задача является в принципе нерешаемой. Для C — решаемой и это — ключевое отличие. Аргумент, что для исходника бесконечного объема требуется и объектник бесконечного объема — не катит, по той простой причине, что транслятор может являться неким сервером, который принимает символы из сокета и посылает результаты в другой сокет. А уж что там в конечном итоге происходит — нам не важно. Так вот, в таких языках, как C++, C#, Java, пока наш гипотетический сервер не засосёт весь класс, он в принципе не может ничего сделать. Ни одного байта сгенерировать не может. А пока он кушает, у него может и рожа треснуть.
А спрашивается, чем в таком случае класс отличается от файла (как единицы трансляции)? Да ни чем! А почему тогда в классе можно использовать имена до их деклараций а в файле нельзя?
В C# или Java ведь тоже запрещено использовать классы вперед их объявлений? Хотя функции внутри классов — можно. Почему? Итак, еще раз, вопрос. Чем в сущности содержимое класса отличается от содержимого файла как единицы трансляции?
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re[7]: Theory and Techniques of Compiler Construction
Здравствуйте, McSeem2, Вы писали:
MS>Здравствуйте, Шахтер, Вы писали:
Ш>>Эти вопросы там не рассматриваются. Но должен заметить, что как раз они не имеют такого уж принципиального значения при построении компиляторов, поскольку все эти объектно-ориентированные навороты легко ложатся поверх обычных процедурных языков. Ш>>Исключением является только С++ с его шаблонами, обработка которых -- действительно нетривиаьлный предмет.
MS>Шаблоны в C++ — это вообще что-то с чем-то. Попытка вывести невыводимую формулу и поженить несовместимые сущности — макросы и функции.
Идея шаблонов очень естественна.
MS>Но несмотря на весь свой негатив, достойной альтернативы шаблонам пока что нет. Generics не считаем — это совершенно другая пара сапог, и эти вещи, можно сказать, ортогональны. MS>Но хотя бы распарсить шаблоны — задача действительно неприподъемной сложности. Только монстры могут, типа GCC или Comeau, да и то с огрехами.
Да не преувеличивай. Прсто в развитие С++ не вкладывается громадных средств.
MS>А все началось с того, что в C++ разрешили использование сущностей вперед их декларации. Вот он, корень зла! Вирт подобные "штучки" считает полной ересью и в чем-то он прав. В самом деле, я могу писать на C++ в традиционном процедурном стиле (Сишном), имея один-единственный огромадный файл и заключив все функции в один класс следующим образом: MS>
MS>При этом, мне не надо никаких прототипов и/или пре-деклараций. То же самое в Java и C#. А теперь представим, что нам требуется написать парсер и (как это по-русски) symbol resolver для подобного класса бесконечного объема, используя конечный объем памяти (оперативной и дисковой). Для C++, C#, Java подобная задача является в принципе нерешаемой. Для C — решаемой и это — ключевое отличие. Аргумент, что для исходника бесконечного объема требуется и объектник бесконечного объема — не катит, по той простой причине, что транслятор может являться неким сервером, который принимает символы из сокета и посылает результаты в другой сокет. А уж что там в конечном итоге происходит — нам не важно. Так вот, в таких языках, как C++, C#, Java, пока наш гипотетический сервер не засосёт весь класс, он в принципе не может ничего сделать. Ни одного байта сгенерировать не может. А пока он кушает, у него может и рожа треснуть.
MS>А спрашивается, чем в таком случае класс отличается от файла (как единицы трансляции)? Да ни чем! А почему тогда в классе можно использовать имена до их деклараций а в файле нельзя? MS>В C# или Java ведь тоже запрещено использовать классы вперед их объявлений? Хотя функции внутри классов — можно. Почему? Итак, еще раз, вопрос. Чем в сущности содержимое класса отличается от содержимого файла как единицы трансляции?
По поводу файла -- лучше, когда использованию объекта предшествует его определение. Это спасает от многих неожиданностей.
Для функций, определённых в классе, сделано исключение. Причина понятна -- не должно быть разницы, где определять тело, внутри или вовне класса.
McSeem2,
> А все началось с того, что в C++ разрешили использование сущностей вперед их декларации. Вот он, корень зла! Вирт подобные "штучки" считает полной ересью и в чем-то он прав.
Гм... Мне лень лезть в спецификацию всевозможных оберонов... Предлагаю поверить в этом Сергею Губанову. Он утверждает
, что для использования класса в Обероне, предварительное объявление не требуется.
> представим, что нам требуется написать парсер и (как это по-русски) symbol resolver для подобного класса бесконечного объема, используя конечный объем памяти (оперативной и дисковой). Для C++, C#, Java подобная задача является в принципе нерешаемой. Для C — решаемой и это — ключевое отличие.
Не решается эта задача ни для Паскаля, ни для Си, если ввести в них запись/структуру бесконечного объема, т.к. невозможно будет даже определить sizeof подобного монстра, я уж не говорю об остальных задачах...
> А спрашивается, чем в таком случае класс отличается от файла (как единицы трансляции)? Да ни чем! А почему тогда в классе можно использовать имена до их деклараций а в файле нельзя?
Не совсем так. В C++ определение функции-члена в теле класса (с точки зрения поиска имен) эквивалентно определению ее за пределами класса + добавление квалификатора inline. Соответственно, в определении функций-членов можно использовать имена, введенные где угодно в определении класса, т.к. по определению считается, что компилятор как бы сам выносит определение функции-члена за пределы класса. В объявлении функций-членов, как и в остальных местах в определении класса (исключая определения функций-членов по месту), можно использовать только имена, определенные ранее. Собственно, в C++ возможность определения функций-членов в теле класса — просто упрощенный синтаксис, действительно, перекладывающий часть работы на компилятор. При большом желании можно использовать "полный" синтаксис, облегчая работу компилятору
> В C# или Java ведь тоже запрещено использовать классы вперед их объявлений?
В C# — не запрещено. В Java — не уверен, но, по-моему, тоже можно.
Т.е., имхо, во всех языках все логично: в C++ везде, кроме convenience случая определения функций-членов в теле класса, нужно предварительное объявление сущностей. В C#/Java — не нужно нигде...
Это если мы молчим о шаблонах В случае шаблонов все, действительно, становится намного сложнее, включая подхват имен, определенных после точки использования. А если мы еще и про экспорт в совокупности с ADL вспомним, то, вообще, будет "мама не горюй": поиск имен в определенных случаях заработает между файлами, которые друг в друга не включаются, и даже в анонимных namespaces между разными файлами...
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Re[10]: Theory and Techniques of Compiler Construction
Здравствуйте, Павел Кузнецов, Вы писали:
ПК>Все проще: для них буквальное следование стандарту было важнее, чем для других.
Парни, безусловно, монстры! Честно сказать, я не хотел бы заниматься подобными вещами. Это настолько кропотливая и нудная работа, что просто ваащее... И именно поэтому заслуживает пения всяческих дифирамбов. Браво! Лично мне сейчас хватает SVG — это такая ж... там столько противоречий...
(резкий переход к другой теме)
А вообще, мысль такова. Вот придумали C++. И все-таки стараются где-то как-то предоставить адекватные средства. Это очень сложно в силу сложности самого языка. Но GCC, например — уже вполне достойный компилятор с точки зрения стандарта. Да, не полный, но один из наилучших доступных и пригодных на практике. А MS любит перекладывать свою головную боль на пользователей. И делают они это очень умело. Перекладывание проблем на чужие плечи — в этом нет равных MS. Я говорю это не в ругательном смысле, а просто как констатацию. Я даже где-то и сам такой. Не знаю, как лучше выразить свою мысль, но вот аналогия. Apple очень серьезно работает над внешним дизайном приложений. Настолько серьезно, что практически не возникает необходимости менять что-либо после установки. Что я делаю после установки Windows — пол-дня тыкаю во всякие пимпочки, чтобы сделать работоспособным. То же самое — со студиями. Мне ни на фиг не уперлись все эти dockable windows, они только мешаются. А MS говорит — "вот вам, делайте как хотите, а нам вся эта юзабилити пох". Я не против того, чтобы "делайте как хотите", я против того, чтобы дефолтные конфигурации были настолько уродливыми.
Аналогичная фигня — с компиляторами. С шаблонами я могу наколбасить такого, что MS съест и не подавится, в то время, как другой компилятор сразу укажет на банальные ошибки. И будет прав, поскольку я действительно допустил оплошность. Именно поэтому, 99% кода на C++ с шаблонами, который успешно компилируется и работает на MS C++ (и только на нем), требует дополнительного портирования на другие компиляторы. Речь здесь не идет о каких-либо системно-зависимых вещах, просто — некий платформо-независимый код. Ставлю 99 против одного, что код размером более 100K, написанный и отлаженный только на MSC++, не странслируется с первого раза на GCC. И GCC будет прав.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re[8]: Theory and Techniques of Compiler Construction
Здравствуйте, Павел Кузнецов, Вы писали:
ПК>Не совсем так. В C++ определение функции-члена в теле класса (с точки зрения поиска имен) эквивалентно определению ее за пределами класса + добавление квалификатора inline. Соответственно, в определении функций-членов можно использовать имена, введенные где угодно в определении класса, т.к. по определению считается, что компилятор как бы сам выносит определение функции-члена за пределы класса. В объявлении функций-членов, как и в остальных местах в определении класса (исключая определения функций-членов по месту), можно использовать только имена, определенные ранее. Собственно, в C++ возможность определения функций-членов в теле класса — просто упрощенный синтаксис, действительно, перекладывающий часть работы на компилятор. При большом желании можно использовать "полный" синтаксис, облегчая работу компилятору
Да, ты прав. Я несколько сгустил краски. Но вот что действительно плохо в C++ — так это ужасный синтаксис с "::". Вместо того, чтобы писать
void foo::bar()
{
. . .
}
гораздо лучше было бы что-то типа такого:
implement foo
{
void bar()
{
. . .
}
}
Сразу исчезли бы проблемы с "template template". Синтаксис шаблона функции-члена шаблона класса, имлементированного вне этого класса — это же застрелиться можно иногда. А заставлять писать все внутри класса — вообще маздай. Совешенно невозможно охватить общую картину вглядом. А в Java и C# это возведено в степень догмы.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re[11]: Theory and Techniques of Compiler Construction
McSeem2 wrote:
> Аналогичная фигня — с компиляторами. С шаблонами я могу наколбасить > такого, что MS съест и не подавится, в то время, как другой компилятор > сразу укажет на банальные ошибки.
Вообще-то VC7.1 почти полностью совместим со Стандартом, и диагностика
ошибок в шаблонах — вполне нормальная. Когда я переносил свой проект,
который писался полгода, на GCC — проблем с шаблонам не возникло (а их у
меня там мнооого).
Вот VC6 — этот действительно с шаблонами не очень дружит.
--
С уважением,
Alex Besogonov (alexy@izh.com)
Posted via RSDN NNTP Server 1.9
Sapienti sat!
Re[6]: Theory and Techniques of Compiler Construction
Здравствуйте, Шахтер, Вы писали:
VD>>>> ...АНТЛР...
СГ>>> АНТЛР — это что?
E>>antlr.org
Ш>Ты знаешь, я глянул бегло сайт и ничего, кроме достаточно тривиальных вещей не нашел. Ш>Что там круче дракона? Чисто конкретно, плиз.
Боюсь, что не ко мне вопрос. Сергей просто спросил, что такое ANTLR, я просто дал ссылку на сайт ANTLR.
В общих словах ANTLR -- это генератор нисходящих парсеров для LL(1) грамматик. Плюс, насколько помню, содержит еще и генератор лексического анализатора.
Что там за теория внутрях реализована, меня никогда не интересовало. Просто я наткнулся на него когда несколько лет назад искал объектно-ориентированную замену yacc-у.
... << RSDN@Home 1.1.4 stable rev. 510>>
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[12]: Theory and Techniques of Compiler Construction
Здравствуйте, Cyberax, Вы писали:
C>Вообще-то VC7.1 почти полностью совместим со Стандартом, и диагностика C>ошибок в шаблонах — вполне нормальная. Когда я переносил свой проект, C>который писался полгода, на GCC — проблем с шаблонам не возникло (а их у C>меня там мнооого).
VC7.1 страдает практически такой же болезнью, что и VC6 — он не толком не проверяет синтаксис шаблонов до момента их реального использования. При написании библиотек это создает проблемы. Даже отсутствие банальной ";" в нужном месте — пропускает. GCC и Intel — диагностируют нормально.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re[13]: Theory and Techniques of Compiler Construction
McSeem2 wrote:
> C>Вообще-то VC7.1 почти полностью совместим со Стандартом, и диагностика > C>ошибок в шаблонах — вполне нормальная. Когда я переносил свой проект, > C>который писался полгода, на GCC — проблем с шаблонам не возникло (а > их у > C>меня там мнооого). > VC7.1 страдает практически такой же болезнью, что и VC6 — он не толком > не проверяет синтаксис шаблонов до момента их реального использования. > При написании библиотек это создает проблемы. Даже отсутствие > банальной ";" в нужном месте — пропускает. GCC и Intel — диагностируют > нормально.
Однако, когда шаблоны все-таки инстанцируются, то происходит полная
проверка.
ЗЫ: я так к это "фиче" привык, что уже забыл про нее. Когда я пишу
шаблоны, то в cpp всегда ставлю явное их инстанцирование.
--
С уважением,
Alex Besogonov (alexy@izh.com)
Posted via RSDN NNTP Server 1.9
Sapienti sat!
Re[7]: Theory and Techniques of Compiler Construction
Здравствуйте, McSeem2, Вы писали:
MS>А все началось с того, что в C++ разрешили использование сущностей вперед их декларации...
С точки зрения разборщика это не такая уж и сложная задача. Есть несколько решений как разбирать классы. Мне наиболее удобным кажется решение отделить семантический анализ от синтаксического. Т.е. сначала пройти по классу, разобрать его синтаксически, т.е. построить дерево вывода, а затем уже по этому дереву пройтись семантическим анализатором с поиском имен т.д. Понятно, что в этом случае взять и в лоб использовать бизон не получается, надо чуть более хитрую программу писать. Но, принципиально, ничего сложного в этом нет. В случае шаблонов сложность разбора повышается, т.к. с поиском имен еще больше проблем. Сам я компилятор си++ не писал, но судя по высказыванием людей, которые это делали, есть две больших проблемы:
1. Грамматика си++ не укладывается в прокрустово ложе LR(k)-анализатора. Конечно, можно попытаться перенести многие свойства грамматики на уровень ручного кодирования — "семантический анализ". Но, оказывается, для си++ слишком много приходится переносить, очень неудобно и нехорошо. Поэтому, опытные люди пишут компилятор для си++ вручную, т.е. такой расширенный LL(k)-парсер с откатами, или при помощи более продвинутых алгоритмов синтаксического анализа, таких как GLR. Недавно в юзенет конференции, посвященной компиляции, развернулась дискуссия на эту тему. Айра Бакстер, архитектор компании Семантик Дизайн, рассказала, что их компилятор си++, как и многих других языков, реализован с помощью GLR генератора, написанного ими же. И никаких проблем с реализацией они не имели. Автор этого топика имел дискуссию с самим Квином Тайлером Джексоном относительно того, какую часть языка выражать грамматикой, а какую передавать в "семантический анализ". Квин отстаивал формальный подход, основанный на традиции, а я уговаривал его, что здесь не должно быть никаких правил, кроме одного — удобства программирования. Если мне удобно перенести какую-то часть языка в "скмантику", то я просто это и делаю, а остальную реализовываю посредством формальных грамматик. Хочется надеяться, что он меня услышал. В общем, для си++ удобно иметь синтаксический анализатор, который в состоянии разобрать ту грамматику, которая прописана в стандарте. Построение другой грамматики — это уже уступка прихотям конкретного генератора разборщика.
2. Пространства имен в си++ очень сложны и не укладываются в рамки простого "монитора". Для реализации, вероятно, это самая сложная вещь. Кроме текущей таблицы, связанной с данной областью видимости, подключаются еще другие таблицы, через декларацию using или поиск, зависящий от аргументов функции. Ну там еще куча проблем. В принципе, и здесь ничего сверх сложного нет, просто надо использовать нестандартные методы, которые в книжке Вирта не описаны. Но тем, по моему мнению, и интереснее.
Re[8]: Theory and Techniques of Compiler Construction
A>>PS Кстати по результату пролистыванияне осталось впечатления что книга очень уж простая и сугубо практическая F>У меня есть такая. Кому надо — вышлю по запросу в мыло. Объем 1.2 Мб в zip
Если можешь, то шли на eroshkin<собака>ispras.ru .
Душа обязана трудиться! (с) Н.Заболоцкий.
Re[5]: Theory and Techniques of Compiler Construction
Здравствуйте, VladD2, Вы писали:
VD>Ну, трешка похоже просто будет практически идеальным построителем парсеров. А 2.х просто довольно мощьный продукт. А есть там много чего. Декларативное заглядывание вперед (правда становится не актуальным в следующей версии). Декларативное построение АСТ. EBNF. Автоматическое пуравление памятью (ну, это скорее Ява себя проявляет).
Это-то да. Но я спрашивал в свете недавнего обсуждения возможности раширения LL(k)-анализатора так, чтобы он имел возможно разбирать параллельно альтернативы, даже если они не укладываются в LL(k) для любого, сколь угодно большого k. Кто-то, не помню кто, дал ссылку на третью версию ANTLR. Я пошел по ссылке, прочитал кучу блогов, но сумел вынести оттуда только одно: ничего про параллельный разбор там нет и единственное улучшение — это использование регулярных выражений в предосмортрах. Идея это не новая, придумана была еще в 60-х годах. Суть ее такова: вместо использования конкретной строки длиной 1 или два символа в качестве предосмотра, использовать класс строк, вводимых с помощью регулярных выражений. Как известно, в LL(k)-анализе практически единственным способом различений контекста является исползование предосмотров. Например, в грамматике
A --> B | C
B --> NUMBER D
C --> STRING D
мы можем выбрать, какую альтернативу для разбора символа A использовать, заглянув на один симовл вперед. Если этот символ есть NUMBER, то выбираем A --> B, если STRING, то выбираем A --> C, если ни то ни другое — возвращаем ошибку. Проблема возникает, когда мы имеем грамматику типа
A --> B | C
B --> NUMBER D
C --> NUMBER D
D --> STRING E
D --> '+' E
Здесь уже LL(1) не подойдет, надо знать два символа впереди, чтобы различить альтернативы A --> B и A --> C. Так вот, а если попытаться вместо конкреных строк предостмотров использовать регулярные выражения как множество строк? Было бы удобно, хотя совершенно не увеличило бы мощность разборщика. Кроме того, сами правила тоже можно представить посредством регулярного выражения, т.е. автомата, и, тем самым, улучшить скорость разборщика. Конечно, надо еще, чтобы сами правила имели такой, "регулярный" вид. Я, конечно, могу ошибаться, просмотрел документы по ссылкам мельком и мог неправильно понять, но улучшения синтаксического анализатора я там не увидел. Вообще, наряду я вненсениям последних достижений теории компиляции в генератор, разработчики ANTLR не хотят использовать последние достижения в области синтаксического анализа. Это, несомненно, обедняет систему. Класс языков, который может быть разобран с помощью этого инструмента, сейчас уже совершенно неудовлетворителен.
Re[2]: Theory and Techniques of Compiler Construction
Здравствуйте, andyJB, Вы писали:
JB>Судя по контенту, довольно поверхностно. К тому же затронуты не самые интересные темы — Мучник, имхо, в качестве референса пополезнее будет. В общем, книжка студентам 1-3 курса.
Енто что такое ?
Re[3]: Theory and Techniques of Compiler Construction
Здравствуйте, Aviator, Вы писали:
JB>>Судя по контенту, довольно поверхностно. К тому же затронуты не самые интересные темы — Мучник, имхо, в качестве референса пополезнее будет. В общем, книжка студентам 1-3 курса.
A>Енто что такое ?
Библия специалистов по генерации кода.
Re[8]: Theory and Techniques of Compiler Construction
Здравствуйте, fplab, Вы писали:
F>Здравствуйте, Aviator, Вы писали:
A>>Здравствуйте, mefrill, Вы писали:
M>>>Здравствуйте, Aviator, Вы писали:
A>>>>Часом не DICK GRUNE, CERIEL JACOBS "PARSING TECHNIQUES" ? Если не эта приведите пожалуйста ссылочку Очень интересно было бы ознакомится .
M>>>Ага, та самая.
A>>К большому сожалению так и не читал эту книжку, хотя давно уже валяется Выс считаете что стоящая книга и если заниматься компиляторами то необходимо прочитать ?
A>>PS Кстати по результату пролистыванияне осталось впечатления что книга очень уж простая и сугубо практическая F>У меня есть такая. Кому надо — вышлю по запросу в мыло. Объем 1.2 Мб в zip
заранне большущее спасибо — qrilka (at) gmail.com
Re[4]: Theory and Techniques of Compiler Construction
Здравствуйте, eao197, Вы писали:
E>В общих словах ANTLR -- это генератор нисходящих парсеров для LL(1) грамматик.
В том то и дело что не LL(1), а LL(k), причем с большим k (3-8) — используется эвристика которая позволяет уменьшить
сложность предпросмотра.Где-то на сайте можно найти диссертацию автора целиком по этой теме.
Re[6]: Theory and Techniques of Compiler Construction
Здравствуйте, Павел Кузнецов, Вы писали:
ПК>Гм... Мне лень лезть в спецификацию всевозможных оберонов... Предлагаю поверить в этом Сергею Губанову. Он утверждает
, что для использования класса в Обероне, предварительное объявление не требуется.
В Обероне определение класса разделено на две части: сначала описывается тип записи, а потом описываются процедуры связанные с этим типом.
Более того:
1) Сначала полностью описываются все типы, а уже потом описываются все процедуры. Вперемешку нельзя. (Хотя некоторым это не очень нравится. Так, например, Трурль "подкрутил чуток" компилятор BlackBox-а и сделал возможным писать типы и процедуры вперемешку.)
2) Для использования еще не определенных процедур требуется их предварительное объявление.
MODULE Test;
TYPE
Bar = POINTER TO RECORD
foo: Foo
END;
Foo = RECORD
bar: Bar
END;
(* Предварительное объявление процедуры DoAnother связанной с типом Bar (т.е. метода) *)PROCEDURE^ (this: Bar) DoAnother (x: INTEGER), NEW;
(* Определения связанных процедур: *)PROCEDURE (VAR this: Foo) DoSomthing (x: INTEGER), NEW;
BEGIN
this.bar.DoAnother(x + 1) (* Вызов еще не определённой, но уже продекларированной процедуры *)END DoSomthing;
PROCEDURE (this: Bar) DoAnother (x: INTEGER), NEW;
BEGIN
this.foo.DoSomthing(x - 1)
END DoAnother;
END Test.
Re[5]: Theory and Techniques of Compiler Construction
Здравствуйте, Aviator, Вы писали:
A>А подробнее можно ?
Ну, знаменитая книжка по генерации кода. Можно купить здесь. Как известно, разработка компиляторов делится на две части: разработка фронтэндов и разработка бэкэндов. Фронтэнд обычно рзрабатывается для языка в единственном числе и компилирует программный код в промежуточное представление, обычно дерево кода программы + таблицы символов и типов. Затем строятся компиляторы этого представления в машинные языки. Язык программирования один, а платформ много. Поэтому и бэкэндов должно быть много, а фронтэнд только один. Процесс построения бэкэнда и называется генерацией код. Это сама по себе сложная наука: анализа потоков данных, оптимизация и т.д. В 80-х годах была построена теория генерации кода и сейчачс активно используется. Поэтому, потребность в специалистах по построению бэкэндов существенно превышает потребность в спецах по фронтэндам. Книжка Мучника — это подробный справочник и учебник по построению бэкэнда, примерно тоже самое, что красный дракон для фронтэндов.
Re[6]: Theory and Techniques of Compiler Construction
Здравствуйте, mefrill, Вы писали:
M>Здравствуйте, Aviator, Вы писали:
A>>А подробнее можно ?
M>Ну, знаменитая книжка по генерации кода. Можно купить здесь. Как известно, разработка компиляторов делится на две части: разработка фронтэндов и разработка бэкэндов. Фронтэнд обычно рзрабатывается для языка в единственном числе и компилирует программный код в промежуточное представление, обычно дерево кода программы + таблицы символов и типов. Затем строятся компиляторы этого представления в машинные языки. Язык программирования один, а платформ много. Поэтому и бэкэндов должно быть много, а фронтэнд только один. Процесс построения бэкэнда и называется генерацией код. Это сама по себе сложная наука: анализа потоков данных, оптимизация и т.д. В 80-х годах была построена теория генерации кода и сейчачс активно используется. Поэтому, потребность в специалистах по построению бэкэндов существенно превышает потребность в спецах по фронтэндам. Книжка Мучника — это подробный справочник и учебник по построению бэкэнда, примерно тоже самое, что красный дракон для фронтэндов.
А в электронном виде книжка существует ?
Re[7]: Theory and Techniques of Compiler Construction
Здравствуйте, Cyberax, Вы писали:
>> C>Вообще-то VC7.1 почти полностью совместим со Стандартом, и диагностика >> C>ошибок в шаблонах — вполне нормальная. Когда я переносил свой проект, >> C>который писался полгода, на GCC — проблем с шаблонам не возникло (а >> их у >> C>меня там мнооого). >> VC7.1 страдает практически такой же болезнью, что и VC6 — он не толком >> не проверяет синтаксис шаблонов до момента их реального использования. >> При написании библиотек это создает проблемы. Даже отсутствие >> банальной ";" в нужном месте — пропускает. GCC и Intel — диагностируют >> нормально.
C>Однако, когда шаблоны все-таки инстанцируются, то происходит полная C>проверка.
C>ЗЫ: я так к это "фиче" привык, что уже забыл про нее. Когда я пишу C>шаблоны, то в cpp всегда ставлю явное их инстанцирование.
Есть еще одна очень большая засада в VC7.1 — не поддерживается полноценный two phase name lookup. Проблема эта, кстати, частично связана и с предыдущей — отутствием синтаксической проверки шаблонов до момента инстанцирования. Это создает видимость нормальной работы на VC7.1, но такой код не будет компилироваться ни GCC, ни Intel C++, ни Comeau. Когда первый раз столкнулся — очень неприятно было.
... << RSDN@Home 1.1.4 stable rev. 510>>
Re[8]: Theory and Techniques of Compiler Construction
CrystaX wrote:
> Есть еще одна очень большая засада в VC7.1 — не поддерживается > полноценный two phase name lookup. Проблема эта, кстати, частично > связана и с предыдущей — отутствием синтаксической проверки шаблонов > до момента инстанцирования. Это создает видимость нормальной работы на > VC7.1, но такой код не будет компилироваться ни GCC, ни Intel C++, ни > Comeau. Когда первый раз столкнулся — очень неприятно было.
Мне хватает SFINAE, двухфазный лукап я не использую.
--
С уважением,
Alex Besogonov (alexy@izh.com)
Posted via RSDN NNTP Server 1.9
Sapienti sat!
Re[16]: Theory and Techniques of Compiler Construction
Проскакивало что-то подобное, по-моему, для шаблонов, в комитетских бумагах...
M> же застрелиться можно иногда. А заставлять писать все внутри класса - M> вообще маздай. Совешенно невозможно охватить общую картину вглядом. А в M> Java и C# это возведено в степень догмы.
+1
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Re[11]: Theory and Techniques of Compiler Construction
McSeem2,
M> А вообще, мысль такова. Вот придумали C++. И все-таки стараются где-то M> как-то предоставить адекватные средства. Это очень сложно в силу M> сложности самого языка. Но GCC, например — уже вполне достойный M> компилятор с точки зрения стандарта. Да, не полный, но один из наилучших M> доступных и пригодных на практике. А MS любит перекладывать свою M> головную боль на пользователей. И делают они это очень умело.
Думаю, не стоит быть столь категоричным. Во всех перечисленных случаях причины более-менее
одни и те же: нужды пользователей. Соответственно, имевшиеся пользователи и определяли приоритеты
разработчиков тех или иных компиляторов. Просто "главные" клиенты у них были разными. В случае MS
это были крупные корпорации, для которых обратная совместимость с тоннами имеющегося у них кода,
качество оптимизации, отладчика и поддержка взаимодействия со всевозможными визуальными бэйсиками
и т.п. были намного более важными, чем соответствие стандарту.
Сейчас приоритеты MS сильно меняются, т.к. удельный вес "мелких" клиентов растет. Соответственно,
меняются и задачи в разработке компилятора. Соответствие стандарту становится более важным, и MS
вкладывает серьезные средства в достижение этой задачи. Но это достаточно нелегко, учитывая что
остальные приоритеты также вовсе не исчезают.
.
M> Apple очень серьезно работает над внешним дизайном приложений. Настолько
Я не большой поклонник usability в исполнении Apple. Порой они настолько "think different",
что их логику я просто перестаю чувствовать. Но что красиво, то красиво -- это есть.
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Re[6]: Theory and Techniques of Compiler Construction
Здравствуйте, mefrill, Вы писали:
M>Здравствуйте, Aviator, Вы писали:
A>>А подробнее можно ?
M>Ну, знаменитая книжка по генерации кода. Можно купить здесь. Как известно, разработка компиляторов делится на две части: разработка фронтэндов и разработка бэкэндов. Фронтэнд обычно рзрабатывается для языка в единственном числе и компилирует программный код в промежуточное представление, обычно дерево кода программы + таблицы символов и типов. Затем строятся компиляторы этого представления в машинные языки. Язык программирования один, а платформ много. Поэтому и бэкэндов должно быть много, а фронтэнд только один. Процесс построения бэкэнда и называется генерацией код. Это сама по себе сложная наука: анализа потоков данных, оптимизация и т.д. В 80-х годах была построена теория генерации кода и сейчачс активно используется. Поэтому, потребность в специалистах по построению бэкэндов существенно превышает потребность в спецах по фронтэндам. Книжка Мучника — это подробный справочник и учебник по построению бэкэнда, примерно тоже самое, что красный дракон для фронтэндов.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, Шахтер, Вы писали:
Ш>>Компиляторы пишут не по книжкам (за исключением самых простых языков).
VD>Ты тему читашь целиком или выборочно?
VD>Вот это
Здравствуйте, mefrill, Вы писали:
M>Это-то да. Но я спрашивал в свете недавнего обсуждения возможности раширения LL(k)-анализатора так, чтобы он имел возможно разбирать параллельно альтернативы, даже если они не укладываются в LL(k) для любого, сколь угодно большого k. Кто-то, не помню кто, дал ссылку на третью версию ANTLR. Я пошел по ссылке, прочитал кучу блогов, но сумел вынести оттуда только одно: ничего про параллельный разбор там нет и единственное улучшение — это использование регулярных выражений в предосмортрах. Идея это не новая, придумана была еще в 60-х годах.
Я не знаю, что ты там смотрел, но в 3-шке точно соврешенно будет так называемый LL(*) или LL(STAR) (как там написано специльно для гугля, жаль он об этом не знает ). Так вот может он и не реализован как параллельный просмотр, но тем не менее эффект дает точно такой же (не знаю уж как со скоростью, но по сути точно). Там есть пример LL-star. В нем как раз демонстрируется фишка не доступная LL(k)-анализу:
grammar SimpleC;
program
: declaration+
;
/** In this rule, the functionHeader left prefix on the last two
* alternatives is not LL(k) for a fixed k. However, it is
* LL(*). The LL(*) algorithm simply scans ahead until it sees
* either the ';' or the '{' of the block and then it picks
* the appropriate alternative. Lookhead can be arbitrarily
* long in theory, but is <=10 in most cases. Works great.
* Use ANTLRWorks to see the lookahead use (step by Location)
* and look for blue tokens in the input window pane. :)
*/
declaration
:
variable
| functionHeader ';'
{System.out.println($functionHeader.name+" is a declaration");}
| functionHeader block
{System.out.println($functionHeader.name+" is a definition");}
;
variable
: type declarator ';'
;
declarator
: ID
;
functionHeader returns [String name]
init
{
name = null; // for now you must init here rather than in "returns"
}
: type ID '(' ( formalParameter ( ',' formalParameter )* )? ')'
{$name = $ID.text;}
;
formalParameter
: type declarator
;
...
M>Здесь уже LL(1) не подойдет, надо знать два символа впереди, чтобы различить альтернативы A --> B и A --> C. Так вот, а если попытаться вместо конкреных строк предостмотров использовать регулярные выражения как множество строк? Было бы удобно, хотя совершенно не увеличило бы мощность разборщика. Кроме того, сами правила тоже можно представить посредством регулярного выражения, т.е. автомата, и, тем самым, улучшить скорость разборщика. Конечно, надо еще, чтобы сами правила имели такой, "регулярный" вид.
В том, то и дело, что правила должны быть обычными, а не регулярными. Незнаю уж почему, но все виданные мной построители парсеров были ХХ(k), т.е. не пасовали на граматиках вроде приведенной выше. А написать предпросмотр для сложных случаев очень не просто. Например, в C# есть контексно-зависимые ключевые слова. Например, слово "partial" может встречаться как идентификатор где угодно и как ключевое слово в ряду модификаторов перед классом или структурой. Было бы так приятно написать нечто вроде:
и т.п. А не заниматься программно апаратным анонизмом обходя проблемы парсеров.
Заметь "partial" пересекается в Type (так как он содержит Ident) и в модификаторов некоторых объявления типов.
Как я понимаю без параллельного сканирования есть только один шанс построить LL(*)-парсер. Нужно выделять дублирующиеся ветви и находить места где граматика различается. В приведенном выше примере это ключевые слова "class", "interface"
M> Я, конечно, могу ошибаться, просмотрел документы по ссылкам мельком и мог неправильно понять, но улучшения синтаксического анализатора я там не увидел. Вообще, наряду я вненсениям последних достижений теории компиляции в генератор, разработчики ANTLR не хотят использовать последние достижения в области синтаксического анализа. Это, несомненно, обедняет систему. Класс языков, который может быть разобран с помощью этого инструмента, сейчас уже совершенно неудовлетворителен.
Мне кажется ты не в теме. Единственный парсер который без костылей позволяет парсить С++ на сегодня является именно АНТЛР. У него куча своих проблем, но тем не менее. Что же до достижений, то единственное что я хотел бы видеть это отсуствие необходимости обходить проблемы парсера при приемлеомй производительности. А будет ли это сделано параллельным парсингом или как-то иначе в общем-то по фигу.
Будем надеяться, что в трешки создатели АНТЛР-а исправят недостатки и таки сделают то что нужно.
... << RSDN@Home 1.2.0 alpha rev. 578>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: Theory and Techniques of Compiler Construction
Здравствуйте, VladD2, Вы писали:
Ш>>У меня такое ощущение, что ты вообще не читаешь сообщения. VD>У меня почуме-то такое же ощущение, но от твоих сообщения.
Ну вы, блин, даете... Любофф?
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re[7]: Theory and Techniques of Compiler Construction
VD>Я не знаю, что ты там смотрел, но в 3-шке точно соврешенно будет так называемый LL(*) или LL(STAR) (как там написано специльно для гугля, жаль он об этом не знает ). Так вот может он и не реализован как параллельный просмотр, но тем не менее эффект дает точно такой же (не знаю уж как со скоростью, но по сути точно). Там есть пример LL-star. В нем как раз демонстрируется фишка не доступная LL(k)-анализу:
Ага, посмотрел я, что такое этот самый LL(*). Нашел презентацию здесь. Так вот, я ошибался, когда писал про то, что разборщик в третьей версии — это тоже самое, что и разборщик второй, только вместо множеств предосмотров используется конечный автомат для описания этих самых множеств. Формально я был прав, но по сути там необходимо было сделать следующий шаг в рассуждении и начать строить автомат и для нетерминальных символов. Иначе ничего путного не выйдет. Идея там совсем простая: вместо алгоритма явного вызова функций, соответствующих правилам грамматики в коде сгененрированного разборщика, строится детерминированный конечный автомат, переходы между состояниями которого есть символы грамматики, причем как терминальные, так и нетерминальные. Простой пример:
A --> B C
B --> b
C --> c
строим для него недетерминированный автомат:
|1| -B-> |2| -C-> |3 успех для правила A --> B C|
|4| -b-> |5 успех для правила B --> b|
|6| -c-> |7 успех для правила C --> c|
По этому автомату строим детерминированный автомат и парсим, используя стек вызовов функций для того, чтобы делать переходы по символу в левой части правила, когда мы распарсили это правило. В данном случае, из состояния номер 5 мы перейдем в состояние 2, тот же переход будет из состояния 7 в состояние 3, а из состояния 2 в состояние 6.
Короче, LR-автомат, только для для LL-анализа. Те же проблемы появляются и для LL-автомата. Например, невозможность обработки правил с пустой правой частью. Или "узость" класса грамматик, которые данный автомат может обрабатывать. Самое интересное, что сам алгоритм был придуман еще в 60-х годах известным авторитетом в области семантики языков (естественных, не программистких) Владимиром Борисовичем Борщевым. Ссылку на работу дать не могу, ибо получил эти сведения также изустно от самого В. Б. Борщева. Этот алгоритм был темой его кандидатской диссертации в далеких 60-х годах и рассказал о нем мне Борщев, в общем-то, случайно. Я ему представлял свою работу, он воодушевился, вспомнил молодость и рассказал. Кто-то там по этому поводу диссертацию защитил?! Ну вот, глядишь, лет через пятьдесят еще кто-нибудь защитит.
VD>Мне кажется ты не в теме. Единственный парсер который без костылей позволяет парсить С++ на сегодня является именно АНТЛР. У него куча своих проблем, но тем не менее. Что же до достижений, то единственное что я хотел бы видеть это отсуствие необходимости обходить проблемы парсера при приемлеомй производительности. А будет ли это сделано параллельным парсингом или как-то иначе в общем-то по фигу.
Вот здесь я как раз сильно сумлеваюсь. Нет, не по тому вопросу, что я не в теме , а относительно следующего:
Единственный парсер который без костылей позволяет парсить С++ на сегодня является именно АНТЛР
Здесь два утверждения:
1. АНТЛР позволяет парсить си++ "без костылей".
2. Он такой единственный.
В общем, я не согласен ни с первым, ни, тем-более, со вторым утверждением. Если интересно, можем обсудить подробно почему.
Скажу только, что анализатор, который находит неоднозначность там где ее в действительности нет (а предмет нашего обсуждения таковой есть), не является на данный момент удовлетворительным.
Re[8]: Theory and Techniques of Compiler Construction
Здравствуйте, mefrill, Вы писали:
M>Ага, посмотрел я, что такое этот самый LL(*). Нашел презентацию здесь. Так вот, я ошибался, когда писал про то, что разборщик в третьей версии — это тоже самое, что и разборщик второй, только вместо множеств предосмотров используется конечный автомат для описания этих самых множеств. Формально я был прав, но по сути там необходимо было сделать следующий шаг в рассуждении и начать строить автомат и для нетерминальных символов. Иначе ничего путного не выйдет. Идея там совсем простая: вместо алгоритма явного вызова функций, соответствующих правилам грамматики в коде сгененрированного разборщика, строится детерминированный конечный автомат, переходы между состояниями которого есть символы грамматики, причем как терминальные, так и нетерминальные.
Дык это практически тоже самое что педлагал я, только вид сбоку. По сути идея то одна. Вместо того, чтобы тупо разбирать граматику до первой неопределенности начинать разбирать ее и дальше в несколько веток. Понятно, что такой параллельный разбор в нескольких направлениях не имеет право выполнять никаких семантических действий до тех пор пока не сделает вывод о корректности каждой из ветвей. Ну, а реализация этого может быть разрой. Это можно сделать на конечном автомате и последовательном вызове его для каждого варианта при неоднозначности, а может быть использование фичи вроде continuations или fibers и дублированием процедур спуска (один набор реальный с семантическими действиями, а второй функции-пустышки цель которых только ответить на вопрос можно ли заробрать код по данному правилу).
M>Короче, LR-автомат, только для для LL-анализа.
Не, LR-ом его назвать я бы не решился. Автомат — да. Но не магазинный. На самом деле АНТЛР не первый парсер использующий автомат для LL(k). CocoR, которым я пользуюсь, испоьзует ДКА для LL(1) анализа. Как не странно, но это дает приемущества. Во-первых, это позволяет отлавливать LL(1)-конфликты на уровне граматики. А, во-вторых, позволяет свести все проврки к одному обращению к таблице.
M> Те же проблемы появляются и для LL-автомата. Например, невозможность обработки правил с пустой правой частью.
Откуда ты это взял? Не появляется там никаких проблем. Более того исчезает проблема левой рекурсии.
M> Или "узость" класса грамматик, которые данный автомат может обрабатывать.
Еще раз, откуда ты это взял? Проблемы LALR(k) парсеров заключаются в том, что они нарываются на конфликт и не знают по какому правилу производить свретку. В GLR этих проблем вроде бы нет. Вместо неоднозначности появляются два варианта. Но у GLR опять таки присуствуют все проблемы LALR-парсеров. Првда, и тут можно делать предвычисление пути и потом просто вызывать семантику так как будто это LL-парсер.
M> Самое интересное, что сам алгоритм был придуман еще в 60-х годах известным авторитетом в области семантики языков (естественных, не программистких) Владимиром Борисовичем Борщевым. Ссылку на работу дать не могу, ибо получил эти сведения также изустно от самого В. Б. Борщева.
Откровенно говоря для меня явлось загадкой то, что до распараллеливания парсеров или до ветвления автоматов не додумались еще когда в первый раз столкнулись с проблемами парсинга сложных языков. Тот же С++ по сей день вяляется неподемной задачей. А ведь такие парсеры должны не просто позволять парсить такие граматики, но делать это цинично просто. Что же о Борщева... Ну, не знаю. Если это правда, то он очень странный человек. Мог бы хотя бы описать идею где-нибудь. А без этого его первенство не стоит и ломанного гроша. К тому же весма странно, что найдя решение такой болезненной проблемы ни он, ни кто другой не попытался создать рельный парсер демонстрирующий приемущества алгоритма.
M>Этот алгоритм был темой его кандидатской диссертации в далеких 60-х годах и рассказал о нем мне Борщев, в общем-то, случайно. Я ему представлял свою работу, он воодушевился, вспомнил молодость и рассказал. Кто-то там по этому поводу диссертацию защитил?! Ну вот, глядишь, лет через пятьдесят еще кто-нибудь защитит.
Мог бы и опубликовать свою диссертацию в интернете.
M>Вот здесь я как раз сильно сумлеваюсь. Нет, не по тому вопросу, что я не в теме , а относительно следующего: M>
M>Единственный парсер который без костылей позволяет парсить С++ на сегодня является именно АНТЛР
M>Здесь два утверждения: M>1. АНТЛР позволяет парсить си++ "без костылей". M>2. Он такой единственный.
M>В общем, я не согласен ни с первым, ни, тем-более, со вторым утверждением. Если интересно, можем обсудить подробно почему.
Ну, на счет первого... Уде есть очень приличный парсер С++ на базе АНТЛР-а. Костылей там не замечено, но есть одна проблема. Он сделан на порте АНТЛР-а на С++. А вот это уже без проблем сделать не удалось. АНТЛР версии 2.х использует банальные заглядывания вперед и откаты. Причем откаты для простоты реализации делаются на исключениях. В Яве с ее автоматическим управлением памятью проблем не возникает. А вот в С++ с этим полный кирдык. Течет эта реализация по страшному. Так что в коммерческих приложениях такой парсер вряд ли применим.
На счет п. 2. ... Да, я тут не прав. Есть эксперементальные парсеры GLR, но я так и не нашел ни одного места где бы можно было на них взглянуть во очую. Если ты знашь такие места, то дай, плиз, ссылку.
Из известных мне парсеров С++ обеспечивающих приемлемое качество почти все или писаны вручную, или используют "костыли" в виде рукопашного кода использующего фичи парсера (например, тот же GCC).
M>Скажу только, что анализатор, который находит неоднозначность там где ее в действительности нет (а предмет нашего обсуждения таковой есть), не является на данный момент удовлетворительным.
А откуда ты взял, что он находит эти неоднозначности? Может я что-то пропустил?
... << RSDN@Home 1.2.0 alpha rev. 578>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[9]: Theory and Techniques of Compiler Construction
Здравствуйте, VladD2, Вы писали:
VD>Дык это практически тоже самое что педлагал я, только вид сбоку. По сути идея то одна. Вместо того, чтобы тупо разбирать граматику до первой неопределенности начинать разбирать ее и дальше в несколько веток. Понятно, что такой параллельный разбор в нескольких направлениях не имеет право выполнять никаких семантических действий до тех пор пока не сделает вывод о корректности каждой из ветвей. Ну, а реализация этого может быть разрой. Это можно сделать на конечном автомате и последовательном вызове его для каждого варианта при неоднозначности, а может быть использование фичи вроде continuations или fibers и дублированием процедур спуска (один набор реальный с семантическими действиями, а второй функции-пустышки цель которых только ответить на вопрос можно ли заробрать код по данному правилу).
Нет, совсем не тоже самое, что ты предлагал. Предлагаю сначала еще раз внимательно посмотреть эту презентацию, построить примеры и затем продолжить дискуссию. То, о чем ты говоришь, называется разборщик с откатами и это совесем не тоже самое, что параллельный разборщик. В АНТЛР нет ни того, не другого. Парсер выбирает альтернативу совершенно случайным образом, основываясь на нименьшем номере продукции, учавствующей в конфликте. Вот тебе пример
A --> B c | B
Попытайся построить для него разборщик по методу АНТЛР 3 и посмотри, что получится. АНТЛР использует так называемый семантический предикат, чтобы разделять состоянии, которые дают неоднозначности при LL-анализе. Все это есть в том документе, надо внимательнее читать.
M>>Короче, LR-автомат, только для для LL-анализа.
VD>Не, LR-ом его назвать я бы не решился. Автомат — да. Но не магазинный. На самом деле АНТЛР не первый парсер использующий автомат для LL(k). CocoR, которым я пользуюсь, испоьзует ДКА для LL(1) анализа. Как не странно, но это дает приемущества. Во-первых, это позволяет отлавливать LL(1)-конфликты на уровне граматики. А, во-вторых, позволяет свести все проврки к одному обращению к таблице.
Почему ж это не магазинный??? Как раз таки совершенно магазинный. Посмотри загадочные $ в описаниях состояний ДКА.
M>> Те же проблемы появляются и для LL-автомата. Например, невозможность обработки правил с пустой правой частью.
VD>Откуда ты это взял? Не появляется там никаких проблем. Более того исчезает проблема левой рекурсии.
Блин. Еще раз
A --> B C
B -->
C --> c
построй автомат. Относительно левой рекурсии, это я хочу тебя спросить: откуда ты это взял??? Ну давай возмем леворекурсивную грамматику
A --> A
A --> a
и построим для нее автомат.
|A --> * A| -A-> |A --> A *|
|A --> * a| -a-> |A --> a *|
имеем вход a. Как будем разбирать? Прочитали символ a из входа, положили его на стек. Далее, читаем символ из стека, это a, значит переход из |A --> * a| в |A --> a *|. Кладем символ A на стек и ищем переходы из начального состояния. Это переход в состояние |A --> A *|, переходим в состояние |A --> A *| , кладем символ A на стек и возвращаемся в начальное состояние. Отттуда снова переход по символу A и т.д. Зациклились. Вот тебе и проблема с левой рекурсией.
M>> Или "узость" класса грамматик, которые данный автомат может обрабатывать.
VD>Еще раз, откуда ты это взял? Проблемы LALR(k) парсеров заключаются в том, что они нарываются на конфликт и не знают по какому правилу производить свретку. В GLR этих проблем вроде бы нет. Вместо неоднозначности появляются два варианта. Но у GLR опять таки присуствуют все проблемы LALR-парсеров. Првда, и тут можно делать предвычисление пути и потом просто вызывать семантику так как будто это LL-парсер.
Ну так вот, что такое этот конфликт ты задумывался? Это не обязательно неоднозначность. Грамматика может быть воплне себе однозначной, но для нее невозможно будет построить ни LR, ни LL автомат. Т.е. для человека грамматика разбирается очень даже определенно, а АНТЛР или Бизон не может. В этом и проблема.
M>> Самое интересное, что сам алгоритм был придуман еще в 60-х годах известным авторитетом в области семантики языков (естественных, не программистких) Владимиром Борисовичем Борщевым. Ссылку на работу дать не могу, ибо получил эти сведения также изустно от самого В. Б. Борщева.
VD>Откровенно говоря для меня явлось загадкой то, что до распараллеливания парсеров или до ветвления автоматов не додумались еще когда в первый раз столкнулись с проблемами парсинга сложных языков. Тот же С++ по сей день вяляется неподемной задачей. А ведь такие парсеры должны не просто позволять парсить такие граматики, но делать это цинично просто. Что же о Борщева... Ну, не знаю. Если это правда, то он очень странный человек. Мог бы хотя бы описать идею где-нибудь. А без этого его первенство не стоит и ломанного гроша. К тому же весма странно, что найдя решение такой болезненной проблемы ни он, ни кто другой не попытался создать рельный парсер демонстрирующий приемущества алгоритма.
До всех этих проблем додумались и все их решили еще в конце 50-х годов прошлого века. Сначал были построены алгоритмы разбора языка, заданного любой грамматикой без ограничений, а только потом были придуманы методы с линейным временем анализа. С точки зрения математика эти методы ничего не стоят, а только сужают класс языков, к которым можно применить данный алгоритм. Поэтому, все эти игры, сначала построить линейный метод, например, LL-анализатор, а затем его немножко расширить, для математика не имеют совершенно никакого смысла. В нашем случае, они ВООБЩЕ смысла не имеют. Что же касается Борщева, то этот человек сделал все как надо, а именно, опубликовал свои работы в специально предназначенных для этого реферативных журналах. И не его вина, что человек, который по этой теме диссертацию защищал, не удосужился в эти журналы заглянуть. Впрочем, как и его руководитель. Меня мало интересует алгоритм, опубликованный в интернете, если он не подкреплен соответствующим анализом производительности и доказательством корректности работы. При этом, мне еще важно, что эту публикацию до меня изучали специалисты и не нашли в ней ошибок. Для этого и существуют реферативные журналы. Борщев же сейчас занимается совсем другими проблемами, на порядок более сложными и интересными. И вряд-ли ему есть дело до некоего билагейтса от компиляции, на рекламу поделок которого кое-кто (не будем показывать пальцем, но это слоник) сильно ведется.
M>>Этот алгоритм был темой его кандидатской диссертации в далеких 60-х годах и рассказал о нем мне Борщев, в общем-то, случайно. Я ему представлял свою работу, он воодушевился, вспомнил молодость и рассказал. Кто-то там по этому поводу диссертацию защитил?! Ну вот, глядишь, лет через пятьдесят еще кто-нибудь защитит.
VD>Мог бы и опубликовать свою диссертацию в интернете.
Уже написал вверху.
M>>Вот здесь я как раз сильно сумлеваюсь. Нет, не по тому вопросу, что я не в теме , а относительно следующего: M>>
M>>Единственный парсер который без костылей позволяет парсить С++ на сегодня является именно АНТЛР
M>>Здесь два утверждения: M>>1. АНТЛР позволяет парсить си++ "без костылей". M>>2. Он такой единственный.
M>>В общем, я не согласен ни с первым, ни, тем-более, со вторым утверждением. Если интересно, можем обсудить подробно почему.
VD>Ну, на счет первого... Уде есть очень приличный парсер С++ на базе АНТЛР-а. Костылей там не замечено, но есть одна проблема. Он сделан на порте АНТЛР-а на С++. А вот это уже без проблем сделать не удалось. АНТЛР версии 2.х использует банальные заглядывания вперед и откаты. Причем откаты для простоты реализации делаются на исключениях. В Яве с ее автоматическим управлением памятью проблем не возникает. А вот в С++ с этим полный кирдык. Течет эта реализация по страшному. Так что в коммерческих приложениях такой парсер вряд ли применим.
Вот что значит "отличный парсер"??? Я видел "отличный парсер", написанный на бизоне. Видел "отличный парсер", написанный вообще вручную. Что такое "отличный парсер"? Вопрос здесь не в невозможности с помощью данного инструмента написать парсер для того или иного языка, а легкостью этого написания. Относительно языка си++ или явы даже не хочу разговаривать, а то в священные войны загремим. Но, мое мнение такое: и на си++ и на яве и на сишарпе можно написать хороший, без утечек и быстрый разборщик.
VD>На счет п. 2. ... Да, я тут не прав. Есть эксперементальные парсеры GLR, но я так и не нашел ни одного места где бы можно было на них взглянуть во очую. Если ты знашь такие места, то дай, плиз, ссылку.
Нет их, за все денежки надо платить. В этом и разница, хорошая вещь деньги стоит.
VD>Из известных мне парсеров С++ обеспечивающих приемлемое качество почти все или писаны вручную, или используют "костыли" в виде рукопашного кода использующего фичи парсера (например, тот же GCC).
Вот и я о том же. Это просто вопрос удобства какой какой инструмент выбирать. Бизон использовать для си++ стремно, слишком много работы надо делать вручную и грамматику уродовать. По моему мнению, генератор должен позволять построить парсер для той грамматики, которая прописана в стандарте языка. Если там есть неоднозначности то вставить предикат, чтобы на "семантическом уровне", т.е. отталкиваясь от неформального описания в стандарте, разрешить данную неоднозначность. Тогда это будет "хороший парсер". АНТЛР — совсем не такой. M>>Скажу только, что анализатор, который находит неоднозначность там где ее в действительности нет (а предмет нашего обсуждения таковой есть), не является на данный момент удовлетворительным.
VD>А откуда ты взял, что он находит эти неоднозначности? Может я что-то пропустил?
Re[10]: Theory and Techniques of Compiler Construction
Здравствуйте, mefrill, Вы писали:
M>До всех этих проблем додумались и все их решили еще в конце 50-х годов прошлого века. Сначал были построены алгоритмы разбора языка, заданного любой грамматикой без ограничений, а только потом были придуманы методы с линейным временем анализа. С точки зрения математика эти методы ничего не стоят, а только сужают класс языков, к которым можно применить данный алгоритм. Поэтому, все эти игры, сначала построить линейный метод, например, LL-анализатор, а затем его немножко расширить, для математика не имеют совершенно никакого смысла. В нашем случае, они ВООБЩЕ смысла не имеют.
Да все конечно так... с некоторой натяжкой. Теоритически до много додумались еще до появления компьютера. Вот только теория и практически работоспособный алгоритм — это как земля и небо. Что толку с универсального метода разбора с квадратичным алгоритмом? Даже на супер-процессоре он загнется на примерах из обучающих книжек по языку.
Интересно, что в этой презентации упоминается АНТЛР 1.х в котром было что-то крутое (я не разбирался), но дико тормозное.
Как я понимаю в 3-шке достигнуто приемлемое качество разбора с приемлемой скоростью. Мне не нужно разбирать естественные языки на которых могут проявиться гипотетические проблемы описанного алгоритма. Мне нужно разбирать довольно синтаксически-сложные языки современные вроде C# и (возможно) С++. Используя доступные современные парсеры результат получается не очень хорошим. В АНТЛР 2.х я вынужден на каждый чих писать, хотя и декларативные, но инородные заглядывалки вперед, изменять граматику приводя ее к LL(k) с минимальным k и т.п. На CocoR я к тому же обязан разруливать неоднозначности рукописным кодом (плюс еще там есть другие проблемы). LALR-парсеры вроде Яков и других коров тоже нуждаются в костялых. Причем тут как и в КокоР костыли рукопашные, а значит на их создание уходит времени бльше чем на всю граматику.
И все это при разборе довольно однозначной и продуманной граматики C#. Если описание LL(*) соотвествует действительности, то это и есть решение большинства проблем. А что еще нужно?
M> Что же касается Борщева, то этот человек сделал все как надо, а именно, опубликовал свои работы в специально предназначенных для этого реферативных журналах. И не его вина, что человек, который по этой теме диссертацию защищал, не удосужился в эти журналы заглянуть.
Ну, конечно. Все правильно. Сделал работу... засунул ее в дальний угол и сидит себе на кухне почитывает работы других ухмыляяс "а я то до того же 20 лет назад попетрил!...". Как, интересно, может быть доступен малоизвесный реферативный журнал на русском языке тем кто защищался на западе? В чем проблема выложить его работы в Интернет (хотя бы сейчас). Если ты знаком с этим Борщевым, то задай ему, плиз, вопрос.
M> Впрочем, как и его руководитель. Меня мало интересует алгоритм, опубликованный в интернете, если он не подкреплен соответствующим анализом производительности и доказательством корректности работы. При этом, мне еще важно, что эту публикацию до меня изучали специалисты и не нашли в ней ошибок. Для этого и существуют реферативные журналы.
А мне важно наличие продукта которым можно воспользоваться. А вся наукобразная финя не интересует. Ну, и реальную критику человек скорее получит если опишет свои идеи доступны человеческим языком и опубликует в интеренете. А то вот 50 лет типа прошло и толку == 0! Куда это годится. В общем, я могу характеризовать эту ситацию только или как обман со стороны этого Борщева, или как крайнее пренебрежение к судьбе своих разработок. И я не знаю, что откровенно говоря хуже.
M> Борщев же сейчас занимается совсем другими проблемами, на порядок более сложными и интересными.
Боюсь, что через 50... 100... лет когда эту проблему решит очердной студент, ученики этого Борщева так же будут сидеть на кухне и тешить свое самолюбие хихиканьем и тыканьем пальцем.
M> И вряд-ли ему есть дело до некоего билагейтса от компиляции, на рекламу поделок которого кое-кто (не будем показывать пальцем, но это слоник) сильно ведется.
Била гейтся уже приплел. В общем, лично я склонен считать труд не находящий отражения на практике сизифовым. Нет ни каких проблем опубликовать свою работу и в ВАК-овских журналах, и в Интернете. А ссылки на билигейтсов просто некрасивая отмазка.
VD>>Мог бы и опубликовать свою диссертацию в интернете.
M>Уже написал вверху.
Это обоснование нежности этого со сылкой на билигейстов?
VD>>...очень приличный парсер С++...
M>Вот что значит "отличный парсер"???
Читай внимательнее. Не отличный, а приличный.
M>Я видел "отличный парсер", написанный на бизоне.
А я не видел. Единственный бизоновский парсер С++ заслуживающий уважения — это GCC. Но от идиала он тоже далек.
M> Видел "отличный парсер", написанный вообще вручную.
Это и не удивительно. При всей громоздкости задачи она невероятно требовательна к гибкости. Так что костыли могут привысить объем чисто ручного парсера.
M> Что такое "отличный парсер"? Вопрос здесь не в невозможности с помощью данного инструмента написать парсер для того или иного языка, а легкостью этого написания.
Не, дело именно в невозможности. Ну, нельзя на Бизоне или Яке написать парсер С++, да и C# не переходя периодически к ручному кодированию.
M> Относительно языка си++ или явы даже не хочу разговаривать, а то в священные войны загремим. Но, мое мнение такое: и на си++ и на яве и на сишарпе можно написать хороший, без утечек и быстрый разборщик.
Можно. Но не LALR или LL(1) парсерах. МС вон фигачит парсер Шарпа вручню. В итоге — ошики. Смешно смотреть как написанный на коленке в промежутке между отдыхом и работой парсер разбирает их же язык более корректно.
M>Нет их, за все денежки надо платить. В этом и разница, хорошая вещь деньги стоит.
Ну, а за денежки где они? И почему при наличии их богатейшие контроы продолжают писать парсеры вручную?
M>Вот и я о том же. Это просто вопрос удобства какой какой инструмент выбирать. Бизон использовать для си++ стремно, слишком много работы надо делать вручную и грамматику уродовать. По моему мнению, генератор должен позволять построить парсер для той грамматики, которая прописана в стандарте языка.
От, золотые слова! А почитай здешние флэймы. Чуть что тебе предлагают граматику переписать. Про костыли вроде ручных заглядываний я вообще не говорю.
M> Если там есть неоднозначности то вставить предикат, чтобы на "семантическом уровне", т.е. отталкиваясь от неформального описания в стандарте, разрешить данную неоднозначность.
Я бы хотел вообще не заниматься ручным разруливаением граматики. Ну, хотя бы для языков это допускающих (например, C#). Кстати, АНТЛР позволяет вставлять предикаты. Именно по этому создать парсер С++ на нем куда проще чем на Бизоне.
M> Тогда это будет "хороший парсер". АНТЛР — совсем не такой.
Мне кажется ты его не дооценивашь. Ну, и я надеюсь, что в 3-шке все вообще будет пушисто.
... << RSDN@Home 1.2.0 alpha rev. 578>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[11]: Theory and Techniques of Compiler Construction
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, mefrill, Вы писали:
M>>До всех этих проблем додумались и все их решили еще в конце 50-х годов прошлого века. Сначал были построены алгоритмы разбора языка, заданного любой грамматикой без ограничений, а только потом были придуманы методы с линейным временем анализа. С точки зрения математика эти методы ничего не стоят, а только сужают класс языков, к которым можно применить данный алгоритм. Поэтому, все эти игры, сначала построить линейный метод, например, LL-анализатор, а затем его немножко расширить, для математика не имеют совершенно никакого смысла. В нашем случае, они ВООБЩЕ смысла не имеют.
VD>Да все конечно так... с некоторой натяжкой. Теоритически до много додумались еще до появления компьютера. Вот только теория и практически работоспособный алгоритм — это как земля и небо. Что толку с универсального метода разбора с квадратичным алгоритмом? Даже на супер-процессоре он загнется на примерах из обучающих книжек по языку.
Зря ты думаешь, что люди в науке об этом не думали. Производительность алгоритма, также как и область его применимости, — это обязательная часть работы, публикующей этот алгоритм. Без этого алгоритм просто не примут и работа ничего не будет стоить. Я хочу просто напомнить, что создание теории синтаксического анализа происходило в 60-х годах, тот же LR-анализатор был придуман Кнутом в 1965 году. В 70-х годах были созданы генераторы разборщиков, и не потому, что в 60-х их не могли создать, их создавали, просто не было потребности. Программисткое сообщество еще не оформилось. Конечно, алгоритм для математика и программиста — это совсем разные требования, я здесь полностью согласен. Но, по моему мнению, как раз задача программиста (инженера) и состоит в том, чтобы выбрать подходящий для его задачи алгоритм как продукт творческой мысли математика и спроектировать програмную модель — реализацию этого алгоритма.
VD>Как я понимаю в 3-шке достигнуто приемлемое качество разбора с приемлемой скоростью. Мне не нужно разбирать естественные языки на которых могут проявиться гипотетические проблемы описанного алгоритма. Мне нужно разбирать довольно синтаксически-сложные языки современные вроде C# и (возможно) С++. Используя доступные современные парсеры результат получается не очень хорошим. В АНТЛР 2.х я вынужден на каждый чих писать, хотя и декларативные, но инородные заглядывалки вперед, изменять граматику приводя ее к LL(k) с минимальным k и т.п. На CocoR я к тому же обязан разруливать неоднозначности рукописным кодом (плюс еще там есть другие проблемы). LALR-парсеры вроде Яков и других коров тоже нуждаются в костялых. Причем тут как и в КокоР костыли рукопашные, а значит на их создание уходит времени бльше чем на всю граматику.
VD>И все это при разборе довольно однозначной и продуманной граматики C#. Если описание LL(*) соотвествует действительности, то это и есть решение большинства проблем. А что еще нужно?
Да я ничего не имею против АНТЛРовского алгоритма. Но он имеет свои ограничения и не подходит для задач, не входящих во вполне определенный набор. Конечно, система спроектирована толково, т.е. программисткая задача выполнена очень хорошо. Но вот сам выбор алгоритма для реализации выглядит для меня уступкой общественному вкусу. А вкус этот дилетанский (пишу это без какой-либо иронии) и, следовательно, выбор алгоритма обусловлен прежде всего его простотой и легкостью понимания неспециалистом. Вот почему я сравнил сбиломгейтсом, таже уступка общественному вкусу и таже реклама. Т.е. я вижу товар,который делают привлекательным для покупателя. Наверное, это нормальный и верный подход, но лично я привык к немного другому отношению к генераторам парсеров. Вероятно, поэтому что-то меня настораживает. Хотя, это опять-же только личное, а следовательно, субъективное впечатление.
M>> Что же касается Борщева, то этот человек сделал все как надо, а именно, опубликовал свои работы в специально предназначенных для этого реферативных журналах. И не его вина, что человек, который по этой теме диссертацию защищал, не удосужился в эти журналы заглянуть.
VD>Ну, конечно. Все правильно. Сделал работу... засунул ее в дальний угол и сидит себе на кухне почитывает работы других ухмыляяс "а я то до того же 20 лет назад попетрил!...". Как, интересно, может быть доступен малоизвесный реферативный журнал на русском языке тем кто защищался на западе? В чем проблема выложить его работы в Интернет (хотя бы сейчас). Если ты знаком с этим Борщевым, то задай ему, плиз, вопрос.
Да зачем? Понимаешь, он же член научного сообщества, ну зачем ему рекламировать свои работы в других сообществах? В научном сообществе он человек известный, да и занимается сейчас совсем другими вещами. Вообщем, давай не будем его обсуждать, человек он всеми уважаемый и мною в частности. Я могу высказать только мое мнение: я бы не стал рекламировать свои работы вне нацчного сообщества, для меня это иная мотивация. Наука для меня — это "священный храм", бог которому я молюсь, а рекламируя свои работы в интернет, я как-бы бросаю это мое сокровенное к ногам толпы.
M>> Впрочем, как и его руководитель. Меня мало интересует алгоритм, опубликованный в интернете, если он не подкреплен соответствующим анализом производительности и доказательством корректности работы. При этом, мне еще важно, что эту публикацию до меня изучали специалисты и не нашли в ней ошибок. Для этого и существуют реферативные журналы.
VD>А мне важно наличие продукта которым можно воспользоваться. А вся наукобразная финя не интересует. Ну, и реальную критику человек скорее получит если опишет свои идеи доступны человеческим языком и опубликует в интеренете. А то вот 50 лет типа прошло и толку == 0! Куда это годится. В общем, я могу характеризовать эту ситацию только или как обман со стороны этого Борщева, или как крайнее пренебрежение к судьбе своих разработок. И я не знаю, что откровенно говоря хуже.
У меня все-же другая точка зрения. Я уверен, что при разработке программного продукта должен быть специалист, эксперт, как сейчас модно говорить, который хорошо понимает область, в которой оперирует программная система. Вот этот человек должен читать журналы и быть в курсе разработок за последние 100-50 лет. Ведь реферативные журналы специально для этого созданы, это коллективная память человечества. И самое важное, что я могу этой иныормации доверять, мне не нужно будет проверять и доказывать что-то снова, потому что все это уже доказано и проверено компетентными людьми. В этом главное отличие: меня сначала проверят несколько экспертов и только потом опубликуют, а в интернете можно выкладывать что хочешь. Существующая модель мне кажется разумной.
M>> Борщев же сейчас занимается совсем другими проблемами, на порядок более сложными и интересными.
VD>Боюсь, что через 50... 100... лет когда эту проблему решит очердной студент, ученики этого Борщева так же будут сидеть на кухне и тешить свое самолюбие хихиканьем и тыканьем пальцем.
M>> И вряд-ли ему есть дело до некоего билагейтса от компиляции, на рекламу поделок которого кое-кто (не будем показывать пальцем, но это слоник) сильно ведется.
VD>Била гейтся уже приплел. В общем, лично я склонен считать труд не находящий отражения на практике сизифовым. Нет ни каких проблем опубликовать свою работу и в ВАК-овских журналах, и в Интернете. А ссылки на билигейтсов просто некрасивая отмазка.
В общем, оставим Борщева, а насчет билагейтса я уже написал выше. Ничего плохого не имел ввиду, только специфическое отношение к области, которая всегда числилась как вотчина научного и инженерного сообщества.
Re[8]: Theory and Techniques of Compiler Construction
Здравствуйте, little_alex, Вы писали:
_>В том то и дело что не LL(1), а LL(k), причем с большим k (3-8) — используется эвристика которая позволяет уменьшить _>сложность предпросмотра.Где-то на сайте можно найти диссертацию автора целиком по этой теме.
Из-за этой эвристики ANTLR2.x не является полноценным LL(k)-анализатором. В корректных LL(k)-грамматиках возникают неоднозначности. С введением в ANTLR3 поддержки LL(*)-грамматик проблема отпала.
Re[7]: Theory and Techniques of Compiler Construction
Здравствуйте, VladD2, Вы писали:
VD>В том, то и дело, что правила должны быть обычными, а не регулярными. Незнаю уж почему, но все виданные мной построители парсеров были ХХ(k), т.е. не пасовали на граматиках вроде приведенной выше. А написать предпросмотр для сложных случаев очень не просто. Например, в C# есть контексно-зависимые ключевые слова. Например, слово "partial" может встречаться как идентификатор где угодно и как ключевое слово в ряду модификаторов перед классом или структурой.
Строго говоря "partial" не является ключевым словом. Об этом специально сказано в стандарте. И никаких проблем с его обработкой не возникает. Тем более что разработчики языка C# очень сильно постарались над тем чтобы разбор грамматики был достаточно простым.
Re[8]: Theory and Techniques of Compiler Construction
Здравствуйте, Алексей., Вы писали:
А>Строго говоря "partial" не является ключевым словом. Об этом специально сказано в стандарте.
Он им не является и не строго говоря. Он является контекстно-зависимым ключевым словом, т.е. выступает в роли ключевого слова только находясь в определенном контексте.
А> И никаких проблем с его обработкой не возникает. Тем более что разработчики языка C# очень сильно постарались над тем чтобы разбор грамматики был достаточно простым.
Попробуй на досуге создать LL(1)-грамматику которая бы корректно распозновала бы это слово. Еще лучше скачай R# и попробуй добиться корректного разбора этого слова без рукопашных заглядываний вперед. Хотя меня бы устроило и с заглядываниями . Я за трахался с ним в свое время. А вот был бы LL(*) я бы и не парился.
Для тестирования:
public partial class A
{
partial partial = 0;
partial class partial
{
partial partial = 0;
}
class A
{
B _b;
}
void F1()
{
i = (A.B[])(xxx + 23);
i = (A.B[])23;
}
}
public partial class MyClass
{
partial partial;
partial interface IFoo
{
int Hello(Test foo);
}
}
public partial class MyClass
{
partial partial;
partial interface IFoo
{
int Hello(Test foo);
}
}
using System;
namespace Digiton
{
public class TestA
{
#region enum Test
public enum Test // line 9
{
Value1,
Value2,
}
#endregion enum Test
}
public class TestB
{
#region Methods
private int TestMe() {
int test = 3;
//checked(test++); // line 24return test; // line 25
}
#endregion Methods
}
[CLSCompliant(false)]
public partial struct TestC // line 32
{
#region Fields
#endregion Fields
#region Constructor
public TestC(int? value) {
this.@value = value;
}
#endregion Constructor
}
}
... << RSDN@Home 1.2.0 alpha rev. 578>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: Theory and Techniques of Compiler Construction
Владимир, ты тут продемонстрировал неслабое владение материалом, лично я впечатлился. Не просветишь ли меня по двум маленьким вопросам?
Когда-то давно читали нам курс по синтаксическим анализаторам. И сказали такую штуку, мол было доказано, что любая контекстно-чувствительная грамматика может быть преобразована к LR(1) грамматике. Если это так, то к чему весь сыр-бор вокруг LL(*) парсеров? Ведь можно же просто грамматику привести к LR(1) виду?
На том же курсе нам прочитали такую штуку, как "Правила подстановки Флойда" (это как раз для разбора LR(1) грамматик). Но затем я пробовал сам в интернете найти описание этого метода, но ничего не получилось. Хоть я свой аналог yacc-а на основе этих правил когда-то сделал. Вот меня любопытство мучает, где про "Правила подстановки Флойда" почитать можно. Не подскажешь?
... << RSDN@Home 1.1.4 stable rev. 510>>
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[9]: Theory and Techniques of Compiler Construction
Здравствуйте, VladD2, Вы писали:
VD>Попробуй на досуге создать LL(1)-грамматику которая бы корректно распозновала бы это слово. Еще лучше скачай R# и попробуй добиться корректного разбора этого слова без рукопашных заглядываний вперед. Хотя меня бы устроило и с заглядываниями . Я за трахался с ним в свое время. А вот был бы LL(*) я бы и не парился.
За примерчик спасибо. Как раз забыл добавить обработку вложенных partial-типов. Пришлось добавить 15 строчек кода.
В целом, разбор "partial" довольно прост — нужно просто проверить следующий за ним токен. Если он class, struct или interface — переходишь к разбору вложенного типа, если левая скобка и класс называется partial — к разбору конструктора. Если нет, то partial является частью типа.
У меня гораздо больше возникло проблем 9.2.3 и с разбором member-name + type-parameter-list. Для разрешения 9.2.3 без заглядывания вперед ну никак не обойтись, тем более что на это косвенно намекает стандарт.
Re[9]: Theory and Techniques of Compiler Construction
Здравствуйте, eao197, Вы писали:
E>Здравствуйте, mefrill
E>Владимир, ты тут продемонстрировал неслабое владение материалом, лично я впечатлился. Не просветишь ли меня по двум маленьким вопросам?
E>Когда-то давно читали нам курс по синтаксическим анализаторам. И сказали такую штуку, мол было доказано, что любая контекстно-чувствительная грамматика может быть преобразована к LR(1) грамматике. Если это так, то к чему весь сыр-бор вокруг LL(*) парсеров? Ведь можно же просто грамматику привести к LR(1) виду?
Нет, контекстно-зависимая (КЗ) грамматика — это следующая, над контекстно-свободной (КС), ступень в иерархии грамматик, которую определил Хомский. Он определил четыре уровня, по которым можно охарактеризовать формальные грамматики. классификация идет по виду правил грамматики. Правила без ограничения на вид — это уровень 0, затем идут КЗ-грамматика, КС-грамматика и, так называемая, атвоматная грамматика. Термин КЗ появился из-за специфического вида правил: alpha A beta --> alpha B beta, где alpha и beta — строки, состоящие из нетерминалов и терминалов грамматики, и могут быть вообще пустыми. Отсюда видно причина названия "контекстно-зависимая", символ A не просто меняется на символ B, а меняется только "в контексте" т.е. когда слева стоит alpha, а справа beta. Интересно, что есть эквивавлентное свойство вида правил грамматики: это правила вида alpha --> beta, где alpha <= beta. короче говоря, левая часть не меньше правой, т.е. при подстановке полученная строка имеет не меньшую длину, чем исходная. Поэтому ,часто КЗ-грамматики называют также неукорачивающимися. Некоторые авторы делают это свойство определением КЗ-грамматики, поэтому при чтении совсем непонятно, где же там, собственно, контекст. КС-грамматика, это грамматика с правилами вида A --> с, где — это, может быть пустая, строка нетерминальных и терминальных символов грамматики. Видно, что не всякая КС-грамматика является КЗ. Т.е прямого вложения нет, уровни независимы друг от друга. Оказывается, что выразимая мощь грамматик, как устройств для генерации слов языка, зависит как раз от иерархии Хомского. Вот возмем условие объявления переменной до ее использования. легко доказать (здесь этого я делать не буду), что это условие невыразимо в КС-грамматике, а в КЗ — выразима очень даже хорошо. Идея здесь состоит в том, что генерировать сначала объявление переменной вместе со всеми необходимыми случаями использования этой переменной в программе, а затем двигать эти случае на свои места в процессе гененрации. Сам процесс генерации — это как программа на специфическом языке, только в некоторых местах алгоритм недетермнирован. Такие места называются альтернативами. Что такое LR(1)-грамматика? Это КС-грамматика, с некоторыми ограничениями на вид правил. Т.е. это еще меньше, чем КС-грамматика, и привести КЗ-грамматику к ней, конечно, почти всегда невозможно. Как понимать условие, накладываемое на LR-грамматику? Довольно проблематично эти условия сформулировать, и вообще, объяснить не просто. Лучше всего при объяснении исходить из понятия LR(k)-атвомата. Вот, чтобы определить, является ли данная грамматика LR(k)-грамматикой для некоторого, определенного числа k, можно просто попытаться построить по этой грамматике LR(k)-автомат. Если автомат получается детерминированным, то грамматика является LR, иначе — не явдяется. Например, возмем следующую грамматику
E --> E + E
E --> N
N --> n
n и + — терминальные символы. Грамматика эта неоднозначная, так как для строки n + n + n возможны два различных вывода:
E ==> E + E ==> N + E ==> n + E ==> n + E + E ==> n + N + E ==> n + n + E ==> n + n + N ==> n + n + n
E ==> E + E ==> E + E + E ==> N + E + E ==> n + E + E ==> n + N + E ==> n + n + E ==> n + n + N ==> n + n + n
каждый раз, заменяя только левый символ в строке, мы в результате получили два разных вывода. Построим для этой грамматики LR(0)-автомат:
В начальное состояние добавим только правила с начальным сиволом E в левой части
Состояние 1:
E --> * E + E
E --> * N
(* — это точка, означает, что какая-то часть правила уже поучавствовала в выводе).
Теперь надо применить операцию замыкания. Если точка стоит перед нетерминалом, то добавить в состояние все правила, где в левой части стоит этот нетерминал. У нас точка стоит перед двумя нетерминалами: E и N. Правила с символом E мы уже добавили, осталось добавить правило с символом N:
Состояние 1:
E --> * E + E
E --> * N
N --> * n
все, состояние 1 сформировали. Теперь добавляем переходы по символам за точкой. Это символы E, N и n. Сначала по символу n, получаем
Состояние 2
N --> n *
обратим внимание, что точка переместилась на один символ вправо, значит, мы прочитали символ n из входной строки. Добавляем переходы по остальным символам и формируем новые состояния
Состояние 3:
E --> E * + E
и состояние 4:
E --> N *
В обоих случаях замыкание не работает, т.к. точка стоит перед терминальным символом. Идем дальше из состояния 3, из остальных идти некуда.
Состояние 5:
E --> E + * E
Производим замыкание
Состояние 5:
E --> E + * E
E --> * E + E
E --> * N
N --> * n
из состояния 5 переходы по N в состояние 4, а по n — в состояние 2. также есть переход по E
Состояние 6:
E --> E + E *
E --> E * + E
Вот здесь мы пршли к конфликту. Из состояния 6 мы можем сделать переход по символу + или сделать так называемую "свертку", т.к. мы закончили разбор целого правила E --> E + E *, и вернуться в состояние, откуда мы начали разбор этого правила, т.е. в состояние 1 (E --> * E + E). Конфликт называется конфликтом свертка/сдвиг. Как раз здесь мы выявили неоднозначность грамматики. Отсюда способ проверить, является ли данная грамматика неоднозначной или нет. Построить LR-автомат и, если грамматика неоднозначная, то обязательно будет конфликт. Но, бывает так, что грамматика однозначная, но конфликты все-равно появляются. Поэтому, условие, которое мы проверяли, есть лишь необходимое условие на проверку неоднозначности, но отнюдь не достаточное. Задача определения того, является ли данная грамматика однозначной или нет, в общем случае алгоритмически неразрешима. Интересно, что один из способов определения является ли данная грамматика LR(k) для какого-нибудь числа k, является чисто алгебраический способ, придуманный в 90-х годах кем сейчас вылетело из головы, надо дома посмотреть его статьи. К сожалению, этот способ был опубликован в юзенет-конференции по математике в виде серии статей. Я их собрал и прочитал, но к сожалению, не уверен что там нет ошибок (преимущество реферативного журнала). Вообще, алгебраический способ определения формального языка вместо грамматики интересен и мало изучен. Можно упомянуть еще работы Футсбюрже с Хомским в 60-е годы.
E>На том же курсе нам прочитали такую штуку, как "Правила подстановки Флойда" (это как раз для разбора LR(1) грамматик). Но затем я пробовал сам в интернете найти описание этого метода, но ничего не получилось. Хоть я свой аналог yacc-а на основе этих правил когда-то сделал. Вот меня любопытство мучает, где про "Правила подстановки Флойда" почитать можно. Не подскажешь?
Не знаю, даже не слышал об этом методе. В известной литературе не встречается. Скорее всего, твой препод что-то писал по этому методу, поэтому включил в лекции.
Re[10]: Theory and Techniques of Compiler Construction
Спасибо за развернутый ответ. Не скажу, что сразу все стало понятно, поскольку теорией никогда не занимался, все больше практикой. Но для общего развития полезно будет разобраться.
E>>На том же курсе нам прочитали такую штуку, как "Правила подстановки Флойда" (это как раз для разбора LR(1) грамматик). Но затем я пробовал сам в интернете найти описание этого метода, но ничего не получилось. Хоть я свой аналог yacc-а на основе этих правил когда-то сделал. Вот меня любопытство мучает, где про "Правила подстановки Флойда" почитать можно. Не подскажешь?
M>Не знаю, даже не слышал об этом методе. В известной литературе не встречается. Скорее всего, твой препод что-то писал по этому методу, поэтому включил в лекции.
Видимо так и было.
... << RSDN@Home 1.1.4 stable rev. 510>>
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[2]: Theory and Techniques of Compiler Construction
Здравствуйте, fplab, Вы писали:
F>Здравствуйте, Сергей Губанов, Вы писали:
СГ>>Книга Н. Вирта
СГ>>Theory and Techniques of Compiler Construction. Addison-Wesley, Reading, April 1996.
СГ>>http://www.cs.ucr.edu/~phf/mir/wirth-compiler-1996.pdf F>Знаем такую, достойная вещь. Только не хватает страниц 58, 59, 74 и 75. А они довольно важны Вот их бы почитать.
Кстати, интересущимся практической стороной разработки компиляторов, очень рекомендую посмотреть книгу "Implementation of the icon programming languag" на сайте http://www.cs.arizona.edu/icon/ibsale.htm. Тут расписано все так подробно, что, кажется, уж дальше и некуда
Приходиться заниматься гадостью — зарабатывать на жизнь честным трудом (Б.Шоу)
Re[10]: Theory and Techniques of Compiler Construction
Здравствуйте, Алексей., Вы писали:
А>За примерчик спасибо. Как раз забыл добавить обработку вложенных partial-типов. Пришлось добавить 15 строчек кода.
А ты чем занимашся то? Зачем тебе граматика Шарпа?
А>В целом, разбор "partial" довольно прост — нужно просто проверить следующий за ним токен. Если он class, struct или interface — переходишь к разбору вложенного типа, если левая скобка и класс называется partial — к разбору конструктора. Если нет, то partial является частью типа.
В LL(1)-граматике такое не описать. А так ка я использую коку, то при разрешении LL(1)-конфликтов начинается серьезный геморрой. Дело в том, что в CocoR встроен механизм разруливания конфликтов. Но к сожалению при добавлении оного начинает не верно строиться конечный автомат разбора и геморрой начинает появляться на ровном месте.
На самом деле конфликт с "partial" похоже проще разрешить в лексере. Нужно просто считать это слово ключевым, но при его выдаче проверять какой токен следующий. Если это не class, struct или interface, то менять тип лексемы на identifier. Тогда в граматике можно будет просто использовать "partial" как ключевое слово.
К сожалению до этого я додумался только когда писал предыдущее сообщени, так что я убил день или даже два на борбу с конфликтами вызванными этим гребанным "partial". Надо признать, что ни с чем я так не трахался.
А>У меня гораздо больше возникло проблем 9.2.3 и с разбором member-name + type-parameter-list. Для разрешения 9.2.3 без заглядывания вперед ну никак не обойтись, тем более что на это косвенно намекает стандарт.
В C# 2.0 таких мест не одной. Я уже пожалел, что выбрал в качестве парсера CocoR, а не ANTLR. В нем эти заглядывания хотя бы можно декларативно делать. Да и оптимизация там делается в автомате.
Собственно по этому и говорю о GLL/LL(*)-парсерах. Они по идее должны были бы решать такие задачки легко и не принужденно. Страшно подумать... чистая граматика без костылей и никакого траха.
... << RSDN@Home 1.2.0 alpha rev. 578>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[12]: Theory and Techniques of Compiler Construction
Здравствуйте, mefrill, Вы писали:
M>Да я ничего не имею против АНТЛРовского алгоритма. Но он имеет свои ограничения и не подходит для задач, не входящих во вполне определенный набор. Конечно, система спроектирована толково, т.е. программисткая задача выполнена очень хорошо. Но вот сам выбор алгоритма для реализации выглядит для меня уступкой общественному вкусу.
ОК, фиг с ними с учеными и т.п. Давай лучше обсудим этот алгоритм. Я еще раз поглядел презентаху и не понял, что тебе в нем не нарвится. Может пояснишь? Только плиз не нужно всех этих рассуждений про "уступки общественному вкусу". Меня это дико раздражает.
Объясни, конструктивно, что тебе не нравится в алгоритме. По мне так идея очень неплоха. Для совпадающих частей строится ДКА, а верный путь определяется по лексемам идущим за этим ДКА. Таким образом граматика выглядит как набор ДКА и проверок между ними. Ну, а далее идет банальный рекусивный спуск управляемый логикой ДКА + доп. проверками. При этом можно так же
M>Да зачем? Понимаешь, он же член научного сообщества, ну зачем ему рекламировать свои работы в других сообществах?
Я смотрю на это с другой стороны. Не рекламировать, а делать доступными для народа и открытыми. Если это прикладная наука, то она должна находить отражение на практике. Вот опубликуй какой-нить ученый статью в Интернете, и глядишь в следующий раз какой нибудь АНТЛР будет еще лучше, ну, или раньше лет на 10-20.
Ведь смешно же, но в 2005 году нет ни одного доступного парсера позволяющего не трахаться, а просто описывать граматику.
M>...У меня все-же другая точка зрения. Я уверен, что при разработке программного продукта должен быть специалист, эксперт, как сейчас модно говорить, который хорошо понимает область, в которой оперирует программная система. Вот этот человек должен читать журналы и быть в курсе разработок за последние 100-50 лет.
Зашибись. Ну, вот предположим я хочу стать таким специалистом. И что мне делать? Идти в Ленинку и перерывать все подшивки за последние 50 лет? Угробить лет десять только на это?
А в Интернет я могу за пять минут найти гуглем то что меня интересут. Главное, чтобы оно тут было.
M> Ведь реферативные журналы специально для этого созданы, это коллективная память человечества.
На сегодня это плохой путь. Вернее недостаточный. Правильным решением является создание своего сайта, ну, или проекта на некотором сайте.
В общем, все течет, все именяется. Должны изменяться и подходы ученых в области популяризации своих идей.
Особенно это верно для области компьютерных наук. В этой области есть огромные сообщества занимающиеся исследованиями и разработками "фор-фан". Опен-сорс уже давно конкурирует с коммерческим софтом (и питает его идеями). Так почему не пользоваться таким подспорьем? Сам ученый не сделает много. Так пусть позволит сделать большее другим.
M>И самое важное, что я могу этой иныормации доверять, мне не нужно будет проверять и доказывать что-то снова, потому что все это уже доказано и проверено компетентными людьми. В этом главное отличие: меня сначала проверят несколько экспертов и только потом опубликуют, а в интернете можно выкладывать что хочешь. Существующая модель мне кажется разумной.
Знашь, я много раз видел "проверенную экспертами информацию" которая на поверку аказывалась полнейшим булшитом. Большинство дисертаций ни стоят и выеденного яйца. Они делаются ради степени. А проверенность... это конечно хоршо. Но меня удовлетворит и банальная проверенность на практике. Когда я читаю про те же построители лексеров и натыкаюсь на слова что мол "ДКА в некоторых случаях может быть неприемлемо большим, но на практике обычно все ОК" меня это более чем удовлетворяет. И мне не нужно 10 страниц формальных доказательств.
M>В общем, оставим Борщева, а насчет билагейтса я уже написал выше. Ничего плохого не имел ввиду, только специфическое отношение к области, которая всегда числилась как вотчина научного и инженерного сообщества.
Оставим. Оставим и билгейтсов. Пойми, то такое пренебрижительное отношение к тем, кто что-то делат на практие сильно раздражает. Надо все же понимать, что тот же билигейст сейчас нехило двигат ту же науку вперед давая миллионы баксов на исследования иститутам.
Про то что все украдено, тфу-ты, придумано до нас я слышал много раз. Появляется Ява/дотнет и мы тут же слышим, о том, что все эти идеи давно известны. Появляется парсер которым можно ползоваться не матерясь по каждому поводу и мы поять слышим "а что тут тагого?". Да ничего. Просто ребята не треплются, аделают. А то что у них нехватает иформации... в этом конечно есть и их вина, но думаю как раз основная вина здесь лежит на тех самых ученых/исследователях которые не думают о разумной популяризации своих идей.
... << RSDN@Home 1.2.0 alpha rev. 578>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[11]: Theory and Techniques of Compiler Construction
Здравствуйте, VladD2, Вы писали:
VD>А ты чем занимашся то? Зачем тебе граматика Шарпа?
На досуге пишу на C++ парсер для C#2.0. Парсер для C#1.x уже написан.
VD>В LL(1)-граматике такое не описать. А так ка я использую коку, то при разрешении LL(1)-конфликтов начинается серьезный геморрой. Дело в том, что в CocoR встроен механизм разруливания конфликтов. Но к сожалению при добавлении оного начинает не верно строиться конечный автомат разбора и геморрой начинает появляться на ровном месте.
По-поводу CocoR. Вроде как в инете на ихнем сайте лежит граммaтика C#2.0. Почему бы не использовать ее. Или она некорректная?
VD>На самом деле конфликт с "partial" похоже проще разрешить в лексере. Нужно просто считать это слово ключевым, но при его выдаче проверять какой токен следующий. Если это не class, struct или interface, то менять тип лексемы на identifier. Тогда в граматике можно будет просто использовать "partial" как ключевое слово.
VD>К сожалению до этого я додумался только когда писал предыдущее сообщени, так что я убил день или даже два на борбу с конфликтами вызванными этим гребанным "partial". Надо признать, что ни с чем я так не трахался.
Разные инструменты порождают разные проблемы и способы их решения. В парсере написаном вручную таких проблем не возникает. Странно, а как же 9.2.3?
VD>В C# 2.0 таких мест не одной. Я уже пожалел, что выбрал в качестве парсера CocoR, а не ANTLR. В нем эти заглядывания хотя бы можно декларативно делать. Да и оптимизация там делается в автомате.
Угу. Правда стоит отметить что на сайте ANTLR до сих пор нет полной C#1.x-грамматики (не говоря уже о C#2.0). Они недоделаны и неоптимизированы. Так что с ANTLR тоже не все так просто. Может с выходом ANTLR3 ситуация изменится.
VD>Собственно по этому и говорю о GLL/LL(*)-парсерах. Они по идее должны были бы решать такие задачки легко и не принужденно. Страшно подумать... чистая граматика без костылей и никакого траха.
Будем надеяться.
Re[12]: Theory and Techniques of Compiler Construction
Здравствуйте, Алексей., Вы писали:
А>На досуге пишу на C++ парсер для C#2.0. Парсер для C#1.x уже написан.
Маньяк, однако. А зачем?
А>По-поводу CocoR. Вроде как в инете на ихнем сайте лежит граммaтика C#2.0. Почему бы не использовать ее. Или она некорректная?
Она не просто не корректна. Она ужасна. Хотя может что-то изменилось за последнее время. Но гда я ее смотрел, то плевался по страшному. Я тоже думал... вот она халява. А оказался обман.
А>Разные инструменты порождают разные проблемы и способы их решения. В парсере написаном вручную таких проблем не возникает.
В рукопашном парсере ровно одна проблема — невозможность увидеть чистую граматику и как следствие гарантировать ее корректность.
А>Странно, а как же 9.2.3?
Это тот что "Grammar ambiguities"? И что с него? Про тот же partial там не слова. А как средство разрешения конфликтов с тем что там описано я его использовал по полной. Вот только это тоже рукопашный код.
А>Угу. Правда стоит отметить что на сайте ANTLR до сих пор нет полной C#1.x-грамматики (не говоря уже о C#2.0).
Да, практически полная 2.0-грамматика у меня и у самого есть. Нехватает только работы с nulable-типами и префиксами простарнств имен. Но вот сколько ошибок в парсере в следствии обхода LL(1) конфликтов?
А> Они недоделаны и неоптимизированы. Так что с ANTLR тоже не все так просто. Может с выходом ANTLR3 ситуация изменится.
Вот я и смотрю на него. Судя по тому что я увидел C# на нем должен парситься просто и красиво. Да и С++ скорее всего без особых костылей должен проскачить (хотя, фиг бы с ним).
Вот только жаль, что он явский. Хорошо бы его хотя бы на J# перетащить.
... << RSDN@Home 1.2.0 alpha rev. 578>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: Theory and Techniques of Compiler Construction
1. Доступны ли где-нибудь публично GLR-построители парсеров?
2. Хотелоь бы услышать мнение по поводу LL(*) или другими словами GLL-парсеров: General LL
Здравствуйте, Алексей., Вы писали:
А>Из-за этой эвристики ANTLR2.x не является полноценным LL(k)-анализатором. В корректных LL(k)-грамматиках возникают неоднозначности. С введением в ANTLR3 поддержки LL(*)-грамматик проблема отпала.
Я бы сказал видимо отпадет. Кстати, когда они оафициальные бэты хотят выпустить?
... << RSDN@Home 1.2.0 alpha rev. 578>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: Theory and Techniques of Compiler Construction
Здравствуйте, VladD2, Вы писали:
VD>Кстати, когда они официальные бэты хотят выпустить?
В начале года говорилось о том что ANTLR3 выйдет осенью.
В последнее время о сроках выпуска ничего не говорилось. Все увлечены тестированием eap'ов и портированием ANTLR3 на другие языки (ANTLR/C#, ANTLR/C++ и т.д.).
Re[11]: Theory and Techniques of Compiler Construction
Здравствуйте, Алексей., Вы писали:
А>В начале года говорилось о том что ANTLR3 выйдет осенью. А>В последнее время о сроках выпуска ничего не говорилось.
Ясно.
А> Все увлечены тестированием eap'ов и портированием ANTLR3 на другие языки (ANTLR/C#, ANTLR/C++ и т.д.).
А исходники доступны? И какой смысл портировать до выхода окончательной версии?
... << RSDN@Home 1.2.0 alpha rev. 587>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[12]: Theory and Techniques of Compiler Construction
Здравствуйте, VladD2, Вы писали:
VD>А исходники доступны? И какой смысл портировать до выхода окончательной версии?
Если честно, то не в курсе. Исходников пока никто не выкладывал. Для ANTLR/C++ существует экспериментальная ветка (под условным названием ANTLR2.8) на которой отрабатываются внутренности вроде сборщика мусора для AST-узлов и прочие оптимизации.
Re[13]: Theory and Techniques of Compiler Construction
Прошу прощения, что ответил не сразу, был в отпуске, подставляя свою бледную кожу жарким лучам южного солнца в районе озера Иссык-Куль . Дисскутировать дальше не имею никакого желания, я и не хотел этого делать изначально, просто высказывал свою позицию. Отвечу только на вопрос, чем мне не нравится алгоритм, примененный в АНТЛР3. Только одним — узостью класса грамматик, для которых он может работать. Конечно, можно сказать, что для большинства языков программирования легко придумать подходящую дя АНТЛР грамматику, но вот как раз это мне и не нравится. Я хочу использовать ту грамматику, которая нравится мне, а не данному генратору разборщиков. Можно было бы смериться с ситуацией, если бы не было других алгоритмов синтаксического анализа, позволяющих производить разбор языка на основе любой грамматики, но ведь они есть. Зачем ездить на самокате, если есть вездеход?
ных/исследователях которые не думают о разумной популяризации своих идей.
Re[14]: Theory and Techniques of Compiler Construction
Здравствуйте, mefrill, Вы писали:
M>Отвечу только на вопрос, чем мне не нравится алгоритм, примененный в АНТЛР3. Только одним — узостью класса грамматик, для которых он может работать. Конечно, можно сказать, что для большинства языков программирования легко придумать подходящую дя АНТЛР грамматику, но вот как раз это мне и не нравится. Я хочу использовать ту грамматику, которая нравится мне, а не данному генратору разборщиков. Можно было бы смериться с ситуацией, если бы не было других алгоритмов синтаксического анализа, позволяющих производить разбор языка на основе любой грамматики, но ведь они есть. Зачем ездить на самокате, если есть вездеход?
А какие, по-твоему, алгоритмы обеспечивают более широкую полосу анализа?
И почему ты думашь, что LL(*) охватывает узкий класс граматик.
Мне почему-то кажется, что LL(*) ни чем не хуже GLL.
... << RSDN@Home 1.2.0 alpha rev. 591>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[15]: Theory and Techniques of Compiler Construction
Здравствуйте, VladD2, Вы писали:
VD>А какие, по-твоему, алгоритмы обеспечивают более широкую полосу анализа?
Ну, есть несколько таких алгоитмов. Это классические алгоритмы разбора сверху вниз и снизу вверх с поиском в глубину. Существуют способы избежать зацикливания в этих алгоритмах, но способы не очень хорошие. Алгоритм Кока-Янгера-Касами позволяет производить разбор любой грамматики, но требует перевода ее в нормальную форму Хомского. Алгоритм Эрли позволяет производить разбор языка, заданного любой КС-граммаикой. До недавнего времени не было корректного алгоритма построения деревьев вывода для метода Эрли, но моими усилиями этот алгоритм был создан. Алгоритм Томиты, известный еще как GLR, также позволяет разбирать языки, заданные любой КС-грамматикой. В общем, есть два хороших алгоритма: алгоритм Эрли и алгоритм Томиты.
VD>И почему ты думашь, что LL(*) охватывает узкий класс граматик.
Блин, ну ты читаешь мои ответы??? Я же там распинался, на конкретных примерах тебе показывал, что алгортим зацикливается для грамматик, содержащих леворекурсивные правила и правила с пустой правой частью. Как будут обрабатываться неоднозначности? Моя модификация алгоритма Эрли, например, строит всевозможные деревья вывода для входной строки, если есть неоднозначности. LL(*) не строит, а выбирает только одно дерево по ходу пъесы, руководствуясь либо семантическими ограничениями, либо случайно выбирая конкретную альтернативу. Далее, все ограничения, связанные с LL(k) алгоритмом никто не отменял и в LL(*).
VD>Мне почему-то кажется, что LL(*) ни чем не хуже GLL.
Что за GLL такой??? Не слышал о таком методе. Вообще, Влад, ну ты хоть немного прислушивайся к мнению других людей. Я этой темой занимаюсь уже несколько лет, написал диссертацию. Зачем спорить об очевидных вещах? И мне совершенно непонятна твоя любовь к АНТЛР. Чем она вызвана? И о чем мы вообще спорим?
Re[16]: Theory and Techniques of Compiler Construction
Здравствуйте, mefrill, Вы писали:
VD>>А какие, по-твоему, алгоритмы обеспечивают более широкую полосу анализа?
<...skipped...> M>В общем, есть два хороших алгоритма: алгоритм Эрли и алгоритм Томиты.
В каких нибудь antlr/yacc/cocor — подобных инструменах они доступны?
M>Что за GLL такой??? Не слышал о таком методе. Вообще, Влад, ну ты хоть немного прислушивайся к мнению других людей. Я этой темой занимаюсь уже несколько лет, написал диссертацию. Зачем спорить об очевидных вещах? И мне совершенно непонятна твоя любовь к АНТЛР. Чем она вызвана? И о чем мы вообще спорим?
Очень похоже на спор программиста-практика и математика-теоретика. Одному нужен работающий инструмент здесь и сейчас. Другому нужен метод, к которому, может быть, инструмент со временем приложится. Вот только эта дельта t проблемой и является.
... << RSDN@Home 1.1.4 stable rev. 510>>
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[17]: Theory and Techniques of Compiler Construction
Здравствуйте, eao197, Вы писали:
E>Здравствуйте, mefrill, Вы писали:
VD>>>А какие, по-твоему, алгоритмы обеспечивают более широкую полосу анализа?
E><...skipped...> M>>В общем, есть два хороших алгоритма: алгоритм Эрли и алгоритм Томиты.
E>В каких нибудь antlr/yacc/cocor — подобных инструменах они доступны?
К сожалению, нет. Все известные мне реализации платные. Компания делает инструмент для себя, это требует ресурсов и, поэтому, никому не хочется делать такой инструмент бесплатным. У меня есть реализация алгоритма Эрли и некоторой системы динамической компиляции на его основе. Парсер регулярных выражений, лексический анализатор и синтаксический анализатор. Вот, если кому интересно, можно довести это до ума, написать еще один бесплатный открытый генератор парсеров.
Здравствуйте, mefrill, Вы писали:
VD>>И почему ты думашь, что LL(*) охватывает узкий класс граматик.
M>Я же там распинался, на конкретных примерах тебе показывал, что алгортим зацикливается для грамматик, содержащих леворекурсивные правила и правила с пустой правой частью. Как будут обрабатываться неоднозначности?
При постпроении ДКА можно попытаться выявлять такие места и переписывать их.
M> Моя модификация алгоритма Эрли, например, строит всевозможные деревья вывода для входной строки, если есть неоднозначности. LL(*) не строит, а выбирает только одно дерево по ходу пъесы, руководствуясь либо семантическими ограничениями, либо случайно выбирая конкретную альтернативу. Далее, все ограничения, связанные с LL(k) алгоритмом никто не отменял и в LL(*).
Насколько я понимаю основная идея этого LL(*) — это построение единого ДКА. Если состояния автомата совпадают с несколькими правилами, то входной поток сканируется до тех пор пока не будет найден токен который будет удовлетворять только одному правилу. Мне кажется, это решает большинство проблем LL(k)-анализаторов. Ну, да конечно в данной области мои познания не столь велеки.
VD>>Мне почему-то кажется, что LL(*) ни чем не хуже GLL.
M>Что за GLL такой??? Не слышал о таком методе.
Это не метод. Это только так "мысли в слух".
Это я про идею описанную здесь: General LL
.
M> Вообще, Влад, ну ты хоть немного прислушивайся к мнению других людей. Я этой темой занимаюсь уже несколько лет, написал диссертацию.
Я и прислушиваюсь. Только хочу не просто поверить слову, а хоть немного разобраться в проблеме. Мне эта информация нужно в сугубо практическом плане.
M> Зачем спорить об очевидных вещах?
Это они тебе очевидны. Даже если отбросить мысль о том, что ты можешь банльно не правильно понять суть этго LL(*), то нужно понимать, что это ты на этом собаку съел. А я так только понадкусывал. По этому то что тебе кажется очевидным для меня может таковым не являться (не хватает предпосылок).
M> И мне совершенно непонятна твоя любовь к АНТЛР. Чем она вызвана?
Да нет никакой любви к АНТЛР. Просто это даже на сегодны один из самых мощьных построителей парсеров из доступных свободно. А эта 3-шка вроде как обещает стать еще лучше. Вот мне и интересно мнение о ней и вообще о том как можно заполучить построитель парсеров удовлетворительного качетсва.
M> И о чем мы вообще спорим?
Разве это спор? Так... выуживаем из тебя доступную информацию.
... << RSDN@Home 1.2.0 alpha rev. 591>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[18]: Theory and Techniques of Compiler Construction
Здравствуйте, mefrill, Вы писали:
M>К сожалению, нет. Все известные мне реализации платные. Компания делает инструмент для себя, это требует ресурсов и, поэтому, никому не хочется делать такой инструмент бесплатным. У меня есть реализация...
В каком виде?
M> алгоритма Эрли и некоторой системы динамической компиляции на его основе. Парсер регулярных выражений, лексический анализатор и синтаксический анализатор. Вот, если кому интересно, можно довести это до ума, написать еще один бесплатный открытый генератор парсеров.
Несколько вопросов:
1. Какова оценочная эффективность этого алгоритма. Ведь для рельной жизни важно не только качество разбора, но и скорость парсинга.
2. Где можно почитать о твоем методе. (по возможности популярно).
3. Насколко ты готов разобраться в этом вопросе тем кто займется этоим доведением до ума?
В принципе задача интересная. Ею можно было бы заняться.
... << RSDN@Home 1.2.0 alpha rev. 591>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Сергей Губанов, Вы писали:
СГ>Здравствуйте, fplab, Вы писали:
F>> Знаем такую, достойная вещь. Только не хватает страниц 58, 59, 74 и 75. А они довольно важны Вот их бы почитать.
СГ>Можете сказать спасибо Владимиру Лосю...
СГ>http://blackbox.thundersign.su/docs.html
Спасибо ! То, что надо
Приходиться заниматься гадостью — зарабатывать на жизнь честным трудом (Б.Шоу)
Re[19]: Theory and Techniques of Compiler Construction
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, mefrill, Вы писали:
M>>К сожалению, нет. Все известные мне реализации платные. Компания делает инструмент для себя, это требует ресурсов и, поэтому, никому не хочется делать такой инструмент бесплатным. У меня есть реализация...
VD>В каком виде?
В виде программмы на си++. Есть еще адаптер к вижуал прологу, выдает дерево вывода в приемлемом для пролога виде. Небольшая тестовая утилитка берет грамматику из текстового файла и осуществляет разбор входной строки, а затем показывает дерево вывода в контроле листвью мфс. В общем, готовая программа, но понятно, написанная достаточно небрежно. Можно ее дописать, а можно и вообще переписать, если интересно. Токены задаются в виде регулярных выражений, которые затем парсятся в детерминированный конечный автомат, минимизированный относительно количества состояний. Лексический анализатор запускает параллельно все такие автоматы и возвращает тот, который читает самую длинную строку. Синтаксический анализатор разбирает поток токенов, которые для синтаксического анализатора являются просто терминальными символами входной грамматики, и возвращает дерево вывода (или множество таких деревьев, если грамматика неоднозначная).
M>> алгоритма Эрли и некоторой системы динамической компиляции на его основе. Парсер регулярных выражений, лексический анализатор и синтаксический анализатор. Вот, если кому интересно, можно довести это до ума, написать еще один бесплатный открытый генератор парсеров.
VD>Несколько вопросов: VD>1. Какова оценочная эффективность этого алгоритма. Ведь для рельной жизни важно не только качество разбора, но и скорость парсинга.
Алгоритм Эрли позволяет разбирать линейные грамматики (т.е. грамматики, для которых только одна альтернатива, как в LL(k) или LR(k) грамматиках) за O(n), где n — длина входной терминальной строки, однозначные грамматики — за O(n^2) и неоднозначные — за O(n^3). В общем случае, алгоритм Эрли работает медленнее LR(k)-анализатора, проблема в константе для O(n). Но, в 90-х годах была придумана модификация алгоритма Эрли, которая позволяет разбирать линейные грамматики с той же скоростью, что и бизон. Для этого метода пока не создан алгоритм построения дервьев вывода, это как раз тема кандидатской диссертации. Так что, кому интересно — можно над этим поработать. Сам алгоритм можно использовать прямо сейчас, работа состоит в доказательстве его корректности.
VD>2. Где можно почитать о твоем методе. (по возможности популярно).
Мой метод — это алгоиритм Эрли, расширенный и модифицированный таким образом, чтобы строить деревья вывода, что оригинальный алгоритм Эрли делать не мог. Точнее, сам Эрли думал, что мог, но в его рассуждениях была ошибка. Эту ошибку обнаружил в 80-х Томита, исправить ее не смог и взялся за другой алгоритм — LR-анализа, расширил его и получил GLR. Я нашел как исправить эту ошибку и показал корректность работы нового алгоритма. Прочитать об алгоритме Эрли можно в моих работах, но там много математики и очень формально. Лучшее популярное описание все в той же книжке двух голландцев "Техника синтаксического анализа", насколько я помню. Вообще, там надо разобраться, знаю по своему опыту. Объяснял многим людям.
VD>3. Насколко ты готов разобраться в этом вопросе тем кто займется этоим доведением до ума?
Я готов помочь, объяснить алгоритм, рассказать о задачах, которые стоят и все такое прочее. Программировать я, к сожалению, не смогу. Но, можно было бы коллективно поработать над новой реализацией быстрого алгоритма Эрли с построением деревьев вывода. Если это получится (в чем я абсолютно уверен), то будет вне конкуренции.
VD>В принципе задача интересная. Ею можно было бы заняться.
По моему мнению, в таком генераторе необходимо реализовать несколько алгоритмов синтаксического анализа. Главные из них: быстрый алгоритм Эрли и GLR. Затем, необходимо реализовать адапатированный для построения деревьев вывода алгоритм Эрли (мой), так чтобы позволить легко менять исходныю грамматику прямо между двумя запусками алгоритма разбора. Бизон, например, этого делать не позволяет, также как и АНТЛР. Ведь они берут грамматику из текстового файла, обрабатывают ее, извлекая дополнительную информацию, и только затем генерируют разборщик. Я назвал такую модель генерации разборщиков статической моделью компиляции (СМК). Классический алгоритм Эрли ничего такого не требует, просто берет грамматику правило за правилом и разбирает. Я назвал такую можель динамической моделью компиляции (ДМК). ДМК полезен в тех ситуациях, когда исходный язык часто меняется, пополняется пользователем. С другой стороны, СМК работает быстрее, так как "знает" больше о свойствах грамматики. Это знание в случае LR-анализа есть LR-автомат, а случае LL(*)-анализа есть LL(*)-автомат. В общем, работы там много и работы интересной. Есть еще проблема обработки ошибок, тоже есть несколько интересных решений.
Re[17]: Theory and Techniques of Compiler Construction
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, mefrill, Вы писали:
VD>>>И почему ты думашь, что LL(*) охватывает узкий класс граматик.
M>>Я же там распинался, на конкретных примерах тебе показывал, что алгортим зацикливается для грамматик, содержащих леворекурсивные правила и правила с пустой правой частью. Как будут обрабатываться неоднозначности?
VD>При постпроении ДКА можно попытаться выявлять такие места и переписывать их.
Нет, там ничего такого не получится. В презентации предлагается либо случайно выбирать продукцию по наименьшему номеру (на стр. 11 верхняя картинка "пример неоднозначности"), либо использовать семантические предикаты, разрешая необнозначности вручную (стр. 11).
M>> Моя модификация алгоритма Эрли, например, строит всевозможные деревья вывода для входной строки, если есть неоднозначности. LL(*) не строит, а выбирает только одно дерево по ходу пъесы, руководствуясь либо семантическими ограничениями, либо случайно выбирая конкретную альтернативу. Далее, все ограничения, связанные с LL(k) алгоритмом никто не отменял и в LL(*).
VD>Насколько я понимаю основная идея этого LL(*) — это построение единого ДКА. Если состояния автомата совпадают с несколькими правилами, то входной поток сканируется до тех пор пока не будет найден токен который будет удовлетворять только одному правилу. Мне кажется, это решает большинство проблем LL(k)-анализаторов. Ну, да конечно в данной области мои познания не столь велеки.
Да, примерно эта идея. Но, проблемы, к сожалению, все-равно остаются. на странице 11 презентации как раз показан пример неоднозначности. А можно найти примеры однозначных грамматик, для которых невозможно построить LL(*) ДКА, недетерминизм по любому остается.
VD>>>Мне почему-то кажется, что LL(*) ни чем не хуже GLL.
M>>Что за GLL такой??? Не слышал о таком методе.
VD>Это не метод. Это только так "мысли в слух". VD>Это я про идею описанную здесь: General LL
Здравствуйте, mefrill, Вы писали:
M>В виде программмы на си++.
А он доступен?
M> Есть еще адаптер к вижуал прологу, выдает дерево вывода в приемлемом для пролога виде. Небольшая тестовая утилитка берет грамматику из текстового файла и осуществляет разбор входной строки, а затем показывает дерево вывода в контроле листвью мфс. В общем, готовая программа, но понятно, написанная достаточно небрежно.
Пролог это здорово, но я с ним знаком только по картинкам. Да и не очень практичен он. От парсера требуется максимальная скорость. Тут без хаков не обойтись.
M>Можно ее дописать, а можно и вообще переписать, если интересно. Токены задаются в виде регулярных выражений, которые затем парсятся в детерминированный конечный автомат, минимизированный относительно количества состояний. Лексический анализатор запускает параллельно все такие автоматы и возвращает тот, который читает самую длинную строку.
То есть нет единого автомата лексера? А как осуществляется выбор конкретного автомата? Перебором? Это же медленно.
Не лучше ли сделать один автомат который будет просто запихивать информацию о правилах при проходе пути? Ну, предположим правила:
Конфликтуют по первому символу. Но можно создать общий ДКА который при появлении новго символа будет запихивать/удалять в/из некоторый список информацию о удовлетворяющих правилах. Так на символе '/' в списке окажется два правила (MultylineComment и SinglelineComment). Но уже при появлении '*' или '/' правило останется одно и проблемы исчезнут. Остается только проблема при совпадении правил, но если они не порождают токенов, то и проблем нет (встраивать их тела по месту в более "широкие" правила.
Это даст скорость линейного поиска при относительно простом решении.
Вот только в современных языках есть кое какие проблемы. Например, в C# есть контексные ключевые слова. Так слова "get"/"set" встречаются только в эксесорах свойств, т.е. в:
int Property { get { return 1; } }
"get" бедет ключевым словом. А в:
int get;
нет.
Для решения этой проблемы можно просто переписать граматику объявив идентификатор таким образом:
Ident : ident | "get" | "set".
Тогда проблема решается. Но ведь мы как раз говорили, о том, что желательно иметь парсер для которого не требуется изменять граматику.
Еще более забавным случаем является контекстное ключевое слово "partial". Оно является ключевым только если перед ним идут слова "class"/"interface"/"struct". Тут уже просто так засунуть "partial" в Ident не удается. А на уровне лексера проблема решается путем несколькоих заглядываний вперед при появлени слова "partial". Нужно просто проверить идет ли за ним одно из этих слов, пропуская при этом коментарии и пробельные символы.
Интересно как в этих случаях может помочь распараллеливание лексера?
M> Синтаксический анализатор разбирает поток токенов, которые для синтаксического анализатора являются просто терминальными символами входной грамматики,
Ну, это классика.
M> и возвращает дерево вывода (или множество таких деревьев, если грамматика неоднозначная).
А насколько затормозится парсер если однозначость появляется при довольно глубоком заглядывании вперед? И как решаются проблемы "неудобных" рекурсий.
M>Алгоритм Эрли позволяет разбирать линейные грамматики (т.е. грамматики, для которых только одна альтернатива, как в LL(k) или LR(k) грамматиках) за O(n),
LL(k) за O(n)? Странно. Мне казалось, что за O(n) может работать только LL(1), а вся борба в LL(k)-апрсерах связана с оптимизицией заглядываний вперед. Я так понял, что LL(*) как раз и является разумным решением дя LL-арсеров.
M> где n — длина входной терминальной строки, однозначные грамматики — за O(n^2) и неоднозначные — за O(n^3). В общем случае, алгоритм Эрли работает медленнее LR(k)-анализатора, проблема в константе для O(n). Но, в 90-х годах была придумана модификация алгоритма Эрли, которая позволяет разбирать линейные грамматики с той же скоростью, что и бизон. Для этого метода пока не создан алгоритм построения дервьев вывода, это как раз тема кандидатской диссертации. Так что, кому интересно — можно над этим поработать. Сам алгоритм можно использовать прямо сейчас, работа состоит в доказательстве его корректности.
То есть нет полной уверенности, что алгоритм корректен?
VD>>2. Где можно почитать о твоем методе. (по возможности популярно).
M>Мой метод — это алгоиритм Эрли, расширенный и модифицированный таким образом, чтобы строить деревья вывода, что оригинальный алгоритм Эрли делать не мог. Точнее, сам Эрли думал, что мог, но в его рассуждениях была ошибка. Эту ошибку обнаружил в 80-х Томита, исправить ее не смог и взялся за другой алгоритм — LR-анализа,
Алгоритм Эрли тоже LR? А как при этом с простотой отладки граматик и с разумностью сообщений об ошибках парсинга? У Яков с Бизонами с этим серьезные проблемы.
M> расширил его и получил GLR. Я нашел как исправить эту ошибку и показал корректность работы нового алгоритма. Прочитать об алгоритме Эрли можно в моих работах, но там много математики и очень формально. Лучшее популярное описание все в той же книжке двух голландцев "Техника синтаксического анализа", насколько я помню.
К сожалению у меня ее нет. Она доступна в магазинах?
Кстати, может быть первым делом сделать доступную статью и опубликовать ее у нас? Я мог бы помочь в плане разжевывания и упрощения изложения. Думаю это могло бы двинуть энтузиазм, ну, и за одно я бы по ходу пьесы разобрался бы в алгоритме.
M> Вообще, там надо разобраться, знаю по своему опыту. Объяснял многим людям.
Ну, вот объясни мен и мы вместе напишем популярную статью которая откроет суть твоего алгоритма для всех.
VD>>3. Насколко ты готов разобраться в этом вопросе тем кто займется этоим доведением до ума?
M>Я готов помочь, объяснить алгоритм, рассказать о задачах, которые стоят и все такое прочее. Программировать я, к сожалению, не смогу.
ОК. Давай попробуем. Предлагаю для этого открыть новую тему и обсудеть суть этого алгоритма в нем.
M>Но, можно было бы коллективно поработать над новой реализацией быстрого алгоритма Эрли с построением деревьев вывода. Если это получится (в чем я абсолютно уверен), то будет вне конкуренции.
А как, по-твоему, он по сравнению тем же GLR по скорости на явзыках типа С++/C# (т.е. языках в которых есть множество мест когда конкретное правило можно определить только при многократном заглядывании вперед)?
M>По моему мнению, в таком генераторе необходимо реализовать несколько алгоритмов синтаксического анализа. Главные из них: быстрый алгоритм Эрли и GLR.
А смысл несколько?
M> Затем, необходимо реализовать адапатированный для построения деревьев вывода алгоритм Эрли (мой), так чтобы позволить легко менять исходныю грамматику прямо между двумя запусками алгоритма разбора.
На ходу? Без создания ДКА? Боюсь, что это станет тормозом. Хотя лично для моих нужд (расширение языка с целью внедрения в него средств метапрограммирования) динамический парсер был бы удобен.
M> Бизон, например, этого делать не позволяет, также как и АНТЛР. Ведь они берут грамматику из текстового файла, обрабатывают ее, извлекая дополнительную информацию, и только затем генерируют разборщик.
Дык это самое эффективное решение. Конкретная граматика превращается в эффектинвный код разбора. Никакой интерпретации. Возможность использовать хот switch-ей, хоть двумерных массивов...
M> Я назвал такую модель генерации разборщиков статической моделью компиляции (СМК). Классический алгоритм Эрли ничего такого не требует, просто берет грамматику правило за правилом и разбирает. Я назвал такую можель динамической моделью компиляции (ДМК). ДМК полезен в тех ситуациях, когда исходный язык часто меняется, пополняется пользователем. С другой стороны, СМК работает быстрее, так как "знает" больше о свойствах грамматики. Это знание в случае LR-анализа есть LR-автомат, а случае LL(*)-анализа есть LL(*)-автомат.
Боюсь, без заранее построенных автоматов (лучше в виде генерируемого кода) тут не обойтись. На сегодны динамическая компиляция не является проблемой. Так что делать интерпретатор без ДКА в основе крайне не разумно. И никакие блага простой модификации тут не перевесят. Все же в рельных проектах унжно перелопачивать по 3-15 мег кода и медленный парсет тут будет большой проблемой. Ну, и парсеры намного проще писать на языках с GC. А у них есть своим потери на разные "барьеры записи". Так что крайне желательно иметь действительно эффективный алгоритм.
M> В общем, работы там много и работы интересной.
Это понятно.
M> Есть еще проблема обработки ошибок,
Вот этого я и боюсь. Когда я сравнивал бесплатные построители парсеров, то Яки и Безоны пошли в лес отчасти потому что реализация на них осмысленных сообщений об ошибках крайне затруднительно.
M>тоже есть несколько интересных решений.
... << RSDN@Home 1.2.0 alpha rev. 591>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[21]: Theory and Techniques of Compiler Construction
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, mefrill, Вы писали:
M>>В виде программмы на си++.
VD>А он доступен?
Ну да, у меня на компутере .
M>> Есть еще адаптер к вижуал прологу, выдает дерево вывода в приемлемом для пролога виде. Небольшая тестовая утилитка берет грамматику из текстового файла и осуществляет разбор входной строки, а затем показывает дерево вывода в контроле листвью мфс. В общем, готовая программа, но понятно, написанная достаточно небрежно.
VD>Пролог это здорово, но я с ним знаком только по картинкам. Да и не очень практичен он. От парсера требуется максимальная скорость. Тут без хаков не обойтись.
О прологе можно забыть. Реализация интерфейса для пролога была связана со спецификой моей работы. Я реализовывал интерфейсную систему для базы знаний, написанной на прологе.
M>>Можно ее дописать, а можно и вообще переписать, если интересно. Токены задаются в виде регулярных выражений, которые затем парсятся в детерминированный конечный автомат, минимизированный относительно количества состояний. Лексический анализатор запускает параллельно все такие автоматы и возвращает тот, который читает самую длинную строку.
VD>То есть нет единого автомата лексера? А как осуществляется выбор конкретного автомата? Перебором? Это же медленно.
Для каждого токена строится минимизированный ДКА. Понятно, что в результате, при лексическом анализе, получается недетерминированный автомат. Поэтому, я на ходу произвожу моделированние ДКА делая параллельный проход по автоматам для каждого подходящего токена. Такая реализация была связана со спецификой задачи, которую я реализовывал. Необходимо было создать лексический анализатор, который оперирует на основе динамически пополняемого множества токенов. Поэтому, неудобно было создавать и потом каждый раз убивать общий ДКА, очень медленно получалось. Нет никакого ограничения на построение единого ДКА для всех токенов грамматики.
VD>Не лучше ли сделать один автомат который будет просто запихивать информацию о правилах при проходе пути? Ну, предположим правила: VD>
VD>Конфликтуют по первому символу. Но можно создать общий ДКА который при появлении новго символа будет запихивать/удалять в/из некоторый список информацию о удовлетворяющих правилах. Так на символе '/' в списке окажется два правила (MultylineComment и SinglelineComment). Но уже при появлении '*' или '/' правило останется одно и проблемы исчезнут. Остается только проблема при совпадении правил, но если они не порождают токенов, то и проблем нет (встраивать их тела по месту в более "широкие" правила.
VD>Это даст скорость линейного поиска при относительно простом решении.
Можно сделать и так. Но, мне бы, например, хотелось предложить альтернативу. Чтобы данный генератор работал не только для создания разборщиков для языков программирования, но и для естественных языков (для продвинутых текстовых редакторов) и для интерфейсных динамически пополняемых языков.
VD>Вот только в современных языках есть кое какие проблемы. Например, в C# есть контексные ключевые слова. Так слова "get"/"set" встречаются только в эксесорах свойств, т.е. в: VD>
VD>int Property { get { return 1; } }
VD>
VD>"get" бедет ключевым словом. А в: VD>
VD>int get;
VD>
VD>нет.
VD>Для решения этой проблемы можно просто переписать граматику объявив идентификатор таким образом: VD>
VD>Ident : ident | "get" | "set".
VD>
VD>Тогда проблема решается. Но ведь мы как раз говорили, о том, что желательно иметь парсер для которого не требуется изменять граматику.
VD>Еще более забавным случаем является контекстное ключевое слово "partial". Оно является ключевым только если перед ним идут слова "class"/"interface"/"struct". Тут уже просто так засунуть "partial" в Ident не удается. А на уровне лексера проблема решается путем несколькоих заглядываний вперед при появлени слова "partial". Нужно просто проверить идет ли за ним одно из этих слов, пропуская при этом коментарии и пробельные символы.
VD>Интересно как в этих случаях может помочь распараллеливание лексера?
Здесь не нужно решать эти проблемы на уровне лексического анализатора. Лексер для того и придуман, чтобы упростить анализ, позволяя выделять простые подмножества исходного языка перед сложным анализом. В данном случае можно просто возвращать что-то типа string-token, а затем, зная контекст, уже преобразовывать его в ключевое слово или идентификатор. Но это уже проблема конкретного компилятора, а не генератора разборщиков. Можно конечно, ввести специальный контекст в лексический анализатор, но принципиально это нехорошо, т.к. ведет к излишнему усложнению системы. Можно реализовать систему фильтров. Например, в си++ токен ">>". Как известно, в определенном контексте это может быть окончание декларации шаблонного параметра шаблона плюс окончание декларации самого шаблона. Лексический анализатор, встречая подряд две угловые скобки, возвращает оператор правого побитового сдвига. Вот, пусть лексический анализатор возвращает всегда одну угловую скобку, а верхний фильтр, в зависимости от контекста, интерпретирует это как часть оператора сдвига или конец декларации шаблона или знак больше.
M>> Синтаксический анализатор разбирает поток токенов, которые для синтаксического анализатора являются просто терминальными символами входной грамматики,
VD>Ну, это классика.
M>> и возвращает дерево вывода (или множество таких деревьев, если грамматика неоднозначная).
VD>А насколько затормозится парсер если однозначость появляется при довольно глубоком заглядывании вперед? И как решаются проблемы "неудобных" рекурсий.
Там нет "заглядываний вперед", происходит параллельное построение деревьев вывода снизу вверх.
M>>Алгоритм Эрли позволяет разбирать линейные грамматики (т.е. грамматики, для которых только одна альтернатива, как в LL(k) или LR(k) грамматиках) за O(n),
VD>LL(k) за O(n)? Странно. Мне казалось, что за O(n) может работать только LL(1), а вся борба в LL(k)-апрсерах связана с оптимизицией заглядываний вперед. Я так понял, что LL(*) как раз и является разумным решением дя LL-арсеров.
Нет, для любого LL(k) разбор идет за время O(n), для этого и придуманы множества FIRST и FOLLOW.
M>> где n — длина входной терминальной строки, однозначные грамматики — за O(n^2) и неоднозначные — за O(n^3). В общем случае, алгоритм Эрли работает медленнее LR(k)-анализатора, проблема в константе для O(n). Но, в 90-х годах была придумана модификация алгоритма Эрли, которая позволяет разбирать линейные грамматики с той же скоростью, что и бизон. Для этого метода пока не создан алгоритм построения дервьев вывода, это как раз тема кандидатской диссертации. Так что, кому интересно — можно над этим поработать. Сам алгоритм можно использовать прямо сейчас, работа состоит в доказательстве его корректности.
VD>То есть нет полной уверенности, что алгоритм корректен?
Алгоритмов на самом деле много. Есть классический алгоритм Эрли, который не строит деревьев вывода. Есть мой алгоритм, который строит деревья вывода для классического алгоритма Эрли Есть, так называемый, быстрый алгоритм Жрли, придуманный двумя канадцами в конце 90-х годов. Вот этот алгоритм стравним по скорости с LR-анализатором, быстрее которого нет ничего, но не строит деревьев вывода. Можно придумать (точнее, я уже придумал) как строить деревья вывода и для этого алгоритма. Тогда новый алгоритм будет работать быстро, а также будет позволять производить семантическую корректировку синтаксического анализа на ходу, отбрасывая семантически некорректные альтернативы и, тем самым, увеличивая скорость разбора. В этом и состоит преимущество алгоритма, который я предлагаю реализовать, перед GLR.
VD>>>2. Где можно почитать о твоем методе. (по возможности популярно).
M>>Мой метод — это алгоиритм Эрли, расширенный и модифицированный таким образом, чтобы строить деревья вывода, что оригинальный алгоритм Эрли делать не мог. Точнее, сам Эрли думал, что мог, но в его рассуждениях была ошибка. Эту ошибку обнаружил в 80-х Томита, исправить ее не смог и взялся за другой алгоритм — LR-анализа,
VD>Алгоритм Эрли тоже LR? А как при этом с простотой отладки граматик и с разумностью сообщений об ошибках парсинга? У Яков с Бизонами с этим серьезные проблемы.
Да нет у них проблем с сообщениями об ошибках. Есть проблемы с восстановлением работы после возникновения ошибки. Там это дело решается входом в так называемый "режим паники", что не есть хорошо во многих случаях. Алгоритм Эрли позволяет использовать длругую стратегию. Вообще, это тема очень обширная и требует отдельного большого обсуждения.
M>> расширил его и получил GLR. Я нашел как исправить эту ошибку и показал корректность работы нового алгоритма. Прочитать об алгоритме Эрли можно в моих работах, но там много математики и очень формально. Лучшее популярное описание все в той же книжке двух голландцев "Техника синтаксического анализа", насколько я помню.
VD>К сожалению у меня ее нет. Она доступна в магазинах?
я уже давал ссылку на нее.
VD>Кстати, может быть первым делом сделать доступную статью и опубликовать ее у нас? Я мог бы помочь в плане разжевывания и упрощения изложения. Думаю это могло бы двинуть энтузиазм, ну, и за одно я бы по ходу пьесы разобрался бы в алгоритме.
Да наверное, если что-то проклюнется, я бы мог написать такое введение (у меня что-то уже есть) и потом ответить на вопросы. Но, для этого, вероятно, необходимо уже отдельную ветку открыть. Статью я, конечно, могу прислать.
M>> Вообще, там надо разобраться, знаю по своему опыту. Объяснял многим людям.
VD>Ну, вот объясни мен и мы вместе напишем популярную статью которая откроет суть твоего алгоритма для всех.
VD>>>3. Насколко ты готов разобраться в этом вопросе тем кто займется этоим доведением до ума?
M>>Я готов помочь, объяснить алгоритм, рассказать о задачах, которые стоят и все такое прочее. Программировать я, к сожалению, не смогу.
VD>ОК. Давай попробуем. Предлагаю для этого открыть новую тему и обсудеть суть этого алгоритма в нем.
Ну вот, можно. Посмотрю что-то у меня уже есть, просто скопирую туда и статью присоеденю. А затем уже обсуждать будем.
M>>Но, можно было бы коллективно поработать над новой реализацией быстрого алгоритма Эрли с построением деревьев вывода. Если это получится (в чем я абсолютно уверен), то будет вне конкуренции.
VD>А как, по-твоему, он по сравнению тем же GLR по скорости на явзыках типа С++/C# (т.е. языках в которых есть множество мест когда конкретное правило можно определить только при многократном заглядывании вперед)?
M>>По моему мнению, в таком генераторе необходимо реализовать несколько алгоритмов синтаксического анализа. Главные из них: быстрый алгоритм Эрли и GLR.
VD>А смысл несколько?
Ну, может быть и никакого.
M>> Затем, необходимо реализовать адапатированный для построения деревьев вывода алгоритм Эрли (мой), так чтобы позволить легко менять исходныю грамматику прямо между двумя запусками алгоритма разбора.
VD>На ходу? Без создания ДКА? Боюсь, что это станет тормозом. Хотя лично для моих нужд (расширение языка с целью внедрения в него средств метапрограммирования) динамический парсер был бы удобен.
M>> Бизон, например, этого делать не позволяет, также как и АНТЛР. Ведь они берут грамматику из текстового файла, обрабатывают ее, извлекая дополнительную информацию, и только затем генерируют разборщик.
VD>Дык это самое эффективное решение. Конкретная граматика превращается в эффектинвный код разбора. Никакой интерпретации. Возможность использовать хот switch-ей, хоть двумерных массивов...
Да я не против, просто бывает, что так не получается. В случае расширяемых языков, например. Поэтому, я и говорю, что надо бы дать альтернативу.
M>> Я назвал такую модель генерации разборщиков статической моделью компиляции (СМК). Классический алгоритм Эрли ничего такого не требует, просто берет грамматику правило за правилом и разбирает. Я назвал такую можель динамической моделью компиляции (ДМК). ДМК полезен в тех ситуациях, когда исходный язык часто меняется, пополняется пользователем. С другой стороны, СМК работает быстрее, так как "знает" больше о свойствах грамматики. Это знание в случае LR-анализа есть LR-автомат, а случае LL(*)-анализа есть LL(*)-автомат.
VD>Боюсь, без заранее построенных автоматов (лучше в виде генерируемого кода) тут не обойтись. На сегодны динамическая компиляция не является проблемой. Так что делать интерпретатор без ДКА в основе крайне не разумно. И никакие блага простой модификации тут не перевесят. Все же в рельных проектах унжно перелопачивать по 3-15 мег кода и медленный парсет тут будет большой проблемой. Ну, и парсеры намного проще писать на языках с GC. А у них есть своим потери на разные "барьеры записи". Так что крайне желательно иметь действительно эффективный алгоритм.
Ну да, это более узкая задача построения трансляторов языков программирования. А вот, как быть с задаче построения анализатора грамматики в текстовом редакторе? Там неоднозначностей очень много, язык уж больно сложен, и язык часто пополняется новыми терминалами (добавить в словарь в ворде). Здесь уже можно пожертвовать скростью. при этом, это ведь тоже типичная программисткая задача. Поэтому, я считаю, что необходимо предложить альтернативу.
M>> В общем, работы там много и работы интересной.
VD>Это понятно.
M>> Есть еще проблема обработки ошибок,
VD>Вот этого я и боюсь. Когда я сравнивал бесплатные построители парсеров, то Яки и Безоны пошли в лес отчасти потому что реализация на них осмысленных сообщений об ошибках крайне затруднительно.
M>>тоже есть несколько интересных решений.
Re[22]: Theory and Techniques of Compiler Construction
Здравствуйте, mefrill, Вы писали:
M>Поэтому, я на ходу произвожу моделированние ДКА делая параллельный проход по автоматам для каждого подходящего токена.
Что то я не очень улвливаю. Т.е. ты создаешь из множества ДКА единый в рантайме?
M>Можно сделать и так. Но, мне бы, например, хотелось предложить альтернативу. Чтобы данный генератор работал не только для создания разборщиков для языков программирования, но и для естественных языков (для продвинутых текстовых редакторов) и для интерфейсных динамически пополняемых языков.
Я вот как раз сейчас пытаюсь создать реализацию лексера пригодную для тексового редактопра с подсветкой синтаксиса и возможно для автономного использования. Незнаю как для естественных языков, но для моих задач статического ДКА вроде хватает.
Что же до "динамически пополняемых языков", то лексер то можно пополнить, но как на это отреагирует граматическая часть?
M>Здесь не нужно решать эти проблемы на уровне лексического анализатора. Лексер для того и придуман, чтобы упростить анализ, позволяя выделять простые подмножества исходного языка перед сложным анализом. В данном случае можно просто возвращать что-то типа string-token, а затем, зная контекст, уже преобразовывать его в ключевое слово или идентификатор.
А кто будет преобразовывать? Я пиршел к выводу, что проще всего это как раз делать в лексере.
M> Но это уже проблема конкретного компилятора, а не генератора разборщиков.
Проблема генератора парсеров в том, чтобы с его помощью можно было максимально просто создать парсер для любого сязыка.
M> Можно конечно, ввести специальный контекст в лексический анализатор, но принципиально это нехорошо, т.к. ведет к излишнему усложнению системы.
А идентификатор вместо "partial" — это хорошо? Ведь все равно будет проблема. Надо будет на уровне семантики проверять, что этот идентификатор на самом деле "partial". И это еще в лучшем случае. В худшем попрут неоднозначности.
M> Можно реализовать систему фильтров. Например, в си++ токен ">>". Как известно, в определенном контексте это может быть окончание декларации шаблонного параметра шаблона плюс окончание декларации самого шаблона.
Нет. Тут ты ошибашся. В С++ >> — это всегда оператор сдвига. По этому очень часто бывает ошибка когда во вложенных шаблонах народ забывает добавить пробел между знаками ">". А вот в C# >> действительно перегружен. Но есть правило празрешения конфлитка описанное в спецификации. Я тебе уже приводил это место: http://rsdn.ru/Forum/Message.aspx?mid=958690&only=1
M> Лексический анализатор, встречая подряд две угловые скобки, возвращает оператор правого побитового сдвига. Вот, пусть лексический анализатор возвращает всегда одну угловую скобку, а верхний фильтр, в зависимости от контекста, интерпретирует это как часть оператора сдвига или конец декларации шаблона или знак больше.
Ну, примерно так и делается. Вот только такой "фильтр" выраждается в довольно сложную процедуру заглядывания вперед.
M>Там нет "заглядываний вперед", происходит параллельное построение деревьев вывода снизу вверх.
Т.е. еще на стадии построения парсера мы строим несколько автоматов и в местах где может появиться неоднозначность просто по парсим оба варианта, а там как получится?
M>Нет, для любого LL(k) разбор идет за время O(n), для этого и придуманы множества FIRST и FOLLOW.
Что-то мне казалось, что чем больше k, тем больше время.
Кстати, ты где нибудь видел человеческое описание преобразования НКА в ДКА и построение ДКА по синтаксическому дереву регулярных выражений. А то, то что я нашел это какая-то задница. Понять очень не просто.
M>Алгоритмов на самом деле много. Есть классический алгоритм Эрли, который не строит деревьев вывода. Есть мой алгоритм, который строит деревья вывода для классического алгоритма Эрли Есть, так называемый, быстрый алгоритм Жрли, придуманный двумя канадцами в конце 90-х годов. Вот этот алгоритм стравним по скорости с LR-анализатором, быстрее которого нет ничего,
Ну, LL(1) без конфликтов еще никто не обгонял.
M>но не строит деревьев вывода.
А в чем такая проблема построить деревья вывода? Это ведь как я понимаю просто путь реального разбора. Так? Ну, так для каждой однозначной ветки можно построить ДКА. Для пересекающихся это будет общий ДКА с указанием что состояние принадлежит нескольким символам разных правил. Причем, похоже, что тут и LR нафиг не упал (с магазинами). Достаточно одного аннотированного ДКА и некой механики отслеживания путей. Если путей два, то просто отплевываем два. Если один из них оборвался, то просто забываем про него.
В общем, или все очень просто и я не понимаю почему эта идея не пришла раньше никому в голову. Или у меня какая-то ошибка.
Хотя может это и есть LALR(*) вид сбоку и LL(*), LALR(*) с GLL есть не что иное как разные точки зрения на один алгоритм.
M> Можно придумать (точнее, я уже придумал) как строить деревья вывода и для этого алгоритма. Тогда новый алгоритм будет работать быстро, а также будет позволять производить семантическую корректировку синтаксического анализа на ходу, отбрасывая семантически некорректные альтернативы и, тем самым, увеличивая скорость разбора. В этом и состоит преимущество алгоритма, который я предлагаю реализовать, перед GLR.
Проясни для меня один вопрос. Вот если у нас есть некие два правила:
A : B {C|D} E;
A : B {C|D} F;
то в твоем случае парсер будет разбирать два пути пареллельно или он все же пройдет неоднозначную цепочку "B {C|D}" и разрешит проблему найдя E или F?
M>Да нет у них проблем с сообщениями об ошибках. Есть проблемы с восстановлением работы после возникновения ошибки.
Ну, можешь называть это как хочешь. Но при сканировании слева на право понять что случилось намного проще. Дубовые же Яки псото выкидывают сообщение "ожидается: ..." где "..." — это пара десятков токенов и думай что хочешь. В LL(1) парсере тебе говорят, что ожидается Х или У и нет проблем.
M> Там это дело решается входом в так называемый "режим паники", что не есть хорошо во многих случаях. Алгоритм Эрли позволяет использовать длругую стратегию. Вообще, это тема очень обширная и требует отдельного большого обсуждения.
Согласен, но по своему опыту замучу, что в LL(k) парсерах она решается куда проще. Да и рекурсивный спуск позволяет трассировать граматику понимая что происходит в данный момент.
VD>>Кстати, может быть первым делом сделать доступную статью и опубликовать ее у нас? Я мог бы помочь в плане разжевывания и упрощения изложения. Думаю это могло бы двинуть энтузиазм, ну, и за одно я бы по ходу пьесы разобрался бы в алгоритме.
M>Да наверное, если что-то проклюнется, я бы мог написать такое введение (у меня что-то уже есть) и потом ответить на вопросы. Но, для этого, вероятно, необходимо уже отдельную ветку открыть. Статью я, конечно, могу прислать.
Давай. И попробуем в интерактивном режиме довести ее до того состояния чтобы средний программист ее мог понять. Я как раз на этом собачек поел приизрядно.
M>Ну вот, можно. Посмотрю что-то у меня уже есть, просто скопирую туда и статью присоеденю. А затем уже обсуждать будем.
M>Да я не против, просто бывает, что так не получается. В случае расширяемых языков, например. Поэтому, я и говорю, что надо бы дать альтернативу.
А как часто в таких языках появляются новые токены?
M>Ну да, это более узкая задача построения трансляторов языков программирования. А вот, как быть с задаче построения анализатора грамматики в текстовом редакторе?
На естесвтенном языке? Дык если слово отсуствует, то кроме как некую абстракцию типа "идентификатор" ты ее не определишь. А если пользователь пополнит словарь, то не грех и автомат перестроить. Ведь динамическая компиляция это доли секунды (десятые обычно, если говорить про дотнет) и человек этой задержки даже не заметит. А вот задержку при анализе большого текста заметит. Даже если она в отдельном потоке убдет.
M> Там неоднозначностей очень много, язык уж больно сложен, и язык часто пополняется новыми терминалами (добавить в словарь в ворде). Здесь уже можно пожертвовать скростью. при этом, это ведь тоже типичная программисткая задача. Поэтому, я считаю, что необходимо предложить альтернативу.
И все же пополняться словами динамически не нужно. А человек настолько медлителен, что пересоздания кода парсера он незаметит. Ну, конечно если код будет достойно написан.
... << RSDN@Home 1.2.0 alpha rev. 591>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[23]: Theory and Techniques of Compiler Construction
Здравствуйте, VladD2, Вы писали:
VD>Кстати, ты где нибудь видел человеческое описание преобразования НКА в ДКА и построение ДКА по синтаксическому дереву регулярных выражений. А то, то что я нашел это какая-то задница. Понять очень не просто.
ИМХО в "Красном драконе" написано достаточно понятно.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[23]: Theory and Techniques of Compiler Construction
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, mefrill, Вы писали:
M>>Поэтому, я на ходу произвожу моделированние ДКА делая параллельный проход по автоматам для каждого подходящего токена.
VD>Что то я не очень улвливаю. Т.е. ты создаешь из множества ДКА единый в рантайме?
Ага. Точнее, моделирую его создание в алгоритме лексического анализа. Ниже ты спрашивал, где найти хорошее описание алгоритма преобразования НКА в ДКА. Вот ключ к пониманию идеи этого алгоритма и есть то, о чем я писал. Идея проста: если у тебя есть НКА, значит из какого-то состояния есть по крайне мере два перехода по одному и тому же символу в разные состояния. Идея в том, чтобы каким-то образом "различить" эти переходы. Это возможно только "заглядыванием вперед" чтобы увидеть какие переходы будут дальше из следующих состояний. Вот идешь параллельно по таким двум разным путям, покуда не раличишь, т.е. не найдешь разные переходы. По пути получаешь последовательность состояний. Это есть подмножество множества всех состояний данного НКА. Поэтому состояниями ДКА будем подмножества состояний исходного НКА. Например, у тебя есть два ДКА 1-a->2-b->3 и 4-a->5-c->6. Один допускает строку ab, другой — строку ac. Сливая их, мы объединяем начальные состояния 1 и 4 и получаем недетерминизм: из состояния (1,4) есть два перехода по симолу a, в состояние 2 и состояние 5. Конструируем ДКА: идем по первомй пути, получаем последовательность {(1,4),2}, по второму пути — {(1,4),5}. Из первого состояния переход в состояние 3 по символу b, из второго в остояние 6 по символу c. Вот и все. Тоже самое делал и я в динамическом варианте лексического анализатора на основе ДКА для каждого токена. Вначале я запускал все ДКА с начального состояния, затем, считал переходы по входному символу. Если был недетерминизм, то как раз и получались такие пути-последовательности множеств состояний каждого ДКА.
M>>Можно сделать и так. Но, мне бы, например, хотелось предложить альтернативу. Чтобы данный генератор работал не только для создания разборщиков для языков программирования, но и для естественных языков (для продвинутых текстовых редакторов) и для интерфейсных динамически пополняемых языков.
VD>Я вот как раз сейчас пытаюсь создать реализацию лексера пригодную для тексового редактопра с подсветкой синтаксиса и возможно для автономного использования. Незнаю как для естественных языков, но для моих задач статического ДКА вроде хватает.
Ну может быть, для этих задач и хватает. Я еще писал не только о подсветке, а о синтаксическом анализе предложений, как в ворде подчеркивание зеленым цветом, не красным.
VD>Что же до "динамически пополняемых языков", то лексер то можно пополнить, но как на это отреагирует граматическая часть?
M>>Здесь не нужно решать эти проблемы на уровне лексического анализатора. Лексер для того и придуман, чтобы упростить анализ, позволяя выделять простые подмножества исходного языка перед сложным анализом. В данном случае можно просто возвращать что-то типа string-token, а затем, зная контекст, уже преобразовывать его в ключевое слово или идентификатор.
VD>А кто будет преобразовывать? Я пиршел к выводу, что проще всего это как раз делать в лексере.
M>> Но это уже проблема конкретного компилятора, а не генератора разборщиков.
VD>Проблема генератора парсеров в том, чтобы с его помощью можно было максимально просто создать парсер для любого сязыка.
M>> Можно конечно, ввести специальный контекст в лексический анализатор, но принципиально это нехорошо, т.к. ведет к излишнему усложнению системы.
VD>А идентификатор вместо "partial" — это хорошо? Ведь все равно будет проблема. Надо будет на уровне семантики проверять, что этот идентификатор на самом деле "partial". И это еще в лучшем случае. В худшем попрут неоднозначности.
Ну да, так и надо. Это как раз и позволит четко отделить семантику от синтаксиса.
M>> Можно реализовать систему фильтров. Например, в си++ токен ">>". Как известно, в определенном контексте это может быть окончание декларации шаблонного параметра шаблона плюс окончание декларации самого шаблона.
VD>Нет. Тут ты ошибашся. В С++ >> — это всегда оператор сдвига. По этому очень часто бывает ошибка когда во вложенных шаблонах народ забывает добавить пробел между знаками ">". А вот в C# >> действительно перегружен. Но есть правило празрешения конфлитка описанное в спецификации. Я тебе уже приводил это место: http://rsdn.ru/Forum/Message.aspx?mid=958690&only=1
Пару лет назад кто-то мне говорил, что в новом стандарте хотели сделать это свойство. Чтобы в шаблонном параметре можно было писать две завершающие угловые скобки без пробела. Значит, не сделали.
M>> Лексический анализатор, встречая подряд две угловые скобки, возвращает оператор правого побитового сдвига. Вот, пусть лексический анализатор возвращает всегда одну угловую скобку, а верхний фильтр, в зависимости от контекста, интерпретирует это как часть оператора сдвига или конец декларации шаблона или знак больше.
VD>Ну, примерно так и делается. Вот только такой "фильтр" выраждается в довольно сложную процедуру заглядывания вперед.
M>>Там нет "заглядываний вперед", происходит параллельное построение деревьев вывода снизу вверх.
VD>Т.е. еще на стадии построения парсера мы строим несколько автоматов и в местах где может появиться неоднозначность просто по парсим оба варианта, а там как получится?
Нет, там по другому. Автоматы строятся в быстром алгоритме Эрли, но только для того, чтобы увеличить скорость разбора, сам алгоритм Эрли обходится без автоматов.
M>>Нет, для любого LL(k) разбор идет за время O(n), для этого и придуманы множества FIRST и FOLLOW.
VD>Что-то мне казалось, что чем больше k, тем больше время.
Вообще говоря, конечно это так. Дело здесь в поиске по множествам FIRST и FOLLOW. Но это совершенно не зависит от длины входной строки, т.е. считается, в данном случае, константой. Т.е. скорость есть O(n), но величина константы больше.
VD>Кстати, ты где нибудь видел человеческое описание преобразования НКА в ДКА и построение ДКА по синтаксическому дереву регулярных выражений. А то, то что я нашел это какая-то задница. Понять очень не просто.
M>>Алгоритмов на самом деле много. Есть классический алгоритм Эрли, который не строит деревьев вывода. Есть мой алгоритм, который строит деревья вывода для классического алгоритма Эрли Есть, так называемый, быстрый алгоритм Жрли, придуманный двумя канадцами в конце 90-х годов. Вот этот алгоритм стравним по скорости с LR-анализатором, быстрее которого нет ничего,
VD>Ну, LL(1) без конфликтов еще никто не обгонял.
Ну как же, LR-анализатор быстрее работает. Он делает примерно тоже самое, но еще и учитывает контекст.
M>>но не строит деревьев вывода.
VD>А в чем такая проблема построить деревья вывода? Это ведь как я понимаю просто путь реального разбора. Так? Ну, так для каждой однозначной ветки можно построить ДКА. Для пересекающихся это будет общий ДКА с указанием что состояние принадлежит нескольким символам разных правил. Причем, похоже, что тут и LR нафиг не упал (с магазинами). Достаточно одного аннотированного ДКА и некой механики отслеживания путей. Если путей два, то просто отплевываем два. Если один из них оборвался, то просто забываем про него.
Не все так просто. Там сложнее на самом деле.
VD>В общем, или все очень просто и я не понимаю почему эта идея не пришла раньше никому в голову. Или у меня какая-то ошибка.
VD>Хотя может это и есть LALR(*) вид сбоку и LL(*), LALR(*) с GLL есть не что иное как разные точки зрения на один алгоритм.
Нет, LALR(k) — это тот же LR(k), но для уменьшения количества состояний LR(k)-автомата некоторые состояния сливаются. Это, так называемые, состояния с одиннаковыми ядрами. Получается в результате автомат, который хоть и, бывает, не допускает некоторые строки, как это делает LR(k)-автомат, но все-же достаточно мощный и, главное, содержит намного меньше состояний, что в 70-х годах имело большое значение. интересная проблема была в том, чтобы получить LALR(k)-атвомат, не строя LR(k)-автомата. Здесь в 1978 году был придуман алгоритм Де Ремьера, который является ни чем иным, как алгоритмом нахождения сильно связанных компонент графа за линейное время Боба Тарджана. Алгоритм, приведенный в красном драконе был применен в яке, я называю его "алгоритмом прибытия на станции" и он не так эффективен. В бизоне уже применен алгоритм Де Ремьера. Хотя бизон, на самом деле, это стыренный беркли як.
M>> Можно придумать (точнее, я уже придумал) как строить деревья вывода и для этого алгоритма. Тогда новый алгоритм будет работать быстро, а также будет позволять производить семантическую корректировку синтаксического анализа на ходу, отбрасывая семантически некорректные альтернативы и, тем самым, увеличивая скорость разбора. В этом и состоит преимущество алгоритма, который я предлагаю реализовать, перед GLR.
VD>Проясни для меня один вопрос. Вот если у нас есть некие два правила: VD>
VD>A : B {C|D} E;
VD>A : B {C|D} F;
VD>
VD>то в твоем случае парсер будет разбирать два пути пареллельно или он все же пройдет неоднозначную цепочку "B {C|D}" и разрешит проблему найдя E или F?
Честно говоря, не вижу здесь неоднозначности. Разве два дерева вывода строится?
M>>Да нет у них проблем с сообщениями об ошибках. Есть проблемы с восстановлением работы после возникновения ошибки.
VD>Ну, можешь называть это как хочешь. Но при сканировании слева на право понять что случилось намного проще. Дубовые же Яки псото выкидывают сообщение "ожидается: ..." где "..." — это пара десятков токенов и думай что хочешь. В LL(1) парсере тебе говорят, что ожидается Х или У и нет проблем.
M>> Там это дело решается входом в так называемый "режим паники", что не есть хорошо во многих случаях. Алгоритм Эрли позволяет использовать длругую стратегию. Вообще, это тема очень обширная и требует отдельного большого обсуждения.
VD>Согласен, но по своему опыту замучу, что в LL(k) парсерах она решается куда проще. Да и рекурсивный спуск позволяет трассировать граматику понимая что происходит в данный момент.
Так и построение дерева снизу вверх также позволяет все это понимать. Только изучение труднее и все.
VD>>>Кстати, может быть первым делом сделать доступную статью и опубликовать ее у нас? Я мог бы помочь в плане разжевывания и упрощения изложения. Думаю это могло бы двинуть энтузиазм, ну, и за одно я бы по ходу пьесы разобрался бы в алгоритме.
M>>Да наверное, если что-то проклюнется, я бы мог написать такое введение (у меня что-то уже есть) и потом ответить на вопросы. Но, для этого, вероятно, необходимо уже отдельную ветку открыть. Статью я, конечно, могу прислать.
VD>Давай. И попробуем в интерактивном режиме довести ее до того состояния чтобы средний программист ее мог понять. Я как раз на этом собачек поел приизрядно.
Ага, вечером из дома вышлю.
M>>Ну вот, можно. Посмотрю что-то у меня уже есть, просто скопирую туда и статью присоеденю. А затем уже обсуждать будем.
M>>Да я не против, просто бывает, что так не получается. В случае расширяемых языков, например. Поэтому, я и говорю, что надо бы дать альтернативу.
VD>А как часто в таких языках появляются новые токены?
M>>Ну да, это более узкая задача построения трансляторов языков программирования. А вот, как быть с задаче построения анализатора грамматики в текстовом редакторе?
VD>На естесвтенном языке? Дык если слово отсуствует, то кроме как некую абстракцию типа "идентификатор" ты ее не определишь. А если пользователь пополнит словарь, то не грех и автомат перестроить. Ведь динамическая компиляция это доли секунды (десятые обычно, если говорить про дотнет) и человек этой задержки даже не заметит. А вот задержку при анализе большого текста заметит. Даже если она в отдельном потоке убдет.
Ну как хочешь. Можно реализовать только быстрый алгоритм Эрли. Если ставить только специфическую задачу разработки транслятора для языков программирования.
M>> Там неоднозначностей очень много, язык уж больно сложен, и язык часто пополняется новыми терминалами (добавить в словарь в ворде). Здесь уже можно пожертвовать скростью. при этом, это ведь тоже типичная программисткая задача. Поэтому, я считаю, что необходимо предложить альтернативу.
VD>И все же пополняться словами динамически не нужно. А человек настолько медлителен, что пересоздания кода парсера он незаметит. Ну, конечно если код будет достойно написан.
Re[24]: Theory and Techniques of Compiler Construction
mefrill,
m> Пару лет назад кто-то мне говорил, что в новом стандарте хотели сделать m> это свойство. Чтобы в шаблонном параметре можно было писать две m> завершающие угловые скобки без пробела. Значит, не сделали.
Просто новый стандарт еще не выходил. Выйдет году в 2009 или около того.
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Re[24]: Theory and Techniques of Compiler Construction
Здравствуйте, mefrill, Вы писали:
M>Ага. Точнее, моделирую его создание в алгоритме лексического анализа. Ниже ты спрашивал, где найти хорошее описание алгоритма преобразования НКА в ДКА. Вот ключ к пониманию идеи этого алгоритма и есть то, о чем я писал. Идея проста: если у тебя есть НКА, значит из какого-то состояния есть по крайне мере два перехода по одному и тому же символу в разные состояния. Идея в том, чтобы каким-то образом "различить" эти переходы. Это возможно только "заглядыванием вперед" чтобы увидеть какие переходы будут дальше из следующих состояний. Вот идешь параллельно по таким двум разным путям, покуда не раличишь, т.е. не найдешь разные переходы. По пути получаешь последовательность состояний. Это есть подмножество множества всех состояний данного НКА. Поэтому состояниями ДКА будем подмножества состояний исходного НКА. Например, у тебя есть два ДКА 1-a->2-b->3 и 4-a->5-c->6. Один допускает строку ab, другой — строку ac. Сливая их, мы объединяем начальные состояния 1 и 4 и получаем недетерминизм: из состояния (1,4) есть два перехода по симолу a, в состояние 2 и состояние 5. Конструируем ДКА: идем по первомй пути, получаем последовательность {(1,4),2}, по второму пути — {(1,4),5}. Из первого состояния переход в состояние 3 по символу b, из второго в остояние 6 по символу c. Вот и все. Тоже самое делал и я в динамическом варианте лексического анализатора на основе ДКА для каждого токена. Вначале я запускал все ДКА с начального состояния, затем, считал переходы по входному символу. Если был недетерминизм, то как раз и получались такие пути-последовательности множеств состояний каждого ДКА.
Ясно. Но это интерпретация, а значит замедление. Все же лучше объеденять ДКА заранее и аннотировать общие состояния (как я уже описывал).
M>Ну может быть, для этих задач и хватает. Я еще писал не только о подсветке, а о синтаксическом анализе предложений, как в ворде подчеркивание зеленым цветом, не красным.
Как я уже говорил, добавление новых токенов настолько редки по сравнению с постоянным анализом огромных текстов, что я бы предпочел динамическую компиляцию. Я переодически правлю генератор парсеров CocoR и даже не замечаю его перекомпиляции.
VD>>А идентификатор вместо "partial" — это хорошо? Ведь все равно будет проблема. Надо будет на уровне семантики проверять, что этот идентификатор на самом деле "partial". И это еще в лучшем случае. В худшем попрут неоднозначности.
M>Ну да, так и надо. Это как раз и позволит четко отделить семантику от синтаксиса.
Дык намного проще заложить проверку в лексере. Там делов то будет:
if (token.Kind == Tokens.Partial)
{
Token next = Peek();
if (next.Kind == Tokens.Class)
token = Tokens.Identifier;
}
или что-то в этом ролде. А вот в парсере... Как обяснить автомату?
M>Пару лет назад кто-то мне говорил, что в новом стандарте хотели сделать это свойство. Чтобы в шаблонном параметре можно было писать две завершающие угловые скобки без пробела. Значит, не сделали.
Последний стандарт С++ был впринят в 1998-ом году. Может это он о том, что будет в 2008? Ну, да это меня пока не трогает. Ладно. Это все фигня.
M>Нет, там по другому. Автоматы строятся в быстром алгоритме Эрли, но только для того, чтобы увеличить скорость разбора, сам алгоритм Эрли обходится без автоматов.
Хм... загадочно. Опять боюсь что "быстрый" на деле окажется не очень быстрым.
VD>>Ну, LL(1) без конфликтов еще никто не обгонял.
M>Ну как же, LR-анализатор быстрее работает. Он делает примерно тоже самое, но еще и учитывает контекст.
Да что же может быть быстрее простого рекурсивного спуска?
VD>>Хотя может это и есть LALR(*) вид сбоку и LL(*), LALR(*) с GLL есть не что иное как разные точки зрения на один алгоритм.
M>Нет, LALR(k) — это тот же LR(k),
Ну, это не важно. Я про саму суть. Как только вместо некоторого k появляется * (т.е. бесконечность), то возможно разница между снизу вверх и сверху вниз уже может стереться. Ведь всегда можно простроить все дерево со всеми неоднозначностями до конца и получить просто направленный ациклический граф. А там уже можно безать по нему и тупо делать то что нужно.
Вопрос опять таки в обработке ошибок. Ведь не так просто бодет сопоставить ДКА и исходную граматику.
VD>>Проясни для меня один вопрос. Вот если у нас есть некие два правила: VD>>
VD>>A : B {C|D} E;
VD>>A : B {C|D} F;
VD>>
VD>>то в твоем случае парсер будет разбирать два пути пареллельно или он все же пройдет неоднозначную цепочку "B {C|D}" и разрешит проблему найдя E или F?
M>Честно говоря, не вижу здесь неоднозначности. Разве два дерева вывода строится?
Ну, это как реализовать. Я зе не знаю суть предлагаемых тобой алгоритмов.
M>Так и построение дерева снизу вверх также позволяет все это понимать. Только изучение труднее и все.
Ага. Всего лишь труднее. Остается только понять насколько.
M>Ага, вечером из дома вышлю.
Тогда поключай ее к новой теме.
M>Ну как хочешь. Можно реализовать только быстрый алгоритм Эрли. Если ставить только специфическую задачу разработки транслятора для языков программирования.
А как же какая-то там ошибка?
... << RSDN@Home 1.2.0 alpha rev. 591>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[25]: Theory and Techniques of Compiler Construction
VD>>>Хотя может это и есть LALR(*) вид сбоку и LL(*), LALR(*) с GLL есть не что иное как разные точки зрения на один алгоритм.
M>>Нет, LALR(k) — это тот же LR(k),
VD>Ну, это не важно. Я про саму суть. Как только вместо некоторого k появляется * (т.е. бесконечность), то возможно разница между снизу вверх и сверху вниз уже может стереться. Ведь всегда можно простроить все дерево со всеми неоднозначностями до конца и получить просто направленный ациклический граф. А там уже можно безать по нему и тупо делать то что нужно.
Очень интересно как они будут обрабатывать левую рекурсию типа
A-> ( A "," a )| a
Re[25]: Theory and Techniques of Compiler Construction
Здравствуйте, VladD2, Вы писали:
WH>>ИМХО в "Красном драконе" написано достаточно понятно. VD>Просто никак. Первод убит до ужаса.
Ну не знаю я с первого раза понял
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[25]: Theory and Techniques of Compiler Construction
Здравствуйте, VladD2, Вы писали:
WH>>Ну не знаю я с первого раза понял VD>Понял? Попробуй написать на ЯП. А я посмотрю сколько времени и сил убъёш. Ну, или в своих словах пересказать.
Писать не буду. Не до того сечас. А словами объяснить могу.
Преобразование НДКА в ДКА.
Из каждого состояния НДКА может быть неограниченое колличество переходов по одному и томуже сигналу. Так же может быть неограниченое колличество эпсилон переходов те переходов по которым может быть произведен переход по любому сигналу.
Имея на входе НДКА нужно построить ДКА. Для этого нам понадобятся две вспомогательные функции.
Первая функция (Move) по списку состояний НДКА и сигналу должна возвращать список состояний НДКА в которые можно перейти из данных состояний по данному сигналу.
Вторая функция (EpsilonMove) должна возвращать по списку состояний НДКА список состояний НДКА в которые можно перейти по одному или нескольким эпсилон переходам также в это множество нужно включить исходное множество переходов.
Работа алгоритма сводится к тому что несколько состояний НДКА превращаютя в одно состояние ДКА.
Состояния ДКА с одинаковым набором состояние НДКА являются одним и темже состоянием.
Теперь сам алгоритм
Берем список стартовых состояний НДКА и применяем EpsilonMove.
Мы получили стартовое состояние ДКА.
Добавляем это состояние в список состояний ДКА.
пока есть непомеченые состояния ДКА
{
состояние = берем первое не помеченое состояние ДКА
помечаем состояние
для каждого сигнала
{
новое_состояние = EpsilonMove(Move(состояние, сигнал))
если новое_состояние еще не добавлено то добавляем его
создаем переход по текущему сигналу из состояния в новое_состояние
}
}
Понятно?
Чтобы было понятнее посмотри пример из красного дракона на странице 130
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[28]: Theory and Techniques of Compiler Construction
Как-то больно примитивно. Фактически переложение доказательства теоремы о том, что для любого НДКА существует эквивалентный ДКА, единственная здравая мысль — строить состояния ДКА динамически, но это неизбежно, поскольку ДКА из НДКА получается невероятно большим.
Re[29]: Theory and Techniques of Compiler Construction
Здравствуйте, Quintanar, Вы писали:
Q>Как-то больно примитивно. Фактически переложение доказательства теоремы о том, что для любого НДКА существует эквивалентный ДКА, единственная здравая мысль — строить состояния ДКА динамически, но это неизбежно, поскольку ДКА из НДКА получается невероятно большим.
На практике, не таким уж и большим, ведь не всякое подмножество состояний исходного НКА есть состояние полученного ДКА, это еще зависит от количества переходов. Кроме того, можно затем мимнимизировать полученный ДКА по количеству состояний, часто получается ДКА с количеством состояний, меньшим чем исходный НКА.
Re[26]: Theory and Techniques of Compiler Construction
Здравствуйте, little_alex, Вы писали:
VD>>Ну, это не важно. Я про саму суть. Как только вместо некоторого k появляется * (т.е. бесконечность), то возможно разница между снизу вверх и сверху вниз уже может стереться. Ведь всегда можно простроить все дерево со всеми неоднозначностями до конца и получить просто направленный ациклический граф. А там уже можно безать по нему и тупо делать то что нужно.
_>Очень интересно как они будут обрабатывать левую рекурсию типа _>
A->> ( A "," a )| a
_>
_>
В том то и дело, что никак. Такова цена метода построения дерева вывода сверху вниз и с разбором альтернатив в глубину. Поэтому я и говорю, что толку от этого GLL будет мало, альтернативы то он распараллеливать будет, но на простой левой рекурсии зациклится.
Re[8]: Theory and Techniques of Compiler Construction
Здравствуйте, WolfHound, Вы писали:
VD>>Понял? Попробуй написать на ЯП. А я посмотрю сколько времени и сил убъёш. Ну, или в своих словах пересказать. WH>Писать не буду. Не до того сечас. А словами объяснить могу.
Вот реализация НДКА и функций Move и EpsilonMove
public class State
{
private int m_Number;
public int Number
{
get { return m_Number; }
}
public State(int number)
{
m_Number = number;
}
private StateSet m_Epsilon = new StateSet();
public StateSet Epsilon
{
get { return m_Epsilon; }
}
private Hashtable m_SignalTransitionsMap = new Hashtable();
public StateSet this[char signal]
{
get
{
StateSet set = (StateSet) m_SignalTransitionsMap[signal];
if (set == null)
{
set = new StateSet();
m_SignalTransitionsMap[signal] = set;
}
return set;
}
}
public bool CanMoveTo(char signal)
{
return m_SignalTransitionsMap.Contains(signal);
}
}
public class StateSet : IEnumerable
{
private Hashtable m_States = new Hashtable();
public StateSet Clone()
{
StateSet set = new StateSet();
foreach (State state in this)
set.Add(state);
return set;
}
public void Add(State state)
{
if (!Contains(state))
m_States.Add(state, state);
}
public void Remove(State state)
{
m_States.Remove(state);
}
public bool Contains(State state)
{
return m_States.Contains(state);
}
public IEnumerator GetEnumerator()
{
return m_States.Keys.GetEnumerator();
}
public int Count
{
get { return m_States.Count; }
}
public override bool Equals(object obj)
{
StateSet that = obj as StateSet;
if (that == null)
return false;
if (this.Count != that.Count)
return false;
foreach (State state in this)
if (!that.Contains(state))
return false;
return true;
}
public override int GetHashCode()
{
int hash = 0;
foreach (State state in this)
hash += state.GetHashCode();
return hash;
}
}
private static StateSet Move(StateSet set, char signal)
{
StateSet newSet = new StateSet();
foreach (State state in set)
if (state.CanMoveTo(signal))
foreach (State nextState in state[signal])
newSet.Add(nextState);
return newSet;
}
private static StateSet EpsilonMove(StateSet set)
{
StateSet newSet = set.Clone();
foreach (State state in set)
EpsilonMoveRec(state, newSet);
return newSet;
}
private static void EpsilonMoveRec(State state, StateSet newSet)
{
foreach (State nextState in state.Epsilon)
if (!newSet.Contains(nextState))
{
newSet.Add(nextState);
EpsilonMoveRec(nextState, newSet);
}
}
private static void Main()
{
State s1 = new State(1);
State s2 = new State(2);
State s3 = new State(3);
State s4 = new State(4);
State s5 = new State(5);
State s6 = new State(6);
State s7 = new State(7);
State s8 = new State(8);
State s9 = new State(9);
s1.Epsilon.Add(s2);
s1.Epsilon.Add(s3);
s1.Epsilon.Add(s6);
s2['b'].Add(s5);
s3['a'].Add(s4);
s4.Epsilon.Add(s6);
s5.Epsilon.Add(s6);
s6.Epsilon.Add(s1);
s6['a'].Add(s7);
s7['b'].Add(s8);
s8['b'].Add(s9);
StateSet set = new StateSet();
set.Add(s1);
set = EpsilonMove(set);
PrintSet(set);
set = Move(set, 'a');
PrintSet(set);
set = Move(set, 'b');
PrintSet(set);
set = EpsilonMove(set);
PrintSet(set);
}
private static void PrintSet(StateSet set)
{
if (set.Count == 0)
{
Console.WriteLine("Empty set.");
}
else
{
foreach (State state in set)
Console.Write(state.Number + " ");
Console.WriteLine();
}
}
}
Остальное допишу в другой раз. Сейчас времени нет.
НДКА для регулярного выражения (a|b)*abb
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[28]: Theory and Techniques of Compiler Construction
Здравствуйте, WolfHound, Вы писали:
WH>Писать не буду. Не до того сечас. А словами объяснить могу.
Нашол немного времени.
Из такого (a|b)*abb регулярного выражения получается вот такой ДКА:
1
a -> 5
b -> 2
2 end
a -> 5
b -> 4
3 start
a -> 5
b -> 4
4
a -> 5
b -> 4
5
a -> 5
b -> 1
Этот автомат еще можно оптимизировать по колличеству состояний но это в другой раз.
Вот полная версия
DFSMBuilder.cs
using System.Collections;
namespace FSM
{
internal class DFSMBuilder
{
private Queue m_Queue = new Queue();
private Hashtable m_States = new Hashtable();
public Hashtable States
{
get { return m_States; }
}
public void Build(params State[] states)
{
StateSet set = new StateSet();
foreach (State state in states)
set.Add(state);
Add(EpsilonMove(set));
while (m_Queue.Count > 0)
{
StateData state = (StateData) m_Queue.Dequeue();
foreach (char signal in Signals(state.Set))
{
StateSet next = EpsilonMove(Move(state.Set, signal));
state.SetTransition(signal, next);
Add(next);
}
}
}
private IEnumerable Signals(StateSet set)
{
Hashtable signals = new Hashtable();
foreach (State state in set)
foreach (char signal in state.Signals)
signals[signal] = null;
return signals.Keys;
}
private void Add(StateSet set)
{
if (!m_States.Contains(set))
{
StateData state = new StateData(set);
m_Queue.Enqueue(state);
m_States[set] = state;
}
}
public class StateData
{
private readonly StateSet m_Set;
public StateData(StateSet set)
{
m_Set = set;
}
private Hashtable m_Transitions = new Hashtable();
public Hashtable Transitions
{
get { return m_Transitions; }
}
public StateSet Set
{
get { return m_Set; }
}
public void SetTransition(char signal, StateSet set)
{
m_Transitions.Add(signal, set);
}
}
private StateSet Move(StateSet set, char signal)
{
StateSet newSet = new StateSet();
foreach (State state in set)
foreach (State nextState in state.Get(signal))
newSet.Add(nextState);
return newSet;
}
private StateSet EpsilonMove(StateSet set)
{
StateSet newSet = set.Clone();
foreach (State state in set)
EpsilonMoveRec(state, newSet);
return newSet;
}
private void EpsilonMoveRec(State state, StateSet newSet)
{
foreach (State nextState in state.Epsilon)
if (!newSet.Contains(nextState))
{
newSet.Add(nextState);
EpsilonMoveRec(nextState, newSet);
}
}
}
}
State.cs
using System.Collections;
namespace FSM
{
public class State
{
private object m_Data;
public object Data
{
get { return m_Data; }
}
public State()
{}
public State(object data)
{
m_Data = data;
}
private StateSet m_Epsilon = new StateSet();
public StateSet Epsilon
{
get { return m_Epsilon; }
}
private Hashtable m_SignalTransitionsMap = new Hashtable();
public void Add(char signal, State state)
{
StateSet set = (StateSet) m_SignalTransitionsMap[signal];
if (set == null)
{
set = new StateSet();
m_SignalTransitionsMap[signal] = set;
}
set.Add(state);
}
public StateSet Get(char signal)
{
StateSet set = (StateSet) m_SignalTransitionsMap[signal];
if (set == null)
return new StateSet();
return set;
}
public IEnumerable Signals
{
get { return m_SignalTransitionsMap.Keys; }
}
}
}
StateSet.cs
using System.Collections;
namespace FSM
{
public class StateSet : IEnumerable
{
private Hashtable m_States = new Hashtable();
public StateSet Clone()
{
StateSet set = new StateSet();
foreach (State state in this)
set.Add(state);
return set;
}
public void Add(State state)
{
if (!Contains(state))
m_States.Add(state, state);
}
public void Remove(State state)
{
m_States.Remove(state);
}
public bool Contains(State state)
{
return m_States.Contains(state);
}
public IEnumerator GetEnumerator()
{
return m_States.Keys.GetEnumerator();
}
public int Count
{
get { return m_States.Count; }
}
public override bool Equals(object obj)
{
StateSet that = obj as StateSet;
if (that == null)
return false;
if (this.Count != that.Count)
return false;
foreach (State state in this)
if (!that.Contains(state))
return false;
return true;
}
public override int GetHashCode()
{
int hash = 0;
foreach (State state in this)
hash += state.GetHashCode();
return hash;
}
}
}
SM.cs
namespace FSM
{
public struct SM
{
public State S1;
public State S2;
public static SM Signal(char signal)
{
SM sm = new SM();
sm.S1 = new State();
sm.S2 = new State();
sm.S1.Add(signal, sm.S2);
return sm;
}
public static SM Or(params SM[] seq)
{
SM sm = new SM();
sm.S1 = new State();
sm.S2 = new State();
foreach (SM sm1 in seq)
{
sm.S1.Epsilon.Add(sm1.S1);
sm1.S2.Epsilon.Add(sm.S2);
}
return sm;
}
public static SM Seq(params SM[] seq)
{
SM sm = new SM();
sm.S1 = seq[0].S1;
sm.S2 = seq[seq.Length - 1].S2;
for (int i = 0; i < seq.Length - 1; ++i)
seq[i].S2.Epsilon.Add(seq[i + 1].S1);
return sm;
}
public static SM Star(SM sm)
{
sm.S1.Epsilon.Add(sm.S2);
sm.S2.Epsilon.Add(sm.S1);
return sm;
}
}
}
Programm.cs
using System;
using System.Collections;
namespace FSM
{
internal class Programm
{
private static void Main()
{
SM sm =
SM.Seq(
SM.Star(
SM.Or(
SM.Signal('a'),
SM.Signal('b')
)
),
SM.Signal('a'),
SM.Signal('b'),
SM.Signal('b')
);
State start = new State();
State end = new State();
sm.S2.Epsilon.Add(end);
start.Epsilon.Add(sm.S1);
DFSMBuilder builder = new DFSMBuilder();
builder.Build(start);
Hashtable dfsm = new Hashtable();
int n = 1;
foreach (DFSMBuilder.StateData data in builder.States.Values)
dfsm[data.Set] = n++;
foreach (DFSMBuilder.StateData stateData in builder.States.Values)
{
Console.Write(dfsm[stateData.Set]);
if (stateData.Set.Contains(start))
Console.Write(" start");
if (stateData.Set.Contains(end))
Console.Write(" end");
Console.WriteLine();
foreach (DictionaryEntry entry in stateData.Transitions)
{
char signal = (char) entry.Key;
StateSet stateSet = (StateSet) entry.Value;
Console.WriteLine("{0} -> {1}", signal, dfsm[stateSet]);
}
Console.WriteLine();
}
}
}
}
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[29]: Theory and Techniques of Compiler Construction
Неплохо. Хотя Epsilon и EpsilonMove требует более детального описания.
Кстати, раз уж ты хорошо въехал в это дело, то может поможешь решить одну задачку?
Простой пример. C-шные комментарии:
Тестовая /*строка для эксперементов над*/ комментариями. Она /*используется для того*/ чтобы было что комментарить.
Можно создать простую грамматику чтобы распарсить комментарии:
/\*.*\*/
Для нее не составляет труда построить конечный автомат описнным тобой методом или методом построения ДКА из АСТ.
Но, к сожалению, эта грамматика найдет комментарий не верно:
Тестовая /*строка для экспериментов над*/ комментариями. Она /*используется для того*/ чтобы было что комментарить.
Грубо говоря ДКА подведет "жадность".
В МС-ных регэкспах можно уменьшить жадность выражения ".*" подставив за звездочкой вопросительный знак:
/\*.*?\*/
Этот вариант дас верный результат:
Тестовая /*строка для экспериментов над*/ комментариями. Она /*используется для того*/ чтобы было что комментарить.
Собственно вопрос в том, как подобное запихнуть в построитель ДКА?
Как варинт устроило бы нечто вроде введения контекста. Например, в КокоР данную грамматику можно описать так?
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, Шахтер, Вы писали:
Ш>>Здравствуйте, VladD2, Вы писали:
Ш>>/\*([^*]|((\*)+[^/*]))*(\*)*\*/
VD>Здорово, но я к стыду не могу понять принцип того как это работает.
VD>Объясни, плиз.
VD>ЗЫ
VD>Ну, и все же впрос остается, так как выкидывать такие кренделя вместо простого и элегентного решения — это не задорово.
Суть дела проста. У нас есть грубое решение LongCommentsDraft = "/*" + All + "*/" , где All — класс всех строк.
Что нас не устраивает. Если задана строка из этого класса, то некоторый префикс может тоже принадлежать этому же классу. И нам нужно это дело исключить.
Данная ситуация возникает, как легко видеть, когда мы имеем дело со строкой "/*" + s + "*/" , где s -- строка, которая содержит внутри подстроку "*/".
Таким образом, правильное решение -- LongComments = "/*" + LongCommentBody + "*/" , где LongCommentBody -- класс строк, не содержащих подстрок "*/" .
Чтобы описать этот класс строк, опишем сначала дополнительный класс -- ~LongCommentBody, это класс строк, которые содержат подстроки "*/" ,
этот класс легко описать регулярным выражением All + "*/" + All . Хорошо известно, что дополнение к регулярному классу есть регулярный класс.
И это дополнение тривиально строится, если этот регулярный класс задан стейт-машиной. Таким образом, нам надо перейти от регулярного выражения к стейт-машине, инвертировать её, а затем опять построить регулярное выражение.
Будем обозначать множество всех символов через A (алфавит).
M>Для каждого токена строится минимизированный ДКА. Понятно, что в результате, при лексическом анализе, получается недетерминированный автомат. Поэтому, я на ходу произвожу моделированние ДКА делая параллельный проход по автоматам для каждого подходящего токена. Такая реализация была связана со спецификой задачи, которую я реализовывал. Необходимо было создать лексический анализатор, который оперирует на основе динамически пополняемого множества токенов. Поэтому, неудобно было создавать и потом каждый раз убивать общий ДКА, очень медленно получалось. Нет никакого ограничения на построение единого ДКА для всех токенов грамматики.
Кстати, интересный подход. Я когда лет 10 назад "додумался" до его модификации — строил несколько ДКА по грамматике. Правда, не на каждый токен, а на как бы класс похожих токенов. Это было связано со сложностью, объемностью и плохой минимизируемостью "общего" ДКА. Одна деталь беспокоила — я так и не додумался как объединять токены в группы ДКА, кроме как полным перебором вариантов с поиском минимальных. По тем временам эта была задача не решаемая в разумные сроки техникой (PC-XT), поэтому группировал вручную, строил ДКА, потом опять и т.д. итеративно пока результат не удовлетворил.
Re[29]: Theory and Techniques of Compiler Construction
Здравствуйте, Quintanar, Вы писали:
Q>Как-то больно примитивно. Фактически переложение доказательства теоремы о том, что для любого НДКА существует эквивалентный ДКА, единственная здравая мысль — строить состояния ДКА динамически, но это неизбежно, поскольку ДКА из НДКА получается невероятно большим.
Без минимизации да. Более того, не из всякого НДКА можно построить ДКА. Если к состояниям НДКА привязаны выходные сигналы и они конфликтуют при объединении состояний в процессе построения ДКА, то на этом — конец построения с неудачей.
Oberon Books
Programming in Oberon — M. Reiser and N. Wirth [PDF (21.7 MB)]
The Oberon System — M. Reiser — Out-of-print
Project Oberon — The Design of an Operating System and Compiler — N. Wirth and J. Gutknecht [PDF (4'398 KB)]
Compiler Construction — N. Wirth [PDF (597 KB)]
Programming in Oberon (2004) — A derivative of Programming in Modula-2 (1982) — N. Wirth [PDF (334 KB)]
Algorithms and Data Structures (1985) (Oberon version: August 2004) — N. Wirth [PDF (1'241 KB)]
Re[8]: Theory and Techniques of Compiler Construction
Здравствуйте, compiler-dev, Вы писали:
F>>У меня есть такая. Кому надо — вышлю по запросу в мыло. Объем 1.2 Мб в zip CD>Большое спасибо! CD>compiler-dev@narod.ru
Вот их бы почитать.
АНТЛР — это что?
Очень интересно было бы ознакомится 
