OSDev

для всех
Текущее время: 17 дек 2017, 01:21

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Формальные грамматики
СообщениеДобавлено: 19 апр 2015, 16:13 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1057
Тема выделена из темы "Язык программирования Кантор". Freeman.

Я не много не понял. У вас есть структуры данных или их нет?
Структурированное программирование это фундаментальное понятие.

Я долго создавал свой компилятор в разных ипостасиях. И пришел к выводу что использование структур облегчает программирование. Но не я первой до меня об этом писали многие в том числе Вирт. Он тоже занимался созданием компиляторов и видимо также пришёл к этому выводу.
Структуры+алгоритмы=программы. Без структур очень сложно писать компилятор. Так как не понятно что и куда идёт и для чего что нужно.


Можно ли построить компилятор без структур? Фортран который дословно являлся транслятором формул был без структур но он был многопроходным. В вашем случае я бы рассмотрел подход RR компилятора. Подчёркиваю что компилятору, в отличие от парсера который работает со структурами данных.

Согласно теории язык должен быть LR(N). Лучше LR(1). Типичным примером такого компилятора является Borland Pascal. В нём нет AST. Но для разбора выражений приходится крутится со стеком.

Правда тогда вопрос встаёт про управление и организацию памятью. Два стека не достаточно. Это типичная задача про ханойские башни. Она решается только для 3-х. Но скорость выполнения при этом медленная. Есть задача про кенгуру и мост. Так вот там наглядно демонстрирует скорость пересылки кенгуру из одного стека в другой через третий. Когда как быстрее использовать указатели. И сразу обменять кенгуру за N/2 ходов (где N-общее число попрыгунчиков - кенгуру ;-)).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Язык программирования Кантор
СообщениеДобавлено: 19 апр 2015, 16:31 

Зарегистрирован: 26 мар 2012, 17:32
Сообщения: 208
pavia писал(а):
Согласно теории язык должен быть LR(N). Лучше LR(1). Типичным примером такого компилятора является Borland Pascal. В нём нет AST. Но для разбора выражений приходится крутится со стеком.
Ссылку на эту теорию в студию, пожалуйста. Ну и сразу напомню, что большая часть компилятора - не парсер (фронтенд), а алгоритмы оптимизации, которым нужно IR (промежуточное/внутреннее представление), которое обычно строится по AST.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Язык программирования Кантор
СообщениеДобавлено: 19 апр 2015, 17:02 
Аватара пользователя

Зарегистрирован: 28 май 2012, 23:44
Сообщения: 237
Откуда: Санкт-Петербург
pavia писал(а):
Я не много не понял. У вас есть структуры данных или их нет?

Вопрос относится к Кантору или к коду, реализующему Кантор на Delphi?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Язык программирования Кантор
СообщениеДобавлено: 19 апр 2015, 17:28 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1057
Я наверно плохо объяснил. И вы немного не поняли.

Безусловно используя функциональный подход можно сконструировать любой компилятор. Вопрос в том что не любой стоит строить. А только тот который будет быстро работать. Для этого язык должен быть контексто независимым. Иначе при каждой зависимости придётся останавливаться и анализировать весь стек. Контексто независимые языки обычно делятся на два больших класса LR, RR (левая рекурсия, правая рекурсия) иногда классов больше. LR - требуется меньший размер стека. В RR всё вначале заносится в стек и затем идёт свертка. В LR вначале идёт свёртка.
Паскаль считается LR(1) языком. Это наиболее простая форма которая требует минимума анализа.
1 - определяет насколько надо заглядывать вперёд.

Поэтому BP 7 и Delphi 1 и хвастался тем что мог скомпилировать 10 000 строк кода в секунду.


Последний раз редактировалось pavia 19 апр 2015, 18:11, всего редактировалось 4 раз(а).

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Язык программирования Кантор
СообщениеДобавлено: 19 апр 2015, 17:29 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1057
Freeman писал(а):
pavia писал(а):
Я не много не понял. У вас есть структуры данных или их нет?

Вопрос относится к Кантору или к коду, реализующему Кантор на Delphi?

Вы вроде говорили что хотите раскрутить свой компилятор. Поэтому вопрос относится к самому Кантору.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Язык программирования Кантор
СообщениеДобавлено: 19 апр 2015, 18:08 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1057
SII писал(а):
Не в курсе, случаем, как с этим делом у Це++? (т.е. насколько далеко вперёд надо смотреть)

Затрудняюсь ответить. Я в такие тонкости не лез. Тем более такое измерение не фундаментальное, а частное.
Это как с удавом, а в попугаях я гораздо длине. По одним меркам 3 по другим 5. Хотя я бы сказал что можно свести к 1.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Язык программирования Кантор
СообщениеДобавлено: 19 апр 2015, 22:13 
Аватара пользователя

Зарегистрирован: 28 май 2012, 23:44
Сообщения: 237
Откуда: Санкт-Петербург
pavia писал(а):
Согласно теории язык должен быть LR(N). Лучше LR(1). Типичным примером такого компилятора является Borland Pascal. В нём нет AST. Но для разбора выражений приходится крутится со стеком.

Исходники компилятора и среды Turbo Pascal 6.0 то ли официально были выложены Borland, то ли каким-то образом утекли в Сеть, так что теперь всё можно выяснить, если не бояться ассемблера.

На данный момент Кантор считается LR(1)-языком, если брать декларативный синтаксис без оператора is. В первой альфе так и будет.

В дальнейшем, когда добавится и is, и командный синтаксис, разбор станет многостадийным и усложнится до LR(1+1) или LR(1+2), то есть лексический анализатор по-прежнему будет проходить исходник один раз, но разобранные элементы объектного кода могут изменить свой статус и/или уточниться после завершения лексического анализа. Для Кантора это штатная ситуация, для чего объектный код изначально проектируется как ОО-база данных, так что большого замедления не должно быть. Эталоном скорости для меня служит Delphi 6 или 7, ориентируюсь на них. Как оно будет на самом деле, посмотрим. За ассемблер хвататься пока рано. :lol:

pavia писал(а):
Вы вроде говорили что хотите раскрутить свой компилятор. Поэтому вопрос относится к самому Кантору.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Язык программирования Кантор
СообщениеДобавлено: 20 апр 2015, 14:56 
Аватара пользователя

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 938
Откуда: Дагоба
pavia писал(а):
Согласно теории язык должен быть LR(N). Лучше LR(1). Типичным примером такого компилятора является Borland Pascal. В нём нет AST.

"Смешались в кучу кони, люди" (с). Этот ужас свидетельствует о вашей низкой теоретической подготовке. Вы применяете кучу умных слов, притягиваете за уши ханойские башни и кенгуру, чтобы создать видимость наукообразности. Пожалуйста, так не делайте.
1. В первой фразе вы "внезапно" смешали в кучу синтаксис языка и грамматику. Язык не бывает ни LR(N) ни каким-то другим. Принято говорить, что синтаксис языка допускает грамматику LR(N). Разные грамматики могут порождать один и тот же язык, соответственно, один и тот же язык можно выразить при помощи разных грамматик, многое зависит от вашего умения составлять такую грамматику для заданного языка.
2. Для любого детерминированного контекстно свободного языка существует LR(N) грамматика.
3. Далее, каждая LR(N)-грамматика может быть автоматически преобразована в LR(1) грамматику. Таким образом, если ваш язык детерминированный контекстно свободный (а таких большинство), то вы обязательно можете создать для него LR(1)-парсер. Из сложных для разбора языков мне известны, пожалуй, только два - FORTRAN (незначащие пробелы не позволяют провести лексический анализ в отрыве от синтаксического) и PL/1 (классический случай контекстно-зависимого языка, т.к. в нём нет зарезервированных слов, – смысл лексемы зависит от её контекста). Следовательно, пользуясь вашей терминологией, любой контекстно свободный язык является LR(1) языком.
4. Затем вы также "внезапно" смешали понятия языка и компилятора. С точки зрения компиляторостроения современные инструменты позволяют легко реализовать любую КСГ. Более того, вообще нет необходимости составлять LR(1) или LR(N) грамматику, достаточно описать синтаксис языка в формате BNF и генератор типа YACC/Bison самостоятельно сгенерирует вам нужный парсер. Также, как правильно заметил Nable, синтаксический анализ - достаточно простая задача, в современном компиляторе занимает o-малое от времени работы компилятора и от его сложности. Основное - это оптимизация.
5. Простите, а причём здесь AST??? "Летели два крокодила - один зелёный, другой на север". AST может являться продуктом любой грамматики, а может и не являться, если не захотите. Смысл AST заключается не в том, чтобы его избежать, а в том, что он представляет собой удобное промежуточное представление для выполнения ряда задач, связанных с определением семантики программы, которые не могут быть выполнены в рамках синтаксического разбора. Например, для проверки и выведения типов, определения областей видимости и использования.

SII писал(а):
Не в курсе, случаем, как с этим делом у Це++? (т.е. насколько далеко вперёд надо смотреть)

У C++ с этим делом всё нормально. Он является классическим контекстно-свободным языком, как и почти все остальные языки. Есть некоторые проблемы с лексическим анализом, так как C/C++ утратили свойство регулярности с появлением так называемых "сырых строковых литералов" (raw string literals), но такие литералы - общая тенденция современных языков, C/C++ здесь не уникальны.

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.

<<< OS Boot Tools. >>>


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Язык программирования Кантор
СообщениеДобавлено: 20 апр 2015, 15:55 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1057
Yoda писал(а):
"Смешались в кучу кони, люди" (с). Этот ужас свидетельствует о вашей низкой теоретической подготовке. Вы применяете кучу умных слов, притягиваете за уши ханойские башни и кенгуру, чтобы создать видимость наукообразности. Пожалуйста, так не делайте.

Подготовка у меня хорошая. Смешения сделано целенаправленно. Да бы не писать большие трактаты. Не ожидал что тут кто-то так глубоко её знает. А во вторых она бессмысленна.
Я уже всё пояснил в следующем посте важные моменты viewtopic.php?p=12933#p12933

Yoda писал(а):
1. В первой фразе вы "внезапно" смешали в кучу синтаксис языка и грамматику. Язык не бывает ни LR(N) ни каким-то другим. Принято говорить, что синтаксис языка допускает грамматику LR(N). Разные грамматики могут порождать один и тот же язык, соответственно, один и тот же язык можно выразить при помощи разных грамматик, многое зависит от вашего умения составлять такую грамматику для заданного языка.
2. Для любого детерминированного контекстно свободного языка существует LR(N) грамматика.

Согласно Книге дракона синтаксис и грамматика это одно и тоже.
Судя по всему вы имели в виду формальную грамматику.


Yoda писал(а):
3. Далее, каждая LR(N)-грамматика может быть автоматически преобразована в LR(1) грамматику.
...
Следовательно, пользуясь вашей терминологией, любой контекстно свободный язык является LR(1) языком.

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

Yoda писал(а):
4. Затем вы также "внезапно" смешали понятия языка и компилятора. С точки зрения компиляторостроения современные инструменты позволяют легко реализовать любую КСГ. Более того, вообще нет необходимости составлять LR(1) или LR(N) грамматику, достаточно описать синтаксис языка в формате BNF и генератор типа YACC/Bison
самостоятельно сгенерирует вам нужный парсер.

А зачем тогда потребовались раширения EBNF и собственный формат YACC и раширения бизона? И дженерики они уже научились поддерживать?
На самом деле толку от утилит мало:
1) Они позволяют только повторить то что поддерживает конкретная утилита. А что-бы добавить придётся переделывать код. Дело в том что эти утилиты генерируют не человеко понятный код, а машинно ориентированный. Что усложняет поддержку.
2) Выходной формат не тот, который хотелось бы видеть.

Yoda писал(а):
Также, как правильно заметил Nable, синтаксический анализ - достаточно простая задача, в современном компиляторе занимает o-малое от времени работы компилятора и от его сложности. Основное - это оптимизация.

Куча времени впустую ради жалких крох скорости.

Yoda писал(а):
5. Простите, а причём здесь AST??? "Летели два крокодила - один зелёный, другой на север". AST может являться продуктом любой грамматики, а может и не являться, если не захотите. Смысл AST заключается не в том, чтобы его избежать, а в том, что он представляет собой удобное промежуточное представление для выполнения ряда задач, связанных с определением семантики программы, которые не могут быть выполнены в рамках синтаксического разбора. Например, для проверки и выведения типов, определения областей видимости и использования.

Так я и не спорю что с AST проще в классическом подходе. Но тут другое дело. Дело в том что у Фримана подход функционального программирования (Термин функциональное программирование по Чёрчу).
Так вот в таком подходе не предусмотрено указателей. И как следствие всякое подобие дерева отсутствует. Остаётся только рекурсия. И упрощать язык так что-бы он был проще в написании. А теория компиляторов для этого построена. Поэтому я и говорил что грамматику языка надо записать в виде LR(1).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Язык программирования Кантор
СообщениеДобавлено: 20 апр 2015, 17:28 
Аватара пользователя

Зарегистрирован: 28 май 2012, 23:44
Сообщения: 237
Откуда: Санкт-Петербург
Yoda писал(а):
3. Далее, каждая LR(N)-грамматика может быть автоматически преобразована в LR(1) грамматику. Таким образом, если ваш язык детерминированный контекстно свободный (а таких большинство), то вы обязательно можете создать для него LR(1)-парсер.

Раз у вас такая теоретическая подготовка, прошу ответить на мой конкретный вопрос. Я то ли чего-то недопонял, то ли еще что, но не смог найти ответа сам, опираясь на учебник.

Вопрос касается Delphi. В Delphi есть индексированные свойства:
Код:
type
  TSomeClass = class
    // все нужные объявления
    property MyProp[Index: Integer]: Integer read GetMyProp write SetMyProp;
  end;

Также в Delphi есть обертки индексированных свойств -- своего рода частичное применение:
Код:
type
  TAnotherClass = class(TSomeClass)
    property FirstMy: Integer index 0 read MyProp write MyProp;
  end;

При объявлении TSomeClass.MyProp можно использовать любой идентификатор для индекса, но наиболее логичным выглядит Index, его и используют. IDE ошибочно его подсвечивает, но компилятор не считает ключевым словом, и компиляция успешно проходит. А в объявлении TAnotherClass.FirstMy index явно используется как ключевое слово, IDE его также подсвечивает (уже правомерно), и компиляция также успешна.

Является ли такое вольное обращение с ключевыми словами нарушением принципов контекстно-свободной грамматики?


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB