29376

Принципы работы сканера

Доклад

Информатика, кибернетика и программирование

Синтаксис целых констант представляется: целое ::=цифра знак цифра целое цифра знак ::= Для представления грамматики состояния целых констант диаграмма имеет вид:Вершины соответствуют состояниям автомата и определяются нетерминальными символами. Построим диаграмму состояний для автомата который распознает лексемы трех типов: целые константы десятичные константы идентификаторы идентр ::=буква идентр буква идентр цифра десятичная константа: дес.число цифра смеше число цифра смеше число ::= целое целое ::=цифра знак цифра целое цифра...

Английский

2013-08-21

95.5 KB

0 чел.

12) Принципы работы сканера.

Синтаксис отдельных лексем описывается, главным образом, с использованием регулярных грамматик. Для них продукция имеет следующую форму:
А→а|Ва или А→а|аВ
а – терминальные символы, А,В – нетерминальные
Функционирование сканера базируется на грамматическом описании лексем, в основе построения сканера лежит конечный автомат, соответствующий используемой грамматике.
Конечный автомат – математическая машина, которая определяется множеством возможных состояний, множеством возможных переходов между состояниями и множеством возможных символов, управляющих этими переходами.
Геометрическое функционирование конечного автомата можно задать графовой моделью, которая называется диаграммой состояния.
Пример. 
Синтаксис целых констант представляется:

<целое>::=цифра|<знак>цифра|<целое>цифра
<знак>::= +|-
Для представления грамматики состояния целых констант диаграмма имеет вид:

Вершины соответствуют состояниям автомата и определяются нетерминальными символами. Дуги описывают возможные переходы между состояниями и соответствуют продукции грамматики.
Для заданной грамматики определяются следующие лексемы:
1) каждому нетерминальному символу сопоставляется вершина графа с соответствующим именем
2) добавляется дополнительная вершина, соответствующая начальному состоянию автомата с именем Старт
3) каждому правилу вывода следующего вида А→а сопоставляется дуга, связывающая вершины Старт и А, которая помечается терминальным символом а
4) каждой продукции А→Ва сопоставляется дуга 
, которая также помечается терминальным символом а
Распознавание лексем с использованием диаграмм состояний конечного автомата осуществляется следующим образом:
1) исходным состоянием является состояние Старт
2) последовательно сканируются (считываются) символы входной цепочки и в соответствии с очередным считывающимся символом выполняется переход автомата в следующее состояние. Этот переход происходит из текущей вершины в то состояние ( вершину), в которую направлена дуга, помеченная символом, совпадающим со считанным символом входной цепи.
3) Переходы между состояниями продолжаются до остановки автомата, которая происходит в двух случаях:
• Считаны все символы входной цепочки
• Переход в следующее состояние невозможен, т.к. не найдена дуга, помеченная считанным символом.
В итоге лексемы будут распознаны, если работа автомата заканчивается в состоянии, соответствующем начальному символу грамматики. На диаграмме эта вершина выделена 

По мере считывания символов входной цепочки фиксируется символ, на котором автомат начинает работу ( выходит из состояния Старт) и на котором заканчивает работу, т.е. останавливается. 
Сама лексема состоит из тех считанных символов, начиная с которых автомат вышел из сосояния старт и до символа, на котором автомат завершил работу. 

Построим диаграмму состояний для автомата, который распознает лексемы трех типов: целые константы, десятичные константы, идентификаторы

<идент-р>::=буква|<идент-р>буква|<идент-р>цифра



десятичная константа:

<дес.число>::=<дес.число>цифра|<смеш-е число>цифра
<смеш-е число>::=<целое>
<целое>::=цифра|<знак>цифра|<целое>цифра
<знак>::=+|-


С точки зрения процесса трансляции в целом, сканер может быть реализован в двух вариантах:
1) сканер выполняет полный лексический анализ всей программы и формирует эквивалентную последовательность лексем, которая потом используется на фазе синтаксического анализа

2) сканер выполняется в виде подпрограмм, к которым обращается синтаксический анализатор, когда требуется очередная лексема для грамматического разбора

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


 

А также другие работы, которые могут Вас заинтересовать

55163. Робота з об'єктами в ОС Windows 2.11 MB
  Мета: Формування умінь та навичок по створенню, копіюванню, перейменуванню, знищенню та відновленню обєктів в операційній системі Windows. Постановка загальної проблеми: Як створювати, копіювати, перейменовувати, знищувати та відновлювати об'єктів в операційній системі Windows?
55164. Планування як функція управління 48.5 KB
  Мета: зясувати сутність планування як функції управління виділити основні етапи процесу планування та типи планів в організації класифікувати цілі управлінського планування зясувати механізм управління за цілями та визначити його сильні та слабкі сторони...
55166. Використання фреймів в html-документах 488 KB
  Мета роботи: навчитись застосовувати фрейми при створенні html-документів. 1 Підготовка до заняття 1. Вивчити відповідні розділи теоретичної частини методички та відповідного лекційного курсу. 2. Підготувати малюнки в Pаint та зберегти їх як fon1.bmp та fon2.bmp.
55167. Використання службових програм для обслуговування операційної системи Windows 52.5 KB
  У вікні що відкриється прочитати інформацію і клацнути на кнопці Далее; У наступному вікні буде відображено список програм і утиліт для вибору і запуску. Можна скористатися кнопкою Обзор для пошуку програми якої нема у списку; В наступному вікні...
55168. Переходная экономика: понятие, основные задачи и методы их реализации 22.64 KB
  Переходная экономика — экономика, осуществляющая переход из одного состояния в другое, в процессе которого происходит радикальное преобразование всей социально-экономической системы
55170. Особливості спілкування соціальних педагогів/працівників і клієнтів 60 KB
  МЕТА: Сформувати уявлення щодо структури професійного спілкування у соціальній роботі; зясувати механізми міжособистісного розуміння у професійнопедагогічному спілкуванні. Розкрийте зміст дефініції спілкування. Визначте мету і функції спілкування.
55171. Мовний етикет 42.5 KB
  Мовний етикет як соціальне і лінгвістичне явище. Мовленнєвий етикет, спілкувальний етикет. Стандартні етикетні ситуації. Парадигма мовних формул.