Theory and Techniques of Compiler Construction - Философия программирования

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

M>Это-то да. Но я спрашивал в свете недавнего обсуждения возможности раширения LL(k)-анализатора так, чтобы он имел возможно разбирать параллельно альтернативы, даже если они не укладываются в LL(k) для любого, сколь угодно большого k. Кто-то, не помню кто, дал ссылку на третью версию ANTLR. Я пошел по ссылке, прочитал кучу блогов, но сумел вынести оттуда только одно: ничего про параллельный разбор там нет и единственное улучшение — это использование регулярных выражений в предосмортрах. Идея это не новая, придумана была еще в 60-х годах.

Я не знаю, что ты там смотрел, но в 3-шке точно соврешенно будет так называемый LL(*) или LL(STAR) (как там написано специльно для гугля, жаль он об этом не знает

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" может встречаться как идентификатор где угодно и как ключевое слово в ряду модификаторов перед классом или структурой. Было бы так приятно написать нечто вроде:

Ident : letter { letter | digit }
      | "partial"
      | "get"
      | "set"
      .

Modifiers
      : "public"
      | "private"
      | "protected"
      | "internal"
      .

Atributs : ... .

Class : Atributs Modifiers [ "partial" ] "class"     Ident [ TypeParameters ] [ ClassBase ] ClassBody [ ";" ] .
Itf   : Atributs Modifiers [ "partial" ] "interface" Ident [ TypeParameters ] [ ItfBase ]   ItfBody [ ";" ] .
Enum  : Atributs Modifiers "enum" Ident [ ":" IntegralType ] EnumBody [ ";" ] .
Field : Atributs Modifiers Type Ident [ "=" FieldInit ] .

Type  : "int" | "char" "string" | "double" | Ident.

и т.п. А не заниматься программно апаратным анонизмом обходя проблемы парсеров.

Заметь "partial" пересекается в Type (так как он содержит Ident) и в модификаторов некоторых объявления типов.

Как я понимаю без параллельного сканирования есть только один шанс построить LL(*)-парсер. Нужно выделять дублирующиеся ветви и находить места где граматика различается. В приведенном выше примере это ключевые слова "class", "interface"

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

Мне кажется ты не в теме. Единственный парсер который без костылей позволяет парсить С++ на сегодня является именно АНТЛР. У него куча своих проблем, но тем не менее. Что же до достижений, то единственное что я хотел бы видеть это отсуствие необходимости обходить проблемы парсера при приемлеомй производительности. А будет ли это сделано параллельным парсингом или как-то иначе в общем-то по фигу.

Будем надеяться, что в трешки создатели АНТЛР-а исправят недостатки и таки сделают то что нужно.

... << RSDN@Home 1.2.0 alpha rev. 578>>

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

Ш>У меня такое ощущение, что ты вообще не читаешь сообщения.

У меня почуме-то такое же ощущение, но от твоих сообщения.

... << RSDN@Home 1.2.0 alpha rev. 578>>

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

Ш>>У меня такое ощущение, что ты вообще не читаешь сообщения.
VD>У меня почуме-то такое же ощущение, но от твоих сообщения.

Ну вы, блин, даете...

Любофф?

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

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. Он такой единственный.

В общем, я не согласен ни с первым, ни, тем-более, со вторым утверждением. Если интересно, можем обсудить подробно почему.

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

Здравствуйте, 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>Вот здесь я как раз сильно сумлеваюсь. Нет, не по тому вопросу, что я не в теме

, а относительно следующего:
M>

M>Единственный парсер который без костылей позволяет парсить С++ на сегодня является именно АНТЛР

M>Здесь два утверждения:
M>1. АНТЛР позволяет парсить си++ "без костылей".
M>2. Он такой единственный.

M>В общем, я не согласен ни с первым, ни, тем-более, со вторым утверждением. Если интересно, можем обсудить подробно почему.

Ну, на счет первого... Уде есть очень приличный парсер С++ на базе АНТЛР-а. Костылей там не замечено, но есть одна проблема. Он сделан на порте АНТЛР-а на С++. А вот это уже без проблем сделать не удалось. АНТЛР версии 2.х использует банальные заглядывания вперед и откаты. Причем откаты для простоты реализации делаются на исключениях. В Яве с ее автоматическим управлением памятью проблем не возникает. А вот в С++ с этим полный кирдык. Течет эта реализация по страшному. Так что в коммерческих приложениях такой парсер вряд ли применим.

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

Из известных мне парсеров С++ обеспечивающих приемлемое качество почти все или писаны вручную, или используют "костыли" в виде рукопашного кода использующего фичи парсера (например, тот же GCC).

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

А откуда ты взял, что он находит эти неоднозначности? Может я что-то пропустил?

... << RSDN@Home 1.2.0 alpha rev. 578>>

Здравствуйте, 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>А откуда ты взял, что он находит эти неоднозначности? Может я что-то пропустил?

Здравствуйте, 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>>

Здравствуйте, 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>Била гейтся уже приплел.

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

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

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

_>В том то и дело что не LL(1), а LL(k), причем с большим k (3-8) — используется эвристика которая позволяет уменьшить
_>сложность предпросмотра.Где-то на сайте можно найти диссертацию автора целиком по этой теме.

Из-за этой эвристики ANTLR2.x не является полноценным LL(k)-анализатором. В корректных LL(k)-грамматиках возникают неоднозначности. С введением в ANTLR3 поддержки LL(*)-грамматик проблема отпала.

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

VD>В том, то и дело, что правила должны быть обычными, а не регулярными. Незнаю уж почему, но все виданные мной построители парсеров были ХХ(k), т.е. не пасовали на граматиках вроде приведенной выше. А написать предпросмотр для сложных случаев очень не просто. Например, в C# есть контексно-зависимые ключевые слова. Например, слово "partial" может встречаться как идентификатор где угодно и как ключевое слово в ряду модификаторов перед классом или структурой.

Строго говоря "partial" не является ключевым словом. Об этом специально сказано в стандарте. И никаких проблем с его обработкой не возникает. Тем более что разработчики языка C# очень сильно постарались над тем чтобы разбор грамматики был достаточно простым.

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

А>Строго говоря "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 24
      return 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>>

Здравствуйте, mefrill

Владимир, ты тут продемонстрировал неслабое владение материалом, лично я впечатлился. Не просветишь ли меня по двум маленьким вопросам?

Когда-то давно читали нам курс по синтаксическим анализаторам. И сказали такую штуку, мол было доказано, что любая контекстно-чувствительная грамматика может быть преобразована к LR(1) грамматике. Если это так, то к чему весь сыр-бор вокруг LL(*) парсеров? Ведь можно же просто грамматику привести к LR(1) виду?

На том же курсе нам прочитали такую штуку, как "Правила подстановки Флойда" (это как раз для разбора LR(1) грамматик). Но затем я пробовал сам в интернете найти описание этого метода, но ничего не получилось. Хоть я свой аналог yacc-а на основе этих правил когда-то сделал. Вот меня любопытство мучает, где про "Правила подстановки Флойда" почитать можно. Не подскажешь?

... << RSDN@Home 1.1.4 stable rev. 510>>

Здравствуйте, 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 без заглядывания вперед ну никак не обойтись, тем более что на это косвенно намекает стандарт.

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

E>мол было доказано, что любая контекстно-чувствительная грамматика может быть преобразована к LR(1) грамматике.

Может быть, контекстно-независимая?

Здравствуйте, 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-а на основе этих правил когда-то сделал. Вот меня любопытство мучает, где про "Правила подстановки Флойда" почитать можно. Не подскажешь?

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

	От:	Павел Кузнецов
	Дата:	19.07.05 15:19
	Оценка:

	От:	Павел Кузнецов
	Дата:	19.07.05 15:48
	Оценка:

	От:	Шахтер
	Дата:	20.07.05 00:15
	Оценка:

	От:	Шахтер
	Дата:	20.07.05 00:23
	Оценка:

От:	VladD2	www.nemerle.org
Дата:	20.07.05 00:31
Оценка:

От:	McSeem2	http://www.antigrain.com
Дата:	20.07.05 00:58
Оценка:

	От:	mefrill
	Дата:	20.07.05 12:57
	Оценка:	6 (1) +1

	От:	Алексей.
	Дата:	20.07.05 16:55
	Оценка:	+1

От:	eao197	http://eao197.blogspot.com
Дата:	20.07.05 20:21
Оценка:

	От:	Дарней
	Дата:	21.07.05 08:34
	Оценка: