Теория автоматов и формальных языков

языки. Примеры языков. Грамматики. КА
Лекция 2. Теория конечных автоматов-распознавателей
Лекция 3. Трансляция автоматных языков
Лекция 4. Регулярные множества и регулярные выражения
Лекция 5. Язык MiLan и стековая машина
Порождающие грамматики Хомского – 3 л
Атрибутные трансляции и двусмысленные КС-грамматики – 2 л
Распознаватели КС-языков и трансляция – 6 л
Дополнительные лекции 2 л

программирования:
один тип данных – целые;
в программе нет описаний переменных;
программа начинается ключевым словом begin, заканчивается словом end;
управление процессом вычислений: Условный оператор и Цикл:
if <УСЛОВИЕ> then <ОПЕРАТОРЫ> else <ОПЕРАТОРЫ>;
if <УСЛОВИЕ> then <ОПЕРАТОРЫ>;
while <УСЛОВИЕ> do <ОПЕРАТОРЫ>;
условия в операторах if и while – два арифметических выражения, связанные знаками отношения >, <, =, !=, >=, <=
оператор ввода read вводит очередное целое число из входного потока; оператор x:=read присваивает введенное число переменной с именем x;
оператор вывода write(<ВЫРАЖЕНИЕ>) выводит на печать значение, полученное как результат вычисления арифметического выражения.

begin m:=read; n:=read; while m!=n do m:=1; if m>n then m:=m-read else n:=n-m; write(m)
end

Вопрос: почему begin, end, while, ... НЕ подчеркнуты???

операторов Условный и Цикл могут быть включены любое число операторов языка;
в языке НЕТ подпрограмм, методов, функций и процедур;
начальные значения переменных устанавливаются равными нулю.

Ю.Г.Карпов

Автоматы и формальные языки

begin m:=read; n:=read; while m!=n do if m>n then m:=m-read else n:=n-m; write(m)
end

Р0::

begin x:=read; ; if x>y2-3 then ;
write(x +2 *y)
end

Р1::

begin m:=34; n:=read *( m+2); while m!=3*n do
n:=m+ rea d; wri te(m – 2* n) end

Р2::

Как понимать программы P1, P2?

– программа на базовом языке MiLan

Базовый компилятор языка MiLan

Выход – программа для стековой машины

begin m:=read; n:=read; while m!=n do if m>n then m:=m-read else n:=n-m; write(m)
end

?

Виртуальный однопроцессорный компьютер с простой архитектурой. Содержит:
память данных (ПД) – линейная память, каждый регистр Памяти данных может хранить одно целое число;
память программ (ПП) - линейная память, каждый регистр Памяти программ может хранить одну команду (код операции и адрес);
стек – линейная память с доступом только к верхушке стека;
‘счетчик команд’ (СчК); в нем хранится адрес выполняемой команды;
регистр Команд - в нем хранится выполняемая команда (ОДНОАДРЕСНАЯ);
регистры А, В – в них помещаются данные при выполнении команд.

Память данных

Память программ

Стек

всегда один и тот же:
адрес очередной выполняемой команды находится в Счетчике Команд; перед выполнением программы он устанавливается в 0;
(1-й ШАГ) из Памяти Программ по адресу, находящемуся в СчК, выбирается код (КодОп и Адрес) и помещается в Регистр Команд;
(2-й ШАГ) содержимое Счетчика Команд увеличивается на 1 (готовимся к выполнению следующей команды);
(3-й ШАГ) поле КодОп Регистра Команд дешифрируется и соответствующая операция выполняется (например, Jump Addr реализуется так: Addr помещается в СчК).

COMPARE k

k=0? ‘=‘ k=1? ‘!=’ k=2? ‘<‘ k=3? ‘>’ k=4? ‘≤’ k=5? ‘≥’

Арифметика: ADD SUB MULT DIV

d

LOAD addr a LOAD addr b SUB LOAD addr d ADD

LOAD addr a

LOAD addr b

SUB

LOAD addr d

ADD

a – b + d – выполнение программы стековой машины:

Результат компиляции Ар. Выр:

последовательность команд, помещающих в верхушку стека результат вычисления арифметического выражения

Первый операнд операции находится в стеке ниже, чем второй

e

LOAD addr b LOAD addr d LOAD addr e MULT SUB STORE addr a

Результат компиляции оператора:

последовательность команд, реализующих вычисление арифм. выражения и присваивание результата

LOADaddr b

LOADaddr d

SUB

выполнение программы стековой машины:

LOAD addr e

MULT

Внимание! Здесь учтены приоритеты операций

e

z

STORE addr a

a:=b-d*e

После выполнения присваивания стек остается в том же состоянии, в котором он был до начала оператора

‘≠’ k=2? ‘<‘ k=3? ‘>’ k=4? ‘≤’ k=5? ‘≥’

q3 = ‘>’ 15 > 23 (?)

LOAD addr a

LOAD addr b

SUB

LOAD addr c

COMPARE 3

a - b > c выполнение программы стековой машины:

нет

LOAD addr a LOAD addr b SUB LOAD addr с COMPARE 3

a – b > c

Результат компиляции:

Результат: 0 или 1 помещается в верхушку стека

Значение 0 или 1 в верхушке стека может быть использовано следующей командой условного перехода

‘≠’ k=2? ‘<‘ k=3? ‘>’ k=4? ‘≤’ k=5? ‘≥’

q4 = ‘<=’ 15 <= 23 (?)

a - b ≤ c + d * f

LOAD addr a

LOAD addr b

SUB

LOAD addr c

LOAD addr d

LOAD addr f

MULT

COMPARE 4

LOAD addr a LOAD addr b SUB LOAD addr c LOAD addr d LOAD addr f MULT ADD COMPARE 4

ADD

a - b ≤ c + d * f – выполнение программы стековой машины:

Результат компиляции:

ДА!

на языке стековой машины (промежуточный язык).
Программа на языке стековой машины обычно затем интерпретируется. Такой интерпретатор пишется элементарно.

Ю.Г.Карпов

Автоматы и формальные языки

ЛА

Следующие фазы трансляции (СА)

Таблица имен

Поток лексем

Вход

Выход

Транслятор ЯВУ

Что внутри?

begin a := b – d * e; write ( a ) end

0: LOAD addr b 1: LOAD addr d 3: LOAD addr e 4: MULT 5: SUB 6: STORE addr a 7: STOP

Лексический анализатор

фазы трансляции (СА)

Таблица имен

Поток лексем

Вход

Выход

begin i0 ass read sc i1 ass read sc while c0 q1 i1 do if i0 q2 i1 then - лексемы

begin m13 := read ; alpha237 := read ; while 243 < > alpha237 do if m13 > a2 then ... символы ASCII

Вход ЛА – цепочка кодов символов клавиатуры:

Выход ЛА – цепочка лексем (во внутреннем представлении):

Таблица констант:

Транслятор ЯВУ

является автоматными.
Некоторые фрагменты языка описываются автоматами: имена, константы...

begin
/************* ПРОГРАММА вычисления НОД на Милане ****************/ m13 := read; /* переменная m13 читается из входного потока */ alpha237:=read; /* переменная alpha237 означает ширину */ while m13 <> alpha237 do if m13 >= alpha237 then m13 : = m13 - alpha237 else write(alpha237) ; alpha237:= alpha237 – m13;
end

Чем неудобна программа на входном языке МИЛАН?
Бессмысленны отдельные символы: например, е в словах begin, read.
Каждое служебное слово представляет единый ‘символ’.
Все имена с точки зрения синтаксиса – одно и то же, но имеют разную семантику (также неразличимы и все константы).
Очень трудно формально описать включение произвольного числа пробелов и комментариев в любое место программы.
Целые группы входных символов представляют одну лексему: ‘:=‘ , ‘>=‘ ... .

if m < 1 then max := 10 ;

Ю.Г.Карпов

if i0 q2 c0 then i1 := c1 ;

После лексического анализа – цепочка лексем:

ik – k-е имя

сk – k-я константа

qk – k-е отношение

называемый лексический анализ входной программы - предварительная обработка входного текста с выделением в нем структурно значимых единиц – лексем.
Лексемы – минимальные единицы языка, которые имеют смысл.
В естественном языке лексемами являются не буквы, а слова (словоформы), в языке программирования – не отдельные символы, а имена, служебные слова, константы, знак оператора присваивания из двух символов ‘:=’ и т.д.
На входе транслятора исходная программа for j : = 1 to max do x2[j] : = 10;
представлена в виде неструктурированного потока байтов в коде АSCII: 66 6F 72 20 6A 20 3A 3D 31 64 6F 20 6D 61 78 20 64 6F 0D 0A 09 20 20 20 78 32 5B 6A 5D 20 3A 3D 20 31 30 3B
Символы не имеют смысла, смысл имеют ЛЕКСЕМЫ – группы символов.
for j := 1 to max do x2 [ j ] := 10 ;
В этом фрагменте 14 лексем: служебные слова: for, to, do; 4 лексемы 3-х имен: j, max, x2; два вхождения лексемы присваивания := и т.д.

исходную программу как последовательность лексем (лексических единиц).
Лексемы и являются терминальными символами грамматики языка.

begin i0 ass read sc i1 ass read sс while i0 q1 i1 do if i0 q2 i1 then i0 ass i0 addop0 i1 … …

По цепочке (последовательности) байтов на входе лексический анализатор должен построить цепочку лексем:

begin
/******* ПРОГРАММА вычисления НОД на Милане *********/ m13 := read; // переменная m13 из входного потока alpha237:=read; /* alpha237 означает ширину */ while m13 <> alpha237 do if m13 > alpha237 then m13:= m13 + alpha237 ;

Каждая лексема имеет свой смысл, так же, как при трансляции естественного языка каждое слово имеет смысл (буквы смысла не имеют)

ass read sс while i0 q1 i1 do if i0 q2 i1 then i0 ass i0 addop1 i1 else i1 ass i1 addop1 i0 sc write lb i0 rb end

begin – служебное слово begin read – служебное слово read ... i0, i1, ... Имена переменных c номерами 0, 1, ... ass – assign (присваивание :=) sc – semicolon – точка с запятой ( ; ) q0, q1, q2, ... – отношения =, <>, >, <, ... addop0, addop1 – операция типа сложения (+ и -) ...

begin m:=read; n:= read; while m≠n do if m>n then m : = m-n else n:=n-m; write (m)
end

Программа вычисления НОД двух чисел
на языке MiLan:

Каждый студент в качестве части курсовой работы
строит лексический анализатор языка Милан.

Цепочка лексем программы

где можно вставлять пробелы?

где нужно вставлять пробелы?

основные вопросы ЛА

– перечислимый тип

в буфер
y2: это служебное слово? Если нет, то это имя. Проверить/добавить в таблице имен. Выдать соотв. лексему.

... ... ...

любой белый символ (таб., пробел, перевод строки, ...)

Таблица имен:

... ... ...

буфер

a l p h a 2 3 7

в буфер
y2: это служебное слово? Если нет, то это имя. Проверить/добавить в таблице имен. Выдать соотв. лексему.
y3: добавить в таблицу констант. Выдать лексему <22, k>
y4: Выдать лексему <23,0> (ass ‘:=‘)
y5: Выдать лексему <24,0> (semicolon – ‘;’ )
y6: Выдать лексему <25,0> ( ‘=‘ )
y7: Выдать лексему <25, 2> ( ‘≥’ )
y8: Выдать лексему <25,3> ( ‘>’ )
y9: Выдать лексему <25,5> ( ‘<’ )
y10: Выдать лексему <25,4> (‘≤‘)
y11: Выдать лексему <28,0> ( ‘(‘)
… … … …

... ... ...

любой белый символ (таб., пробел, перевод строки, ...)

какие ошибки может найти этот ЛА?

имен:

ЛА

Следующие фазы трансляции Синтаксический Анализ

Таблица имен Таблица констант

Поток лексем

Вход

Выход

begin i0 ass read sc i1 ass read sc while i1 q1 i1 do if i0 q2 i1 then - 19 лексем

Транслятор ЯВУ

begin m13 := read ; alpha237 := read ; while m13 < > alpha237 do if m13 > 237 then ... – ЛЮБАЯ цепочка из символов ASCII. В этой цепочке 120 символов ASCII.

Вход ЛА – цепочка кодов символов клавиатуры:

Выход – цепочка кодировок лексем (во внутреннем представлении):

Таблица констант:

в виде цепочек символов клавиатуры с пробелами. Что будет выдавать ЛА для каждой из них?
Какая расстановка дополнительных пробелов в программе Р0 приведет к обнаружению в ней ошибок лексическим анализатором?
Какая программа будет обработана ЛА, но в ней обнаружит ошибки синтаксический анализатор?
Вставьте (уберите) максимальное число пробелов в Р0 так, чтобы: а) не нарушить синтаксическую корректность Р0; б) нарушить синтаксическую корректность Р0.

Ю.Г.Карпов

Автоматы и формальные языки

begin m:=read; n:=read; while m!=n do if m>n then m:=m-n else n:=n-m; write(m)
end

Р0::

любой входной цепочке символов ASCII построить результирующую цепочку лексем языка Милан.
САМОСТОЯТЕЛЬНО: построить ПОЛНЫЙ лексический анализатор языка Паскаль

Ю.Г.Карпов

Автоматы и формальные языки

имен:

ЛА

Следующие проходы транслятора

Таблица имен Табл. констант

Поток лексем

Вход

Выход

Транслятор ЯВУ

Вход следующей фазы трансляции – цепочка кодировок лексем. Выход – программа СТЕКОВОЙ МАШИНЫ

Таблица констант:

под переменные отводим первые адреса Памяти Данных под константы – следующие адреса ПД

программа на языке Милан

программа в командах стековой машины

языки

лексемы служебных слов;
ik – лексема имя с номером k в Таблице Имен, в стековой машине ей отводим адрес k Памяти Данных (ПД);
ck – лексема константы с номером k в Таблице Конст, ей отводим адрес Ni +k ПД; (Ni – число имен в программе)
qk – лексема ‘отношение’ с номером k;
addopk – лексема операции ‘+’ при k=0, ‘-’ при k=1;
multopk - лексема операции ‘*’ при k=0, ‘/’ при k=1;
ass – лексема знака ‘присвоить’ ‘:=’.

Ю.Г.Карпов

Автоматы и формальные языки

begin
m:=read; n:=read;
while m!=n+33 do
if m>n then m:=m-2;
write(n+142)
end

исходная программа:

результат лексического анализа:

begin i0 ass read sc i1 ass read sc
while i0 q1 i1 addop0 c0 do if i0 q3 i1 then i0 ass i0 addop1 c1 sc
write ( c1 addop0 c2 ) end

k=0? ‘=‘ k=1? ‘!=’ k=2? ‘<‘ k=3? ‘>’ k=4? ‘≤’ k=5? ‘≥’

qk – лексема ‘отношение’

имен:

ЛА

Следующие проходы транслятора

Таблица имен Таблица констант

Поток лексем

Вход

Выход

Транслятор ЯВУ

Вход следующей фазы трансляции – цепочка кодировок лексем. Выход – программа СТЕКОВОЙ МАШИНЫ

Таблица констант:

Язык MiLan представлен, стековая машина описана, что должны получить на выходе транслятора - знаем.

Как строить следующие фазы трансляции?

программа на языке Милан

программа в командах стековой машины

while m!= n+33 do if m>n then m:=m-2; write(n+142) end

исх. программа:

Таблица имен:

Таблица констант:

программа на языке стековой машины

0: INPUT
1: STORE 0
2: INPUT
3: STORE 1
4: LOAD 0
5: LOAD 1
6: LOAD 2
7: ADD
8: COMPARE 1
9: JUMP_NO 23
10: LOAD 0
11: LOAD 1
12: COMPARE 3
13: JUMP_NO 18
14: LOAD 0
15: LOAD 3
16: SUB
17: STORE 0
18: LOAD 1
19: LOAD 4
20: ADD
21: PRINT
22: JUMP 4
23: STOP

адреса переменных 0 и 1,
адреса констант – 2, 3 и 4

ввод m
ввод n
начало цикла
m != n + 33 ?
1 – сравнение по != (не равно)
если нет, то выход из цикла
начало оператора if-then
3 – сравнение m > n ?
если нет, то на write
часть then оператора if-then
m:=m-2
write (n + 142)
последний оператор цикла
возврат на начало цикла
выход из программы в ОС

такое язык Милан?
Нужно ли ставить ‘;’ после оператора write?
Можно ли НЕ ставить?
Как строить условия для цикла и условного оператора?

Ю.Г.Карпов

Автоматы и формальные языки

begin m:=read; n:=read; while m! = n do if m >n then m:=m-n else n:= n-m; write(m);
end

Р::

Как задать язык Милан?
Полностью язык Милан можно задать только ГРАММАТИКОЙ. Но язык Милан НЕ автоматный, конечным автоматом его задать нельзя.
Нужна другая грамматика

программе оператор while включает write ИЛИ нет?
Оператор if-then включает write ИЛИ нет??
Когда выполнять write – внутри цикла, внутри if??

Ю.Г.Карпов

Автоматы и формальные языки

begin
m:=read; n:=read;
while m!=n+33 do
if m>n then m:=m-2;
write(n+142*m)
end

Как задать язык MiLan формально?

Какие другие виды грамматик существуют?
Как задать сложную семантику (например, для оператора цикла или для арифметических выражений)?

Язык MiLan НЕ ЗАДАН ФОРМАЛЬНО!

НЕТ!

Нужна другая грамматика, более мощная, чем автоматная

формальных языков и грамматик.
Но мы уже многое умеем!

языка можно описать (например, КА) и для каждой задать семантику (какую функцию вызывать, если распознана эта лексема – например, обратиться к таблице служебных слов и искать там, если нет, то ... ).

Настраиваемый лексический анализатор можно построить как доп вариант КР.

Вход – цепочка символов; выход – цепочка лексем

Семантика: что делать с куском текста, представляющим конкретную лексему (код на С++)

input;
x1 := -23;
x2 := x1*56;
print (x1, ++x0)
end

Для самостоятельной проработки

Варианты расширения языка:
разные типы (int, real) и операции;
логические переменные и операторы
условное присваивание;
логические переменные и операции;
инкремент и декремент;
комментарии;
не только десятичные числа;
...

1. Построить транслятор этого языка
2. В качестве дополнительного варианта можно использовать бестиповые переменные: переменная считается объявленной при первом использовании, тип переменной определяется типом присвоенного выражения. Инициализированной переменной можно присваивать значения типов, отличающихся от первоначально присвоенного

В выражении не больше одной операции

вычисления
f:= a – b * 25 + d
должны написать программу:
##
х := b * 25;
y := a – x;
z := y + d;
f := z
##

у1: Gen: ; C++

у2: Gen: ; C++

у3: Gen: ; C++

у4: Gen: ; C++

Этот язык – автоматный!

С – счетчик сгенерированных команд стековой машины. Вначале он 0.

Семантики:

алгоритма обработки данных с помощью графа переходов конечного автомата (либо в виде стейтчартов - карт состояний) в программу на языке Java, либо С, либо Паскаль, ...

Ю.Г.Карпов

Автоматы и формальные языки

Вход: стейтчарт или граф переходов конечного автомата

Выход: программа, имитирующая динамику работы автомата

из описания BDD в программу вычисления значений логической функции

BDD:: f={<5, x1, 3, 4>; <4, x2, 3, 1>; <3, x3, 2, 1>; <2, x4, 0, 1>}

v5: if(x1 == 0) goto v3; else goto v4;
v4: if(x2 == 0) goto v1; else goto v4;
v3: if(x3 == 0) goto v2; else goto v1;
v2: if(x4 == 0) goto v0; else goto v1;
v1: return (1);
v0: return (0);

Эквивалентная программа

⇒

Использовать текстовое представление BDD:

3, 2>; <2, x2, 3, 1>; <3, x3, 4, 1>; <4, x4, 0, 1>}

BDD::

при заданных значениях аргументов

BDD:: f= {<5, x1, 3, 2>; <2, x2, 3, 1>; <3, x3, 4, 1>; <4, x4, 0, 1>}

Целое(k):: ...

Имя (a):: ...

Семантика – всего две семантических функции (кроме Целого и Имени) генерации текстов: у1: Ген( ‘ v_k: if(x == 0 goto v_i; else goto v_j; ’ )
y2: Ген( ‘ v_1: return (1); ’ ); Ген( ‘v_0: return (0); ’ )

v5: if(x1 == 0) goto v3; else goto v4;
v4: if(x2 == 0) goto v1; else goto v4;
v3: if(x3 == 0) goto v2; else goto v1;
v2: if(x4 == 0) goto v0; else goto v1;
v1: return (1);
v0: return (0);

машины, подсчитывающую значение формулы при заданных значениях переменных.
Можно использовать пакет Buddy для построения BDD по исходной формуле.

Ю.Г.Карпов

Автоматы и формальные языки

3 уравнений:
-3.56 X[1] + 13.0 X[3] = 0.342;
0.236 X[2] + 223.8 X[3] = -233.3;
8.12 X[1] - 6.6 X[2] = 5.1
методом Гаусса.

Как задать все возможные программы?
Как описать все возможные системы уравнений?

Грамматикой!

...

как построить грамматику, задающую все возможные правильные тексты такого вида?

Решить систему 3 уравнений:
-3.56 X[1] + 13.0 X[3] = 0.342;
0.236 X[2] + 223.8 X[3] = -233.3;
8.12 X[1] - 6.6 X[2] = 5.1
методом Гаусса.

...

Целое:: ...

Распознаватель строится однозначно по синтаксическим диаграммам не всегда!
Только тогда, когда выбор в каждом разветвлении синтаксической диаграммы однозначен

Решить систему 3 уравнений:
-3.56 X[1] + 13.0 X[3] = 0.342;
0.236 X[2] + 223.8 X[3] = -233.3;
8.12 X[1] - 6.6 X[2] = 5.1
методом Гаусса.

3 уравнений:
-3.56 X[1] + 13.0 X[3] = 0.342;
0.236 X[2] + 223.8 X[3] = -233.3;
8.12 X[1] - 6.6 X[2] = 5.1
методом Гаусса.

Какие ошибки выявит распознаватель?

int Ук:=0;
void main( ) { if( s[ Yk ] <> ‘Решить систему’) then Ош(1) ; else Yk +=16; Целое( ); if( s[ Yk ] <> ‘уравнений:’) then Ош(2) ; else Yk +=10; Система( ); ... };
void Система( ) { m: Уравнение( ); if( s[Ук] == ‘;’) then { Ук++; goto m } else skip };
void Уравнение( ) { m: Число( ); if( s[Ук] == ‘X’) then Ук++; else Ош3( ); ); if( s[Ук] == ‘[’) then Ук++; else Ош4( ); ; void Целое( ); if( s[Ук] == ‘]’) then Ук++; else Ош5( ); if( s[Ук] <> ‘=’) goto m; else {Ук++; Число() } };

3 уравнений:
-3.56 X[1]+13.0 X[3]= 0.342;
0.236X[2]+223.8 X[3]= -23.3;
8.12 X[1] - 6.6 X[2] = 5.1
методом Гаусса.

main::

Уравнение(i)::

Число(r):: ...

Целое(n) :: ...

y1: Объявить матрицы А[N,N] =0, B[N] и Х[N];

y2: k:=1;

y3: k++;

y4: A[i,j] := a;

y5: B[i] := b;

y6: ГАУСС(А, В, N, X, E); (Е – тип ошибки)

y7: НЬЮТОН(А, В, N, X, E);

y8: Вывод результата Х, если Е=0; Вывод причины ошибки i, если Е=i≠0;

Какие проверки можно сделать??

коэффициентов

-3.56 a[1] + 15.0 a[4];
0.26 a[2]+ 25.6 a[3]-3.5 a[4];
13.36 a[2] +28.8 a[4];
15.2 a[1]+23.88 a[3];

Вход – разреженная матрица:

Выход – списочная структура

Для самостоятельной проработки

1

2

4

3

1

4

3

2

– 5 + 6 = // одноприоритетные операции
32 + 2 * 13 * 4 - 5÷2 = // операции двух разных приоритетов
2*(3-1*4)+(5) = // скобки (вложенные скобки не допускаются)
Реализовать калькулятор смартфона SAMSUNG GALAXY NOTE 5 (или какого-нибудь другого смартфона)

Ю.Г.Карпов

Автоматы и формальные языки

но и для трансляции языков. Для этого на переходах распознающего КА выполняются семантические действия
Схему распознавателей и трансляторов автоматных языков удобно представлять с помощью синтаксической диаграммы
Синтаксические диаграммы для сложного автоматного языка удобно строить иерархически, выделяя конструкции языка, и строя синтаксическую диаграмму, задающую каждую конструкцию
Для трансляции в любое место синтаксической диаграммы может быть помещено семантическое действие
Для реализации транслятора для каждой конструкции языка по ее синтаксической диаграмме строится своя распознающая процедура. Такая процедура может быть построена по синтаксической диаграмме, которая соответствует детерминированному конечному автомату
С помощью этого подхода можно строить трансляторы довольно сложных языков. Большинство скриптовых языков - автоматные

смысл. Лексемами являются имена, константы, символы, представляемые группами (например, ‘+=‘, ‘++’, ‘:=‘ и т.д.)
Лексический анализатор выбрасывает комментарии, ‘белые’ символы, и т.п., строит лексемы из нескольких символов (например, служебные слова), представляя программу во внутреннем виде как последовательность лексем (терминальных символов грамматики)
Лексический анализ выполняется с помощью алгоритма, реализующего функционирование конечного автомата, поскольку лексемы – это автоматные языки

Э. Хоаром и Э.Дейкстрой)
Разработал языки Паскаль, Модула, Оберон, Ада, …
Разработал пи-код (код витруальной стековой машины)
Придумал синтаксические диаграммы и использовал их для формального описания синтаксиса языка Паскаль
Награды:
Премия Тьюринга (1984)
ACM Award for Outstanding Contributions to Computer Science Education
ACM Outstanding Research Award in Software Engineering (1999)
…

Ю.Г.Карпов

Автоматы и формальные языки

Никлаус Вирт (р.1934) – швейцарский ученый, внесший огромный вклад в теорию и технологию программирования