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

A>То есть если количество символов текста одинаковое у двух разных разборов, эвристика не применяется?

В общем, да, но дело не в общем количестве токенов.

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

A>Кстати, если в языке описываются или импортируются новые грамматические расширения, то эти места должны наверное быть однозначными?
A>То есть конструкция using GrammarExtension; должна быть однозначной. Если же эту конструкцию невозможно сразу однозначно разобрать, то как подключить расширение для разбора последующего кода? Или же производить несколько ветвей разбора — с подключенным расширением и без?

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

VD>>В результате получится вполне себе нормальное дерево разбора, возможно с неоднозначностями.
A>В таком дереве разбора будет довольно много ветвей.

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

A>Даже если хранить его сжато в виде графа, всё равно в худшем случае может получиться как минимум линейное увеличение количество узлов, пропорциональное количеству неоднозначных правил.

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

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

Исключением является восстановление после ошибок. Тут возможны любые варианты. Именно этим и была вызвана задержка в работе над восстановлением.

A>Интересно, сколько это в цифрах?

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

A>Но тут проблема в том, что полезной информации в таком дереве разбора мало:
A>1. Имена конструкций верхнего уровня (классов, функций) и их границы
A>2. Границы statement внутри функций.

Если неоднозначности по делу, то их будет не много и будет очевидный способ их устранения.

A>В большинстве случаев то, что лежит внутри statement (между точками с запятой) может быть всем чем угодно — декларация, вызов функции, вызов оператора () и тд. Наверное эффективнее запомнить границы неоднозначности и распарсить её снова, когда будет доступен контекст.

Мы имеем дело с конкретным текстом. Чем угодно он быть не может. Скажем если язык С++, а пользователь написал:

A* B;

то в statment мы получим неоднозначность состоящую из двух вариантов (точно грамматику плюсов не знаю, так что пишу примерно):
1. Statment.Expression.
2. Statment.VarDecl.
Где Statment.Expression состоит из одного подправила типа Expression которое разберется по варианту Expression.Mul(Expression.Identifier, "*", Expression.Identifier).
Чтобы выбрать один из них нужно сначала построить таблицы символов, а потом по ним разрешить имя. Если имя будет типом, то на втором проходе мы откинет Statment.Expression(Expression.Mul(Expression.Identifier, "*", Expression.Identifier)), так как первое подвыражение будет типом. Ну, и т.п.

VD>>Именно их можно разрешить отдельным проходом выполняемым более примитивными парсерами во время синтаксического анализа.
A>Грамматики для этих парсеров нужно описывать вручную или парсеры могут быть сгенерированы автоматически?

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

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

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

VD>>Это не проблема. Более того наш парсер при этом будет даже удобнее, так как всеми этими приседаниями просто не нужно будет заниматься.
A>Если строить парсеры для предварительного разбора (tentative parsing) автоматически на основе исходной грамматики, то приседаний не будет.

Само создание таких парсеров (я уже не говорю о сопряжении) и есть не хилые приседания. Человек создающий поддержку для языка не дожен тратить свое время на не относящиеся к делу вещи.

Собственно плюсы нами не рассматриваются в качестве целевого языка. Уж больно криво они спроектированы. Мы создаем средство для построения, в первую очередь, расширяемых языков. Понятно, что они должны быть по возможности однозначны и вообще просты. Все же навороты Нитры скорее нужны для того чтобы создавая свои языки и расширения к ним не приходилось обходить ограничения Нитры, а можно было бы сосредоточиться на творчестве в области языкостроения.

A>В процессе типизации нужно будет ещё производить инстанциирование шаблонов, чтобы парсить конструкции типа MyTemplate<param>::typeOrVariable.

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

A>Как предлагается описывать схему типизации, включающей в себя работу с шаблонами?

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

A>Кроме этого в зависимости от того, как описана система типов, могут возникать неоднозначности типизации.

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

A>Будет ли в этом случае рантайм ошибка или же предлагается как-то заранее проверить систему типов на однозначность?

Расширяемость не дает возможность проверять даже однозначность грамматики (да и вычислительно это вряд ли возможно). В рантайме (на конкретном дереве разбора) это делается без проблем.

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

VD>>У С++ проблемы будут совсем с дргуим. Там сложен сам процесс типизации. Причем основная сложность — вычислительная. То что нет метаданных, а есть инклюды сильно усложняет жизнь.

A>Это только на скорость компиляции влияет.

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

A>Может в С++17 появятся модули и проблема исчезнет.

О модульности в С++ я слышу уже 15 лет, как минимум. А воз и ныне там (ц).

Им придется сломать совместимость, чтобы сделать модульность. Да и шаблоны этому не способствуют. В прочем, если комитету удастся это сделать и это не вызовет проблем, я буду только рад. Пускай дерзают.

Я думаю, что с совместимостью плюсам давно нужно заканчивать. Обеспечить совместимость на уровне линковки и на уровне компиляции старых версиях в едином процессе компиляции и всех это устроит. Один фиг плюсы давно не совместимы с тем же Си на 100%. И никого это не напрягает. А вот то, что даже разные Майкрософты не могут ослить последних стандартов С++ очень сильно печалит.