Статья для Хабра №9 ‘Лексический анализ в 11l’

9.en.pq.txt

[[[
[[[Хабы: Компиляторы, Программирование]]]
[[[Title: Lexical Analysis in 11l]]]
[[[Tags: 11l, bilingual article, двуязычная статья]]]
]]]
This article discusses the lexical analyzer, which is an integral part of any compiler.

The task of the lexical analyzer is to split the source code of the program into tokens.

So for example the code
#(Python)‘
print(1 + 2)
’
will be tokenized as
`print`, `(`, `1`, `+`, `2` and `)`
'‘<cut />’'
H‘Significance of indentation’

Historically, compilers for most programming languages ‘strip away’[‘as there are no whitespace tokens’] all [[[delimiters/]]]whitespace characters such as space, tab, and newline.
What does this mean? It means the compiler sees the source code like this:
#(C)‘
if (foo)
   if (bar)
      m1();
else
   m2();
’
              ↓
`if`, `(`, `foo`, `)`, `if`, `(`, `bar`, `)`, `m1`, `(`, `)`, `;`, `else`, `m2`, `(`, `)`, `;`

This code is taken from ‘the Nemerle programming language documentation’[https://github.com/rsdn/nemerle/wiki/The-basics-(tutorial)#Rewriting_Line_Counter_without_the_loop]. It contains a so-called dangling else bug: when looking at this code, you might think that the “else” branch refers to the condition “foo”, whereas in programming languages with C-like syntax (including C++, C#, Java and others) the “else” branch refers to the condition “bar”.
As a solution to this problem, the developers of the Nemerle language introduced a rule that an “if” statement must always have an “else” branch, and if the “else” branch is not required, then the “when” statement should be used instead of “if”.
In many new programming languages, such as Swift, Rust, and Go, the use of curly braces is mandatory even if the body of the “if” [or other control [[[structure/]]]statement] is only one line. When curly braces are used, the problem disappears:
#(C)‘
if (foo) {
   if (bar) {
      m1();
   }
}
else {
   m2();
}
’

Some coding standards, for example those ‘from Oracle’[https://docs.oracle.com/cd/E12517_01/back_office/pdf/141/html/pos_impg2/developmentstandards.htm <- google:‘oracle coding standard’], ‘from Stanford University’[https://stanford.edu/class/archive/cs/cs106b/cs106b.1158/styleguide.shtml <- https://tproger.ru/translations/stanford-cpp-style-guide/ <- google:‘c++ code style’] or ‘Carnegie Mellon University’[https://wiki.sei.cmu.edu/confluence/display/c/EXP19-C.+Use+braces+for+the+body+of+an+if,+for,+or+while+statement], require the bodies of “if” and “else” [[[constructs/]]]statements to be enclosed in curly braces, to avoid the possibility of this [[[error/]]]bug:
#(C)‘
int login;

if (invalid_login())
    login = 0;
else
    printf("Login is valid\n");
    login = 1;
’
Here the line `login = 1;` will be executed in any case, no matter what value is returned by the `invalid_login` function.

But in both of the above cases, the problem is not at all that “if” [allowing an “else” branch to be either absent or present] expresses the wrong logic, or even that the curly braces were forgotten: it is... the discrepancy between the way this code is perceived by the human programmer and by the compiler. A human being perceives block boundaries visually, using indentation as a guide; but the compiler makes use of symbols [which a human hardly notices]. What is more, the compiler [for C/C++, C#, Java, Nemerle, etc.] treats all whitespace characters[[[ [delimiters]]]] in the same way, and, thus, completely ignores the indentation. This is where *‘the root of the problem lies: the compiler and the human see code like this differently’.

And to solve this problem, the compiler must somehow take indentation into account [so that the code examples given earlier either work as the programmer expects, or give an error at the compilation stage (or at least a warning[https://developers.redhat.com/blog/2016/02/26/gcc-6-wmisleading-indentation-vs-goto-fail <- google:‘Wmisleading-indentation’])].

For this reason, it was decided to provide the new programming language 11l with a lexical analyzer that takes indentation into account.

Now let's look at the implementation process. A brief description of the algorithm for parsing indentation is given in the ‘Python programming language documentation’[https://docs.python.org/reference/lexical_analysis.html#indentation]. In short, the algorithm works like this: at the beginning of each line, the indentation level is compared to the value[[[/number]]] on the top of a special stack. If it is larger, then it is pushed onto the stack and the lexer generates an INDENT token. If it is smaller, then all values exceeding the current line indentation level are removed from the stack and a DEDENT token is generated for each value removed. Further, at the end of the source file, a DEDENT is generated for each value remaining on the stack.

In addition to the fact that the lexical analyzer of the 11l language takes indentation into account, like the lexical analyzer of the Python language, the new language adds support for curly braces, which makes it possible to write code on one line or without indentation:
Т‘‘‘With indentation:
#(11l)‘
fn sum(a, b)
   return a + b
’
On one line:
#(11l)‘
fn sum(a, b) {return a + b}
’
Without indentation:
#(11l)‘
fn sum(a, b)
{
return a + b
}
’
’’’
In addition, code can be written using both indention and curly braces.
‘Here is how it works (in brief)’{
The indentation levels stack (`indentation_levels`) in 11l, in contrast to the lexical analyzer of the Python language, stores not just the indentation level but also a flag that is set to true whenever a new block of code is formed by the symbol `{`[[[}]]], rather than by increasing the indentation level. The indentation level is then set to `-1`.
The `{` character is immediately followed by a new, arbitrary {i.e. lowering the indentation level is allowed} indentation level {its level is set instead of `-1`}, which remains in effect up to the matching `}` character.
Here is a link[https://github.com/11l-lang/_11l_to_cpp/blob/529675344a73eac5cb313b5e22ab11191f2a1493/tokenizer.py#L212] to the corresponding source code.
}
This solution is the most versatile, and will suit both those who prefer using curly braces and those who prefer indentation.
All popular ‘indentation styles’[https://en.wikipedia.org/wiki/Indentation_style] are supported:
Т‘
Н‘‘Allman’ ‘K&R’ ‘GNU’’
‘
‘#(С)‘
if x == y
{
    something()
    somethingelse()
}
’’
‘#(С)‘
if x == y {
    something()
    somethingelse()
}
’’
‘#(С)‘
if x == y
  {
    something ()
    somethingelse ()
  }
’’
’
Н‘‘Whitesmiths’ ‘Ratliff’’
‘
‘#(С)‘
if x == y
    {
    something()
    somethingelse()
    }
’’
‘#(С)‘
if x == y {
    something()
    somethingelse()
    }
’’
’
’

H‘Automatic line [[[concatenation/]]]joining’

In addition to [[[dividing/]]]splitting the source code of a program into tokens, the lexical analyzer is also charged with determining statement boundaries. [Although in some programming languages (like ‘JavaScript or Kotlin’[https://temperlang.dev/design-sketches/parsing-program-structure.html#syntactic-asi]) assistance from the parser is required.]

Traditionally, a semicolon is used in C-like programming languages (C++, C#, Java, D) as a statement terminator. However, most new programming languages (e.g. Swift, Go, Kotlin, CoffeeScript, Nim, Julia, Crystal, and others) allow the semicolon to be omitted, by using the newline character as the end of a statement. [‘I am not the only one to have noticed this trend.’[https://elizarov.medium.com/the-end-of-the-semicolon-era-60ab95e669ab]]

But the question then arises: when do two consecutive lines of source code represent parts of the single statement, and when are they two different statements? And different programming languages solve this problem in different ways.

Python uses[https://docs.python.org/3/reference/lexical_analysis.html#implicit-line-joining] one simple rule for implicit line joining: if a line contains an unclosed parenthesis, square bracket, or curly brace, then it concatenates with following lines until all matching parentheses/brackets/braces are closed.

Go uses[https://golang.org/doc/effective_go#semicolons] the rule: [[[if a newline character follows a token that can end a statement]/]]if the newline comes after a token that could end a statement, then the statement is ended. However, this rule imposes significant restrictions on coding style.
For example, in an “if” statement, the curly brace that opens a block must be on the same line - moving it down to the next line is not allowed. The “else” statement must[https://stackoverflow.com/questions/26371645/unexpected-semicolon-or-newline-before-else-even-though-there-is-neither-before <- google:‘go lang semicolons problem’] also appear on the same line as the closing curly brace.
T‘H‘‘Right’ ‘Wrong’’
‘‘#(Go)‘
if i < f() {
    g()
}

’’‘#(Go)‘
if i < f()
{
    g()
}
’’
’
‘‘#(Go)‘
if x < 0 {
    return -1
} else {
    return 1
}

’’‘#(Go)‘
if x < 0 {
    return -1
}
else {
    return 1
}
’’
’
’
JavaScript uses a rather complex ‘system of rules’[http://www.ecma-international.org/ecma-262/6.0/index.html#sec-automatic-semicolon-insertion] to carry out automatic semicolon insertion.
#(JavaScript)‘
a = 1
b = 2
’
In this example, a semicolon will be automatically inserted at the end of the first line, since `a = 1 b = 2` ‘is not a valid statement’[https://slides.com/evanyou/semicolons/#/14].
However, in some cases a semicolon is not inserted, leading the code to function incorrectly.

For example, the following two lines of JavaScript code will be mistakenly [[[combined/]]]joined into one.
#(JavaScript)‘
a = b + c
[d, e] = [e, d]
’

And in this example, on the contrary, a semicolon will be erroneously inserted immediately after `return`.
#(JavaScript)‘
return
  "something";
’
That is, instead of returning a string `"something"`, the value `undefined` will be returned.

In most programming languages that allow semicolons to be omitted (for example, Python, Go, Kotlin, Ruby, Julia, and Nim), this code will not work:
#‘
r = 1
  + 2
’
Moreover, in Python, Go and Nim an error message will be displayed, while in Kotlin, Ruby and Julia the value of the variable `r` will be set to `1`.

To solve this problem, 11l uses the following 3 simple rules that are easily understood by both the programmer and the lexical analyzer:
1. If a line ends with a binary operator, then it is [[[concatenated/]]]joined with the next line.
2.‘If a line begins with a binary operator, then it is [[[concatenated/]]]joined with the previous line.
‘(It is necessary to check that it is not a unary operator!)’{
#(С)‘
a = b
++i // the plus character at the beginning of this line should not be mistaken for the binary operator `+`
’
}’
3. And also, just as in Python, a newline within expressions in parentheses or square brackets is ignored.

#(11l)‘
// 1.
if condition1 & // this line will be joined with the next one,
   condition2   \\ since it ends with the binary operator `&`
    some_func()

// 2.
some_variable = 2
              + 3 // this line will be joined with the previous one,
                  \\ since it starts with the binary operator `+`

// 3.
some_func(    // since this line includes an unclosed parenthesis, all
   argument1, \\ subsequent lines will be joined until
   argument2) \\ the parenthesis is closed
’

H‘Semicolons’

While it is not necessary to use a semicolon to mark the end of statements in 11l, semicolons can be used to place multiple statements on one line:
#(11l)‘
a = 1; b = 2; c = 3
’

But, for example, in Python it is not obvious what this line of code corresponds to:
#(Python)‘
if b: print(1); print(2)
’

Т‘
‘
‘This code in Python:’
‘#(Python)‘
if b:
    print(1)
    print(2)
’’
’‘
‘Or this:’
‘#(Python)‘
if b:
    print(1)
print(2)
’’
’
’
Т‘
‘
‘This code in 11l:’
‘#(11l)‘
if b {print(1); print(2)}
’’
’‘
‘Or this:’
‘#(11l)‘
if b {print(1)}; print(2)
’’
’
’
Python's behavior in this case is logical in principle, but not obvious.
The behavior of 11l, by contrast, is both logical and obvious.

Furthermore, it is impossible to write a one-line function like this in Python:
#(Python)‘
def f(x): if x: print(x)
’
But in 11l, it is possible:
#(11l)‘
fn f(x) {if x {print(x)}}
’

H‘Always room for improvement’

In my \/‘anything but’ humble opinion, 11l implements the most advanced lexical analyzer [[[in any/]]]of all currently existing programming languages. However, it can still be improved.

For example, the third automatic line [[[concatenation/]]]joining rule could be dropped, to support code like this:
#(11l)‘
set_timeout(
            1.0,
            fn ()
               alert(‘!’)
            ,
            0
           )
’
In this case, the third rule must be replaced with the following two rules:
. If a line ends with an opening parenthesis (`(`) or square bracket (`[`), or a comma (`,`), then it is [[[concatenated/]]]joined with the next line.
. If a line begins with a closing parenthesis (`)`) or square bracket (`]`), then it is [[[concatenated/]]]joined with the previous line.

But since at the moment 11l parser does not support constructs of this kind {in particular, anonymous functions are not supported [instead, you can use "arrow" functions (for example, `(x, y) -> x + y`)]}, their implementation at the level of the lexical analyzer would make no practical sense.

In conclusion, I will provide links to the source code for the 11l lexical analyzer, which is available in three languages: Python[https://github.com/11l-lang/_11l_to_cpp/blob/master/tests/python_to_cpp/_11l_to_cpp/tokenizer.py], 11l[https://github.com/11l-lang/_11l_to_cpp/blob/master/tests/python_to_cpp/_11l_to_cpp/tokenizer.11l] and C++[https://github.com/11l-lang/_11l_to_cpp/blob/master/tests/python_to_cpp/_11l_to_cpp/tokenizer.hpp].

9.pq.txt

[[[
[[[Хабы: Компиляторы, Программирование]]]
[[[Заголовок: Лексический анализ в 11l]]]
[[[Метки: 11l, двуязычная статья, bilingual article]]]
]]]
В данной статье [[[речь пойдёт]]/]говорится о лексическом анализаторе, который является неотъемлемой частью любого компилятора.

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

Так, например, код
#(Python)‘
print(1 + 2)
’
будет разбит на лексемы
`print`, `(`, `1`, `+`, `2` и `)`
'‘<cut />’'
Н‘Значимость отступов’

Исторически так сложилось, что компилятор большинства языков программирования отбрасывает[‘т.е. имеется в виду, что для «пробельных» символов нет соответствующих токенов’] все «пробельные» символы[[[ разделители]]], такие как пробел, табуляция и символ перевода строки.
К чему это приводит? К тому, что компилятор видит исходный код так:
#(C)‘
if (foo)
   if (bar)
      m1();
else
   m2();
’
              ↓
`if`, `(`, `foo`, `)`, `if`, `(`, `bar`, `)`, `m1`, `(`, `)`, `;`, `else`, `m2`, `(`, `)`, `;`

Данный код взят из ‘документации к языку программирования Nemerle’[https://github.com/rsdn/nemerle/wiki/The-basics-(tutorial)#Rewriting_Line_Counter_without_the_loop]. Он содержит так называемый баг висящего[[[\dangling]]] else, заключающийся в том, что при взгляде на данный код можно подумать, что ветка else относится к условию foo, тогда как в языках программирования, синтаксис которых основан на языке Си (включая С++, С#, Java и другие), ветка else относится к условию bar.
В качестве решения данной проблемы разработчики языка Nemerle ввели такое правило, что оператор if должен всегда иметь ветку else, а если ветка else не требуется, то вместо if следует использовать оператор when.
Во многих новых языках программирования, например в Swift, Rust и Go, обязательно использовать фигурные скобки даже если тело оператора if [и других операторов управления] состоит лишь из одной строки. При использовании фигурных скобок данная проблема пропадает[[[/исчезает]]]:
#(C)‘
if (foo) {
   if (bar) {
      m1();
   }
}
else {
   m2();
}
’

В некоторых стандартах кодирования, например ‘от Oracle’[https://docs.oracle.com/cd/E12517_01/back_office/pdf/141/html/pos_impg2/developmentstandards.htm <- google:‘oracle coding standard’], ‘от Стэнфордского университета’[https://stanford.edu/class/archive/cs/cs106b/cs106b.1158/styleguide.shtml <- https://tproger.ru/translations/stanford-cpp-style-guide/ <- google:‘c++ code style’] или ‘Университета Карнеги — Меллона’[https://wiki.sei.cmu.edu/confluence/display/c/EXP19-C.+Use+braces+for+the+body+of+an+if,+for,+or+while+statement], стоит требование заключать тело операторов if и else в фигурные скобки, чтобы исключить такую ошибку:
#(C)‘
int login;

if (invalid_login())
    login = 0;
else
    printf("Login is valid\n");
    login = 1;
’
Здесь строка `login = 1;` будет выполнена в любом случае, независимо от того, какое значение вернула функция `invalid_login`.

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

И [[[в качестве/]]]для решения данной проблемы компилятор так или иначе должен учитывать отступы [чтобы приведённые ранее примеры кода либо работали так, как ожидает этого программист, либо выдавали ошибку на этапе компиляции (или как минимум предупреждение[https://habr.com/ru/post/490850/#wmisleading-indentation])].

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

Теперь рассмотрим процесс реализации.[[[\Implementation notes]]] Краткое описание алгоритма учёта отступов приводится в ‘документации к языку программирования Python’[https://docs.python.org/reference/lexical_analysis.html#indentation]. [[[Ссылка указана на слайде. ]]]Вкратце алгоритм работает так: в начале каждой строки уровень отступа сравнивается со значением[[[/числом]]] в вершине специального стека. Если он больше, тогда он помещается в стек и лексический анализатор генерирует токен INDENT. А если меньше, то из стека удаляются все значения превышающие уровень отступа текущей строки и на каждое удаленное значение генерируется токен DEDENT. Также в конце исходного файла генерируется DEDENT для каждого оставшегося в стеке значения.

Помимо того, что лексический анализатор языка 11l [[[основан на отступах/]]]учитывает отступы, как и лексический анализатор языка Python, в новом языке добавлена поддержка фигурных скобок, что позволяет писать код в одну строку, либо без отступа:
Т‘‘‘С отступом:
#(11l)‘
fn sum(a, b)
   return a + b
’
В одну строку:
#(11l)‘
fn sum(a, b) {return a + b}
’
Без отступа:
#(11l)‘
fn sum(a, b)
{
return a + b
}
’
’’’
Кроме того, можно писать код и с отступом, и с фигурными скобками.
‘Вот как это работает (вкратце)’{
Стек уровней отступа (`indentation_levels`) в 11l в отличие от лексического анализатора языка Python помимо уровня отступа хранит флаг, который устанавливается в истину в случае, когда новый блок кода образован символом `{`[[[}]]], а не увеличением уровня отступа. При этом уровень отступа устанавливается в `-1`.
Сразу после символа `{` идёт новый произвольный {т.е. допускается понижение уровня отступа} отступ {его уровень [[[заменяет/]]]ставится вместо `-1`}, который действует вплоть до парного символа `}`.
Вот ссылка[https://github.com/11l-lang/_11l_to_cpp/blob/529675344a73eac5cb313b5e22ab11191f2a1493/tokenizer.py#L212] на соответствующий исходный код.
}
Такое решение является наиболее универсальным и подойдёт как предпочитающим использовать фигурные скобки, так и сторонникам отступов.
Поддерживаются [[[практически ]]]все популярные ‘[[[возможные ]]]стили отступов’[https://en.wikipedia.org/wiki/Indentation_style]:
Т‘
Н‘‘Allman’ ‘K&R’ ‘GNU’’
‘
‘#(С)‘
if x == y
{
    something()
    somethingelse()
}
’’
‘#(С)‘
if x == y {
    something()
    somethingelse()
}
’’
‘#(С)‘
if x == y
  {
    something ()
    somethingelse ()
  }
’’
’
Н‘‘Whitesmiths’ ‘Ratliff’’
‘
‘#(С)‘
if x == y
    {
    something()
    somethingelse()
    }
’’
‘#(С)‘
if x == y {
    something()
    somethingelse()
    }
’’
’
’

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

Помимо разбиения исходного текста программы на лексемы или токены, в задачу лексического анализатора также входит определение границ утверждений. [Хотя в некоторых языках программирования (например ‘в JavaScript и Kotlin’[https://temperlang.dev/design-sketches/parsing-program-structure.html#syntactic-asi]) требуется помощь синтаксического анализатора.]

Традиционно, для [[[разделения/]]]обозначения конца утверждений в языках программирования, основанных на Си (C++, C#, Java, D), используется символ "точка с запятой". Однако большинство [[[современных/]]]новых языков программирования (например Swift, Go, Kotlin, CoffeeScript, Nim, Julia, Crystal и другие) позволяют опускать [[[этот символ]]]"точки с запятой" используя символ новой строки как признак конца утверждения. [‘Не только я заметил эту тенденцию.’[https://elizarov.medium.com/the-end-of-the-semicolon-era-60ab95e669ab]]

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

В языке Python используется[https://docs.python.org/3/reference/lexical_analysis.html#implicit-line-joining] одно простое правило для неявного объединения строк: если строка содержит незакрытую круглую, квадратную или фигурную скобку, то она объединяется со следующими строками до тех пор, пока все соответствующие скобки не будут закрыты.

В языке Go используется[https://golang.org/doc/effective_go#semicolons] правило: если символ новой строки следует за лексемой, которая может завершить утверждение, то утверждение завершается[[[This could be summarized as, “if the newline comes after a token that could end a statement, insert a semicolon”.]]]. Однако такое правило [[[значительно ограничивает ]]]накладывает существенные ограничения на стиль кодирования.
Так, например, при использовании оператора `if` фигурная скобка, открывающая блок, должна располагаться в той же строке, другими словами, переносить её на следующую строку не допускается. Также, оператор `else` должен[https://stackoverflow.com/questions/26371645/unexpected-semicolon-or-newline-before-else-even-though-there-is-neither-before <- google:‘go lang semicolons problem’] располагаться в той же строке, что и закрывающая фигурная скобка.
Т‘Н‘‘Правильно’ ‘Неправильно’’
‘‘#(Go)‘
if i < f() {
    g()
}

’’‘#(Go)‘
if i < f()
{
    g()
}
’’
’
‘‘#(Go)‘
if x < 0 {
    return -1
} else {
    return 1
}

’’‘#(Go)‘
if x < 0 {
    return -1
}
else {
    return 1
}
’’
’
’
В языке JavaScript используется довольно сложная ‘система правил’[http://www.ecma-international.org/ecma-262/6.0/index.html#sec-automatic-semicolon-insertion], по которым производится автоматическая вставка символа "точка с запятой".
#(JavaScript)‘
a = 1
b = 2
’
В данном примере в конце первой строки будет автоматически вставлена "точка с запятой", так как `a = 1 b = 2` ‘не является действительным утверждением’[https://slides.com/evanyou/semicolons/#/14].[[[http://slides.com/evanyou/semicolons/fullscreen#/14]]]
Однако в некоторых случаях "точка с запятой" не будет вставлена, что приведёт к некорректной работе кода.

Например, следующие[[[/эти]]] две строки кода на JavaScript ошибочно [[[склеятся/]]]объединятся в одну.
#(JavaScript)‘
a = b + c
[d, e] = [e, d]
’

А в таком примере, наоборот, "точка с запятой" будет вставлена по ошибке сразу после `return`.
#(JavaScript)‘
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 для выражений в круглых и квадратных скобках символ новой строки игнорируется.

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

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

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

Н‘Точка с запятой’

Несмотря на то, что использовать точку с запятой для обозначения конца утверждений в 11l не требуется, точки с запятой могут быть использованы для размещения нескольких утверждений на одной строке:
#(11l)‘
a = 1; b = 2; c = 3
’

Но, к примеру, в Python неочевидно, чему соответствует данная строка кода:
#(Python)‘
if b: print(1); print(2)
’

Т‘
‘
‘Этому коду на Python:’
‘#(Python)‘
if b:
    print(1)
    print(2)
’’
’‘
‘Или этому:’
‘#(Python)‘
if b:
    print(1)
print(2)
’’
’
’
Т‘
‘
‘Этому коду на 11l:’
‘#(11l)‘
if b {print(1); print(2)}
’’
’‘
‘Или этому:’
‘#(11l)‘
if b {print(1)}; print(2)
’’
’
’
Поведение Python в данном случае в принципе логично, но не очевидно.
А поведение 11l — и логично, и очевидно.

Кроме того, в Python нельзя[[[вообще-то можно :)(: #(Python)‘f = lambda x: print(x) if x else None’, но пока лучшего примера я не смог придумать]]] написать такую однострочную функцию:
#(Python)‘
def f(x): if x: print(x)
’
В 11l же это возможно:
#(11l)‘
fn f(x) {if x {print(x)}}
’

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

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

Например, можно отказаться от 3-го правила автоматического объединения строк для поддержки такого кода:
#(11l)‘
set_timeout(
            1.0,
            fn ()
               alert(‘!’)
            ,
            0
           )
’
В этом случае 3-е правило нужно заменить на следующие 2 правила:
. Если строка оканчивается на открывающую круглую скобку (`(`), квадратную (`[`) или запятую (`,`), то она объединяется со следующей строкой.
. Если строка начинается на закрывающую круглую скобку (`)`) или квадратную (`]`), то она объединяется с предыдущей строкой.

'‘<!--[-->’'Но так как на данный момент синтаксический анализатор языка 11l не поддерживает такие конструкции {в частности, не поддерживаются анонимные функции [вместо них можно использовать "стрелочные"[[[[https://ru.wikipedia.org/wiki/Анонимная_функция google:‘анонимные функции’]:‘Стрелочная функция (arrow function expression)’]]] функции (например `(x, y) -> x + y`)]}, реализация на уровне лексического анализатора не имеет практического смысла.'‘<!--]-->’'

В заключение, приведу ссылки на исходный код лексического анализатора 11l, который доступен на трёх языках: Python[https://github.com/11l-lang/_11l_to_cpp/blob/master/tests/python_to_cpp/_11l_to_cpp/tokenizer.py], 11l[https://github.com/11l-lang/_11l_to_cpp/blob/master/tests/python_to_cpp/_11l_to_cpp/tokenizer.11l] и C++[https://github.com/11l-lang/_11l_to_cpp/blob/master/tests/python_to_cpp/_11l_to_cpp/tokenizer.hpp].

9.ru.pq.txt

[[[
[[[Хабы: Компиляторы, Программирование]]]
[[[Заголовок: Лексический анализ в 11l]]]
[[[Метки: 11l, двуязычная статья, bilingual article]]]
]]]
В данной статье говорится о лексическом анализаторе, который является неотъемлемой частью любого компилятора.

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

Так, например, код
#(Python)‘
print(1 + 2)
’
будет разбит на лексемы
`print`, `(`, `1`, `+`, `2` и `)`
'‘<cut />’'
Н‘Значимость отступов’

Исторически так сложилось, что компилятор большинства языков программирования отбрасывает[‘т.е. имеется в виду, что для «пробельных» символов нет соответствующих токенов’] все «пробельные» символы[[[ разделители]]], такие как пробел, табуляция и символ перевода строки.
К чему это приводит? К тому, что компилятор видит исходный код так:
#(C)‘
if (foo)
   if (bar)
      m1();
else
   m2();
’
              ↓
`if`, `(`, `foo`, `)`, `if`, `(`, `bar`, `)`, `m1`, `(`, `)`, `;`, `else`, `m2`, `(`, `)`, `;`

Данный код взят из ‘документации к языку программирования Nemerle’[https://github.com/rsdn/nemerle/wiki/The-basics-(tutorial)#Rewriting_Line_Counter_without_the_loop]. Он содержит так называемый баг висящего else, заключающийся в том, что при взгляде на данный код можно подумать, что ветка else относится к условию foo, тогда как в языках программирования, синтаксис которых основан на языке Си (включая С++, С#, Java и другие), ветка else относится к условию bar.
В качестве решения данной проблемы разработчики языка Nemerle ввели такое правило, что оператор if должен всегда иметь ветку else, а если ветка else не требуется, то вместо if следует использовать оператор when.
Во многих новых языках программирования, например в Swift, Rust и Go, обязательно использовать фигурные скобки даже если тело оператора if [и других операторов управления] состоит лишь из одной строки. При использовании фигурных скобок данная проблема пропадает:
#(C)‘
if (foo) {
   if (bar) {
      m1();
   }
}
else {
   m2();
}
’

В некоторых стандартах кодирования, например ‘от Oracle’[https://docs.oracle.com/cd/E12517_01/back_office/pdf/141/html/pos_impg2/developmentstandards.htm <- google:‘oracle coding standard’], ‘от Стэнфордского университета’[https://stanford.edu/class/archive/cs/cs106b/cs106b.1158/styleguide.shtml <- https://tproger.ru/translations/stanford-cpp-style-guide/ <- google:‘c++ code style’] или ‘Университета Карнеги — Меллона’[https://wiki.sei.cmu.edu/confluence/display/c/EXP19-C.+Use+braces+for+the+body+of+an+if,+for,+or+while+statement], стоит требование заключать тело операторов if и else в фигурные скобки, чтобы исключить такую ошибку:
#(C)‘
int login;

if (invalid_login())
    login = 0;
else
    printf("Login is valid\n");
    login = 1;
’
Здесь строка `login = 1;` будет выполнена в любом случае, независимо от того, какое значение вернула функция `invalid_login`.

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

И для решения данной проблемы компилятор так или иначе должен учитывать отступы [чтобы приведённые ранее примеры кода либо работали так, как ожидает этого программист, либо выдавали ошибку на этапе компиляции (или как минимум предупреждение[https://habr.com/ru/post/490850/#wmisleading-indentation])].

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

Теперь рассмотрим процесс реализации. Краткое описание алгоритма учёта отступов приводится в ‘документации к языку программирования Python’[https://docs.python.org/reference/lexical_analysis.html#indentation]. Вкратце алгоритм работает так: в начале каждой строки уровень отступа сравнивается со значением[[[/числом]]] в вершине специального стека. Если он больше, тогда он помещается в стек и лексический анализатор генерирует токен INDENT. А если меньше, то из стека удаляются все значения превышающие уровень отступа текущей строки и на каждое удаленное значение генерируется токен DEDENT. Также в конце исходного файла генерируется DEDENT для каждого оставшегося в стеке значения.

Помимо того, что лексический анализатор языка 11l учитывает отступы, как и лексический анализатор языка Python, в новом языке добавлена поддержка фигурных скобок, что позволяет писать код в одну строку, либо без отступа:
Т‘‘‘С отступом:
#(11l)‘
fn sum(a, b)
   return a + b
’
В одну строку:
#(11l)‘
fn sum(a, b) {return a + b}
’
Без отступа:
#(11l)‘
fn sum(a, b)
{
return a + b
}
’
’’’
Кроме того, можно писать код и с отступом, и с фигурными скобками.
‘Вот как это работает (вкратце)’{
Стек уровней отступа (`indentation_levels`) в 11l в отличие от лексического анализатора языка Python помимо уровня отступа хранит флаг, который устанавливается в истину в случае, когда новый блок кода образован символом `{`[[[}]]], а не увеличением уровня отступа. При этом уровень отступа устанавливается в `-1`.
Сразу после символа `{` идёт новый произвольный {т.е. допускается понижение уровня отступа} отступ {его уровень ставится вместо `-1`}, который действует вплоть до парного символа `}`.
Вот ссылка[https://github.com/11l-lang/_11l_to_cpp/blob/529675344a73eac5cb313b5e22ab11191f2a1493/tokenizer.py#L212] на соответствующий исходный код.
}
Такое решение является наиболее универсальным и подойдёт как предпочитающим использовать фигурные скобки, так и сторонникам отступов.
Поддерживаются все популярные ‘стили отступов’[https://en.wikipedia.org/wiki/Indentation_style]:
Т‘
Н‘‘Allman’ ‘K&R’ ‘GNU’’
‘
‘#(С)‘
if x == y
{
    something()
    somethingelse()
}
’’
‘#(С)‘
if x == y {
    something()
    somethingelse()
}
’’
‘#(С)‘
if x == y
  {
    something ()
    somethingelse ()
  }
’’
’
Н‘‘Whitesmiths’ ‘Ratliff’’
‘
‘#(С)‘
if x == y
    {
    something()
    somethingelse()
    }
’’
‘#(С)‘
if x == y {
    something()
    somethingelse()
    }
’’
’
’

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

Помимо разбиения исходного текста программы на лексемы или токены, в задачу лексического анализатора также входит определение границ утверждений. [Хотя в некоторых языках программирования (например ‘в JavaScript и Kotlin’[https://temperlang.dev/design-sketches/parsing-program-structure.html#syntactic-asi]) требуется помощь синтаксического анализатора.]

Традиционно, для обозначения конца утверждений в языках программирования, основанных на Си (C++, C#, Java, D), используется символ "точка с запятой". Однако большинство новых языков программирования (например Swift, Go, Kotlin, CoffeeScript, Nim, Julia, Crystal и другие) позволяют опускать "точки с запятой" используя символ новой строки как признак конца утверждения. [‘Не только я заметил эту тенденцию.’[https://elizarov.medium.com/the-end-of-the-semicolon-era-60ab95e669ab]]

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

В языке Python используется[https://docs.python.org/3/reference/lexical_analysis.html#implicit-line-joining] одно простое правило для неявного объединения строк: если строка содержит незакрытую круглую, квадратную или фигурную скобку, то она объединяется со следующими строками до тех пор, пока все соответствующие скобки не будут закрыты.

В языке Go используется[https://golang.org/doc/effective_go#semicolons] правило: если символ новой строки следует за лексемой, которая может завершить утверждение, то утверждение завершается. Однако такое правило накладывает существенные ограничения на стиль кодирования.
Так, например, при использовании оператора `if` фигурная скобка, открывающая блок, должна располагаться в той же строке, другими словами, переносить её на следующую строку не допускается. Также, оператор `else` должен[https://stackoverflow.com/questions/26371645/unexpected-semicolon-or-newline-before-else-even-though-there-is-neither-before <- google:‘go lang semicolons problem’] располагаться в той же строке, что и закрывающая фигурная скобка.
Т‘Н‘‘Правильно’ ‘Неправильно’’
‘‘#(Go)‘
if i < f() {
    g()
}

’’‘#(Go)‘
if i < f()
{
    g()
}
’’
’
‘‘#(Go)‘
if x < 0 {
    return -1
} else {
    return 1
}

’’‘#(Go)‘
if x < 0 {
    return -1
}
else {
    return 1
}
’’
’
’
В языке JavaScript используется довольно сложная ‘система правил’[http://www.ecma-international.org/ecma-262/6.0/index.html#sec-automatic-semicolon-insertion], по которым производится автоматическая вставка символа "точка с запятой".
#(JavaScript)‘
a = 1
b = 2
’
В данном примере в конце первой строки будет автоматически вставлена "точка с запятой", так как `a = 1 b = 2` ‘не является действительным утверждением’[https://slides.com/evanyou/semicolons/#/14].
Однако в некоторых случаях "точка с запятой" не будет вставлена, что приведёт к некорректной работе кода.

Например, следующие две строки кода на JavaScript ошибочно объединятся в одну.
#(JavaScript)‘
a = b + c
[d, e] = [e, d]
’

А в таком примере, наоборот, "точка с запятой" будет вставлена по ошибке сразу после `return`.
#(JavaScript)‘
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 для выражений в круглых и квадратных скобках символ новой строки игнорируется.

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

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

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

Н‘Точка с запятой’

Несмотря на то, что использовать точку с запятой для обозначения конца утверждений в 11l не требуется, точки с запятой могут быть использованы для размещения нескольких утверждений на одной строке:
#(11l)‘
a = 1; b = 2; c = 3
’

Но, к примеру, в Python неочевидно, чему соответствует данная строка кода:
#(Python)‘
if b: print(1); print(2)
’

Т‘
‘
‘Этому коду на Python:’
‘#(Python)‘
if b:
    print(1)
    print(2)
’’
’‘
‘Или этому:’
‘#(Python)‘
if b:
    print(1)
print(2)
’’
’
’
Т‘
‘
‘Этому коду на 11l:’
‘#(11l)‘
if b {print(1); print(2)}
’’
’‘
‘Или этому:’
‘#(11l)‘
if b {print(1)}; print(2)
’’
’
’
Поведение Python в данном случае в принципе логично, но не очевидно.
А поведение 11l — и логично, и очевидно.

Кроме того, в Python нельзя написать такую однострочную функцию:
#(Python)‘
def f(x): if x: print(x)
’
В 11l же это возможно:
#(11l)‘
fn f(x) {if x {print(x)}}
’

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

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

Например, можно отказаться от 3-го правила автоматического объединения строк для поддержки такого кода:
#(11l)‘
set_timeout(
            1.0,
            fn ()
               alert(‘!’)
            ,
            0
           )
’
В этом случае 3-е правило нужно заменить на следующие 2 правила:
. Если строка оканчивается на открывающую круглую скобку (`(`), квадратную (`[`) или запятую (`,`), то она объединяется со следующей строкой.
. Если строка начинается на закрывающую круглую скобку (`)`) или квадратную (`]`), то она объединяется с предыдущей строкой.

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

В заключение, приведу ссылки на исходный код лексического анализатора 11l, который доступен на трёх языках: Python[https://github.com/11l-lang/_11l_to_cpp/blob/master/tests/python_to_cpp/_11l_to_cpp/tokenizer.py], 11l[https://github.com/11l-lang/_11l_to_cpp/blob/master/tests/python_to_cpp/_11l_to_cpp/tokenizer.11l] и C++[https://github.com/11l-lang/_11l_to_cpp/blob/master/tests/python_to_cpp/_11l_to_cpp/tokenizer.hpp].