WedX - журнал о программировании и компьютерных науках

Не удалось найти first() и follow() для грамматика, отличного от LR

Я удалил левую рекурсию из данной грамматики. Но теперь я должен сначала выяснить это, а затем создать таблицу синтаксического анализа.

Оригинал: S -> aSb | bSa | SS | epsilon

Новое: после удаления левой рекурсии: S -> aSbSS' | bSaSS' | S' и S'-> SS' | epsilon

Я пытаюсь сделать сначала (S) = {a, b} и сначала (S'). Но сначала (S) - это сначала (SS'). Теперь это становится рекурсивным. Как найти первый и следовать за нетерминалами S и S'?


  • Эта ссылка решает только для FOLLOW . Должен ли я сделать грамматик как непосредственный левый рекурсивный и решить для FIRST? Потому что я только что удалил левую рекурсию. 03.07.2019
  • Теперь набор в FIRST и FOLLOW одинаковый. Это создаст 2 записи в таблице разбора. Итак, даже если я уберу левую рекурсию, таблица все равно будет содержать 2 продукции для одного нетерминала. Это правильно? 04.07.2019
  • Если S все еще рекурсивен, вы на самом деле не удалили левую рекурсию. Вы удалили только прямую левую рекурсию. Кроме того, удаление левой рекурсии не устраняет неоднозначность. Неоднозначные грамматики производят таблицы синтаксического анализа с конфликтами. 04.07.2019
  • В любом случае, вы можете найти наборы FIRST так же, как вы делаете это для наборов FOLLOW, даже для леворекурсивных грамматик. Но леворекурсивная грамматика не имеет анализатора LL, независимо от того, прямое это направление или нет. 04.07.2019
  • Спасибо за ответ @rici. Я удалил левую рекурсию как указано: S -> aSbSS' | bSaSS' | S' and S'-> SS' | epsilon. Итак, вы хотите сказать, что даже после удаления левой рекурсии таблица синтаксического анализа может содержать несколько записей? 04.07.2019
  • Да, это правильно. Есть много грамматик, которые не являются леворекурсивными, которые все еще не могут быть проанализированы с помощью LL(k)-автомата. 04.07.2019
  • Я просто попытался построить дерево синтаксического анализа для строки, используя нелеворекурсивную грамматику, которую я сделал, и я мог построить другое дерево для той же строки. Итак, это означает, что это неоднозначно, верно? И, да, у него есть несколько записей в таблице. Итак, это не LL(1). Большое спасибо за ответ. 04.07.2019

Новые материалы

Объяснение документов 02: BERT
BERT представил двухступенчатую структуру обучения: предварительное обучение и тонкая настройка. Во время предварительного обучения модель обучается на неразмеченных данных с помощью..

Как проанализировать работу вашего классификатора?
Не всегда просто знать, какие показатели использовать С развитием глубокого обучения все больше и больше людей учатся обучать свой первый классификатор. Но как только вы закончите..

Работа с цепями Маркова, часть 4 (Машинное обучение)
Нелинейные цепи Маркова с агрегатором и их приложения (arXiv) Автор : Бар Лайт Аннотация: Изучаются свойства подкласса случайных процессов, называемых дискретными нелинейными цепями Маркова..

Crazy Laravel Livewire упростил мне создание электронной коммерции (панель администратора и API) [Часть 3]
Как вы сегодня, ребята? В этой части мы создадим CRUD для данных о продукте. Думаю, в этой части я не буду слишком много делиться теорией, но чаще буду делиться своим кодом. Потому что..

Использование машинного обучения и Python для классификации 1000 сезонов новичков MLB Hitter
Чему может научиться машина, глядя на сезоны новичков 1000 игроков MLB? Это то, что исследует это приложение. В этом процессе мы будем использовать неконтролируемое обучение, чтобы..

Учебные заметки: создание моего первого пакета Node.js
Это мои обучающие заметки, когда я научился создавать свой самый первый пакет Node.js, распространяемый через npm. Оглавление Глоссарий I. Новый пакет 1.1 советы по инициализации..

Забудьте о Matplotlib: улучшите визуализацию данных с помощью умопомрачительных функций Seaborn!
Примечание. Эта запись в блоге предполагает базовое знакомство с Python и концепциями анализа данных. Привет, энтузиасты данных! Добро пожаловать в мой блог, где я расскажу о невероятных..


Для любых предложений по сайту: [email protected]