Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Прочее

Выбор кодировки для компилятора

Чтобы язык программирования, давал возможность программировать на родном языке, его компилятор должен использовать кодировку, которая бы обеспечивала удобство работы с многими языками. Идеальных кодировок для этого нет. Использовать 8-битные кодировки слишком непрактично по многим причинам. Старые кодировки типа ASCII неудобны для поддержки нескольких языков.

кодировка для компилятора

        Прежде, чем остановиться на какой либо кодировке, давайте сформулируем, каким требованиям она должна отвечать.

  1. Она должна поддерживать все или почти все распространённые языки.
  2. Символы этой кодировки должны иметь постоянный размер (в байтах, конечно, а не в пикселах).
  3. Желательно, чтобы символы в выбранной кодировке были бы представлены в ней единственным способом.
  4. Массив, индексом которого выступает код символа, должен помещаться в оперативной памяти.
        Прежде, чем обсудить эти требования и способы их воплощения, рассмотрим некоторые примеры. Когда происходит лексический разбор, то лексему «идентификатор» в учебниках разбирают примерно так: (это первое приходит на ум, да и в учебниках пишут именно так):
bool  Это идентификатор (char  входная строка) {
    char  символ = входная строка [0];
    if (! ( 'A' <= символ && символ <= 'Z' || 'a' <= символ && символ <= 'z'))
        return  false;
    for (int i=1; i < strlen (входная строка); i++) {
        символ = входная строка [i];
        if (! ( 'A' <= символ && символ <= 'Z' || 'a' <= символ && символ <= 'z'
             || '0' <= символ && символ <= '9' ))
            return  false;
    }
    Поместить идентификатор в таблицу(....);
    return  true;
}
        Если в язык добавляем поддержку кириллицы, то разбор уже такой:
bool  Это идентификатор (char  входная строка) {
   char  символ = входная строка [0];
   // добавляем проверку символов кириллицы
   if (! ( 'A' <= символ && символ <= 'Z' || 'a' <= символ && символ <= 'z' 
      || ( 'A' <= символ && символ <= 'Я' || 'a' <= символ && символ <= 'я'))
      return  false;
   for (int i=1; i < strlen (входная строка); i++) {
      символ = входная строка [i];
      // добавляем проверку символов кириллицы
      if (!('A' <= символ && символ <= 'Z' || 'a' <= символ && символ <= 'z' ||
           ('A' <= символ && символ <= 'Я' || 'a' <= символ && символ <= 'я' || 
            '0' <= символ && символ <= '9' ))
          return  false;
   }
   Поместить идентификатор в таблицу(....);
   return  true;
}
        Если язык должен поддерживать греческий, грузинский, армянский, арабский алфавиты, то код распухает ещё больше. Но можно использовать приём, который приведёт к значительному упрощению кода. Массив, описанный ниже, содержит некоторые признаки для каждого символа. Для получения признаков символа X нужно прочитать элемент массива с индексом X:
массив признаков [код символа A] = ПЕРВЫЙ СИМВОЛ ИДЕНТИФИКАТОРА |
                                   СЛЕДУЮЩИЙ СИМВОЛ ИДЕНТИФИКАТОРА |
                                   ШЕСТНАДЦАТИРИЧНАЯ ЦИФРА ... ;
...
массив признаков [код символа F] = ПЕРВЫЙ СИМВОЛ ИДЕНТИФИКАТОРА |
                                   СЛЕДУЮЩИЙ СИМВОЛ ИДЕНТИФИКАТОРА |
                                   ШЕСТНАДЦАТИРИЧНАЯ ЦИФРА ... ;
массив признаков [код символа G] = ПЕРВЫЙ СИМВОЛ ИДЕНТИФИКАТОРА |
                                   СЛЕДУЮЩИЙ СИМВОЛ ИДЕНТИФИКАТОРА ... ;
...
массив признаков [код символа Z] = ПЕРВЫЙ СИМВОЛ ИДЕНТИФИКАТОРА |
                                   СЛЕДУЮЩИЙ СИМВОЛ ИДЕНТИФИКАТОРА ... ;
массив признаков [код символа 0] = СЛЕДУЮЩИЙ СИМВОЛ ИДЕНТИФИКАТОРА |
                                   ЦИФРА | 
                                   ШЕСТНАДЦАТИРИЧНАЯ ЦИФРА ...;
...
массив признаков [код символа 9] = СЛЕДУЮЩИЙ СИМВОЛ ИДЕНТИФИКАТОРА |
                                   ЦИФРА | 
                                   ШЕСТНАДЦАТИРИЧНАЯ ЦИФРА ...;
        А дальше разбор лексемы "идентификатор" выглядит так:
bool  Это идентификатор (char  входная строка) {
    char  символ = входная строка [0];
    if (! (массив признаков [символ] && ПЕРВЫЙ СИМВОЛ ИДЕНТИФИКАТОРА ))
        return  false;
    for (int i=1; i < strlen (входная строка); i++) {
        символ = входная строка [i];
        if (! (массив признаков [символ] && СЛЕДУЮЩИЙ СИМВОЛ ИДЕНТИФИКАТОРА ))
            return  false;
    }
    Поместить идентификатор в таблицу(....);
    return  true;
}
        После этого код становится проще даже в сравнении с первым вариантом, который только для латиницы. Уменьшается число сравнений, что увеличивает скорость разбора. Но! Вышеприведённый массив должен иметь в качестве индекса код символа. Вот только в какой кодировке должен быть этот символ? Конечно же, в первую очередь думаем о Юникоде.

Справка. Первая версия Юникода представляла собой кодировку с фиксированным размером символа в 16 бит. Но вследствие расширения кодового пространства Юникод сам по себе перестал является кодировкой. Для кодирования символов Юникода стали использовать UTF (англ. Unicode Transformation Format): UTF-8, UTF-16, UTF-32.

Все версии Юникода позволяют использовать 1 112 064 символа. Это число было выбрано в качестве окончательной величины кодового пространства Юникода. Нулевая (базовая) плоскость Юникода (первые 65536 символов), позволяет использовать алфавиты практически всех языков. За переделами нулевой плоскости — редко используемые иероглифы и исторические письменности.

Некоторые символы Юникода могут быть представлены не одним способом. Например, символ «Й» представляется 2 способами:
— (U+0419)
— в виде базового символа «И» (U+0418) и модифицирующего символа «крючок над буквой» (U+0306)

UTF-8: символы в этой кодировке имеют переменную длину и занимают от 1 до 6 байтов — это в теории. На практике от 1 до 4 байтов, поскольку байты 5 и 6 не используются.

UTF-16: символы в этой кодировке имеют переменную длину и имеют размер 2 или 4 байта.

UTF-32: символы в этой кодировке занимают ровно 32 бита.

        Рассмотрим сразу пункт II наших требований, поскольку пункт I в комментариях пока не нуждается. Использую кодировки, в которых символы кодируются переменным числом байтов, мы лишаемся возможности обращаться к строкам, используя порядковый номер символа: string[i]. Чтобы узнать количество символов в строке, нужно провести её разбор. А уж если строку читать с конца, то возникают трудности с определением предыдущего символа.

        Но это не всё. Как мы видим, что некоторые символы могут кодироваться более, чем одним способом, типа буквы «Й» (см. пункт III). Чем это мешает? Тем, что одни и те же идентификаторы могут быть представлены несколькими способами. Поэтому нам нужно заменить составные символы на обычные, занимающие столько же битов, что и все. Википедия описывает формы нормализации для таких случаев, нужно использовать форму нормализации NFC. Эта тема требует дальнейшей проработки, чтобы выявить возможные подводные камни.

        Теперь пункт IV. Нам нужно обеспечить, чтобы массив характеристик для каждого символа помещался в память. И чем меньше он будет, тем лучше. Более миллиона символов (1 112 064) — это тоже многовато. Здравый смысл подсказывает, что шумерская письменность в языках программирования не нужна, древние шумеры не восстанут из небытия и не потребуют равенства возможностей. Выбирая нулевую (базовую) плоскость Юникода (первые 65536 символов), мы оставим за бортом лишь редко используемые иероглифы. Остальные символы оставшихся 16 плоскостей Юникода не имеют практической пользы для языка программирования.

        Поэтому из всех кодировок останавливаемся на UTF-16. 65536 символов нас устроят. Можно вспомнить ещё такой факт, что диапазон D80016..DFFF16 используется для кодирования так называемых суррогатных пар — символов, которые кодируются двумя 16-битными словами. Поскольку наша цель — 16 бит на символ, то символы этого диапазона нужно вычеркнуть. Итого: 65536-2048=63488

Как быть с другими кодировками?

        Мы вели речь о кодировке для компилятора. Т.е. «внутри» компилятора, в служебных таблицах и словарях должна использоваться UTF-16. Но это не значит, что «снаружи» не может быть подан текст в других кодировках: ASCII, UTF-8 и других. Среда разработки для нашего языка должна работать с UTF-16 нулевой плоскости — так удобнее. Но эта среда должна преобразовывать исходный текст из любых распространённых кодировок в выбранную нами. В случае неиспользования IDE компилятор так должен уметь выполнять такие же преобразования.

Выводы

  • Первые 65536 символов кодировки UTF-16 (нулевая плоскость Юникода) обеспечат возможностью программирования на родном языке. Эти символы имеют фиксированные размер. Массив, описывающий характеристики символов, будет иметь приемлемый размер.
  • Необходимо избавляться от составных символов, все символы должны иметь размер 16 битов
  • Остальные кодировки должны преобразовываться к выбранной нами UTF-16.

Последняя правка: 2016-03-18    21:14

ОценитеОценки посетителей
   █████████████████ 2 (40%)
   █████████████████ 2 (40%)
   █████████ 1 (20%)
   ▌ 0

Отзывы

     2016/01/03 11:31, Павиа

Нет кодировки лучше GB18030 ;-)

     2016/01/03 14:57, Автор сайта

Смех смехом, но кодировку выбирать всё равно придётся.

В этой статье, изложено, почему UTF-16 – лучшее решение. Но потом подумалось, что на 64-разрядных системах нет 16-битных регистров и команд. Работать с 16-битными объектами, конечно, можно, но с дополнительными накладными расходами. Пришёл к выводу, что 32-битнная кодировка хоть и избыточна, но легче ложится на х86-64. И вот попадается информация, что в библиотеке Qt класс для работы со строками QString оперирует со строками в UTF-16. И тут у меня лёгкий ступор. А как они работают на х86-64? Вроде как в этой архитектуре нет 16-разрядных регистров и нельзя обратиться в память и прочитать ровно 16 бит. Или я что-то не догоняю, всё-таки в х86-64 можно работать напрямую с 16-битными объектами? Или в Qt пошли на небольшие извращения и таки запихнули плохо впихуемое?

     2016/01/05 18:26, Павиа

QString имеют универсальный интерфейс подходящий под любую Юникодовую кодировку. Но на нижнем уровне там 8-битные строки. Но прикрутить 16-бит не составляет труда, хедеры в сети видел.

По поводу избыточности. 80% информации на жестком диске составляет текстовая не сжатая информация! Это справка, XML файлы, txt, макросов и коды программ.
А текстовая информация сжимается в 10 раз. Т.е. диск расходуется впустую.

Нет смысла делать 32 бита. Индексный доступ нужно только для обучения программированию. А на практике основная операция со строками это копирования, а также конкатенация(тоже копирование). И чем строка короче тем быстрее идёт работа.

Во-вторых 32 бита нужны только для КЯК. Но если посмотреть на Юникод. То там 30 тысяч иероглифов расположено в приделах 16 бит. И только 8 тысяч выше 16 бит. Хватило бы 17 бит.

Собственно поэтому 50% сайтов в Китае на gb2312 16-битной кодировке, которая имеет покрытие 99.75%. Им хватает! И не надо делать больше. Кому не хватает, тот пользуется gb18030.

И вам советую посмотреть gb18030, так как только Китай поддерживает интересы России и составил правильную кодировку. В отличие от американцев и их подопечных, которые специально суют палки в колеса. Вернее, кодировки портят намерено.

     2016/01/08 16:27, Автор сайта

Я прочитал про UTF-16 в QString, а Вы пишите про 8-битные строки. Т.е. Вы опровергаете?

Но прикрутить 16-бит не составляет труда

Да это элементарно сделать самому. Просто лексический разбор будет чуть медленнее, если 16-битные данные обрабатывать 8 или 32-битными командами.

Индексный доступ нужно только для обучения программированию

Да нет же, выше написано, как сделать очень простой и очень быстрый лексический анализатор, применив для этого индекс, который совпадает с кодом символа. Можно было бы сделать свою собственную кодировку с таким расположением букв: АаБб..ЕеЁёЖж..Яя. Вы не находите её логичной? Буква «а» в ней стоит впереди «Б», а в UTF, cp-2151, cp-866 – наоборот. Буквы «Ёё» стоят на месте. В принципе, почему бы нет? Ведь это внутренняя для компилятора кодировка! Но её минус в том, что её надо разрабатывать для каждого языка, который планируется использовать в языке программирования. Большинство языков обойдётся 8-битной кодировкой. Правда, союзникам 8 бит будет мало.

     2016/04/03 16:28, Вежливый Лис

С приходом UTF-8 исчезло понятие "текстовый редактор". Остались только текстовые процессоры. Ибо как можно что-то редактировать по одному симоволу, если в Unicode есть накладывающиеся последовательности (например и + крышечка = й ). Такая последовательность - это два кода unicode, но выглядит на экране как одно знакоместо. Значит это уже не текстовый редактор, а WYSIWYG-текстовый процессор.

     2016/04/03 16:44, Автор сайта

Нет, не исчезло. Википедия:

Notepad++ — свободный текстовый редактор с открытым исходным кодом для Windows...

А он работает и с UTF-8, и с cp-1251. Давайте не будем ввязываться в терминологический спор. Но работать с кодировкой, где символы однозначно представлены словом фиксированной разрядности, гораздо удобнее.

     2016/04/15 13:19, utkin

Люди уже предложили годное решение - выбрать готовую библиотеку для работы с нужной кодировкой и не заморачиваться. Чуть быстрей, чуть медленней для 4-хядерного процессора сейчас вообще не актуально. Большую часть времени процессор простаивает ожидая реакции юзера. Поэтому смысла в том, что компилятор будет работать на 0,0007 микросекунды быстрей особого нету. Оптимизация будет нужна только в случае реальных проблем со скоростью. Ну вон та же Ява далеко не спринтер, но лидер и решает большое количество задач разного направления.

     2016/04/15 15:29, Автор сайта

Не знаю ни одного человека, кто бы протестовал против быстрой работы его программ. Если можно сделать быстро – почему бы и нет? Тем более, что для этого всё есть.

     2016/04/18 07:53, utkin

Это да, но! Полная скорость включает время на создание инструмента его автором. То есть то время, которое будет потрачено на создание компилятора. Если из-за библиотеки его разработка затянется на несколько лет, компилятор может вообще стать не нужным. То есть если я компилирую прогу сейчас и жду две секунды больше или я компилирую мгновенно через 3 года, то разница для меня очевидна. Вот этого рядовые программисты никак не могут принять. С одной стороны действительно - медленный и неэффективный код заставляет людей покупать более мощное и более дорогое железо. С другой стороны время и деньги в конечном счете на стороне неэффективных программ работающих сейчас, а не оптимизированных систем работающих потом.

     2016/04/18 11:59, Автор сайта

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

     2017/05/03 03:17, rst256

Да нет же, выше написано, как сделать очень простой и очень быстрый лексический анализатор, применив для этого индекс, который совпадает с кодом символа. Можно было бы сделать свою собственную кодировку с таким расположением букв: АаБб..ЕеЁёЖж..Яя. Вы не находите её логичной? Буква «а» в ней стоит впереди «Б», а в UTF, cp-2151, cp-866 – наоборот. Буквы «Ёё» стоят на месте. В принципе, почему бы нет? Ведь это внутренняя для компилятора кодировка! Но её минус в том, что её надо разрабатывать для каждого языка, который планируется использовать в языке программирования. Большинство языков обойдётся 8-битной кодировкой. Правда, союзникам 8 бит будет мало.

С чего бы это дополнительный проход при компиляции, для создания этой самой внутренней для компилятора кодировки, сделает лексический анализ более быстрым?
А необходимость обратного преобразования в исходную кодировку тех же строковых литералов добавит простоты?
Ну а насчет расположения букв "АаБб..ЕеЁёЖж..Яя" для внутренней кодировки в чем смысл?

     2017/05/18 11:29, Автор сайта

дополнительный проход

Зачем дополнительный проход? Хватит простой таблички для перекодировки.

необходимость обратного преобразования в исходную кодировку

Обратное преобразование необходимо при выводе информации. Если не надо выводить, то и преобразовывать не надо.

насчет расположения букв "АаБб..ЕеЁёЖж..Яя" для внутренней кодировки в чем смысл?

Просто сама такая кодировка нравится, безо всякой связи с компиляторами. Сортировка в такой кодировке удобнее.

     2017/10/18 13:14, rst256

Просто сама такая кодировка нравится, безо всякой связи с компиляторами. Сортировка в такой кодировке удобнее.

А что, там разве часто будет нужно такую сортировку выполнять?

     2017/10/25 13:20, Автор сайта

Достаточно один раз возникнуть такой необходимости – и всё, надо делать. Нужна проверка существования некого типа или переменной? Значит надо сделать поиск среди ранее определённых сущностей. А где поиск – там и сортировка, это очень связанные задачи. Недаром Дональд Кнут объединил эти темы в один том.

Написать отзыв

Написать автору можно на электронную почту mail(аt)compiler.su

Авторизация

Регистрация

Выслать пароль

Карта сайта


Каким должен быть язык программирования?

Анализ и критика

Описание языка

Компилятор

Надо ли использовать YACC, LEX и подобные инструменты

Выбор кодировки для компилятора

Раскрутка компилятора

Лексический анализатор

●  Разбор цепочек знаков операций

●  Как отличить унарный минус от бинарного

Отечественные разработки

Cтатьи на компьютерные темы

Компьютерный юмор

Прочее

Последние комментарии

2018/07/03 03:27, rst256
Философия языка

2018/06/25 15:10, Автор сайта
Продолжение цикла и выход из него

2018/06/14 00:37, rst256
Лень — двигатель прогресса

2018/05/31 18:52, rst256
Программирование без программистов — это медицина без врачей

2018/05/31 17:57, rst256
Циклы

2018/05/31 17:50, Comdiv
Разбор цепочек знаков операций

2018/05/31 17:42, Comdiv
Как отличить унарный минус от бинарного

2018/05/30 18:57, Александр Коновалов aka Маздайщик
Раскрутка компилятора