29376

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

Доклад

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

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

Английский

2013-08-21

95.5 KB

0 чел.

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

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

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

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

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

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

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



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

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


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

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

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


 

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

62441. Моделирование и изготовление формы 1.2 MB
  Поверхность может иметь покрытие глазурью ценинный изразец не иметь покрытия терракотовый изразец. Недаром само слово изразец это то что вырезано обработано.
62443. КУЛЬТУРА ЗАПАДНОЙ ЕВРОПЫ В РАННЕЕ СРЕДНЕВЕКОВЬЕ 20.44 KB
  Ознакомить с искусством рукописной книги в частности книжной миниатюры. Влияние христианства на развитие культуры в области литературы образования искусства рукописной книги. Карл I и его семья придворные в Аахене образовали такой кружок где читали и обсуждали церковные книги...
62444. Виды треугольников. Углы равнобедренного треугольника 25.06 KB
  опросы для проверки устно: Какой треугольник называется прямоугольным Какой треугольник называется равнобедренным А какой равносторонним Как называются стороны прямоугольного треугольника Какие стороны равнобедренного треугольника называются боковыми...
62445. СОЦИАЛЬНЫЕ НОРМЫ. СОЦИАЛЬНЫЙ КОНТРОЛЬ 18.57 KB
  Социальные нормы определяют границы допустимого поведения людей применительно к конкретным условиям их жизнедеятельности. превосходства; 3 моральные обеспечиваются авторитетом общественного мнения; 4 корпоративные нормы или нормы общественных объединении...
62446. Ангобирование 1017.39 KB
  Цветными ангобами расписывают изделия имеющие самое разнообразное назначение: посуду подсвечники броши кулоны бусы и многое другое. Нанесение ангоба Цветные ангобы наносят на поверхность изделия кистью рожком воронкой резиновой грушей пластмассовым пузырьком и пипеткой.
62448. Present Continuous Tense. Future Simple Tense. Оборот to be going to + глагол 37.07 KB
  Употребление настоящего продолженного времени (Present Continuous Tense) для обозначения действия в будущем Оборот to be going to + глагол Будущее простое время (Future Simple Tense) Количественные слова a lot (of), many, much, little, a little, few, a few...
62449. Внутреннее строение листа 19.04 KB
  Цель урока: Продолжить изучение листа в связи с выполняемыми функциями и приспособленностью растений и родным условием среды. Образовательная задача: Познакомить учащихся с особенностями клеточного строения листа в связи с его функциями обеспечить закрепление биологических понятий...