29376

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

Доклад

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

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

Английский

2013-08-21

95.5 KB

0 чел.

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

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

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

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

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

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

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



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

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


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

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

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


 

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

18944. Межкультурная коммуникация 43 KB
  Межкультурная коммуникация МЕЖКУЛЬТУРНАЯ КОММУНИКАЦИЯ У каждой культуры своя логика свое представление о мире. То что значимо в одной культуре может быть несущественным в другой. Поэтому важно всегда с уважением смотреть на своего партнера с иной культурой. Он де
18945. Коммуникации в организациях: виды и формы 81.5 KB
  Коммуникации в организациях: виды и формы Действенным средством повышения эффективности работы фирм и даже отдельным направление в ПР является работа с внутренней общественностью представленной служащими организации. Это часть организации человеческий ресурс ф
18946. Роль ПР-специалиста в разрешении конфликтов в группах и организациях 34 KB
  Роль ПРспециалиста в разрешении конфликтов в группах и организациях Специалист по связям с общественностью должен играть ключевую роль в антиконфликтном и антикризисном управлении. Занимаясь управлением конфликтами и кризисами специалист по PR имеет дело собствен
18947. Межличностные конфликты. Специфика проявления 41.5 KB
  Межличностные конфликты. Специфика проявления МК Емельянов – противоборство двух людей на основе столкновения противоположно направленных мотивов. МК Гришина – ситуация противоречий разногласий столкновений между людьми. Он может быть определен как ситуация п...
18948. Коммуникационный менеджмент как процесс 49.5 KB
  Коммуникационный менеджмент как процесс Компании всегда занимались коммуникацией – выстраивали вокруг и внутри систему взаимодействий призванную помогать бизнесу в достижении его стратегических и текущих целей. Успехи организации зависят от конструктивности вз...
18949. Организация и проведение избирательной кампании: стратегический замысел, цели и масштаб работы с избирательными территориями 200.5 KB
  Организация и проведение избирательной кампании: стратегический замысел цели и масштаб работы с избирательными территориями Избирательная кампания это те же самые скоординированные целенаправленные но осуществляемые в течение отделенного законодательством в
18950. Телевизионная журналистика: особенности, виды, способы финансирования 88.5 KB
  Телевизионная журналистика: особенности виды способы финансирования Телевидение – одно из самых глобальных достижений человечества. Оно отбирает у своих поклонников не только способность мыслить но и способность сопротивляться воздействию: яркая движущаяся кар
18951. Радиожурналистика. Свойства и формат радио как вида массовой коммуникации 37 KB
  Радиожурналистика. Свойства и формат радио как вида массовой коммуникации Радио появилось именно в то время когда человечество стало нуждаться в предельной оперативности информации: глобальные потрясения изменившиеся в начале столетия административный ментальны...
18952. Конспекты занятий по экологии для старшей группы 199.5 KB
  Способствовать развитию у детей умения составлять сравнительные рассказы о растительном мире; развитию умения различать растения по стволам, веткам, плодам, листьям; различению многолетних и однолетних растений; развитию сравнения по признакам, закрепленным в модели, умения использовать модель в качестве плана рассказа; воспитывать бережное отношение к растительному миру.