Лексический анализ в 11l

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

Так, например, код

print(1 + 2)

будет разбит на лексемы
print, (, 1, +, 2 и )

Значимость отступов

Исторически так сложилось, что компилятор большинства языков программирования отбрасывает все «пробельные» символы, такие как пробел, табуляция и символ перевода строки.
К чему это приводит? К тому, что компилятор видит исходный код так:

if (foo)
   if (bar)
      m1();
else
   m2();

              ↓
if, (, foo, ), if, (, bar, ), m1, (, ), ;, else, m2, (, ), ;

Данный код взят из документации к языку программирования Nemerle ^[1]. Он содержит так называемый баг висящего else, заключающийся в том, что при взгляде на данный код можно подумать, что ветка else относится к условию foo, тогда как в языках программирования, синтаксис которых основан на языке Си (включая С++, С#, Java и другие), ветка else относится к условию bar.
В качестве решения данной проблемы разработчики языка Nemerle ввели такое правило, что оператор if должен всегда иметь ветку else, а если ветка else не требуется, то вместо if следует использовать оператор when.
Во многих новых языках программирования, например в Swift, Rust и Go, обязательно использовать фигурные скобки даже если тело оператора if [и других операторов управления] состоит лишь из одной строки. При использовании фигурных скобок данная проблема пропадает:

if (foo) {
   if (bar) {
      m1();
   }
}
else {
   m2();
}

В некоторых стандартах кодирования, например от Oracle ^[2], от Стэнфордского университета ^[3] или Университета Карнеги — Меллона ^[4], стоит требование заключать тело операторов if и else в фигурные скобки, чтобы исключить такую ошибку:

int login;
 
if (invalid_login())
    login = 0;
else
    printf("Login is validn");
    login = 1;

Здесь строка login = 1; будет выполнена в любом случае, независимо от того, какое значение вернула функция invalid_login.

Но в обоих приведённых случаях проблема отнюдь не в неправильной логике if [допускающем как отсутствие ветви else, так и её наличие], и даже не в забытых фигурных скобках, а в… расхождении в восприятии данного кода человеком-программистом и компилятором. Человек воспринимает границы блоков визуально, за счёт отступов, а компилятор — с помощью [малоприметных для человека] символов, причём компилятор [языков C/C++, C#, Java, Nemerle и др.] объединяет все «пробельные» символы, и, таким образом, напрочь игнорирует отступы. Вот в этом и заключается корень проблемы — компилятор и человек видят такой код по-разному.

И для решения данной проблемы компилятор так или иначе должен учитывать отступы [чтобы приведённые ранее примеры кода либо работали так, как ожидает этого программист, либо выдавали ошибку на этапе компиляции (или как минимум предупреждение ^[5])].

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

Теперь рассмотрим процесс реализации. Краткое описание алгоритма учёта отступов приводится в документации к языку программирования Python ^[6]. Вкратце алгоритм работает так: в начале каждой строки уровень отступа сравнивается со значением в вершине специального стека. Если он больше, тогда он помещается в стек и лексический анализатор генерирует токен INDENT. А если меньше, то из стека удаляются все значения превышающие уровень отступа текущей строки и на каждое удаленное значение генерируется токен DEDENT. Также в конце исходного файла генерируется DEDENT для каждого оставшегося в стеке значения.

Помимо того, что лексический анализатор языка 11l учитывает отступы, как и лексический анализатор языка Python, в новом языке добавлена поддержка фигурных скобок, что позволяет писать код в одну строку, либо без отступа:

fn sum(a, b)
   return a + b

fn sum(a, b) {return a + b}

fn sum(a, b)
{
return a + b
}

Кроме того, можно писать код и с отступом, и с фигурными скобками.

Такое решение является наиболее универсальным и подойдёт как предпочитающим использовать фигурные скобки, так и сторонникам отступов.
Поддерживаются все популярные стили отступов ^[8]:

if x == y
{
    something()
    somethingelse()
}

if x == y {
    something()
    somethingelse()
}

if x == y
  {
    something ()
    somethingelse ()
  }

if x == y
    {
    something()
    somethingelse()
    }

if x == y {
    something()
    somethingelse()
    }

Автоматическое объединение строк

Помимо разбиения исходного текста программы на лексемы или токены, в задачу лексического анализатора также входит определение границ утверждений. [Хотя в некоторых языках программирования (например в JavaScript и Kotlin ^[9]) требуется помощь синтаксического анализатора.]

Традиционно, для обозначения конца утверждений в языках программирования, основанных на Си (C++, C#, Java, D), используется символ "точка с запятой". Однако большинство новых языков программирования (например Swift, Go, Kotlin, CoffeeScript, Nim, Julia, Crystal и другие) позволяют опускать "точки с запятой" используя символ новой строки как признак конца утверждения. [Не только я заметил эту тенденцию. ^[10]]

Однако в этом случае возникает вопрос: в каких случаях смежные строки исходного кода задают одно утверждение, а в каких случаях — различные утверждения. И разные языки программирования решают эту проблему по-разному.

В языке Python используется ^[11] одно простое правило для неявного объединения строк: если строка содержит незакрытую круглую, квадратную или фигурную скобку, то она объединяется со следующими строками до тех пор, пока все соответствующие скобки не будут закрыты.

В языке Go используется ^[12] правило: если символ новой строки следует за лексемой, которая может завершить утверждение, то утверждение завершается. Однако такое правило накладывает существенные ограничения на стиль кодирования.
Так, например, при использовании оператора if фигурная скобка, открывающая блок, должна располагаться в той же строке, другими словами, переносить её на следующую строку не допускается. Также, оператор else должен ^[13] располагаться в той же строке, что и закрывающая фигурная скобка.

if i < f() {
    g()
}

if i < f()
{
    g()
}

if x < 0 {
    return -1
} else {
    return 1
}

if x < 0 {
    return -1
}
else {
    return 1
}

В языке JavaScript используется довольно сложная система правил ^[14], по которым производится автоматическая вставка символа "точка с запятой".

a = 1
b = 2

В данном примере в конце первой строки будет автоматически вставлена "точка с запятой", так как a = 1 b = 2 не является действительным утверждением ^[15].
Однако в некоторых случаях "точка с запятой" не будет вставлена, что приведёт к некорректной работе кода.

Например, следующие две строки кода на JavaScript ошибочно объединятся в одну.

a = b + c
[d, e] = [e, d]

А в таком примере, наоборот, "точка с запятой" будет вставлена по ошибке сразу после return.

return 
  "something";

Т.е. вместо возврата строки "something" будет возвращено значение undefined.

В большинстве языков программирования, позволяющих опускать "точки с запятой" (например, в Python, Go, Kotlin, Ruby, Julia и Nim), такой код работать не будет:

r = 1
  + 2

Причём в языках Python, Go и Nim будет выдано сообщение об ошибке, а в языках Kotlin, Ruby и Julia значение переменной r будет установлено в 1.

Для решения этой проблемы в 11l используются следующие 3 несложные правила, которые просто понять программисту и легко реализовать в лексическом анализаторе:

1. Если строка оканчивается на бинарный оператор, то она объединяется со следующей строкой.
2. Если строка начинается на бинарный оператор, то она объединяется с предыдущей строкой.
   (При этом необходимо проверить, что это не унарный оператор!)

   a = b
   ++i // символ плюса в начале этой строки не должен быть принят за бинарный оператор `+`
   

3. И также как в Python для выражений в круглых и квадратных скобках символ новой строки игнорируется.

// 1.
if условие1 & // эта строка будет объединена со следующей,
   условие2   \ так как она оканчивается на бинарный оператор `&`
    some_func()

// 2.
some_variable = 2
              + 3 // эта строка будет объединена с предыдущей,
                  \ так как она начинается на бинарный оператор `+`

// 3.
some_func(    // так как в этой строке не закрыта скобка, все
   argument1, \ последующие строки будут объединяться до тех пор,
   argument2) \ пока скобка не будет закрыта

Точка с запятой

Несмотря на то, что использовать точку с запятой для обозначения конца утверждений в 11l не требуется, точки с запятой могут быть использованы для размещения нескольких утверждений на одной строке:

a = 1; b = 2; c = 3

Но, к примеру, в Python неочевидно, чему соответствует данная строка кода:

if b: print(1); print(2)

if b:
    print(1)
    print(2)

if b:
    print(1)
print(2)

if b {print(1); print(2)}

if b {print(1)}; print(2)

Поведение Python в данном случае в принципе логично, но не очевидно.
А поведение 11l — и логично, и очевидно.

Кроме того, в Python нельзя написать такую однострочную функцию:

def f(x): if x: print(x)

В 11l же это возможно:

fn f(x) {if x {print(x)}}

Нет предела совершенству

По моему _нескромному мнению, в 11l реализован самый совершенный на данный момент лексический анализатор из всех существующих языков программирования. Однако и его всё ещё можно улучшить.

Например, можно отказаться от 3-го правила автоматического объединения строк для поддержки такого кода:

set_timeout(
            1.0,
            fn ()
               alert(‘!’)
            ,
            0
           )

В этом случае 3-е правило нужно заменить на следующие 2 правила:

• Если строка оканчивается на открывающую круглую скобку ((), квадратную ([) или запятую (,), то она объединяется со следующей строкой.
• Если строка начинается на закрывающую круглую скобку ()) или квадратную (]), то она объединяется с предыдущей строкой.

Но так как на данный момент синтаксический анализатор языка 11l не поддерживает такие конструкции {в частности, не поддерживаются анонимные функции [вместо них можно использовать "стрелочные" функции (например (x, y) -> x + y)]}, реализация на уровне лексического анализатора не имеет практического смысла.

В заключение, приведу ссылки на исходный код лексического анализатора 11l, который доступен на трёх языках: Python ^[16], 11l ^[17] и C++ ^[18].