Используются 2 стратегии работы лексического анализа:

Второй способ считается предпочтительнее.

1) Преобразование некоторых КС-грамматик в автоматные

2) Диаграмма состояний автоматной грамматики

§ 2.3. КА для анализа вещественной константы

2.09M

Category:

informatics

Лексический анализ (глава 2)

1. Глава 2. Лексический анализ

Цель его работы – выделение лексем
и формирование, как правило,
лексической свертки.

2. §2.1. Сканер 2.1.1 Назначение сканера

Сканер представляет собой ту часть
компилятора, которая читает (сканирует)
символы исходной программы и формирует
лексемы:
• идентификаторы,
• числовые, текстовые константы,
• 1- и 2- х символьные разделители,
• знаки операций и т.д.
Одновременно выполняется лексический
контроль.

3. Используются 2 стратегии работы лексического анализа:

1) блок синтаксического анализа обращается к
сканеру, как только требуется выделить очередную
лексему , т.е. лексический анализатор По принципу
не выделен отдельным блоком;
«дай лексему»
2) сканер используется блоком лексического анализа,
отделенным от блока синтаксического анализа и
работающим раньше его. Блок лексического анализа
обращается к сканеру для выделения одной текущей
лексемы, размещает её в таблице и последовательно
формирует лексическую свертку, которая поступает
затем на вход синтаксического анализатора.

4. Второй способ считается предпочтительнее.

Доводы в пользу отделения
лексического анализа от синтаксического:
1) значительная часть времени
компиляции тратится на сканирование и
анализ символов.
Выделение его, как отдельного процесса,
позволяет запрограммировать его более
эффективно, например на Ассемблере.

5.

2) Синтаксис лексем можно описать в
рамках простых грамматик (например,
класса 3),
что позволяет создать более
эффективный распознаватель и даже
автоматизировать процесс его
построения, например, в виде КА(см. п.4)

6.

3) Так как сканер формирует лексемы
вместо отдельных символов, то
синтаксический анализ на каждом шаге
имеет больше информации о структуре
программы.

7. 2.1.2. Автоматные языки и их свойства

Напомним, что автоматные языки
порождаются автоматными
грамматиками (класс 3), правила которых
имеют вид
U -> a,
U -> Va (или aV), где U, V N, a T.
Рассмотрим некоторые свойства
автоматных грамматик и языков.

8. 1) Преобразование некоторых КС-грамматик в автоматные

Отметим, что автоматные грамматики
являются подмножеством КС-грамматик.
Определение 1.
1) Правило вывода КС-грамматики
будем называть заключительным, если оно имеет
вид
A -> , где A N, T*;
2) правило вывода будем называть праволинейным
(леволинейным), если оно имеет вид
A -> B (A -> B ), где A, B N, T*
( может равняться e);
3) неукорачивающая КС-грамматика называется
праволинейной (леволинейной), если все ее правила
праволинейные (леволинейные) или заключительные.

9.

Обе такие грамматики можно привести к
эквивалентной (или почти эквивалентной)
автоматной грамматике.
Теорема 1. По любой праволинейной
(леволинейной) КС-грамматике можно
построить эквивалентную ей автоматную
грамматику. Если КС-грамматика содержит
e-правила, то почти эквивалентную.

10. Доказательство.

Отличие правил праволинейной и
автоматной грамматик только в том,
что в правых частях у праволинейной
грамматики может стоять не один, а
несколько терминальных символов.
Выполним замену этих правил, используя
допустимое преобразование добавление
нетерминала.
U -> a,
U -> aV, где U, V N, a T.
A -> , где A N, T*;
A -> B, где A, B N, T*

11.

Итак, пусть правило КС-грамматики
имеет вид
A -> B, где | | 2, т.е.
A -> a1a2…anB, A,B N, ai T.
Введем n-1 новый нетерминал A1, A2, …,
An-1 N и заменим данное правило группой
правил
A -> a1A1,
A1 -> a2A2,
…,
An-1-> anB.
Если правило заключительное, т.е. имеет вид
A -> , то последнее правило примет вид
An-1 -> an.

12.

- Заменив таким образом все
праволинейные и заключительные
правила, получим эквивалентную
автоматную грамматику.
Если в КС-грамматике были e-правила, то
преобразуем её к почти эквивалентной
неукорачивающей, а затем в автоматную
описанным выше образом.

13.

- Если исходная грамматика
леволинейная, то процедура
преобразования правил
A -> B
и
A ->
аналогична:
A ->A1an,
A1 -> A2an-1,
…,
An-1 -> Ba1.

14. 2) Диаграмма состояний автоматной грамматики

Автоматную грамматику можно
представить в виде ориентированного
графа.
Граф позволяет не только наглядно увидеть
взаимосвязи между символами и правилами,
но и выполнить по нему анализ цепочек на
принадлежность языку, порожденному этой
грамматикой, по простому правилу.

15. Граф строится таким образом:

1) вершины помечаются
нетерминальными символами;
2) дуги – терминальными;
3) вводится дополнительная вершина I –
вход в граф;
4) каждому правилу вида
A -> a
в соответствие ставится фрагмент графа
a
I
A

16.

А правилу
A -> Ba
фрагмент
a
B
A
5. Выделяют заключительную вершину,
соответствующую начальному символу
грамматики.

17. Пример.

Грамматике идентификатора G(ид):
И –> a | b |…| z | Иa | Иb | … | Иz | И0 | И1 |
... | И9
соответствует граф
I

18. Пример.

Грамматике идентификатора G(ид):
И –> a | b |…| z | Иa | Иb | … | Иz | И0 | И1 |
... | И9
соответствует граф
a
I
…
z
И

19. Пример.

Грамматике идентификатора G(ид):
И –> a | b |…| z | Иa | Иb | … | Иz | И0 | И1 |
... | И9
соответствует граф
a
I
…
z
И
a …z
0 … 9

20. Пример.

Грамматике идентификатора G(ид):
И –> a | b |…| z | Иa | Иb | … | Иz | И0 | И1 |
... | И9
соответствует граф
a
I
…
И
a …z
z
И – заключительная вершина.
0 … 9

21. ДС

Граф, представляющий автоматную
грамматику, чаще называют диаграммой
состояний (ДС):
состояния – вершины,
I – начальное состояние.
Приведем теперь правило анализа
цепочек по ДС.

22. Правило анализа.

Пусть задана автоматная грамматика G,
её ДС и цепочка = a1a2…an.
Требуется выяснить,
L(G)?
Встанем в ДС на начальную вершину I, а
в цепочке на первый символ a1.

23. Правило анализа

Найдем дугу, исходящую из I и помеченную
терминалом a1.
Перейдем по этой дуге в следующую вершину
S’, а в цепочке к следующему символу a2.
Процесс продолжим аналогичным образом.
Если цепочка L(G), то её анализ
завершится в заключительной вершине и вся
цепочка, при этом, будет прочитана. В
противном случае L(G).