Организациялексического анализа

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

Необходимость фазы лексического анализа
1. Замена, цепочек символов, представляющих
элементарные конструкции языка, делает внутренне
представление программы более удобным для
дальнейшего анализа распознавателем.
2. Уменьшается длина программы за счет устранения из
нее несущественных для дальнейшего анализа пробелов,
комментариев, игнорируемых символов.
3. Один и тот же язык программирования может иметь
различные внешние представления элементарных
конструкций.
4. Лексический анализатор использует более простые, по
сравнению с синтаксическим анализатором, методы
разбора.
5. Блок лексического анализа естественным образом
вписывается в иерархическую структуру компилятора.
Трансляторы

Транслитератор
Устройство, осуществляющее сопоставление
класса с каждым отдельным символом,
называется транслитератором.
Наиболее типичными классами символов являются:
∙ буква - класс, с которым сопоставляется множество
букв, причем необязательно только одного алфавита;
∙ цифра - множество символов, относящихся к цифрам,
чаще всего от 0 до 9;
∙ разделители - пробел, перевод строки, возврат каретки
перевод формата;
∙ игнорируемые - могут встречаться во входном потоке,
но игнорируются и поэтому просто выбрасываются из
него (например, невидимый код звукового сигнала и
другие аналогичные коды);
∙ запрещенные - те символы, которые не относятся к
алфавиту языка, но встречаются во входной цепочке;
∙ остальные - символы, не вошедшие ни в одну из
определенных категорий.
Трансляторы

Грамматики и распознаватели для
лексического анализа
Праволинейные грамматики - конечный автомат
Построение конечного автомата можно
осуществить с использованием и некоторых
грамматик с левой рекурсией, а также
диаграмм Вирта.
Диаграммы Вирта намного нагляднее при описании
правил.
Между диаграммами Вирта, не содержащими
нетерминалов, и конечными автоматами существует
однозначное соответствие.
Трансляторы

Построение конечного автомата, по диаграмме
Вирта, без нетерминалов:
1. Вход входной дуги диаграммы преобразуется в
начальное состояние конечного автомата.
2. Выход выходной дуги диаграммы образует
заключительное состояние конечного автомата.
3. Выходы отдельных дуг, соединяющих символы, и
точки ветвления остальных дуг диаграммы образуют
множество остальных состояний конечного автомата.
4. Конечные состояния диаграммы являются
допускающими состояниями конечного автомата.
5. Терминальные символы диаграммы Вирта
расположенные между соответствующими дугами,
преобразуются в связи между соответствующими
состояниями, с входным символом, соответствующим
указанному терминалу.
6. Связи, обеспечивающие переход в допускающие
состояния, помечаются множеством оставшихся
символов. Это множество не пересекается с множеством
символов, обеспечивающих переходы из текущего в
другие состояния (обозначены как “прочие”).
Трансляторы

идентификатор
0
0
буква
Диаграмма
Вирта
буква
буква
1
цифра
буква
1
цифра
прочие
end
end
Конечный
автомат,
эквивалентный
представленной
диаграмме Вирта
Преобразование диаграммы Вирта в эквивалентный конечный автомат.
Трансляторы

идентификатор
буква
цифра
0
1
end
Минимизированная диаграмма Вирта, задающая идентификатор.
Трансляторы

Связь между диаграммами Вирта и
праволинейными грамматиками.
Преобразование правой рекурсии в итерацию
A → x
A → yA
A
=> x
y A
Непосредственное преобразование простой грамматики
Трансляторы

идентификатор
$ идентификатор = буква бц .
$ бц = буква бц | цифра бц | .
буква бц
=> бц
буква бц
цифра
Непосредственное преобразование идентификатора
Трансляторы

Замена правой рекурсии на итерацию в
диаграммах Вирта:
∙дуга, входящая в рекурсивно
определяемый нетерминал, замыкается
своим выходом на самое начало
правила, образуя, таким образом, цикл;
∙сам нетерминал, оказавшийся в
подвешенном состоянии
вычеркивается, а выходившая из него
дуга убирается.
Трансляторы

A → x
A → yA
A
y
A
=> x
y A
x => A
A
=>
x
y
Преобразование праволинейной грамматики в итеративную
диаграмму Вирта.
Трансляторы

идентификатор
$ идентификатор = буква бц .
$ бц = буква бц | цифра бц | .
идентификатор
буква бц
бц
буква
буква
идентификатор
буква
=> бц
буква
цифра
буква бц
буква бц
цифра
=>
=>
Преобразование праволинейной грамматики
идентификатора в итеративную диаграмму Вирта.
Трансляторы

Связь между диаграммами Вирта и
грамматиками с левой рекурсией.
Преобразование левой рекурсии в итерацию
Преобразования в итерацию для правил,
содержащих левую рекурсию:
∙дуга, выходящая из рекурсивно
определяемого нетерминала, замыкается
своим входом на самый конец правила,
образуя, таким образом, цикл;
∙сам нетерминал, оказавшийся без адресата,
вычеркивается, а входившая в него дуга
убирается.
Трансляторы

A → x
A → Ay
A
x
A
A
=> x =>
A y
=> A x
y y
Преобразование грамматики с левой рекурсией в
итеративную диаграмму Вирта
Трансляторы

идентификатор
$ идентификатор = буква |
идентификатор буква | =>
идентификатор цифра.
идентификатор
буква
цифра
идентификатор
буква
идентификатор
буква
цифра
=>
буква
цифра
=>
Преобразование грамматики идентификатора с левой рекурсией в
итеративную диаграмму Вирта.
Трансляторы

Методы лексического анализа
Непрямой лексический анализ, или
лексический анализ с возвратами,
заключается в последовательной проверке
версий о классах лексем. Если проверка
текущей версии не подтверждается, то
происходит откат назад по цепочке
символов и осуществляется проверка
следующей версии.
Прямой лексический анализ позволяет
определить значение лексемы без откатов
назад по цепочке символов.
Трансляторы

Входная лента
a0
a1
…
ai
…
an
Старт
Символ
Лексема 1
Блок управления
Распознаватель 1
входной
головкой
Откат
Отказ
Следующий
Лексема 2
Распознаватель 2
Откат
Отказ
Следующий
…
Откат
Отказ
Следующий
Лексема n
Распознаватель n
Откат
Отказ
Нейтрализация
Следующий
Лексема
ошибки
“ошибка”
Обработчик
ошибки
Стоп
Обобщенная структура непрямого лексического анализатора
Трансляторы

К достоинствам непрямого лексического анализатора
следует отнести:
∙прозрачность общей регулярной структуры,
которая легко может изменяться и наращиваться;
∙простота каждого отдельно автомата,
распознающего одну достаточно элементарную
конструкцию;
∙практическая применимость подхода в самых
разнообразных языках, независимо от сложности
выделения в нем тех или иных лексем.
Пример: DOI=3,10,3
DO I = 3, 10, 3 или DOI=3 ?
К недостаткам непрямого лексического анализатора
следует отнести низкую скорость распознавания
правильных лексем. Это связано с постоянными
возвратами входной головки к исходному состоянию,
если версия о лексеме не подтверждается.
Трансляторы

Входная лента
ai
…
aj
…
an
Старт
Символ
Распознаватель 1
Арбитр
Лексема 1
Отказ
Символ
Распознаватель 2
Лексема 2
Отказ
…
Лексема или
ошибка
Следующий
Символ
Распознаватель n
Лексема n
Отказ
Блок выравнивания
головок
Арбитраж
проведен
Стоп
Структура лексического анализатора с параллельной работой
распознавателей
Трансляторы

Входная лента
a0 …
Группа
символов 1
Группа
символов 2
ai …
Старт
Фрагмент 1
Не та
группа
Фрагмент 2
an
Передача
управления
частному блоку
Ошибка
Ошибка
Фрагмент 11
…
Фрагмент 1k
Лексема 1
Лексема i
Группа
символов n
Не та …
группа
…
Фрагмент n
Ошибка
Ошибка
Обработчик лексических ошибок
Лексема j
Фрагмент n1
… Лексема t
Фрагмент nm
Лексема
“ошибка”
Обобщенная структура прямого лексического анализатора
Трансляторы

Лексический анализатор
демонстрационного языка
программирования
Содержание
Транслитератор DPL.
Непрямой лексический анализатор DPL.
Прямой лексический анализатор DPL.
Трансляторы

Общая организация транслитератора
1. Класс букв: прописные и строчные буквы
латинского алфавита
2. Класс цифр: объединяет арабские цифры от 0
до 9.
3. Класс пропусков: состоит из пробела,
перевода строки, табуляции, перевода формата
(разделяющего текст на отдельные страницы).
4. Класс игнорируемых символов: включает все
символы, которые, как предполагается, не
отображаются в окне текстового редактора.
5. Класс прочих символов: включает все
оставшиеся символы.
Трансляторы

tltLetter
A B C D E F G H I
J
K L M
N O P Q R S T U V W X Y Z
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w x y
z
tltDigit
0
1
2
3
4
5
6
7
8
9
tltSkip
пробел
табуляция
перевод строки
перевод формата
Диаграммы Вирта, задающие некоторые из классов символов, порождаемых
Трансляторы

Разработка непрямого
лексического
анализатора
Трансляторы

IsKwAbort
a
IsKwBegin
b
IsKwWrite
w
kwAbort
b o r t
kwBegin
e g i n
…
kwWrite
r i t e
а) Непосредственный анализ ключевых слов.
Трансляторы

kwAbort
IsIdOrKw
tltLetter
_
tltLetter
=>ndKw
tltDiggit
_
kwBegin
…
kwWrite
lexId
б) Семантическое выделение ключевых слов из анализа идентификатора
Трансляторы

IsEof
lexEof
tltEOF
Примечание
1. Лексема, порождаемая при достижении конца
обрабатываемого текста.
kwAbort
IsIdOrKw
tltLetter
_
tltLetter
=>ndKw
tltDiggit
_
kwBegin
…
kwWrite
lexId
lexError
Примечание 2. Идентификатор и ключевые слова описываются
правилом с семантической вставкой. Осуществляется также анализ
на недопустимость возможного слияния идентификатора с
действительным числом, начинающимся с точки.
Трансляторы

IsFloat1
tltDiggit
IsFloat2
tltDiggit
Е +
е -
Е +
е -
lexFloat
tltDiggit
lexError
_
tltLetter
lexFloat
tltDiggit
lexError
_
tltLetter
Трансляторы

IsFloat3
tltDiggit
lexFloat
tltDiggit
lexError
_
tltLetter
IsFloat4
Е
tltDiggit
е
+
tltDiggit
-
lexFloat
lexError
_
tltLetter
Трансляторы

IsFloat5
lexFloat
tltDiggit
lexError
_
tltLetter
Примечание 3 . Пять вариантов правил для распознавания
действительного числа приводятся только для демонстрации
арбитража при непрямом лексическом анализе. На практике легко
можно обойтись одним правилом. Выдача ошибки происходит,
если действительное число не отделяется разделителем от
идентификатора
или
другого
действительного
числа,
начинающегося с десятичной точки
Трансляторы

IsBinary
{
0
2 }
1
lexInt
lexError
_
tltLetter
2
3
4
5
6
7
8
9
Трансляторы

IsOctal
{
8
}
0
1
2
3
4
5
6
7
lexInt
lexError
_
tltLetter
8
9
Примечание 4 . Для двоичных и десятичных целых чисел необходима
проверка того, что оно не сливается с теми цифрами, которые в них не
содержатся.
Трансляторы

IsPrefDecimal
lexInt
{ 1 0 }
IsDecimal
tltDigit
tltDigit
lexInt
lexError
lexError
_
tltLetter
_
tltLetter
Примечание 5. Для целого десятичного числа без префикса
анализ на недопустимость точки излишен, так как похожая
ситуация должна была быть проанализирована раньше для
действительного числа.
Трансляторы

IsHex
{
1
6
}
a
b
c
d e
f
tltDigit
A B C D E F
lexInt
lexError
_
G...Z | g…Z
Примечание 6. Для целого шестнадцатеричного проверка на
недопустимость должна исключать прописные и строчные
буквы, используемые в самом числе. На представленных
диаграммах это показано сокращенной записью путем задания
диапазона. Это сделано для того, чтобы не загромождать
диаграмму деталями.
Трансляторы

IsComment
/ *
1
Примечание
2
остальные
lexComment
* /
lexError
tltEOF
7. Под остальными понимаются
символы не рассматриваемые непосредственно в
текущей точке. В точке 1 - это не “*” и не конец
файла; в точке 2 - это не “*”, не конец файла и не
“/”
Трансляторы

IsSlash
IsStar
IsSemicolon
IsComma
IsLftRndBr
IsRghRndBr
IsLftSqBr
IsRghSqBr
IsPercent
lexSlash
/
* lexStar
lexSemicolon
;
, lexComma
lexLftndBr
(
lexRghRndBr
)
lexLftSqBr
[
lexRghSqBr
]
lexPercent
IsArrow
-
IsMinus -
IsGE
>
IsGT >
IsLE
<
IsLT
<
IsNE
!
IsEQ
=
IsIgnore
lexArrow
>
lexMinus
lexGE
=
lexGT
lexLE
=
lexLT
lexNE
=
lexEQ
lexIgnore
IsPlus
IsAssign
IsColon
Примечание
% tltIgnore
+ lexPlus
lexAssign
: =
: lexColon
8. Лексемы, определяющие разделительные символы,
расположены в соответствии с их приоритетом при анализе сверху вниз и
слева направо.
Трансляторы

NextLexema
IsEof
IsIdOrKw
IsFloat1
…
IsFloat5
IsBinary
IsOctal
IsPrefDecimal
IsDecimal
IsHex
IsComment
IsSlash
IsStar
IsSemicolon
IsComma
lexEof
kwAbort
le …
lexError
lexFloat
lexError
lexFloat
lexError
lexInt
lexError
lexInt
lexError
lexInt
lexError
lexInt
lexError
lexInt
lexError
lexComment
lexError
lexSlash
lexStar
lexSemicolon
lexComma
Трансляторы

IsStar
IsSemicolon
IsComma
IsLftRndBr
IsRghRndBr
IsLftSqBr
IsRghSqBr
IsPercent
IsPlus
IsAssign
IsColon
IsArrow
IsMinus
IsGE
IsGT
IsLE
IsLT
IsNE
IsEQ
IsIgnore
lexStar
lexSemicolon
lexComma
lexLftRndBr
lexRghRndBr
lexLftSqBr
lexRghSqBr
lexPercent
lexPlus
lexAssign
lexColon
lexArrow
lexMinus
lexGE
lexGT
lexLE
lexLT
lexNE
lexEQ
lexIgnore
lexError
Трансляторы

Разработка прямого
лексического
анализатора
Трансляторы

NextLexema
tltEOF
tltLetter
_
tltSkip
tltDiggit
tltIgnore
/
{
;
,
*
(
)
[
]
%
lexEof
kwAbort
IsContinueIdOrKw …
lexId
lexError
lexSkip
lexInt
lexFloat
IsNumber
lexError
lexIgnore
lexSlash
lexComment
IsSlashComment
lexError
lexInt
IsPrefNumber
lexError
lexFloat
IsFloatNumber
lexError
lexSemicolon
lexComma
lexStar
lexLftRndBr
lexRghRndBr
lexLftSqBr
lexRghSqBr
lexPercent
Трансляторы

lexPlus
+
lexColon
:
lexAssign
=
lexMinus
-
lexArrow
>
lexGT
>
lexGE
=
lexLT
<
lexLE
=
lexEQ
=
lexError
!
lexNE
=
lexError
Трансляторы

kwAbort
IsContinueIdOrKw
tltLetter
=>ndKw
tltDiggit
_
kwBegin
…
kwWrite
lexId
lexError
IsNumber
lexInt
tltDiggit
tltDiggit
Е +
tltDiggit
е -
_ lexError
tltLetter
lexFloat
lexError
_
tltLetter
Трансляторы

IsSlashComment
*
1
lexSlash
2
остальные
lexComment
* /
lexError
tltEOF
Трансляторы

IsPrefNumber
{
0
2 } lexError
1
lexInt
lexError
_
tltLetter
2
3
4
5
6
7
8
9
8 }
lexError 0
1 0 }
lexError
1 2 3 4 5
lexInt
tltDigit
lexError
_
tltLetter
6 7
_
tltLetter
8
9
lexInt
lexError
6 }
a
lexError
tltDigit
b c d e f
A B C D E F lexInt
lexError
G...Z |_
g…Z
Трансляторы