Основы теории языков и формальных грамматик Содержание темы Способы определения языков. Формальные грамматики. Грамматики с ограничениями на правила. Способы. - презентация

1 Основы теории языков и формальных грамматик Содержание темы Способы определения языков. Формальные грамматики. Грамматики с ограничениями на правила. Способы записи синтаксиса языка. Распознаватели. 1Трансляторы

2 Два основных способа определения языков: механизм порождения или генератор; механизм распознавания или распознаватель. Они тесно связаны. Первый обычно используется для описания языков, а второй для их реализации. Оба способа позволяют описать языки конечным образом, несмотря на бесконечное число порождаемых ими цепочек. Неформально язык L - это множество цепочек конечной длины в алфавите T. 2Трансляторы

3 Механизм порождения позволяет описать языки с помощью системы правил, называемой грамматикой. Цепочки (предложения) языка строятся в соответствии с этими правилами. Достоинство определения языка с помощью грамматик в том, что операции, производимые в ходе синтаксического анализа и перевода можно делать проще, если воспользоваться структурой, предписываемой цепочкам с помощью этих грамматик. Механизм распознавания использует алгоритм, который для произвольной входной цепочки остановится и ответит " да " после конечного числа шагов, если эта цепочка принадлежит языку. Если цепочка не принадлежит языку, алгоритм ответит " нет ". Распознаватели используются непосредственно при построении синтаксических анализаторов и являются как бы их формальной моделью. Строятся на основе теорий конечных автоматов и автоматов с магазинной памятью. 3Трансляторы

4 Формальные грамматики Грамматикой называется четверка G = (N, T, P, S), где N -конечное множество нетерминальных символов (нетерминалов), T -множество терминалов (не пересекающихся с N ), S -символ из N, называемый начальным, Р -конечное подмножество множества: (N T) * N (N T) * x (N T) *, называемое множеством правил. Множество правил Р описывает процесс порождения цепочек языка. Элемент p i = (, ) множества Р называется правилом (продукцией) и записывается в виде. Здесь и - цепочки, состоящие из терминалов и нетерминалов. Данная запись может читаться одним из следующих способов: цепочка порождает цепочку ; из цепочки выводится цепочка. 4Трансляторы

5 Таким образом, правило P имеет две части: левую, определяемую, и правую, подставляемую. То есть правило p i - это двойка ( p i1, p i2 ), где p i1 = (N T) N * (N T) * - цепочка, содержащая хотя бы один нетерминал, p i2 = (N T) * - произвольная, возможно пустая цепочка ( - цепочка). Если цепочка содержит p i1, то, в соответствии с правилом p i, можно образовать новую цепочку заменив одно вхождение p i1 на p i2. Говорят также, что цепочка выводится из в данной грамматике. 5Трансляторы

6 Простой метаязык терминалы обозначим буквами a, b, c, d или цифрами 0, 1,..., 9; нетерминалы будем обозначать буквами A, B, C, D, S (причем нетерминал S - начальный символ грамматики); буквы U, V,..., Z используем для обозначения отдельных терминалов или нетерминалов; через,,... обозначим цепочки терминалов и нетерминалов; u, v, w, x, y, z - цепочки терминалов; для обозначения пустой цепочки (не содержащей ни одного символа) будем использовать знак ; знак будет отделять левую часть правила от правой и читаться как порождает или есть по определению. Например, A cd, читается как A порождает cd. 6Трансляторы

7 Метаязык - язык, предназначенный для описания другого языка Пример грамматики G1: G1 = ({A, S}, {0, 1}, P, S), где P: 1. S 0A1; 2. 0A 00A1; 3. A. 7Трансляторы

8 Выводимая цепочка грамматики G, не содержащая нетерминалов, называется терминальной цепочкой, порождаемой грамматикой G. Язык L(G), порождаемый грамматикой G, - это множество терминальных цепочек, порождаемых грамматикой G. 8Трансляторы

9 Введем отношение G непосредственного вывода на множестве (N T) *, которое будем записывать следующим образом: G. Данная запись читается: непосредственно выводима из для грамматики G = (N, T, P, S) и означает: если - цепочка из множества (N T) * и - правило из Р, то G. 9Трансляторы

10 Через G + обозначим транзитивное замыкание (нетривиальный вывод за один и более шагов). Тогда G + читается как: выводима из нетривиальным образом. Через G * обозначим рефлексивное и транзитивное замыкание (вывод за ноль и более шагов). Тогда G * означает: выводима из. Пусть k – k-я степень отношения То есть, если k, то существует последовательность k из k+1 цепочек = 0, 1,... i -1 i,1 i k и k =. 10Трансляторы

11 Пример выводов для грамматики G1 S 0A1 00A ; S 1 0A1; S 2 00A11; S ; S + 0A1; S + 00A11; S ; S * S; S * 0A1; S * 00A11; S * 0011; где 0011 L(G1). 11Трансляторы

12 Грамматики с ограничениями на правила В соответствии с классификацией Хомского грамматика G называется: праволинейной, если каждое правило из Р имеет вид: A xB или A x, где A, B - нетерминалы, x - цепочка, состоящая из терминалов; контекстно-свободной (КС) или бесконтекстной, если каждое правило из Р имеет вид: A, где A N, а (N T)*, то есть является цепочкой, состоящей из множества терминалов и нетерминалов, возможно пустой; контекстно-зависимой или неукорачивающей, если каждое правило из P имеет вид:, где То есть, вновь порождаемые цепочки не могут быть короче, чем исходные, а, значит, и пустыми (другие ограничения отсутствуют); грамматикой свободного вида, если в ней отсутствуют выше упомянутые ограничения. 12Трансляторы

13 Пример праволинейной грамматики: G2 = ({S,}, {0,1}, P, S), где P: 1. S 0S; 2. S 1S; 3. S, определяет язык {0, 1}*. Пример КС грамматики: G3 = ({E, T, F}, {a, +, *, (,)}, P, E) где P: 1. E T 2. E E + T 3. T F 4.T T * F 5. F (E) 6. F a. Данная грамматика порождает простейшие арифметические выражения 13Трансляторы

14 Пример КЗ грамматики: G4 = ({B, C, S}, {a, b, c}, P, S) где P: 1. S aSBC; 2. S abC; 3. CB BC; 4. bB bb; 5. bC bc; 6. cC сc, порождает язык {a n b n c n }, n 1. 14Трансляторы

15 Примечание 1. Согласно определению каждая праволинейная грамматика является контекстно свободной. Примечание 2. По определению КЗ грамматика не допускает правил: А ( - правила), т.е. КС грамматика с - правилами не является КЗ. Наличие - правил ведет к грамматике без ограничений. Соглашение. Если язык L порождается грамматикой типа G, то L называется языком типа G. Пример: L(G3) - КС язык типа G3. 15Трансляторы

16 Способы записи синтаксиса языка Метаязык Хомского вышел из недр математической логики. Он имеет следующую систему обозначений: символ отделяет левую часть правила от правой (читается как "порождает" и "это есть"); нетерминалы обозначаются буквой А с индексом, указывающим на его номер; терминалы - это символы используемые в описываемом языке; каждое правило определяет порождение одной новой цепочки, причем один и тот же нетерминал может встречаться в нескольких правилах слева. 16Трансляторы

17 Описание идентификатора на метаязыке Хомского 1. A 1 A 18. A 1 R 35. A 1 i 52. A 1 z 2. A 1 B 19. A 1 S 36. A 1 j 53. A A 1 C 20. A 1 T 37. A 1 k 54. A A 1 D 21. A 1 U 38. A 1 l 55. A A 1 E 22. A 1 V 39. A 1 m 56. A A 1 F 23. A 1 W 40. A 1 n 57. A A 1 G 24. A 1 X 41. A 1 o 58. A A 1 H 25. A 1 Y 42. A 1 p 59. A A 1 I 26. A 1 Z 43. A 1 q 60. A A 1 J 27. A 1 a 44. A 1 r 61. A A 1 K 28. A 1 b 45. A 1 s 62. A A 1 L 29. A 1 c 46. A 1 t 63. A 3 A A 1 M 30. A 1 d 47. A 1 u 64. A 3 A 3 A A 1 N 31. A 1 e 48. A 1 v 65. A 3 A 3 A A 1 O 32. A 1 f 49. A 1 w 16. A 1 P 33. A 1 g 50. A 1 x 17. A 1 Q 34. A 1 h 51. A 1 y 17Трансляторы

18 Метаязык Хомского-Щутценберже Более компактное описание с использованием обозначений: символ = отделяет левую часть правила от правой (вместо символа ); нетерминалы обозначаются буквой А с индексом, указывающим на его номер; терминалы - это символы используемые в описываемом языке; каждое правило определяет порождение нескольких альтернативных цепочек, отделяемых друг от друга символом +, что позволяет, при желании, использовать в левой части только разные нетерминалы. 18Трансляторы

19 Описание идентификатора на метаязыке Хомского-Щутценберже 1. A 1 =A+B+C+D+E+F+G+H+I+J+K+L+M+N+O+P+Q+ R+S+T+U+V+W+X+Y+Z+a+b+c+d+e+f+g+h+i+j+k+l+ m+n+o+p+q+r+s+t+u+v+w+x+y+z 2. A 2 = A 3 =A 1 +A 3 A 1 +A 3 A 2 19Трансляторы

20 Бэкуса-Наура формы (БНФ) символ "::=" отделяет левую часть правила от правой; нетерминалы обозначаются произвольной символьной строкой, заключенной в угловые скобки " "; терминалы - это символы используемые в описываемом языке; каждое правило определяет порождение нескольких альтернативных цепочек, отделяемых друг от друга символом вертикальной черты "|". 20Трансляторы

21 Пример описания идентификатора с использованием БНФ: 1. :: = А|В|С|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V| W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z 2. :: = 0|1|2|3|4|5|6|7|8|9 3. ::= | | Правила можно задавать и раздельно: :: = :: = :: = 21Трансляторы

22 Расширенные Бэкуса-Наура формы (РБНФ) РБНФ, используемые Виртом, имеют следующие особенности: Квадратные скобки " [ " и " ] "" означают, что заключенная в них синтаксическая конструкция может отсутствовать; фигурные скобки " { " и " } " означают ее повторение (возможно, 0 раз); круглые скобки " ( " и " ) " используются для ограничения альтернативных конструкций; сочетание фигурных скобок и косой черты " {/ " и " /} " используется для обозначения повторения один и более раз. Нетерминальные символы изображаются словами, выражающими их интуитивный смысл и написанными на русском языке. 22Трансляторы

23 Синтаксис идентификатора с использованием РБНФ $ буква = "A"|"B"|"C"|"D"|"E"|"F"|"G"|"H"|"I"|"J"| "K"|"L"|"M"|"N"|"O"|"P"|"Q"|"R"|"S"|"T"|"U"|"V"| "W"|"X"|"Y"|"Z"|"a"|"b"|"c"|"d"|"e"|"f"|"g"|"h"|"i"| "j"|"k"|"l"|"m"|"n"|"o"|"p"|"q"|"r"|"s"|"t"|"u"|"v"|"w"| "x"|"y"|"z". $ цифра = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9". $ идентификатор = буква {буква | цифра}. 23Трансляторы

24 Диаграммы Вирта - терминальный символ, A begin блок принадлежащий алфавиту языка - постоянная группа терминальных символов, определяющая название лексемы, ключевое слово и т.д. - нетерминальный символ, определяющий название правила - соединительные линии, обеспечивающие связь между терминальными и нетерминальными символами в правилах, заданных диаграммами Вирта - входная дуга с именем правила, определяющая его начало Графические примитивы, используемые при построении диаграмм Вирта. 24Трансляторы

25 Описание метаобозначений терминальные символы и их постоянные группы располагаются в окружностях или прямоугольниках со скругленным вертикальными сторонами; нетерминальные символы заносятся внутрь прямоугольников; каждый графический элемент, соответствующий терминалу или нетерминалу, имеет по одному входу и выходу, которые обычно рисуются на противоположных сторонах; каждому правилу соответствует своя графическая диаграмма, на которой терминалы и нетерминалы соединяются посредством дуг; альтернативы в правилах задаются ветвлением дуг, а итерации - их слиянием; должна быть одна входная дуга (располагается обычно слева и сверху), задающая начало правила и помеченная именем определяемого нетерминала, и одна выходная, задающая его конец (обычно располагается справа и снизу). 25Трансляторы

26 буква A B C D E F G H IJK L M N O P Q R S T U V W X Y Z abcdefghijklm nopqrs t uvw x yz цифра буква Идентификатор буква цифра Описание идентификатора с использованием диаграмм Вирта. 26Трансляторы

27 Распознаватели Распознаватель - это очень схематизированный алгоритм, определяющий некоторое множество. Его можно представить в виде устройства (автомата). Этот автомат состоит из трех частей: входной ленты, устройства управления с конечной памятью и вспомогательной (рабочей) памяти. 27Трансляторы

28 Правый Клетка (ячейка) Входная лента [a0 Левый концевой маркер (необязателен) концевой маркер (необязателен) a1a2an] Входной символ Входная головка Устройство управления с конечной памятью Вспомогательная (рабочая) память Обобщенная структура распознавателя 28Трансляторы

29 Входная лента - линейная последовательность клеток (ячеек), каждая из которых содержит один входной символ из конечного входного алфавита. Могут присутствовать левый и правый концевые маркеры, может присутствовать только один концевой маркер (левый или правый), могут отсутствовать оба маркера. Входная головка - в каждый момент читает одну входную ячейку. За один шаг входная головка может сдвинуться на одну ячейку влево, вправо и остаться неподвижной. Распознаватель, никогда не передвигающий входную головку влево, называется односторонним. Обычно предполагается, что входная головка только читает. Но могут быть и такие распознаватели, у которых входная головка читает и пишет. Память - хранит информацию, построенную только из символов конечного алфавита памяти. Может иметь различную структуру: очередь, стек (магазин) и т. д. Можно читать из вспомогательной памяти и писать в нее. Для стека и очереди используются специфические операции (вталкивание, выталкивание). Устройство управления с конечной памятью - программа, управляющая поведением распознавателя. Может являться аналогом конечного автомата. Определяет перемещение входной головки и работу с памятью на каждом шаге (такте). Переходит за шаг из одного состояния в другое. 29Трансляторы

30 Конфигурация распознавателя - мгновенный снимок, на котором изображены: 1. состояние устройства управления; 2. содержимое входной ленты; 3. содержимое памяти. Начальная конфигурация - устройство управления находится в заданном начальном состоянии, входная головка читает самый левый символ на входной ленте, память имеет заранее установленное начальное содержимое. Заключительная конфигурация - устройство управления находится в одном из состояний, принадлежащем заранее выделенному множеству заключительных состояний, входная головка обозревает правый концевой маркер или, если маркер отсутствует, сошла с конца входной ленты. Иногда требуется, чтобы заключительная конфигурация памяти удовлетворяла некоторым условиям. 30Трансляторы

31 Распознаватель допускает входную цепочку, если, начиная с начальной конфигурации, в которой цепочка записана на входной ленте, распознаватель может проделать последовательность шагов, заканчивающуюся заключительной конфигурацией. Язык, определяемый распознавателем - это множество цепочек, которые он допускает. 31Трансляторы

32 Для каждой из грамматик, приведенных выше в соответствии с иерархией Хомского, существуют распознаватели определяющие один и тот же класс языков. 1. Язык L праволинейный тогда и только тогда, когда он определяется конечным односторонним детерминированным автоматом. 2. Язык L контекстно-свободный тогда и только тогда, когда он определяется односторонним недетерминированным автоматом с магазинной памятью. 3. Язык L контекстно-зависимый тогда и только тогда, когда он определяется двухсторонним недетерминированным линейно ограниченным автоматом. 4. Язык L рекурсивно перечислимый тогда и только тогда, когда он определяется машиной Тьюринга. 32Трансляторы

33 Демонстрационный язык программирования Литература Дейкстра Э. Дисциплина программирования. М.: Мир, Грис Д. Наука программирования. М.: Мир, Трансляторы

34 Элементарные конструкции Представляют набор базовых понятий языка программирования Имея в своем распоряжении набор базовых кирпичиков, легче изучать более сложные понятия; В большинстве языков программирования смысл и представление элементарных конструкций совпадают, поэтому, поняв их в ходе изучения одного языка, легче перейти к следующему. 34Трансляторы

35 $ буква = "A"|"B"|"C"|"D"|"E"|"F"|"G"|"H"|"I"|"J"|"K"|"L |"M"|"N"|"O"|"P"|"Q"|"R"|"S"|"T"|"U"|"V"|"W"|"X"|"Y"| "Z"|"a"|"b"|"c"|"d"|"e"|"f"|"g"|"h"|"i"|"j"|"k"|"l"|"m"|"n"| "o"|"p"|"q"|"r"|"s"|"t"|"u"|"v"|"w"|"x"|"y"|"z". $ цифра = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9". $ идентификатор = ( буква | "_" ) { буква | цифра | "_" }. $ число = целое | действительное. $ целое = двоичное | восьмиричное | десятичное | шестнадцатиричное. $ двоичное = "{2}" {/ "0" | "1" /}. $ восьмиричное = "{8}"{/ "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7" /}. $ десятичное = ["{10}"] {/ цифра /}. $ шестнадцатиричное = "{16}" {/ цифра |"A"|"B"|"C"|"D"|"E"|"F"| "a"|"b"|"c"|"d"|"e"|"f" /}. 35Трансляторы

36 Синтаксис элементарных конструкций Использование РБНФ $ действительное = числовая_строка порядок | числовая_строка "." [числовая_строка] [порядок] | "." числовая_строка [порядок]. $ числовая_строка = {/ цифра /}. $ порядок = ("E"|"e")["+"|"-"] числовая_строка. $ пробельный_символ = {/ пробел | табуляция | перевод_строки | перевод_формата | комментарий /}. $ комментарий = "/*" { символ } "*/". $ строка = "" { символ | ""} "". 36Трансляторы

" |" " | " =" | "!=". 37Транс" title="$ ключевое_слово = abort | begin | case | end | float | goto | int | loop | or | read | skip | space | tab | var | write |. $ разделитель = "(" | ")" | "[" | "]" | "," | ";" | ":" | ":=" | "*" | "/" | "%" |"+" | "-" | "->" |" " | " =" | "!=". 37Транс" class="link_thumb"> 37 $ ключевое_слово = abort | begin | case | end | float | goto | int | loop | or | read | skip | space | tab | var | write |. $ разделитель = "(" | ")" | "[" | "]" | "," | ";" | ":" | ":=" | "*" | "/" | "%" |"+" | "-" | "->" |" " | " =" | "!=". 37Трансляторы " |" " | " =" | "!=". 37Транс"> " |" " | " =" | "!=". 37Трансляторы"> " |" " | " =" | "!=". 37Транс" title="$ ключевое_слово = abort | begin | case | end | float | goto | int | loop | or | read | skip | space | tab | var | write |. $ разделитель = "(" | ")" | "[" | "]" | "," | ";" | ":" | ":=" | "*" | "/" | "%" |"+" | "-" | "->" |" " | " =" | "!=". 37Транс">

38 Элементарные конструкции. Использование ДВ буква A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ab c d efg h ijk l m n o p q rstu v w x y z цифра Трансляторы

39 буква идентификатор буква цифра целое число действительное целое двоичное восьмиричное десятичное шестнадцатиричное 39Трансляторы

40 двоичное 0 { 2} 1 восьмиричное { 8} десятичное { 10} цифра шестнадцатиричное { 16} ab c d ef цифра A B C D E F 40Трансляторы

41 действительное числовая строка порядок числовая строка цифра Е + порядок цифра е - 41Трансляторы

42 Пробельный символ пробел табуляция перевод строки перевод формата комментарий символ комментарий /**/ символ строка 42Трансляторы

43 разделитель ( )[],;:%*/ +--> =!=:= ключевое слово abort goto space beginint tab caseloop var endread write floatskip or 43Трансляторы

44 Синтаксис составных конструкций Использование РБНФ $ программа = begin ( описание | оператор ) { ";" ( описание | оператор ) } end. $ описание = var идентификатор [ размер ] { "," идентификатор [ размер ] } ":" тип. $ тип = int | float. $ размер = целое. $ оператор = метка непомеченный. $ метка = идентификатор ":". $ непомеченный = присваивания | условный | цикла | пустой | ошибки | ввода | вывода | перехода. $ присваивания = переменная ":=" выражение | переменная "," присваивания "," выражение. 44Трансляторы

=" | "" оператор { ";" оператор }. " title="$ переменная = идентификатор [ "[" выражение "]" ]. $ выражение = [ "-" ] операнд { операция [ "-" ] операнд }. $ операнд = "(" выражение ")" | число | переменная. $ операция = "*" | "/" | "%" | "+" | "-" | " " | ">=" | "" оператор { ";" оператор }. " class="link_thumb"> 45 $ переменная = идентификатор [ "[" выражение "]" ]. $ выражение = [ "-" ] операнд { операция [ "-" ] операнд }. $ операнд = "(" выражение ")" | число | переменная. $ операция = "*" | "/" | "%" | "+" | "-" | " " | ">=" | "" оператор { ";" оператор }. $ пустой = skip |. $ прерывания = abort [строка]. $ ввода = read переменная { "," переменная }. $ вывода = write ( выражение | спецификатор | строка ) { "," ( выражение | спецификатор | строка ) }. $ перехода = goto идентификатор. $ спецификатор = ( space | tab | skip ) [ выражение ]. 45Трансляторы =" | "" оператор { ";" оператор }. "> =" | "" оператор { ";" оператор }. $ пустой = skip |. $ прерывания = abort [строка]. $ ввода = read переменная { "," переменная }. $ вывода = write ( выражение | спецификатор | строка ) { "," ( выражение | спецификатор | строка ) }. $ перехода = goto идентификатор. $ спецификатор = ( space | tab | skip ) [ выражение ]. 45Трансляторы"> =" | "" оператор { ";" оператор }. " title="$ переменная = идентификатор [ "[" выражение "]" ]. $ выражение = [ "-" ] операнд { операция [ "-" ] операнд }. $ операнд = "(" выражение ")" | число | переменная. $ операция = "*" | "/" | "%" | "+" | "-" | " " | ">=" | "" оператор { ";" оператор }. ">

46 Составные конструкции. Использование ДВ программа ; begin описание end оператор описание, var идентификатор [ размер ] : тип Тип int float размер целое 46Трансляторы

47 оператор метка непомеченный присваивания условный цикла ввода вывода пустой прерывания перехода 47Трансляторы

48 присваивания переменная := выражение переменная, присваивания, выражение переменная идентификатор [ выражение ] операция - операнд 48Трансляторы

49 операция * /% +- >=!= оператор 49Трансляторы

50 Оператор присваивания обеспечивает одновременное присваивание нескольким переменным, расположенным слева от знака ":=" значений предварительно вычисленных выражений, расположенных в правой части. Каждой переменной соответствует свое выражение. Присваивания начинаются только после вычисления всех выражений, результаты которых временно сохраняются. Это позволяет произвести обмен значений переменных с использованием только одного оператора присваивания: x, y := y, x В обычных языках программирования необходимо написать три отдельных оператора: t := x; x := y; y := t 50Трансляторы

51 Выражения задаются в традиционной инфиксной форме. Порядок выполнения операций определяется их приоритетом и скобками. В начале выполняются выражения в скобках. Наивысший приоритет имеет унарный минус "-", далее следуют мультипликативные операции "*", "/", "%" (вычисление остатка), затем аддитивные "+", "-" и, наконец операции отношения " ", " =", "!=". 51Трансляторы

52 пустой skip ошибки abort ввода read строка, переменная 52Трансляторы

53 вывода write спецфикатор tab space skip перехода goto, выражение спецификатор строка выражение идентификатор 53Трансляторы

54 Для представления пустой оператора Дейкстра намеренно использовал специальное ключевое слово skip (что мотивировал соответствующим текстом), хотя в большинстве языков программирования пустой оператор - это пустое место: $ пустой =. 54Трансляторы

55 Пример 1. Алгоритм Евклида (нахождение наибольшего общего делителя) begin var x, y: int;/* описание переменных */ read x, y;/* ввод операндов */ /* выполнять до равенства аргументов */ loop x != y -> case x > y -> x := x - y or y > x -> y := y - x end end; write x/* полученный НОД */ end 55Трансляторы

56 Пример 2. Одновременное нахождение наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК). Begin /* описание переменных */ var x, y, u, v: int; read x, y;/* ввод операндов */ u, v := y, x; /* выполнять до равенства аргументов */ loop x > y -> x, v := x - y, v + u or y > x -> y, u := y - x, u +v end; write НОД =, x;/* НОД */ write skip, НОК =, (u + v) / 2/* НОК */ end 56Трансляторы

57 Пример 3. Суммирование n элементов из входного потока. begin var a, i, s, n: int; i,s := 0,0; read n; loop i read a; s,i := s+a,i+1 end; write s end 57Трансляторы

58 Пример 4. Сортировка элементов вектора. begin var A[100], i, n: int; i := 0; read n; /* чтение числа элементов */ /* ввод вектора */ loop i read A[ i ]; i := i +1 end; i := 0; /* сортировка методом пузырька loop i case A[ i ] > A[ i+1 ] -> A[ i ],A[ i+1 ],i := A[ i + 1],A[ i ],0 or A[ i ] i := i + 1 end end; /* вывод вектора */ i := 0; loop i write A[ i ], skip; i := i + 1 end 58Трансляторы