ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.10.2023
Просмотров: 41
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Вопрос 1. На вход автомата поступает последовательность непустых строк, содержащих группы букв и цифр, при этом цифры есть обязательно. Каждая строка завершается символом «#». Автомат должен распознавать и допускать строки, в которых встречается только четное количество цифр в группах, например, допустимы строки:а) fhgfhfjf56787979tuytuyyu45cvbcv#б) 56плорл354356#в) 6789#Нарисуйте синтаксическую диаграмму и постройте таблицу конечного автомата.Решение:
Автомат не минимален, так как есть совпадающие строки. Удаляем 2-ю и 5-ю строки и заменяем состояния: 2 – на 1, 5 – на 4.
Вопрос 2. Дана грамматика, описывающая упрощенный вариант сложных выражений С++:<Сложное выражение>::= <Сложное выражение>, <Выражение> | <Сложное выражение>+<Выражение> | <Сложное выражение>-<Выражение> |<Выражение><Выражение>::= <Ид>Приведите последовательность выполнения грамматического разбора для сентенциальной формы:<Ид>+<Ид> - <Ид>,<Ид>-<Ид>, <Ид>-<Ид>левосторонним восходящим методом.Определите, к какому типу по Хомскому принадлежит грамматика. Почему?Решение: Вводим обозначения:С – сложное выражение;В – выражение;Ид – идентификатор.Тогда правила будут выглядеть так:а) С ::= С, В | С+В | С-В | В б) В ::= Ид Грамматика принадлежит к 3-му типу по Хомскому, так как:- правила в левой части содержат единственный символ – нетерминал, соответственно это не грамматики 0 и 1 типов; - в правой части правил отсутствует вложенная рекурсия, соответственно это не грамматика 2 типа.Основу в сентенциальной форме ищем слева направо, правила подбираем по правой части снизу-вверх и слева-направо (основу отмечаем красным):1) ид + ид - ид, ид - ид, ид – ид2) в + ид - ид, ид - ид, ид – ид3) с + ид - ид, ид - ид, ид – ид4) с + в - ид, ид - ид, ид – ид5) с - ид, ид - ид, ид – ид6) с - в, ид - ид, ид – ид7) с, ид - ид, ид – ид8) с, в - ид, ид – ид8) с - ид, ид – ид9) с - в, ид – ид10) с, ид – ид11) с, в – ид12) с – ид13) с – в14) с Аксиома, конец разбора....В РК4 достаточно привести первые 20 строк :-)... Можно использовать таблицу, как сделано в лекции.
| | б | ц | # | Другие символы |
| 1 | 2 | 3 | Е | E |
| 2 | 2 | 3 | Е | E |
| 3 | Е | 4 | Е | E |
| 4 | 5 | 3 | К | E |
| 5 | 5 | 3 | К | E |
| | б | ц | # | Другие символы |
| 1 | 1 | 3 | Е | E |
| 3 | Е | 4 | Е | E |
| 4 | 4 | 3 | К | E |
Вопрос 2. Дана грамматика, описывающая упрощенный вариант сложных выражений С++:<Сложное выражение>::= <Сложное выражение>, <Выражение> | <Сложное выражение>+<Выражение> | <Сложное выражение>-<Выражение> |<Выражение><Выражение>::= <Ид>Приведите последовательность выполнения грамматического разбора для сентенциальной формы:<Ид>+<Ид> - <Ид>,<Ид>-<Ид>, <Ид>-<Ид>левосторонним восходящим методом.Определите, к какому типу по Хомскому принадлежит грамматика. Почему?Решение: Вводим обозначения:С – сложное выражение;В – выражение;Ид – идентификатор.Тогда правила будут выглядеть так:а) С ::= С, В | С+В | С-В | В б) В ::= Ид Грамматика принадлежит к 3-му типу по Хомскому, так как:- правила в левой части содержат единственный символ – нетерминал, соответственно это не грамматики 0 и 1 типов; - в правой части правил отсутствует вложенная рекурсия, соответственно это не грамматика 2 типа.Основу в сентенциальной форме ищем слева направо, правила подбираем по правой части снизу-вверх и слева-направо (основу отмечаем красным):1) ид + ид - ид, ид - ид, ид – ид2) в + ид - ид, ид - ид, ид – ид3) с + ид - ид, ид - ид, ид – ид4) с + в - ид, ид - ид, ид – ид5) с - ид, ид - ид, ид – ид6) с - в, ид - ид, ид – ид7) с, ид - ид, ид – ид8) с, в - ид, ид – ид8) с - ид, ид – ид9) с - в, ид – ид10) с, ид – ид11) с, в – ид12) с – ид13) с – в14) с Аксиома, конец разбора....В РК4 достаточно привести первые 20 строк :-)... Можно использовать таблицу, как сделано в лекции.
| № | Строка разбора | Основа | Действие |
| 1 | ид + ид - ид, ид - ид, ид - ид | ид | Свертка по правилу б1 |
| 2 | в + ид - ид, ид - ид, ид - ид | в | Свертка по правилу а4 |
| 3 | с + ид - ид, ид - ид, ид - ид | с | Нет правила, след.основа |
| 4 | с + ид - ид, ид - ид, ид - ид | с+ | Нет правила, след.основа |
| 5 | с + ид - ид, ид - ид, ид - ид | с + ид | Нет правила, след.основа |
| 6 | с + ид - ид, ид - ид, ид - ид | + | Нет правила, след.основа |
| 7 | с + ид - ид, ид - ид, ид - ид | + ид | Нет правила, след.основа |
| 8 | с + ид - ид, ид - ид, ид - ид | + ид - | Нет правила, след.основа |
| 9 | с + ид - ид, ид - ид, ид - ид | ид | Свертка по правилу б1 |
| 10 | с + в - ид, ид - ид, ид - ид | с | Нет правила, след.основа |
| 11 | с + в - ид, ид - ид, ид - ид | с+ | Нет правила, след.основа |
| 12 | с + в - ид, ид - ид, ид - ид | с + в | Свертка по правилу а2 |
| 13 | с - ид, ид - ид, ид - ид | с | Нет правила, след.основа |
| 14 | с - ид, ид - ид, ид - ид | с- | Нет правила, след.основа |
| 15 | с - ид, ид - ид, ид - ид | с - ид | Нет правила, след.основа |
| 16 | с - ид, ид - ид, ид - ид | - | Нет правила, след.основа |
| 17 | с - ид, ид - ид, ид - ид | - ид | Нет правила, след.основа |
| 18 | с - ид, ид - ид, ид - ид | - ид, | Нет правила, след.основа |
| 19 | с - ид, ид - ид, ид - ид | ид | Свертка по правилу б1 |
| 20 | с - в, ид - ид, ид - ид | с | Нет правила, след.основа |
| 21 | с - в, ид - ид, ид - ид | с - | Нет правила, след.основа |
| 22 | с - в, ид - ид, ид - ид | с - в | Свертка по правилу а3 |
| 23 | с, ид - ид, ид - ид | с | Нет правила, след.основа |
| 24 | с, ид - ид, ид - ид | с, | Нет правила, след.основа |
| 25 | с, ид - ид, ид - ид | с, ид | Нет правила, след.основа |
| 26 | с, ид - ид, ид - ид | , | Нет правила, след.основа |
| 27 | с, ид - ид, ид - ид | , ид | Нет правила, след.основа |
| 28 | с, ид - ид, ид - ид | , ид - | Нет правила, след.основа |
| 29 | с, ид - ид, ид - ид | ид | Свертка по правилу б1 |
| 30 | с, в - ид, ид - ид | с | Нет правила, след.основа |
| 31 | с, в - ид, ид - ид | с, | Нет правила, след.основа |
| 32 | с, в - ид, ид - ид | с, в | Свертка по правилу а1 |
| 33 | с - ид, ид - ид | с | Нет правила, след.основа |
| 34 | с - ид, ид - ид | с - | Нет правила, след.основа |
| 35 | с - ид, ид - ид | с - ид | Нет правила, след.основа |
| 36 | с - ид, ид - ид | - | Нет правила, след.основа |
| 37 | с - ид, ид - ид | - ид | Нет правила, след.основа |
| 38 | с - ид, ид - ид | - ид, | Нет правила, след.основа |
| 39 | с - ид, ид - ид | ид | Свертка по правилу б1 |
| 40 | с - в, ид - ид | с | Нет правила, след.основа |
| 41 | с - в, ид - ид | с - | Нет правила, след.основа |
| 42 | с - в, ид - ид | с - в | Свертка по правилу а3 |
| 43 | с, ид - ид | с | Нет правила, след.основа |
| 44 | с, ид - ид | с, | Нет правила, след.основа |
| 45 | с, ид - ид | с, ид | Нет правила, след.основа |
| 46 | с, ид - ид | , | Нет правила, след.основа |
| 47 | с, ид - ид | , ид | Нет правила, след.основа |
| 48 | с, ид - ид | , ид - | Нет правила, след.основа |
| 49 | с, ид - ид | ид | Свертка по правилу б1 |
| 50 | с, в - ид | с | Нет правила, след.основа |
| 51 | с, в - ид | с, | Нет правила, след.основа |
| 52 | с, в - ид | с, в | Свертка по правилу а1 |
| 53 | с - ид | с | Нет правила, след.основа |
| 54 | с - ид | с - | Нет правила, след.основа |
| 55 | с - ид | с - ид | Нет правила, след.основа |
| 56 | с - ид | - | Нет правила, след.основа |
| 57 | с - ид | - ид | Нет правила, след.основа |
| 58 | с - ид | ид | Свертка по правилу б1 |
| 59 | с - в | с | Нет правила, след.основа |
| 60 | с - в | с - | Нет правила, след.основа |
| 61 | с - в | с - в | Свертка по правилу а3 |
| 62 | с | Конец | |