понедельник, 20 февраля 2012 г.

C++11 и light-weight парсеры

Нда. Грамматика нового C++ стала настолько сложной, что lightweigh-парсерам с ней справиться становится всё сложнее и сложнее. Взять те же лямбды. Последовательно (без возвратов) анализируя поток токенов, получаемый от лексического анализатора, сложно (точнее, почти невозможно) надёжно отличить операцию индексирования от lambda introducer. Или тело lambda-функции от initializer list. Натолкнулся на это в процессе изучения исходников Qt Creator'а (той их части, которая отвечает за форматирование C++-текста). Форматтер опирается не на предварительно разобранную AST, а содержит в себе свою собственною стейт-машину, реализующую упрощённый вариант C++-грамматики, которая реагирует (в основном) на ключевые слова и знаки пунктуации/операций. Допилить её до состояния, чтобы нормально обрабатывались лямбды, списки инициализации (в аргументах методов) и т. п., но так, чтобы при этом не поломать уже имеющиеся кейсы - хорошая разминка для ума.

10 комментариев:

  1. А что такое "light-weight парсеры"? Это LL?

    ОтветитьУдалить
    Ответы
    1. Под lightweight-парсером я понимаю такой парсер, который не полностью реализует грамматику языка, не углубляется в семантику анализируемого текста. "Облегчённый", так сказать.

      Удалить
    2. Dunno, а они нужны? :) Ну, в смысле, я бы запилил полноценный LR-парсер, с полной поддержкой всего языка. А то ведь прямо скажем, не солидно Qt Creator'у не врубаться даже в то, какой тип возвращает operator -> у итератора QMap'а :)

      Удалить
    3. Для каких-то сценариев - подходят. Как в том же форматировании, когда достаточно понять - что ты начинаешь новый блок или декларацию (например). Подсказками в QtC заведует как раз то полноценный парсер. Но... со своими заморочками. По этому не всегда понимает - какой тип возвращает operator -> у QMap'а. :)

      Удалить
    4. А можно сделать заказ на пост? :) Интересует устройство механизма автодополнения в QtC. С целью понять как делали умные люди, чтобы самому сделать автодополнение для JavaScript'а. Вообще, оно сделано... но уж больно криво :)
      Интересно, как решена проблема "парсинга минимума" - когда пользователь вводит текст, то хотелось бы распарсить как можно меньше, здесь мне не вполне понятен алгоритм.
      Так же интересно как сделан парсер - рукописный, я так понимаю? Как он обрабатывает состояние ошибки, ведь это не компилятор - при наборе текста в редакторе всегда есть ошибки. И т.п. Т.е. нехилый такой пост получается, но интересный :)

      Удалить
    5. Ну, заказ то сделать можно... И, возможно, он даже будет принят. :) А где ты хочешь сделать автокомплетер для JavaScript'а?

      Удалить
    6. Это по работе, ничего опенсорсного :) Вообще, там есть ещё и расширения JavaScript'а, и понятие "проекта", и include'ы... Долгая, короче, история.

      Удалить
    7. Ну, пока ждёшь моего поста, можешь попробовать сам разобраться с тем, как в QtC к QML прикручен javascript-автокомплетер и прочие вкусности. Смотреть здесь:
      https://qt.gitorious.org/qt-creator/qt-creator/trees/master/src/libs/qmljs
      (собственно парсер с разным утилем)
      и здесь:
      https://qt.gitorious.org/qt-creator/qt-creator/trees/master/src/plugins/qmljseditor
      (фронт-энд плюс гуй).

      Удалить
  2. У них есть ветка wip/clang. Возможно ситуация улутшиться после использования clang...

    ОтветитьУдалить
    Ответы
    1. Да, действительно, есть. Но там не без проблем. Основная из которых - это производительность.

      Удалить