Лексикален анализ Програмиране, уроци и примери

Programm.ws е сайт, където можете да четете литература за езици за програмиране, както и да видите примери за работещи програми в C ++, асемблер, pascal и много други.

Програмирането - в обичайния смисъл е процесът на създаване на компютърни програми.
В тесния смисъл (т. Нар. Кодиране) под програмиране се разбира писане на инструкции - програми - на определен програмен език (често според вече съществуващ алгоритъм - план, метод за решаване на даден проблем). Съответно хората, които правят това, се наричат ​​програмисти (на професионален жаргон, кодери), а тези, които разработват алгоритми, се наричат ​​алгоритми, специалисти по темата, математици.
В по-широк смисъл под програмиране се разбира цялата гама от дейности, свързани със създаването и поддръжката на програми - компютърен софтуер. По-точен е съвременният термин - „софтуерно инженерство“ (също иначе „софтуерно инженерство“). Това включва анализ и задаване на проблем, проектиране на програма, изграждане на алгоритми, разработване на структури от данни, писане на текстове на програми, отстраняване на грешки и тестване на програма (тестване на програма), документиране, настройка (конфигуриране), преразглеждане и поддържане.

Глава 2. Сложни структури от данни

Лексикален анализ

Целта на лексикалния анализ е да подчертае и класифицира лексеми в текста на изходната програма. Програмата, която извършва лексикален анализ, се нарича скенер или лексикален анализатор. Скенерът чете файла с изходния код на програмата символ по знак.
Пълният набор от лексеми на даден език се определя от набора от терминални символи в неговата граматика. Сред тях са изменяеми и неизменяеми жетони. Неизменяемите жетони се пишат еднакво във всяка програма. За грам-
псевдоезичните матрици са такива символи като: PROGRAM, VARIABLES, START_PROG, CON_ PROG, START_BLOCK, CON_BLOCK, ".", ";", ":", "/", REAL, INTBYTE, INT_WORD, INTDWORD, ",", ": = "," = "," + "," - "," * ", DIV, MOD," (",") "," [","] "," "," == ", ПРОЧЕТЕТЕ, ПИШЕТЕ, ЗА, ЗАВЪРШЕТЕ, ДОКАТО, НАГОРЕ, АКО, АКО, ПРЕДИ, СЛЕД, GO_TO, ПОВТОРЕТЕ. Три терминални символа са оставени „зад борда“ - ID, CH_INT, CH_REAL. Тези терминални символи съответстват на идентификатори, цели числа и реални числа. Естествено, дори в рамките на една и съща програма, те ще бъдат различни. Задачата на скенера е именно да разпознава изменяеми и неизменяеми терминални символи. От гледна точка на логиката на обработка от скенера е удобно всички терминални символи да се класифицират като един от следните класове (по отношение на нашата псевдоезикова граматика):

  • идентификатори - ID;
  • ключови думи - PROGRAM, VARIABLES, NACHPROG, CON_PROG, NACHBLOCK, CON_ BLOCK, REAL, INTJYTE, INTWORD, INT_DWORD, DIV, MOD, READ, WRITE, FOR, ADD, WHILE, DOWN, IF, IF, PRE, THEN, GO REPEAT;
  • цели числа - CHINT;
  • реални числа - CH_REAL;
  • еднобуквени разделители - ".", ",", ";", ":," + "," - "," * ","/"," (",") "," = "," [ ","] "," ";

В двубуквени разделители - ": =", "=", "> =", "=

Таблицата на класовете на символи се използва само в процеса на сканиране и има за цел да открие класа на символите, когато е избран от скенера от входния поток. Най-добре е тази таблица да се организира под формата на масив, чиито елементи са отразени в използваната кодова таблица (например ASCII таблица). Значението на всеки елемент в таблицата с класове знаци се определя от класа знаци в кодовата таблица. Като цяло могат да бъдат дефинирани следните класове знаци:

  • d - цифра;
  • 1 - писмо;
  • b - символи, които се пренебрегват, те могат да включват например интервал;
  • s1 - единични разделители: ".", ":", "(", ")", "*";
  • s2 - специални единични разделители: ".", "+", "-", ":", "=", ".

Последните разделители се различават по това, че всъщност могат да бъдат или единични разделители, или да бъдат включени в лексемата букви, състояща се от няколко букви. Например разделителят ":" е не само единичен знак, но и първият знак на двубуквения разделител ": =", а буквите ".", "+" И "-" са част от лексемата "реално число".
Броят на изходните таблици може да бъде различен и се определя от сложността на езика за въвеждане. Като минимум се използват две или три таблици: лексикална сгъваема таблица, идентификационна таблица и евентуално постоянна таблица. Да разгледаме пример за псевдоезична програма:

ПРОГРАМА progl (1M14, #progl) ПРОМЕНЛИВИ (2)
INTBYTE 1 (6) (14. #i)
START_PROG (26)
FOR i: = ON TO 9 DO (10Н14, #i) (24) (15. 0) (13) (15. 9Н11) WRITE (i) (9) (12) (14, #i) (25)
КОНПРОГ (27)

  • уникален номер - номерът, който на следващите етапи на излъчването
    ще идентифицира даденото символично име;
  • указател към списък, съдържащ идентификационни знаци;
  • указател към списък с номера на редове, където е намерен даден идентификатор.

По-късно, когато имената на идентификатори не са необходими, можете да изградите хеш таблица въз основа на това дърво, достъпът до елементите на който ще се основава на уникални числа. Между другото, за да увеличите ефектите-
Всички терминални символи - езикови ключови думи, разделители и т.н. (с изключение на id, chint и ch_rea1) - също трябва да бъдат намалени до отделно лексикографско дърво или организирана хеш таблица.
Можете да го направите по различен начин. Тази вариация, която може да се използва за синтактичен анализ на входа в командния ред и т.н., работи, когато скенерът се извиква от анализатор. Същността му е, че скенерът се извиква от анализатора, когато последният се нуждае от друг маркер. Скенерът го извлича във входния поток и дава на анализатора набор от два елемента: кода на символа и низ, съдържащ самия маркер.
Как да организирам процеса на разпознаване на входни програмни лексеми? За целта ще се опитаме да формулираме обобщен алгоритъм за конструиране на скенер.

  1. 1. Изберете класове жетони.
    2. Определете класове букви.
    3. Определете условията за излизане от скенера за всеки клас токени.
    4. За всеки клас лексеми съответствайте на граматиката от клас 3.
    5. За всяка граматика, изградена в стъпка 4, изградете машина с краен щат, която ще разпознае лексемата от този клас.
    6. Извършете обединение ("залепване") на крайни автомати за всички класове жетони.
    7. Създайте преходна матрица за "залепената" машина на крайно състояние.
    8. "Закачете" семантика върху дъгите на "залепената" машина на крайния автомат.
    9. Изберете лексикални сгъваеми кодове за граматични терминали и формат на таблицата с идентификатори.
    10. Разработете програма за скенер.

Няма да приложим напълно този алгоритъм за скенера на преводача на опростения език Pascal. Това не е предмет на нашата книга. Ние се интересуваме преди всичко от организацията на данни и възможностите за работа с тях в асемблер. Следователно, за да изясним подхода към подобни проблеми, ще се съсредоточим върху стъпки 1-8 от горния алгоритъм.