Год назад у нас был семестр в университете, в котором я участвовал, где наша задача заключалась в создании языка программирования. Как группа, мы решили, что хотим иметь возможность вручную писать парсер с нуля, поэтому нам пришлось стремиться к грамматике LL (1), так как было бы совершенно нереалистично писать синтаксический анализатор в противном случае.
Конечно, наша отправная точка была далека от того, чтобы быть LL (1), поэтому нам тоже пришлось спорить на месте. Для этой цели мы использовали инструмент kfgEdit из пакета AtoCC. Все, что вы делаете, это ввести свои правила, а затем проверить, является ли это грамматикой LL (1) одним нажатием кнопки.
Яркое слово предупреждения: Инструмент немного утончен в отношении того, что он принимает. Хотя вы часто используете EBNF для реальной грамматики, чтобы вы могли писать? и * и +, чтобы сигнализировать, сколько раз этот токен должен появляться там, это не поддерживается. Группировка также не поддерживается. Вы можете очень хорошо понять, что для этого требуется очень много времени, и вы почти наверняка захотите выполнить некоторую «перестановку» после того, как вы достигли LL (1), чтобы сделать грамматику даже близкой к читаемой.
Конечно, в зависимости от типа грамматики, с которой вы имеете дело, это может быть для вас не большой проблемой. Мы создали своего рода гибрид Pascal/C с довольно ограниченным набором конструкций (процедур, функций, только встроенных примитивных типов и массивов из них, ifs, единой петлевой конструкции, которую мы придумали вместо стандарт 3 ...), и мне потребовалось не менее недели, чтобы навязать его в грамматику LL (1) - вероятно, 2, на самом деле. Обратите внимание, что это составляет не более 4 месяцев, так что там было много времени.
Если вы абсолютно ДОЛЖНЫ иметь грамматику LL (1), вам, очевидно, потребуется нажать, если вы попадете в такую ситуацию, но если вам разрешено использовать генераторы парсеров, такие как yacc/bison или SableCC, тогда вы, в конечном счете, скорее всего, найдёте намного легче спуститься по этому маршруту. Это не означает, что вы ДОЛЖНЫ пойти по этому пути - я обнаружил, что на самом деле все написанное вручную дало некоторую информацию, которую я, вероятно, не получил бы в противном случае, - но вам может быть лучше получить эту информацию в другой ситуации, чем ваша текущая ,
tl; dr версия: Используйте kfgEdit из пакета AtoCC.
Для kfgEdit будет вычислять первые множества для всех нетерминалов, но только некоторые последующие наборы, основанные на возможных возможных столкновениях. Тем не менее, это было бесценно для борьбы с грамматикой. Благодаря! – Zxaos