Лабораторная работа № 6 Моделирование фу. Лабораторная работа 6 Тема работы Моделирование функционирования распознавателя для ll (1) грамматик
 Скачать 0.58 Mb.
|
|
Министерство науки и высшего образования Российской Федерации Федеральное государственное образовательное учреждение высшего образования ЛАБОРАТОРНАЯ РАБОТА № 6 Тема работы: «Моделирование функционирования распознавателя для LL(1)-грамматик» Дисциплина: (Специальность): _______________
Москва 2022 Лабораторная работа № 6. Моделирование функционирования распознавателя для LL(1)-грамматикЦель: - закрепить понятие «LL(k) - грамматика», необходимые и доста- точные условия LL(k) –грамматики; сформировать умения и навыки построения множеств FIRST(k, ) и FOLLOW(k, ), распознавателя для LL(1)-грамматик. Основы теории Определение 6.1. КС-грамматика обладает свойством LL(k) для некото- рого k>0, если на каждом шаге вывода для однозначного выбора очередной альтернативы МП-автомату достаточно знать символ на верхушке стека и рас- смотреть первые k символов от текущего положения считывающей головки во входной строке. Определение 6.2. КС-грамматика называется LL(k)-грамматикой, если она обладает свойством LL(k) для некоторого k>0. В основе распознавателя LL(k)-грамматик лежит левосторонний разбор строки языка. Исходной сентенциальной формой является начальный символ грамматики, а целевой – заданная строка языка. На каждом шаге разбора пра- вило грамматики применяется к самому левому нетерминалу сентенции. Дан- ный процесс соответствует построению дерева разбора цепочки сверху вниз (от корня к листьям). Отсюда и произошла аббревиатура LL(k): первая «L» (от сло- ва «left») означает левосторонний ввод исходной цепочки символов, вторая «L» левосторонний вывод в процессе работы распознавателя. Определение 6.3. Для построения распознавателей для LL(k)-грамматик используются два множества: FIRST(k, ) – множество терминальных цепочек, выводимых из цепоч- ки (VTVN)*, укороченных до kсимволов; FOLLOW(k, A) – множество укороченных до k символов терминальных цепочек, которые могут следовать непосредственно за AVNв цепочках вывода. Формально эти множества можно определить следующим образом: - FIRST(k, ) = { VT*| вывод * и || kили вывод *x и || = k; x, (VTVN)*, k> 0}; - FOLLOW(k, A) = { VT* | вывод S*A и FIRST(k, ); , V*, AVN, k>0}. |