LL(1) грамматики - Форум администраторов игровых серверов
Форум администраторов игровых серверов StormWall - Защита от DDos атак
Регистрация Мнения Справка Пользователи Календарь Все разделы прочитаны
Вернуться   Форум администраторов игровых серверов > Полезное / Common > Программирование / Programming

Программирование / Programming
Ищете помощи в написании программы, есть сложность в выполнении задания (в институте и т.д.), пожалуйста, спросите у нас в данном форуме и мы обязательно вам поможем.

Ответ
Опции темы
Непрочитано 12.11.2012, 23:42   #1

Автор темы (Топик Стартер) LL(1) грамматики

Возникла необходимость сделать лексический и синтаксический анализатор "простого" класса. Изучив возможные варианты построения, более простыми и надежными(по сравнению с LR) показались LL(1) грамматики. Сказано - сделано, сходу было построено выделение лексем(flex), разобран заголовок класса, дело дошло до тела, и столкнулся с неприятностью. Для того, чтобы обработать объявления переменных, и вовремя перейти к обработке следующей секции - нужно предугадать, когда будет объявлена последняя переменная. Каким образом можно это сделать?
Code:
Свернуть ↑Развернуть ↓


Входные данные:
Свернуть ↑Развернуть ↓
Camelion вне форума Отправить сообщение для Camelion с помощью ICQ Ответить с цитированием
Непрочитано 13.11.2012, 06:51   #2
Аватар для Zubastic
ZG troll squad

По умолчанию Re: LL(1) грамматики

Может я неправильно понял, но при объявлении используются ключевые слова для типа данных? Может искать в строке название и есть оно не найдено то закрывать объявляющую секцию?
Zubastic вне форума Ответить с цитированием
Непрочитано 13.11.2012, 07:46   #3

Автор темы (Топик Стартер) Re: LL(1) грамматики

Цитата:
Сообщение от Zubastic Посмотреть сообщение
Может я неправильно понял, но при объявлении используются ключевые слова для типа данных? Может искать в строке название и есть оно не найдено то закрывать объявляющую секцию?
В таком случае это будет неверно для переменных, объявленных внутри функций, (будет искаться следующая секция, что ошибочно, так как уже идет обработка этой секции)
Camelion вне форума Отправить сообщение для Camelion с помощью ICQ Ответить с цитированием
Непрочитано 13.11.2012, 08:30   #4
Пользователь

По умолчанию Re: LL(1) грамматики

может что-то такое

если на входе терминал(int,float, имя_класса и тд) -> делаем цикл (больше,маленькие буквы, цифры) пока не знак "=" -> цикл по цифрам до ";" -> проверяем, есть ли еще терминалы -> начали новый анализ -> иначе нету переменных.

зы. "Для того, чтобы КС-грамматика была LL(1)-грамматикой, необходимо, чтобы множества выбора для правил с одинаковыми левыми частями не пересекались, т.е. не имели общих терминальных символов." - будешь ли делать такую проверку?)
учусь вне форума Ответить с цитированием
Сказали спасибо:
Непрочитано 13.11.2012, 08:54   #5

Автор темы (Топик Стартер) Re: LL(1) грамматики

Цитата:
Сообщение от учусь Посмотреть сообщение
может что-то такое

если на входе терминал(int,float, имя_класса и тд) -> делаем цикл (больше,маленькие буквы, цифры) пока не знак "=" -> цикл по цифрам до ";" -> проверяем, есть ли еще терминалы -> начали новый анализ -> иначе нету переменных.

зы. "Для того, чтобы КС-грамматика была LL(1)-грамматикой, необходимо, чтобы множества выбора для правил с одинаковыми левыми частями не пересекались, т.е. не имели общих терминальных символов." - будешь ли делать такую проверку?)

То есть после каждого ';' в секции parameters проверять следующий терминал (float, int)/handlers/end_of_class, и в зависимости от этого терминала переходить к дальнейшему разбору?
Camelion вне форума Отправить сообщение для Camelion с помощью ICQ Ответить с цитированием
Непрочитано 13.11.2012, 12:32   #6
Аватар для Array
Супергерой

По умолчанию Re: LL(1) грамматики

Нашёл кусок грамматики про объявление переменных:

Код HTML:
<def>			->	int var <def_end>
<def_end>		->	; | , var <def_end> | <init> ;
<init>			->	= <com_expr> ;
<com_expr>		->	<expr> <oper> <com_expr> | ;
<oper>			->	) | + | - | / | * | < | > | <= | >= | == | != | && | ||
<expr>			->	var | const | ( <expr>
Вот так транслятор выглядел

Давай таблицу разбора делай и вперёд.
Array вне форума Ответить с цитированием
Сказали спасибо:
Непрочитано 13.11.2012, 17:08   #7
Пользователь

По умолчанию Re: LL(1) грамматики

мне тоже кажется, что лучше сначала на бумажке написать полную грамматику. потом применить алгоритмы(устранение недостижимых, рекурсивных и тд) и получить LL(1), а то бесконечные циклы вылезут. но это мое мнение.

нашел самописные реализации алгоритмов:
учусь вне форума Ответить с цитированием
Сказали спасибо:
Непрочитано 13.11.2012, 18:32   #8

Автор темы (Топик Стартер) Re: LL(1) грамматики

Array, учусь, А может LALR(1) лучше подойдет для такого рода разбора?

Добавлено через 3 часа 53 минуты
Всем спасибо, особоенно Array и учусь. Успешно построил грамматику с использованием LALR(1).

Последний раз редактировалось Camelion; 13.11.2012 в 22:25. Причина: Добавлено сообщение
Camelion вне форума Отправить сообщение для Camelion с помощью ICQ Ответить с цитированием
Непрочитано 15.01.2013, 13:42   #9
Аватар для Yorie

По умолчанию Re: LL(1) грамматики

Думаю, что Вашу проблему можно было бы решить LL(1)-парсером с использованием Look Ahead алгоритма. Собственно, yylex поддерживает такую возможность.
Вообще, восходящие алгоритмы для парсеров более приоритетны, т.к. класс разбираемых грамматик нисходящих алгоритмов является подклассом для множества разбираемых грамматик восходящих алгоритмов.
__________________
// aka Deft
Yorie вне форума Ответить с цитированием
Сказали спасибо:
Непрочитано 15.01.2013, 13:52   #10
Аватар для Ashe
Олдфаг

По умолчанию Re: LL(1) грамматики

Цитата:
Сообщение от Yorie Посмотреть сообщение
Думаю, что Вашу проблему можно было бы решить LL(1)-парсером с использованием Look Ahead алгоритма.
Цитата:
Сообщение от Camelion Посмотреть сообщение
Всем спасибо, особоенно Array и учусь. Успешно построил грамматику с использованием LALR(1).
Собственно так и было сделано.

P.S. Некропост наказывается по закону.
__________________
Fortuna - non penis, in manus non recipe.
Ashe вне форума Ответить с цитированием
Сказали спасибо:
Ответ


Здесь присутствуют: 1 (пользователей: 0 , гостей: 1)
 
Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход


© 2007–2024 «Форум администраторов игровых серверов»
Защита сайта от DDoS атак — StormWall
Работает на Булке неизвестной версии с переводом от zCarot
Текущее время: 20:41. Часовой пояс GMT +3.

Вверх