Синтаксический анализатор инфиксных арифметических выражений, основанный на методе нисходящего разбора.
Ярошевской Я.В.
Гр.22-06
Лабораторная работа 1
Распознаватель языка, заданного разделяющей грамматикой
1. Алгоритм, определяющий принадлежит ли входная цепочка заданному языку, или нет.
А) распознаватель языка
Б) грамматика языка
В) определитель языка
2. Грамматики, которые позволяют по текущему символу во входной цепочке однозначно определить правило вывода, использованное на очередном шаге
А) пояснительные
Б) разделяющие
В) последовательные
3. Если язык задан формальной грамматикой, то цепочка принадлежит ему тогда и только тогда, когда она получена в результате вывода
А) используя специальную структуру символов
Б) с помощью специальных символов и алфавита этой грамматики
В) по правилам этой грамматики.
4. Распознаватель для языка задается
А) правилами грамматики
Б) разделяющей грамматикой
В) нетерминальными символами
5. Для каждого нетерминального символа грамматики можно создать подпрограмму, которая выбирает …, выводимую из этого нетерминала
А) подцепочку максимальной длины
Б) цепочку минимальной длины
В) символы, которые являются терминалами
6. Распознаватель языка начинает работу с вызова подпрограммы, начиная просмотр входной цепочки с
А) терминального символа
Б) текущегог символа
В) первого символа
7. Начиная работу, распознаватель вызывает подпрограмму для:
|
|
|
А) конечного нетерминала
Б) стартового нетерминала
В) терминального символа
8. Если правые части всех правил грамматики начинаются с нетерминальных символов, тогда строят множества FIRST(X) для каждого символа чтобы проверить
А) является ли последний символ нетерминалом
Б) есть ли терминальные символы
В) является ли грамматика резделяющей
9. Форма Бэкуса-Наура используется для описания
А) синтаксиса языков программирования
Б) контекстно-свободных формальных грамматик
В) логики последовательных терминалов
10. Произвольную упорядоченную конечную последовательность символов, записанных один за другим называют
А) языком программирования
Б) цепочкой символов
В) правилами языков
Ответы на вопросы к тесту:
1.А
2.Б
3.В
4.Б
5.А
6.В
7.Б
8.В
9.Б
10.Б
Лабораторная работа 2
Интерпретатор работы детерменированного конечного автомата
1. Конечный автомат представляет собой
А) логическую модель устройства
Б) математическую модель устройства
В) двоичную модель устройства
2. Работа конечного автомата завершается, когда головка считывает
А) символ-ограничитель
Б) конечный символ
В) символ остановки
3. В начальный момент времени на входной ленте
|
|
|
А) ничего не записано
Б) записана входная цепочка
В) записан входной интерпретатор
4. Конечный автомат представляет собой набор данных, который содержит
А) символ текущего состояния
Б) символ предстартового состояния
В) символ стартового состояния
5. В детерминированном конечном автомате для любого символа
А) текущее состояние определяет все последующие
Б) из текущего можно перейти только в одно состояние
В) конечный символ обрабатывается первым
6. Детерменированный конечный автомат считывает символы
А) по очереди
Б) хаотично
В) по типам
7. В список параметров, которыми задается детерменированный автомат, входит
А) конечное состояние
Б) начальное состояние
В) функции символов алфавита
8. Результат работы автомата определяется
А) по его конечному состоянию.
Б) по его входному потоку
В) по множеству его состояний
9. При выполнении работы, автомат считывает
А) по паре символов
Б) всю цепочку символов одновременно
В) по одному символу входной строки
10. Константы в регулярном выражении определяют
А) множество операций
Б) множества строк
В) множество операторов
Ответ на вопросы к тесту:
|
|
|
1.Б
2.А
3.Б
4.А, В
5.Б
6.А
7.Б
8.А
9.В
10.Б
Лабораторная работа 3.
Тема: Построение недетерминированного КА-распознавателя
регулярного языка по автоматной грамматике этого языка.
1. Языки, для которых можно построить конечно-автоматный распознаватель называют
А) регулярными
Б) конечными
В) последоветельными
2. Для определения регулярных языков можно использовать
А) стартовые грамматики
Б) автоматные грамматики
В) регулярные грамматики
3. Регулярные грамматики бывают двух видов
А) леволинейные и праволинейные
Б) левые и правые
В) одновсторонние и двухсторонние
4. Оба класса грамматик определяют
А) одни и те же параметры
Б) один класс языков
В) одни и те же правила вывода
5. Если исходная праволинейная автоматная грамматика является разделяющей, то автомат будет
А) конечным
Б) недетерменированным
В) детерменированным
6. Выходные данные конечного автомата можно представить в виде
А) структуры входных параметров
Б) структуры последовательных автоматов
В) таблицы переходов
7. Любой конечный автомат можно преобразовать к
А) детерменированному виду
Б) недетерменированному виду
|
|
|
В) к любому виду
8. Грамматики с правилами вида: A→aB либо A→a, где a – терминальный символ называются
А) автоматными грамматиками
Б) детерменированными грамматиками
В) переходными грамматиками
9. По праволинейной автоматной грамматике языка можно построить
А) леволинейную автоматную грамматику
Б) недетерминированный конечно-автоматный распознаватель
В) детерминированный конечно-автоматный распознаватель
10. Правила автоматной грамматики, имеющие вид A→aB либо A→a относятся к
А) грамматике параметров
Б) леволинейной грамматике
В) праволинейной грамматике
Ответы на вопросы к тесту:
1.А
2.В
3.А
4.Б
5.В
6.В
7.А
8.А
9.Б
10.В
Лабораторная работа 4.
Преобразователь недетерминированного конечного автомата
в детерминированный.
1. В НКА цепочка считается допустимой, если множество состояний, в котором оказался автомат, содержит
А) хотя бы одно допускающее
Б) хотя бы три допускающих
В) ни одного допускающего
2. Недетерменированный конечный автомат это набор данных, который содержит:
А) символ стартового состояния
Б) таблицу переходов
В) таблицу последовательностей
3. Конечный автомат, у которого имеется, по крайней мере, две различные команды 
и 
при одних и тех же a и q называют
А) недетерменированным
Б) детерменированным
В) разреженным
4. В таблице переходов, индексированной парой символов q и a, если считывающая головка обозревает символ a, возможет переход из состояний qв
А )состояния 
Б)состояния 
В)состояние 
5. Входная цепочка принимается автоматом, если в графе переходов этого автомата имеется
А) хотя бы один маршрут, ведущий из начального состояния в конечное
Б) каждый маршрут имеет ссылку на конечное состояние
В) конечный маршрут имеет указатель на первый
6. Число возможных состояний любого конечного автомата конечно и он
А) не содержит выходного потока
Б) содержит выходной поток
В) содержит несколько выходных потоков
7. Конечный автомат называют недетерменированным, если он имеет
А) один единственный вход
Б) более одного входа
В) как минимум три входа
8. В недетерменированном конечном автомате из вершины выходят
А) две дуги с одинаковыми пометками
Б) более двух дуг с одинаковыми пометками
В) две дуги с разными пометками
9. Любая таблица, заполненная 0 и 1, является таблицей соответствия вершин некоторого автомата, если она
А) не имеет ни строк, ни столбцов, содержащих только 1
Б) не имеет ни строк, ни столбцов, содержащих только 0
В) имеет хотя бы пару одинаковых строк и столбцов
10. Любой недетерминированный автомат эквивалентен некоторому
А) набору единичных строк
Б) набору единичных столбцов
В) детерменированному автомату
Правильные ответы к тесту:
1. А
2. А, Б
3. А
4. А
5. А
6. А
7. Б
8. А, Б
9. Б
10. В
Лабораторная работа № 5.
Синтаксический анализатор инфиксных арифметических выражений, основанный на методе нисходящего разбора.
1. Автомат с магазинной памятью для хранения состояний использует
А) стек
Б) специальную команду
В) символ остановки
2. Способ представления множества выводов одной и той же цепочки в контекстно-свободной грамматике
А) дерево вывода
Б) таблица вывода
В) диаграмма вывода
3. Метод определения принадлежности входной строки к некоторому формальному языку, описанному контекстно-свободной диаграммой
А) разветвляющийся синтаксический разбор
Б) нисходящий синтаксический разбор
В) метод классов
4. ДетерменированныйМП-автомат, реализующий алгоритм нисходящего разбора, можно построить для
А) разделяющей грамматики
Б) табличной грамматики
В) классовой грамматике
5. МП-преобразователь для нисходящего разбора строит
А) целостный выход входной цепочки
Б) верхний выход входной цепочки
В) левый вывод входной цепочки.
6. Дерево вывода входной цепочки однозначно определяется по
А) преобразователям грамматики
Б) существующей входной грамматике
В) последовательности правил вывода
7. Дерево вывода входной цепочки МП-преобразователя предназначено для
А) восходящей ленты
Б) нисходящего разбора
В) корневого преобразователя
8. Параллельно работе автомата строится
А) дерево вывода
Б) длина выходящей цепочки
В) терминальный символ входа
9. Для каждого нетерминального символа грамматики А, если имеется правило вида 
, можно определить
А) множество 
Б) систему команд
В) алфавит состояний грамматики
10. Определить систему команд МП-преобразователя для алгоритма нисходящего разбора можно по:
А) символам алфавита
Б) дереву вывода
В) построенным множествам и правилам грамматики
Ответы на тест:
1.А
2.А
3.Б
4.А
5.В
6.В
7.Б
8.А
9.А
10.В
Лабораторная работа № 6.
Дата добавления: 2018-05-12; просмотров: 598; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!