Контрольная. Теория трансляции.

Вариант 3
(ПАСКАЛЬ) Анализаторы языка, включающего оператор условной передачи управления и оператор присваивания, арифметических выражений и языка право-линейной грамматики
1 Распознаватель описания функций форматного ввода-вывода. Например:
Const A563 :array[1..3,-5..-4] of integer = ((-2,-5),(23,0),(34,12));
2 Провести синтаксический анализ арифметических выражений, переведя его после этого в язык ПОЛИЗ. Реализовать вычисления, используя запись в языке ПОЛИЗ, присвоив переменным фиксированные целые положительные значения.
а:=-корень(b*b-4*b+4)
3 Для право-линейной грамматики создать автомат анализатор, детерминируя исходный автомат грамматики, если продукции грамматики имеют вид:
S—>bА|bВ|bE
А—>аS
B—> bE|aC
С—>b
...

Вариант 3
(ПАСКАЛЬ) Анализаторы языка, включающего оператор условной передачи управления и оператор присваивания, арифметических выражений и языка право-линейной грамматики
1 Распознаватель описания функций форматного ввода-вывода. Например:
Const A563 :array[1..3,-5..-4] of integer = ((-2,-5),(23,0),(34,12));
2 Провести синтаксический анализ арифметических выражений, переведя его после этого в язык ПОЛИЗ. Реализовать вычисления, используя запись в языке ПОЛИЗ, присвоив переменным фиксированные целые положительные значения.
а:=-корень(b*b-4*b+4)
3 Для право-линейной грамматики создать автомат анализатор, детерминируя исходный автомат грамматики, если продукции грамматики имеют вид:
S—>bА|bВ|bE
А—>аS
B—> bE|aC
С—>b

Вариант 3
(ПАСКАЛЬ) Анализаторы языка, включающего оператор условной передачи управления и оператор присваивания, арифметических выражений и языка право-линейной грамматики
1 Распознаватель описания функций форматного ввода-вывода. Например:
Const A563 :array[1..3,-5..-4] of integer = ((-2,-5),(23,0),(34,12));
2 Провести синтаксический анализ арифметических выражений, переведя его после этого в язык ПОЛИЗ. Реализовать вычисления, используя запись в языке ПОЛИЗ, присвоив переменным фиксированные целые положительные значения.
а:=-корень(b*b-4*b+4)
3 Для право-линейной грамматики создать автомат анализатор, детерминируя исходный автомат грамматики, если продукции грамматики имеют вид:
S—>bА|bВ|bE
А—>аS
B—> bE|aC
С—>b

3 Идентификаторы1A563Табл. 4 Константы11233-54-45-262370834912Таблицы 1 и 2 хранятся в памяти компьютера и создаются предварительно.Таблицы являются словарями, в которых каждое слово или знак имеет свой номер. По номеру слова и номеру таблицы создаются пара лексем – представителей вида: (i;j), где i – номер таблицы и j – номер рассматриваемого слова в словаре этой таблицы.Лексемы – представители для идентификаторов и констант создаются в процессе лексического анализа текста программы.Лексический анализ программы осуществляется с помощью автомата, который называется лексическим автоматом. Схема лексического автомата представлена на рис. 1.1 . Текст «паскалеобразной» программы: Const A563 :array[1..3,-5..-4] of integer = ((-2,-5),(23,0),(34,12));Транслирование текста паскаль программы в тексте лексем – представителей, согласно лексическому анализатору, представленному на рисунке 1.1.Транслирование текста (1,1) (3,1) (2,1) (1,2) (2,2) (4,1) (2,3) (4,2) (2,4) (4,3) (2,3) (4,4) (2,5) (1,3) (1,4) (2,6) (2,7) (2,7) (4,5) (2,4) (4,3) (2,8) (2,4) (2,7) (4,6) (2,4) (4,7) (2,8) (2,4) (2,7) (4,8) (2,4) (4,9) (2,8) (2,8) (2,9)Рис. 1.1. Лексический автомат.Часть 2. Провестисинтаксический анализ арифметических выражений, переведя его после этого в язык ПОЛИЗ. Реализовать вычисления, используя запись в языке ПОЛИЗ, присвоив переменным фиксированные целые положительные значения.а:=-корень(b*b-4*b+4)Проводим редукцию. Заменяем все переменные на одну букву, например букву "a". Получим a:= - корень(b*b-4*b+4)→ a:=- √(a*a- a * a +a)G= (T,N,S,P) Т= <S,B,V,C,Q,Y,M>ПродукцияS→ aRR→ := VV→ QC | - QC | + QCC→ ε | + QC | - QCY→ ε | *МY | /МY | ↑МYQ→ МYM→ a | (V) | √(V)Начало с аксиомы S. Далее, если есть совпадение слева по одному знаку в правой и продукции, то «переход» по этой продукции, иначе переход по продукции с пустым словом.S1aR2a≔V3бa≔-QC6a≔-MYC7вa≔- VYC3а 3аa≔- QCYC5 a≔- MYCYC7аa≔- aYCYC6б6бa≔- a*MYCYC7а a≔- a*aYCYC6аa≔- a*aCYC4вa4в∶=- a*a-QCYC5a≔- a*a-MYCYC7a7aa≔- a*a-aYCYC6бa≔- a*a-a*MYCYC7а7aa≔- a*a-a*aYCYC5аa≔- a*a-a*aCYC4б4бa≔- a*a-a*a+QCYC6 a≔- a*a-a*a+MYCYC7a7aa≔- a*a-a*a+aYCYC5aa≔- a*a-a*a+aCYC4a 4aa≔- a*a-a*a+aYC5aa≔- a*a-a*a+aC4a5aa≔- a*a-a*a+aСравнение:a≔- a*a-a*a+a=a≔- √(a*a- a * a +a)– верно.После синтаксического анализа арифметического выражения производится его генерация в язык ПОЛИЗ. Табл. 2. Генерации детерминированных автоматов.