Сообщение Re[3]: N2 – языковый фрeймворк от 08.01.2015 20:44
Изменено 08.01.2015 20:47 Aleх
Здравствуйте, VladD2, Вы писали:
VD>Наш парсер допускает неоднозначности в которых неоднозначные конструкции имеют одинаковое количество одинаковых терминалов (токенов). В случае, если в процессе парсинга появилась два варианта разбора с разным числом терминалов или с терминалами разной длинны, то включается эта эвристика и устраняет неоднозначность в пользу более длинных терминалов или в пользу вариантов с большим числам терминалов. Это аналогично поведению лексерных LL(k)-парсеров.
То есть если количество символов текста одинаковое у двух разных разборов, эвристика не применяется?
Кстати, если в языке описываются или импортируются новые грамматические расширения, то эти места должны наверное быть однозначными? То есть конструкция using GrammarExtension; должна быть однозначной. Если же эту конструкцию невозможно сразу однозначно разобрать, то как подключить расширение для разбора последующего кода? Или же производить несколько ветвей разбора — с подключенным расширением и без?
A>>В C++ типизация, включающая в себя инстанциирование шаблонов, должна происходить в процессе синтаксического анализа.
VD>Это не так.
A>>В противном случае в результате парсинга получится, нечто малополезное, что потребует нового, но уже ручного разбора на стадии типизации. Грубо говоря получится только разметить (определить местоположение и имя) классы и функции. Но именно такая задача решается довольно простой грамматикой и это очень малая часть синтаксического анализа.
VD>В результате получится вполне себе нормальное дерево разбора, возможно с неоднозначностями.
В таком дереве разбора будет довольно много ветвей. Даже если хранить его сжато в виде графа, всё равно в худшем случае может получиться как минимум линейное увеличение количество узлов, пропорциональное количеству неоднозначных правил. Интересно, сколько это в цифрах? Но тут проблема в том, что полезной информации в таком дереве разбора мало:
1. Имена конструкций верхнего уровня (классов, функций) и их границы
2. Границы statement внутри функций.
В большинстве случаев то, что лежит внутри statement (между точками с запятой) может быть всем чем угодно — декларация, вызов функции, вызов оператора () и тд. Наверное эффективнее запомнить границы неоднозначности и распарсить её снова, когда будет доступен контекст.
VD>Именно их можно разрешить отдельным проходом выполняемым более примитивными парсерами во время синтаксического анализа.
Грамматики для этих парсеров нужно описывать вручную или парсеры могут быть сгенерированы автоматически?
VD>С точки зрения теории нет разницы осуществлять ли устранение неоднозначностей во время парсинга или же во время отдельного прохода.
С точки зрения результата. А а в процессе выполнения может происходить много лишней работы.
VD>Это не проблема. Более того наш парсер при этом будет даже удобнее, так как всеми этими приседаниями просто не нужно будет заниматься.
Если строить парсеры для предварительного разбора (tentative parsing) автоматически на основе исходной грамматики, то приседаний не будет.
VD>Небольшое отступление.... Твой пример немного упрощенный по этому не совсем показывает проблему. В нем просто нет неоднозначности. Чтобы она появилась объявление inner нужно сделать указателем. Тогда будет неоднозначность между объявлением указателя и умножением. Ну, да это не так важно.
Это да.
VD>После парсинга у нас получится просто неоднозначное дерево разбора в котором будут неоднозначные конструкции будут встречаться два раза. Предположим, что это было объявление указатели, тогда в дереве разбора у нас будет стейтмент с объявлением переменной и еще один с операцией умножения.
VD>Сразу после парсинга мы запускаем процедуру предварительной типизации на которой заполняются таблицы символов и каждому из идентификаторов добавляется информация является ли он именем типа и если да, то каким.
VD>Следующим проходом мы производим устранение неоднозначностей с использованием таблицы символов построенной на предыдущем шаге. Просто связываем имена и если это имя типа, то отбрасываем ветвь с умножением, а если нет, ветвь с объявлением переменной.
В процессе типизации нужно будет ещё производить инстанциирование шаблонов, чтобы парсить конструкции типа MyTemplate<param>::typeOrVariable. Как предлагается описывать схему типизации, включающей в себя работу с шаблонами? Кроме этого в зависимости от того, как описана система типов, могут возникать неоднозначности типизации. Будет ли в этом случае рантайм ошибка или же предлагается как-то заранее проверить систему типов на однозначность?
A>>В исходниках компиляторов clang и gcc это называется tentative parsing.
VD>Вот он нам и не нужен, так как мы используем более мощный парсер.
A>>Кроме отложенного разбора методов классов, может понадобиться предварительный парсинг частей выражения для most vexing parse.
VD>Аналогично и тут. Это всего лишь неоднозначность и в стандарте С++ четко описано как ее устранять. Собственно так и поступает Clang++. О чем свидетельствует его выхлоп "parentheses were disambiguated as a function declaration".
VD>ЗЫ
VD>Вообще, парсинг языков вроде С++ должен радикально упроститься с использованием генерализованных парсеров (так что ли их назвать?) именно потому что не нужно никаких танцев с бубнами. Можно получить неоднозначное дерево разбора соответствующее контекстно-свободной грамматике, а потом разрешить неоднозначности использую уже полное дерево разбора.
VD>У С++ проблемы будут совсем с дргуим. Там сложен сам процесс типизации. Причем основная сложность — вычислительная. То что нет метаданных, а есть инклюды сильно усложняет жизнь.
Это только на скорость компиляции влияет. Может в С++17 появятся модули и проблема исчезнет.
VD>Наш парсер допускает неоднозначности в которых неоднозначные конструкции имеют одинаковое количество одинаковых терминалов (токенов). В случае, если в процессе парсинга появилась два варианта разбора с разным числом терминалов или с терминалами разной длинны, то включается эта эвристика и устраняет неоднозначность в пользу более длинных терминалов или в пользу вариантов с большим числам терминалов. Это аналогично поведению лексерных LL(k)-парсеров.
То есть если количество символов текста одинаковое у двух разных разборов, эвристика не применяется?
Кстати, если в языке описываются или импортируются новые грамматические расширения, то эти места должны наверное быть однозначными? То есть конструкция using GrammarExtension; должна быть однозначной. Если же эту конструкцию невозможно сразу однозначно разобрать, то как подключить расширение для разбора последующего кода? Или же производить несколько ветвей разбора — с подключенным расширением и без?
A>>В C++ типизация, включающая в себя инстанциирование шаблонов, должна происходить в процессе синтаксического анализа.
VD>Это не так.
A>>В противном случае в результате парсинга получится, нечто малополезное, что потребует нового, но уже ручного разбора на стадии типизации. Грубо говоря получится только разметить (определить местоположение и имя) классы и функции. Но именно такая задача решается довольно простой грамматикой и это очень малая часть синтаксического анализа.
VD>В результате получится вполне себе нормальное дерево разбора, возможно с неоднозначностями.
В таком дереве разбора будет довольно много ветвей. Даже если хранить его сжато в виде графа, всё равно в худшем случае может получиться как минимум линейное увеличение количество узлов, пропорциональное количеству неоднозначных правил. Интересно, сколько это в цифрах? Но тут проблема в том, что полезной информации в таком дереве разбора мало:
1. Имена конструкций верхнего уровня (классов, функций) и их границы
2. Границы statement внутри функций.
В большинстве случаев то, что лежит внутри statement (между точками с запятой) может быть всем чем угодно — декларация, вызов функции, вызов оператора () и тд. Наверное эффективнее запомнить границы неоднозначности и распарсить её снова, когда будет доступен контекст.
VD>Именно их можно разрешить отдельным проходом выполняемым более примитивными парсерами во время синтаксического анализа.
Грамматики для этих парсеров нужно описывать вручную или парсеры могут быть сгенерированы автоматически?
VD>С точки зрения теории нет разницы осуществлять ли устранение неоднозначностей во время парсинга или же во время отдельного прохода.
С точки зрения результата. А а в процессе выполнения может происходить много лишней работы.
VD>Это не проблема. Более того наш парсер при этом будет даже удобнее, так как всеми этими приседаниями просто не нужно будет заниматься.
Если строить парсеры для предварительного разбора (tentative parsing) автоматически на основе исходной грамматики, то приседаний не будет.
VD>Небольшое отступление.... Твой пример немного упрощенный по этому не совсем показывает проблему. В нем просто нет неоднозначности. Чтобы она появилась объявление inner нужно сделать указателем. Тогда будет неоднозначность между объявлением указателя и умножением. Ну, да это не так важно.
Это да.
VD>После парсинга у нас получится просто неоднозначное дерево разбора в котором будут неоднозначные конструкции будут встречаться два раза. Предположим, что это было объявление указатели, тогда в дереве разбора у нас будет стейтмент с объявлением переменной и еще один с операцией умножения.
VD>Сразу после парсинга мы запускаем процедуру предварительной типизации на которой заполняются таблицы символов и каждому из идентификаторов добавляется информация является ли он именем типа и если да, то каким.
VD>Следующим проходом мы производим устранение неоднозначностей с использованием таблицы символов построенной на предыдущем шаге. Просто связываем имена и если это имя типа, то отбрасываем ветвь с умножением, а если нет, ветвь с объявлением переменной.
В процессе типизации нужно будет ещё производить инстанциирование шаблонов, чтобы парсить конструкции типа MyTemplate<param>::typeOrVariable. Как предлагается описывать схему типизации, включающей в себя работу с шаблонами? Кроме этого в зависимости от того, как описана система типов, могут возникать неоднозначности типизации. Будет ли в этом случае рантайм ошибка или же предлагается как-то заранее проверить систему типов на однозначность?
A>>В исходниках компиляторов clang и gcc это называется tentative parsing.
VD>Вот он нам и не нужен, так как мы используем более мощный парсер.
A>>Кроме отложенного разбора методов классов, может понадобиться предварительный парсинг частей выражения для most vexing parse.
VD>Аналогично и тут. Это всего лишь неоднозначность и в стандарте С++ четко описано как ее устранять. Собственно так и поступает Clang++. О чем свидетельствует его выхлоп "parentheses were disambiguated as a function declaration".
VD>ЗЫ
VD>Вообще, парсинг языков вроде С++ должен радикально упроститься с использованием генерализованных парсеров (так что ли их назвать?) именно потому что не нужно никаких танцев с бубнами. Можно получить неоднозначное дерево разбора соответствующее контекстно-свободной грамматике, а потом разрешить неоднозначности использую уже полное дерево разбора.
VD>У С++ проблемы будут совсем с дргуим. Там сложен сам процесс типизации. Причем основная сложность — вычислительная. То что нет метаданных, а есть инклюды сильно усложняет жизнь.
Это только на скорость компиляции влияет. Может в С++17 появятся модули и проблема исчезнет.
Re[3]: N2 – языковый фрeймворк
Здравствуйте, VladD2, Вы писали:
VD>Наш парсер допускает неоднозначности в которых неоднозначные конструкции имеют одинаковое количество одинаковых терминалов (токенов). В случае, если в процессе парсинга появилась два варианта разбора с разным числом терминалов или с терминалами разной длинны, то включается эта эвристика и устраняет неоднозначность в пользу более длинных терминалов или в пользу вариантов с большим числам терминалов. Это аналогично поведению лексерных LL(k)-парсеров.
То есть если количество символов текста одинаковое у двух разных разборов, эвристика не применяется?
Кстати, если в языке описываются или импортируются новые грамматические расширения, то эти места должны наверное быть однозначными? То есть конструкция using GrammarExtension; должна быть однозначной. Если же эту конструкцию невозможно сразу однозначно разобрать, то как подключить расширение для разбора последующего кода? Или же производить несколько ветвей разбора — с подключенным расширением и без?
VD>В результате получится вполне себе нормальное дерево разбора, возможно с неоднозначностями.
В таком дереве разбора будет довольно много ветвей. Даже если хранить его сжато в виде графа, всё равно в худшем случае может получиться как минимум линейное увеличение количество узлов, пропорциональное количеству неоднозначных правил. Интересно, сколько это в цифрах? Но тут проблема в том, что полезной информации в таком дереве разбора мало:
1. Имена конструкций верхнего уровня (классов, функций) и их границы
2. Границы statement внутри функций.
В большинстве случаев то, что лежит внутри statement (между точками с запятой) может быть всем чем угодно — декларация, вызов функции, вызов оператора () и тд. Наверное эффективнее запомнить границы неоднозначности и распарсить её снова, когда будет доступен контекст.
VD>Именно их можно разрешить отдельным проходом выполняемым более примитивными парсерами во время синтаксического анализа.
Грамматики для этих парсеров нужно описывать вручную или парсеры могут быть сгенерированы автоматически?
VD>С точки зрения теории нет разницы осуществлять ли устранение неоднозначностей во время парсинга или же во время отдельного прохода.
С точки зрения результата. А а в процессе выполнения может происходить много лишней работы.
VD>Это не проблема. Более того наш парсер при этом будет даже удобнее, так как всеми этими приседаниями просто не нужно будет заниматься.
Если строить парсеры для предварительного разбора (tentative parsing) автоматически на основе исходной грамматики, то приседаний не будет.
VD>Небольшое отступление.... Твой пример немного упрощенный по этому не совсем показывает проблему. В нем просто нет неоднозначности. Чтобы она появилась объявление inner нужно сделать указателем. Тогда будет неоднозначность между объявлением указателя и умножением. Ну, да это не так важно.
Это да.
VD>После парсинга у нас получится просто неоднозначное дерево разбора в котором будут неоднозначные конструкции будут встречаться два раза. Предположим, что это было объявление указатели, тогда в дереве разбора у нас будет стейтмент с объявлением переменной и еще один с операцией умножения.
VD>Сразу после парсинга мы запускаем процедуру предварительной типизации на которой заполняются таблицы символов и каждому из идентификаторов добавляется информация является ли он именем типа и если да, то каким.
VD>Следующим проходом мы производим устранение неоднозначностей с использованием таблицы символов построенной на предыдущем шаге. Просто связываем имена и если это имя типа, то отбрасываем ветвь с умножением, а если нет, ветвь с объявлением переменной.
В процессе типизации нужно будет ещё производить инстанциирование шаблонов, чтобы парсить конструкции типа MyTemplate<param>::typeOrVariable. Как предлагается описывать схему типизации, включающей в себя работу с шаблонами? Кроме этого в зависимости от того, как описана система типов, могут возникать неоднозначности типизации. Будет ли в этом случае рантайм ошибка или же предлагается как-то заранее проверить систему типов на однозначность?
A>>В исходниках компиляторов clang и gcc это называется tentative parsing.
VD>Вот он нам и не нужен, так как мы используем более мощный парсер.
A>>Кроме отложенного разбора методов классов, может понадобиться предварительный парсинг частей выражения для most vexing parse.
VD>Аналогично и тут. Это всего лишь неоднозначность и в стандарте С++ четко описано как ее устранять. Собственно так и поступает Clang++. О чем свидетельствует его выхлоп "parentheses were disambiguated as a function declaration".
VD>ЗЫ
VD>Вообще, парсинг языков вроде С++ должен радикально упроститься с использованием генерализованных парсеров (так что ли их назвать?) именно потому что не нужно никаких танцев с бубнами. Можно получить неоднозначное дерево разбора соответствующее контекстно-свободной грамматике, а потом разрешить неоднозначности использую уже полное дерево разбора.
VD>У С++ проблемы будут совсем с дргуим. Там сложен сам процесс типизации. Причем основная сложность — вычислительная. То что нет метаданных, а есть инклюды сильно усложняет жизнь.
Это только на скорость компиляции влияет. Может в С++17 появятся модули и проблема исчезнет.
VD>Наш парсер допускает неоднозначности в которых неоднозначные конструкции имеют одинаковое количество одинаковых терминалов (токенов). В случае, если в процессе парсинга появилась два варианта разбора с разным числом терминалов или с терминалами разной длинны, то включается эта эвристика и устраняет неоднозначность в пользу более длинных терминалов или в пользу вариантов с большим числам терминалов. Это аналогично поведению лексерных LL(k)-парсеров.
То есть если количество символов текста одинаковое у двух разных разборов, эвристика не применяется?
Кстати, если в языке описываются или импортируются новые грамматические расширения, то эти места должны наверное быть однозначными? То есть конструкция using GrammarExtension; должна быть однозначной. Если же эту конструкцию невозможно сразу однозначно разобрать, то как подключить расширение для разбора последующего кода? Или же производить несколько ветвей разбора — с подключенным расширением и без?
VD>В результате получится вполне себе нормальное дерево разбора, возможно с неоднозначностями.
В таком дереве разбора будет довольно много ветвей. Даже если хранить его сжато в виде графа, всё равно в худшем случае может получиться как минимум линейное увеличение количество узлов, пропорциональное количеству неоднозначных правил. Интересно, сколько это в цифрах? Но тут проблема в том, что полезной информации в таком дереве разбора мало:
1. Имена конструкций верхнего уровня (классов, функций) и их границы
2. Границы statement внутри функций.
В большинстве случаев то, что лежит внутри statement (между точками с запятой) может быть всем чем угодно — декларация, вызов функции, вызов оператора () и тд. Наверное эффективнее запомнить границы неоднозначности и распарсить её снова, когда будет доступен контекст.
VD>Именно их можно разрешить отдельным проходом выполняемым более примитивными парсерами во время синтаксического анализа.
Грамматики для этих парсеров нужно описывать вручную или парсеры могут быть сгенерированы автоматически?
VD>С точки зрения теории нет разницы осуществлять ли устранение неоднозначностей во время парсинга или же во время отдельного прохода.
С точки зрения результата. А а в процессе выполнения может происходить много лишней работы.
VD>Это не проблема. Более того наш парсер при этом будет даже удобнее, так как всеми этими приседаниями просто не нужно будет заниматься.
Если строить парсеры для предварительного разбора (tentative parsing) автоматически на основе исходной грамматики, то приседаний не будет.
VD>Небольшое отступление.... Твой пример немного упрощенный по этому не совсем показывает проблему. В нем просто нет неоднозначности. Чтобы она появилась объявление inner нужно сделать указателем. Тогда будет неоднозначность между объявлением указателя и умножением. Ну, да это не так важно.
Это да.
VD>После парсинга у нас получится просто неоднозначное дерево разбора в котором будут неоднозначные конструкции будут встречаться два раза. Предположим, что это было объявление указатели, тогда в дереве разбора у нас будет стейтмент с объявлением переменной и еще один с операцией умножения.
VD>Сразу после парсинга мы запускаем процедуру предварительной типизации на которой заполняются таблицы символов и каждому из идентификаторов добавляется информация является ли он именем типа и если да, то каким.
VD>Следующим проходом мы производим устранение неоднозначностей с использованием таблицы символов построенной на предыдущем шаге. Просто связываем имена и если это имя типа, то отбрасываем ветвь с умножением, а если нет, ветвь с объявлением переменной.
В процессе типизации нужно будет ещё производить инстанциирование шаблонов, чтобы парсить конструкции типа MyTemplate<param>::typeOrVariable. Как предлагается описывать схему типизации, включающей в себя работу с шаблонами? Кроме этого в зависимости от того, как описана система типов, могут возникать неоднозначности типизации. Будет ли в этом случае рантайм ошибка или же предлагается как-то заранее проверить систему типов на однозначность?
A>>В исходниках компиляторов clang и gcc это называется tentative parsing.
VD>Вот он нам и не нужен, так как мы используем более мощный парсер.
A>>Кроме отложенного разбора методов классов, может понадобиться предварительный парсинг частей выражения для most vexing parse.
VD>Аналогично и тут. Это всего лишь неоднозначность и в стандарте С++ четко описано как ее устранять. Собственно так и поступает Clang++. О чем свидетельствует его выхлоп "parentheses were disambiguated as a function declaration".
VD>ЗЫ
VD>Вообще, парсинг языков вроде С++ должен радикально упроститься с использованием генерализованных парсеров (так что ли их назвать?) именно потому что не нужно никаких танцев с бубнами. Можно получить неоднозначное дерево разбора соответствующее контекстно-свободной грамматике, а потом разрешить неоднозначности использую уже полное дерево разбора.
VD>У С++ проблемы будут совсем с дргуим. Там сложен сам процесс типизации. Причем основная сложность — вычислительная. То что нет метаданных, а есть инклюды сильно усложняет жизнь.
Это только на скорость компиляции влияет. Может в С++17 появятся модули и проблема исчезнет.